This page is maintained by Amit Chakrabarti.
[4] After computing the values of f(n) for n = 1, 2, 3, 4 and 5 one can easily guess that f(n) = f(n-1) + f(n-2) for all n >= 3. This fact can also be proved as follows (though you didn't need to prove it for the homework): Consider a tiling of a 2-by-n board (with n >= 3) placed such that the longer pair of parallel sides are horizontal. The top-left corner square can be covered in exactly two ways leading to two disjoint classes of tilings.
In Class A this square is covered by a horizontal domino. The bottom-left corner square must then be covered by a horizontal domino as well, leaving us a 2-by-(n-2) board to tile. This we can do in f(n-2) ways.
In Class B this square is covered by a vertical domino and this leaves us a 2-by-(n-1) board to tile. This can be done in f(n-1) ways.
Thus f(n) = f(n-1) + f(n-2). Using this relation repeatedly we easily get f(12) = 233.
[7] Very few people scored a perfect 10 on this problem; there are four separate things to be proved here and most people either didn't prove or overlooked at least one.
The final answer is as follows: The n-by-n-by-n cube can be tiled as required iff n is even. The n-by-n-by-n "hollowed out" cube can be tiled as required iff n is 1 mod 4. There are two iffs here and so you have to prove four things:
Proof of 1: Trivial, just arrange n identical planes; in each plane arrange n identical rows of n/2 dominoes each.
Proof of 2: For odd n, the n-by-n-by-n cube has odd volume. The dominoes have volume 2 each and so anything that can be tiled by them must have even volume.
Proof of 3: There are several ways to prove this. Here is one: an n-by-n chessboard with the center square missing can be tiled using flat dominoes, for all odd n (first tile a one-unit thick square ring along the edges of the chessboard, then repeat...). Stacking n such "chessboards" on top of one another we get a n-by-n-by-n cube with a hole drilled through the center from top to bottom. If n is 1 mod 4, (n-1)/2 is even and we can fill this through hole from either end leaving exactly a unit hole in the center.
Proof of 4: Suppose the unit cubes of an n-by-n-by-n cube are alternately coloured black and white; each domino must cover one white and one black unit cube, so in any shape that can be tiled by dominoes there must be an equal number of black and white unit cubes. However, when n is 3 mod 4, the hollowed out n-by-n-by-n cube has two more black squares than white, assuming the corners are black. The deleted center unit cube is white and the entire (non-hollowed-out) cube has one black unit cube in excess. And now the proof is complete.
[12] You just follow the steps of the magic square construction algorithm and that gives you the following magic square:
30 39 48 1 10 19 28 38 47 7 9 18 27 29 46 6 8 17 26 35 37 5 14 16 25 34 36 45 13 15 24 33 42 44 4 21 23 32 41 43 3 12 22 31 40 49 2 11 20Simple!
[22] No, the desired "magic" hexagon does not exist. The simplest way to see this is that considering any two adjacent sides of the hexagon gives us an equality between two sums, each having two summands and with exactly one summand in common to the two sums. In other words, we have an equality like a+b = b+c. This implies that some two cells have the same number in them, a contradiction.
[28] There are five shortest paths of length five each. There's nothing at all to this problem except for being careful and ensuring that you notice all the five paths. Yet, a considerable number people have managed to lose points on this problem as well!
Take A = {(x,y): x = door hiding holidays, y = door chosen by contestant}. x and y can be integers from the set {1,2,3}; each door being given a distinct number. Now, if our strategy is "don't-switch", then we win exactly when x = y; i.e. the winning event in this case is the set T1 = {(x,y) in A: x = y} = {(1,1), (2,2), (3,3)}. If our strategy is "switch", the winning event is the set T2 = {(x,y) in A: x != y}.
Clearly |A| = 9, |T1| = 3 and |T2| = 6. This gives us the probability of winning in the non-switch and switch cases as 1/3 and 2/3 respectively.
[2] For this problem all you needed to do was write a program to find the k for which the success probability of the k-strategy is highest, and the corresponding value of that probability. Most people have got this problem right. Many have given an argument which shows that the best k to use is approximately n/e, using the fact that 1 + 1/2 + 1/3 + ... + 1/m approximately equals ln(m).