In this recitation, I did a live demo of the Euclidean algorithm. We not only figured out the greatest common divisor, but also express the greatest common divisor as an integer combination of the two integers. The significance of finding the integer combination appears in solving Diophantine equations.
I also reviewed some of the combinatorics problems in homework 8. Here are some comments on them.
- Counting the same set twice is really like telling two versions of one story. And most of the time, one of the versions can be easily seen from the problem.
- In general, the number of naturals (including 0) of n digits with m different digits is $${n\choose m}\sum_{k=0}^{k}{m \choose k}(m-k)^n.$$ To prove this, one need to use the inclusion–exclusion principle.
After section C, Vivek challenged me with the following riddle.
Logicians A, B and C each wear a hat with a positive integer on it such that the number on one hat is the sum of the numbers on the other two. They can see the numbers on the other two hats but not their own. They are given this information and asked in turn if they can identify their number. In the first round A, B and C each in turn say they don’t know. In the second round A is first to go and states his number is 50. What numbers are on B and C?
Here is my answer. Let a,b and c be the numbers on A, B and C’s hats. As A didn’t figure out his number right away, a:b:c is not 2:1:1. As B didn’t figure out his number after A said so, a:b:c is not 1:2:1 or 2:3:1. As C didn’t figure out his number after B said so, a:b:c is not 1:1:2, 2:1:3, 1:2:3 or 2:3:5. Since A could figure out after the first round, a:b:c must be 3:2:1, 4:3:1, 3:1:2, 4:1:3, 5:2:3 or 8:3:5. Since a=50, a:b:c must be 5:2:3. Thus b=20, c=30.