Practice Quiz 2, M203E for Quiz 2 Wednesday Oct 19, 2011 Instructions: The quiz is open book (any books) and open notes (any notes or written material). [1] Suppose a man has glossy paint which comes in three colors, and flat paint which comes in two colors. (a) How many different ways are there for him to paint his house? Explain your answer. Solution: He has to make 1 choice from a range of 3 + 2, so there are 5 ways to paint his house. For example, if the glossy colors are red, white and blue, and the flat clors are green and yellow, the possibilities are that he paints his house glossy red, glossy white, glossy blue, flat grren or flat yellow. (b) How many different ways are there for him to paint his house and his daughter's house, if he wants glossy paint on his house and his daughter wants flat paint on her house? Explain your answer. Solution: He has to make 2 choices, and he has 3 ways for the first choice (of how to paint his own house) and 2 ways to for the second choice (of how to paint his daughter's house), so there are 3*2 = 6 different ways. For example, if the glossy colors are red, white and blue, and the flat clors are green and yellow, the possibilities are: RG, RY, WG, WY, BG, BY, where RG means he paints his house red and his daughter's house green, etc. [2] Suppose a developer builds houses painted in one of 6 colors, using any of 4 floor plans, with either electric, gas or geothermal heat. (a) How many different kinds of houses can the developer build? Explain your answer. Solution: There are 6*4*3 = 72, since for each house you must make 3 choices: a choice of color, a choice of floor plan, and a choice of heat. Since you are making a sequence of choices, you have to multiply the number of possibilities for each choice to get the number of kinds of houases altogether. (b) In a subdevelopment of 50 houses, must there be at least two identical houses? Explain why or why not. Solution: There are 72 kinds of houses, so in a development of 50 houses , the 50 houses could all be different. (c) Suppose the subdevelopment has 300 houses. What is the largest number of houses that you can be sure have to be identical knowing nothing more than your answer to (a) and that there are 300 houses altogether? Explain your answer. Solution: The number of houses, on average, of each kind is 300/72 = 4.166. Since the number of houses of each kind can't be less than average for each kind, there must be at least 4.166 houses for one of the kinds. B ut you can't have a fraction of a house, so there must be at least 5 houses for onw of the kinds. Thus there muust be at least 5 identical houses. [3] (a) Write 65 as a sum of Fibonacci numbers, no two of which are consecutive Fibonacci numbers. Solution: Subtract off the biggest Fibonacci number less than or equal to what you have left. The biggest Fibonacci less than or equal to 65 is 55. Now 65 - 55 = 10 and the biggest Fibonacci number less than or equal to 10 is 8. Next, 10 - 8 = 2, and the biggest Fibonacci number less than or equal to 2 is 2 and 2 - 2 = 0 so we're done. Thus our answer is 65 = 55 + 8 + 2. (b) John and Jane play a game of Fibonacci nim, starting with a total of 65. John goes first. (Recall the rules: each player can take away as much of what is left as that player wants with two exceptions: the first player has to leave something for the second player, and after that each player can take at most twice what the previous player took. Whichever player gets stuck with 0 is the loser.) (i) How many should John take away in order to be sure to win? Explain your answer. Solution: He should take the least term when we write the given number, 65, as a sum of non-consecutive Fibonacci numbers. Thus he should take 2. (ii) If John takes away only 1, can Jane win? Explain. Solution: Yes, Jane can win now, since 65 - 1 = 64, so Jane has been left with 64. If we write 64 as a sum of non-consecutive Fibonacci numbers we get 64 = 55 + 8 + 1, so now Jane can hijack the winning strategy by taking the least term in the sum, which is 1. [4] An arithmetic sequence of numbers is a sequence where the difference being consecutive numbers is always the same. For example, for 1, 2, 3, ..., 50, the difference is always 1 since each number is always 1 bigger than the previous number. For 4, 7, 10, ..., 70, 73, the difference is always 3, since each number is always 3 bigger than the previous number. Gauss's trick works to add up any arithmetic sequence of numbers. Recall how Gauss's trick works: write the sum and below it write it in reverse order. 1 + 2 + ... + 100 100 + 99 + ... + 1 Add up the numbers in columns (each column here gives 101), multiply by the number of columns (100*101=10100) and divide by 2, which gives in this case 5050. (a) Explain how to use Gauss' trick to add up the whole numbers from 1 to 75. Solution: 1 + 2 + ... + 75 75 + 74 + ... + 1 ___________________ 76 + 76 + ... + 76 = 75*76 so 1 + 2 + ... + 75 = 75*76/2 = 2850. (b) Explain how to use Gauss's trick to add up the whole numbers from 200 to 320. Solution: 200 + 201 + ... + 320 320 + 319 + ... + 200 ___________________ 520 + 520 + ... + 520 = 520*(320-200+1) = 520*121 so 200 + 201 + ... + 320 = 520*121/2 = 31460. (c) Explain how to use Gauss's trick to add up the whole numbers from 9 to 89, counting by 5's; i.e., add up 9 + 14 + 19 + ... + 89. Solution: 9 + 14 + 19 + ... + 89 89 + 84 + 79 + ... + 9 _______________________ 98 + 98 + 98 + ... + 98 = 98*((89-9)/5+1) = 98*17 so 9 + 14 + 19 + ... + 89 = 98*17/2. [5] (a) What is the remainder if you divide 32117 by 9? Show your work or explain how you get your answer. Solution: 3+2+1+1+7 = 14, 1+4 = 5 so the remainder is 5. (Adding up the digits only works for remainders when dividing by 9.) (b) What is the remainder if you divide 32117 by 10? Show your work or explain how you get your answer. Solution: Since 32117 = 32110 + 7 = 3211*10 + 7, we see that the number of times that 10 goes into 32117 is 3211 with a remainder of 7; so the remainder is 7. (The remainder when dividing by 10 is always the last digit.) [6] (a) Find the postnet check digit for the math department zip code: 68588 0130. Solution: The checkk digit is chosen to make the sum a multiple of 10. For 68588 0130 we have: 6+8+5+8+8+0+1+3+0 = 39 so the check digit is 1. (b) Given that the postnet check digit is 4, fill in the following zip code's missing digit: 12574 3_11. Solution: If we add up the digits of 12574 3_11 and add the check digit we are suppposed to get a multiple of 10. Using x for the unknown digit, what we actually get is: 1+2+5+7+4+3+x+1+1+4 = 28 + x so x = 2. [7] (a) Find the check digit (denoted here by x) for the following UPC code: 0 53000 15108 x. Solution: (0+3+0+1+1+8)*3 +5+0+0+5+0+x = 13*3+10+x = 49+x so x = 1 in order for the sum to be a multiple of 10. (b) Find the missing digit in the following UPC code: 0 15838 _0001 5. Solution: (0+5+3+x+0+1)*3 +1+8+8+0+0+5 = (9+x)*3+22 = 27+3x+22 = 49+3x so x = 7 in order for the sum to be a multiple of 10.