> DFCq`FbjbjqPqP.*::36666"""">$%nooo%%%%%%%$F&h(z5%oM"ooo5%66J%ssso@6"%so%ssV#@Xr$b}N"3$%`%0%?$x()36()$()$Xoosooooo5%5%i
ooo%ooooD""666666Discrete Math problems
Problem 21, page 311
How many strings of three decimal digits?
do not contain the same digit three times?
begin with an odd digit?
have exactly three digits that are 9s?
solution
a) The total number of strings of three decimal digits is 103. Of them, 10 contain the same digit three times they are 000, 111, 222, ..., 999. Hence, the answer is 103 10 = 990.
b) There are 5 odd digits among 10 possible digits. So, half of all strings begin with an odd digit: 103 / 2 = 500.
c) The answer is 1, the only such string is 999.
Problem 31, page 311
How many one-to-one functions are there from a set with five elements to sets with the following number of elements?
4
5
6
7
solution
a) None at all. One-to-one function is possible only if the number of elements are the same in each set.
b) 5! = 120, the number of permutations of 5 elements.
c) None at all.
d) None at all.
Problem 2, page 319
Show that if there are 30 students in a class, then at least two have last names that begin with the same letter.
solution
Because there are only 26 different letters!
Problem 21, page 325
How many permutations of the letters ABCDEFG contain
the string BCD?
the string CFGA?
the strings BA and GF?
the strings ABC and DE?
the strings ABC and CDE?
the strings CBA and BED?
solution
a) Consider a set of strings M = {A, E, F, G, BCD}. Note that the set of permutations of letters ABCDEFG which contain the string BCD is equivalent to the set of permutations of the elements of M. Since M contains 5 elements, the answer is 5! = 120.
b) Consider a set M = {B, D, E, CFGA}. As above, the set of permutations of letters ABCDEFG which contain the string CFGA is equivalent to the set of permutations of the elements of M. The answer is 4! = 24.
c) Here take M = {C, D, E, BA, GF}. The reasoning is same as above. M contains 5 elements, and the answer is 5! = 120.
d) Take M = {ABC, DE, F, G}. With the same reasoning, the answer is 4! = 24.
e) The strings ABC and CDE may be both present in the permutation only if it contains the whole ABCDE string (the letter C may appear only once!). Take M = {ABCDE, F, G}. By the same old reasoning, the answer is 3! = 6.
f) No such permutation possible! B may appear only once. The answer is 0.
Problem 39, page 343
How many ways are there to travel in xyz space from the origin (0,0,0) to the point (4,3,5) by taking steps on unit in the positive x direction, one unit in the positive y direction, or one unit in the positive z direction? (Moving in the negative x, y, or z direction is prohibited, so that no backtracking is allowed).
solution
notation remark: C(n,k) is a number of simple combinations of k elements from n,
C(n,k) = n! / ( k!(n-k)! )
We have to make 4 steps in x direction, 3 steps in y direction and 5 steps in z direction, a total of 12 steps. There are C(12,4) ways to choose which steps will be in x direction. Once they are chosen, there are C(8,3) ways to choose which of the other steps will be in y direction. The 5 left steps are automatically assigned to z direction. So, the answer is C(12,4) * C(8,3) = 27,720.
Problem 9, page 456
How many students are enrolled in a course either in calculus, discrete mathematics, data structures, or programming languages at a school if there are 507, 292, 312, and 344 students in these courses, respectively; 14 in both calculus and data structures; 213 in both calculus and programming languages; 211 in both discrete mathematics and data structures; 43 in both discrete mathematics and programming languages; and no student may take calculus and discrete mathematics, or data structures and programming languages concurrently?
solutions
notations: C the set of students enrolled in calculus, D in discrete maths, S in data structures, P in programming. M = C+D+S+P is the universal set.
CD = C(D is set intersection
C+D = C(D is set union
C S is a set difference
#C is the number of elements in C
We have:
#C = 507, #D = 292, #S = 312, #P = 344;
#CS = 14, #CP = 213, #DS = 211, #DP = 43, #CD = 0, #SP = 0.
We have to find #M = #(C+D+S+P).
Heres the Vienn diagram for this problem:
SHAPE \* MERGEFORMAT
#(S C D) = #S - #CS - #DS = 312 14 211 = 87
#(P C D) = #P - #CP - #DP = 344 213 43 = 88
#M = #(C+D+S+P) = #C + #D + #(S C D) + #(P C D) = 507 + 292 + 87 + 88 = 974
So, the answer is 974.
C
S
D
P
S C - D
P C - D
CS
DS
CP
DP
- u v (
)
>
-.CDY~
%
&
W
b
m
r
8Rn h,wB] huR] hL] hy5]h`)5\h hy5H*hy5h`)6]h`)hSh`)5CJaJL-W (
)
>
.eu
&Fgdy5
&FE
CDY
Z%&/ gdy5
&F%/ 89<mN)*+./9Defpqz{!"9:;<=>qrjhjU"jh UmHnHsHtHujh Uhh jhh jhh`Kshh h%Qh,wBh`)6]h`)@ !5MNX*Dfgp !>rgd`Ks'(2367:;>?BCDEFhRh`Ksh`Ksh`KshjCJaJhjhjhjCJaJ()3478;<?@CDEFgd`Ks,1h/ =!"#$%Dd D
3@@"?B@B1KG=K9CJ_HaJmH sH tH >@>03>;>2>: 1$@&5\D@D03>;>2>: 2$@&56\]BABA=>2=>9 H@8DB 0170F0\i\1KG=0O B01;8F0 :V44
la.k.
5B A?8A:0 "&*.2F "&*.25 F*-W()>.eu
CDYZ%
&
/
!5MNX*Dfgp !>r()3478;<?@CG0000 0 0 000000000) 0) 0) 0) 0)0)0)0)0)0)0)0)00000000D 0D 0D 0D 0D 0D 0D00I0I0I0I0I0I0I0I0I0I0I0I0I0I0I0I0I0I0I0I0I0I0I000000000000000I00I00I0 0I0X0I0
0I0hͮ0I0
0I00I00I0XF
FE!9<F_8@(
%
# s"*?`
c$X99? %\2
3q}"`E4\2
3q}"`g9\2
3q}"`EF\2
3q}"`J;h
3"`TG
h
3"`p a
h
3"`
h
3"`eV
h
3"`W
h
3"`8
h
3"`
h
3"`
w
h
3 "`s)
h
3
"`w
B
S ?:F!tB
E
GWYRX
GJ37st&
.
/
7
prNWXartG3333333333333333333333333333333-)>DYR~
')2468:<>@BGG7oK70wHd?Xw^`6o()^`.pLp^p`L.@@^@`.^`.L^`L.^`.^`.PLP^P`L.^`o()^`.pLp^p`L.@@^@`.^`.L^`L.^`.^`.PLP^P`L.^`o()^`.pLp^p`L.@@^@`.^`.L^`L.^`.^`.PLP^P`L.?70w7oKܻ ܻ 7 R%Q,wB:EPK`KsL`)jy5uRS@thhFP@UnknownGz Times New Roman5Symbol3&z Arial"qhgF!24d
2QHX?y52Discrete Math problemsAngela LyallAndreyOh+'0 $
DP
\hpxDiscrete Math problemsAngela LyallNormal.dotAndrey3Microsoft Office Word@@I@&M՜.+,0hp|
Discrete Math problems
!"#$%&'()*+,-./012456789:<=>?@ABERoot Entry FRNGData
1Table@)WordDocument.*SummaryInformation(3DocumentSummaryInformation8;CompObjq
F Microsoft Office Word
MSWordDocWord.Document.89q