Solutions to Homework Set 1

The solutions that follow are not the only possible ones. They are not necessarily the best possible either. If you find a mistake in any of these solutions or if you feel that any solution can be significantly improved, please feel free to send email to us(Xiaodong Wen and Xiaohu Qie ).

 


 
 

Problems from Section 1.8

[2]

Many people proved this problem by saying the number of whites and blacks are same. This is not sufficient. The following is one of the correct proof.

Without lossing generality, we can assume the cutted white square is located at position ( 1<=i<=m, 1<= j <= n, i and j should be both even or odd). Then we can divide the m-by-n chessboard into four parts(as shown in figure 1): part 1 is a i-by-(j-1) chessboard, part 2 is a (m-i)-by-j chessboard, part 3 is a (m-i+1)-by-(n-j) one, part 4 is a (i-1)-by-(n-j+1) one. It can be proved each part's either row number or column number is even. So each part can have a perfect cover. So the cutted m-by-n chessboard has a perfect cover.

[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:

     
  1. If n is even we can tile an n-by-n-by-n cube.
  2. If n is odd we cannot tile an n-by-n-by-n cube.
  3. If n is 1 mod 4 we can tile an n-by-n-by-n "hollowed out" cube.
  4. If n is 3 mod 4 we cannot tile an n-by-n-by-n "hollowed out" cube.
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  20

[23] The following is only one of the correct solutions. 

<1,1>   <2,2>   <3,3>   <4,4>
<4,2>   <3,1>   <2,4>   <1,3>
<2,3>   <1,4>   <4,1>   <3,2>
<3,4>   <4,3>   <1,2>   <2,1>

[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!


[33] For any heap which  has at least 2j and fewer than 2j+1 coins, let its base-2 representation be (bj bj-1 ..... b1 b0)2, where bj=1. Player I can balance the game by doing: for i=j,j-1,...,0, if column i is not balanced then let ci=1-bi else let ci=bi. If we replace the heap by a heap of (cj cj-1 ... c1 c0 )2 coins the game will be balance. The new number (cj cj-1 ... c1 c0 )2 is less than (bj bj-1 ... b1 b0)2 since jth column is unbalanced then we have cj=0. So Player I can remove (bj bj-1 ... b1 b0)2-(cj cj-1 ... c1 c0)2 coins from that heap to balance the game.


[35]  Player II can guarantee a win. For each round, if Player I add x coins, Player II just add 5-x coins. In this way, Player II can always make the total coins in the pile be a multiple of 5 after his turn.  So the 100th coin will be added by him.
 


Back to COS 341 front page | Handouts