Practice Quiz 1 Solutions: The quiz will be open book (any book) and open notes (any notes or written material).

[1] Use Euclid's algorithm to write the greatest common divisor of 13 and 47 as an integer linear combination of 13 and 47.

47 = 3*13 + 8	8 = 47-3*13
13 = 8 + 5	5 = 13 - 8 = 4*13 - 1*47
8 = 5 + 3	3 = 8 - 5 = (47-3*13) - (4*13 - 1*47) = 2*47-7*13
5 = 3 + 2	2 = 5 - 3 = (4*13 - 1*47) - (2*47-7*13) = 11*13 - 3*47
3 = 2 + 1	1 = 3 - 2 = (2*47-7*13) - (11*13 - 3*47) = 5*47 - 18*13

[2] Suppose a developer builds houses painted in one of 7 colors, uses any of 5 floor plans, with either electric or gas heat. 

(a) How many different houses does the developer build? Explain your answer. 

7*5*2 = 70. You multiply since you must make 3 consecutive choices.
For each of 7 house colors, there are 5 floor plans (this gives
35 possibilities), and for each of those there are two types of heating
(for a total of 70 possibilities).

(b) In a subdevelopment of 50 houses, must there be at least two identical houses? Explain why or why not.

No, since there are more kinds of houses than houses, each house can be different.

(c) Suppose the development has 200 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 only 200 houses? Explain your answer.

The average number of houses per type is 200/70 = 2.86. Since the number of houses can't be less than average for al of the types of houses, some type has to have at least 2.86 (and hence at least 3) houses. Thus there must be at least 3 identical houses. There need not be 4, since there could be 3 identical houses for each of 66 types, and the last two houses could also be the same but of a 67th type.

[3] Write 38 as a sum of Fibonacci numbers, no two of which are consecutive Fibonacci numbers.

38 = 34 + 3 + 1.

[4] John and Jane play a game of Fibonacci nim, starting with a total of 26. John goes first.
(a) How many should John take away in order to be sure to win? Explain your answer.

Since 26 = 21 + 5, John should take 5.

(b) If John takes away only 2, can Jane win? Explain.

Yes, since 26 - 2 = 24 = 21 + 3. If Jane takes 3 then she used the winning strategy and can win if she doesn't make a mistake.

[5] 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) Use Gauss' trick to add up the whole numbers from 1 to 50.

1  + ... + 50 +
50 + ... + 1 = 50*51 = 2550 so 1  + ... + 50 = 2550/2 = 1275.

(b) Use Gauss's trick to add up the whole numbers from 100 to 200.

100 + ... + 200 +
200 + ... + 100 = 101*300 = 30300 so 100 + ... + 200 = 30300/2 = 15150.

(c) Use Gauss's trick to add up the whole numbers from 4 to 73, counting by 3's; i.e., add up 4 + 7 + 10 + ... + 73.

 4 +  7 + ... + 73
73 + 70 + ... +  4 = 24*77 = 1848 so 4 +  7 + ... + 73 = 1848/2 = 924.