Discrete Mathematics

Discrete Mathematics with Ducks Solutions Manual sarah-marie belcastro 1 / 4

Chapter 1 Counting and Proofs 1.2 Try This! Let’s Count

1. 2+6+1+1=10.

2. 3·5=15.

• Six as there are five different ice-cream containers.
• 5·5·5=125 orders because one might want all flavors the same.
• This one is a pain, intentionally. First,

− 5 1 · +2 − 5 2 · + − 5 3 · =5+20+10=35 (the 2 − 5 2 · is because it matters which flavor is ordered with 1 quart and which is ordered with 2 quarts), then just − 5 3 · =10, then − 4 1 · + − 4 2 · + − 4 3 · =4+6+4=14 and − 4 3 · =4. Of course, students do not yet know this notation, so they will likely write out solutions exhaustively and at length.

6. 3+2+1=6.

• Three, as there are only two colors. To assure 7 monochromatic armbands, 13 armbands must

be drawn (worst case: b-g-b-g-b-g-b-g-b-g-b-g-b/g).

8. 5·3·6=90.

• (a)n−1.

(b)n−1, thenn−2.(c)n−i.(d)(n−1) + (n−2) +...1=n(n−1)/2.

• (a) 3·k.

(b)k+1 as there arekcontainers.

• (a) The sum of their sizes.

(b) The sum of their sizes!(c) Yes, the WEBS problem and the Frisbee tournament problems.(d)m+m+···+m=n·m.

12.m·k; yes, related to the ice-cream and snack-box problems.

2 2 / 4

1.9. Problems That Use Counting or Proofs3

1.9 Problems That Use Counting or Proofs

1. 4·7=28.

2. 28·3·2=168.

• An even numberncan be written as 2kfor some integerk. So, the sum of two even numbers

isn1+n2=2k1+2k2=2(k1+k2) =2k3, which is even.

• An odd numberncan be written as 2k+1 for some integerk. So, the sum of two odd numbers

isn1+n2=2k1+1+2k2+1=2k1+2k2+2=2(k1+k2+1) =2k3, which is even.

• 2

8 by the product principle using slots.

6. 5·4+3·3=29.

• A binary numbernthat ends in 0 is the sum of some powers of 2, e.g.,n=2

a +2 b

+···+2

c where the lowest possible power of 2 is 2 1 =2. Then we may writen=2(2 a−1 +2 b−1

+···+

2 c−1 )and sonis even.

• An odd numberncan be written as 2k+1 for some integerk. To writenas a binary number,

we must write it as a sum of powers of 2. This sum must have lowest power 0 (as in 2

• or

else every term of the sum will be divisible by 2. That means that the binary representation will end in a 1=2

.

• There are 11·3·5·k=165kchoices and 1,095 days, sok≥6.63. But, of course,kmust be

an integer . . . so there are at least seven possible drinks.

• Two consecutive perfect squares aren

2 and(n+1) 2 .n 2 −(n+1) 2 =n 2 −n 2 −2n−1= −2n−1=−2n+1−2=2(−n−1) +1, which is odd.

• 11=10+1; and, 3 because there are only two different first digits(1,2).

12. Counterexample: 3

2 +4 2 =25 is odd.

13. 15·8=120.

14. 15·6=90.

15. 5+6+3+4=18.

• Nope. 2+3=5 is odd. (However, if we exclude 2, then the remaining primesare odd and so

the sum of any two of them will be even.)

• There are 1,440 minutes per day and so(1,440)·

2 3 =960 90-second intervals. 1,042>960 so two flights must take off within the same interval.

• Writen=2kfor some integerk. Then(−1)

n

= (−1)

2k

= ((−1)

2 ) k =1 k =1.

19. 10

7

. 3 / 4

• Counting and Proofs
• 9

4

=6561.

• An odd number 2k+1 times an odd number 2r+1 is(2r+1)(2k+1) =4kr+2k+2r+1=

2(2kr+k+r) +1 and thus is odd.

• (a) Check 2,000,000 versus 2

20

=1,048,576: not enough subsets.

(b) By trial and error, see that 2,100,000>2 21 =2,097,152 but 2,200,000<2 22

=4,194,304.

• For evenn=2k, 3(2k)

3 +(2k)+5=2(3·4k 3 )+2k+2·2+1=2(3·4k 3 +k+2)+1, which is odd.For oddn=2k+1, 3(2k+1) 3

• (2k+1) +5=odd+odd+odd=odd.
• 99·2+1=199; 99·3+1=298; 99·k+1.
• Green and brown socks: three for the first pair, then another two for the next pair, and so forth

and so on, so 50·2+1=101.Three colors of socks: four for the first pair, then another two for the second pair (using the

leftover two socks), and so forth and so on: 50·2+2=102.

kcolors of socks:k+1 for the first pair, then another two for the second pair (using the

leftoverk−1 socks), and so forth and so on: 50·2+k−1=99+k.

• All the usual primes are still prime, and 1 is also prime.

If 1 were prime, we would no longer have unique factorizationof natural numbers—for ex- ample, 6=2·3=2·1·1·1·3=1·2·3....

• There are no prime numbers with this definition, because 1is a positive divisor of every

integer, and 1 is not included in this definition!It would be silly to have a class of numbers with no members.

• There are 3·2=6 regular options plus 2·1 Fancy Tips, so 6+2=8.
• By the pigeonhole principle, if each bin had only 13 skeins then you’d only have 104 mini-

skeins.

• (a) Note that the numbers 1–6, paired with the numbers 12–7, form six sums of 13. If no

pair of the 7 numbers sums to 13, then all the numbers must be inone of these two subsets—but that’s only 6 numbers, so the seventh number must come from the other set and pair to make a sum of 13.(b) Similarly, the numbers 12–7, paired with the numbers 6–1, form differences of 6. The same argument applies.(c) Now we look at the numbers 1–3 with 4–6, and 7–9 with 10–12 to get six pairs with differences of 3. The same argument as above applies.

• We have 7 numbers in the range 1–20. There are 2

7 =128 possible subsets, and the highest possible sum is 14+15+16+17+18+19+20=119. So there are at most 119 different subset sums, and more subsets than that—thus, by the pigeonhole principle, there are two subsets that have the same sum.

• / 4