Difficulty: Expert

Oh no, zombies are attacking your house!

Every second, a new zombie drops down on one of the 9 spots of your lawn, which is currently unoccupied. All zombies move towards your house on the left with constant speed, and each of them needs exactly 1 second to traverse a spot of the lawn. Once a zombie steps out of the lawn, it enters your house and waits there for the others (thus each zombie travels total distance between 1 and 9 spots).

Show that after some time, the total distance traversed by any 1000 consecutive zombies will be within the range of just 50 spots.

Remark: Assume your house can accommodate an unlimited amount of zombies.

Since the number of zombies on the lawn never decreases, it must stabilize at some point. Therefore after some time T, there will be exactly K zombies on the lawn at all times, 1 ≤ K ≤ 9.

Consider any 1000 consecutive zombies appearing past time T and take a picture of the lawn at the moment each of them gets dropped on it – this makes a total of 1000 pictures. Since on every picture, there are exactly K zombies, we see exactly 1000K zombies on these pictures.

Now notice that almost all of the selected 1000 zombies appear on as many pictures as lawn spots they traverse. The zombies for which this is not true are just the K zombies, which appear on the last picture. We easily see that they have traveled between 1 + 2 + … + K − 1 and (10 − K) + (11 − K) + … + 8 spots more than the number of pictures they appear on.

Similarly, on the 1000 pictures we have taken, there are K−1 additional zombies, which appear multiple times (you can see all of them on the first picture). The total number of times they show up is again between 1 + 2 + … + K − 1 and (10 − K) + (11 − K) + … + 8.

Therefore we conclude that the total distance the selected 1000 zombies travel is equal to 1000K ± {[(10 − K) + (11 − K) + … + 8] − [1 + 2 + … + K − 1]} = 1000K ± (9 − K)(K − 1).Since (9 − K)(K − 1) is a number between 0 and 16, this solves the problem.

Six pawns are placed in the middle squares of the main diagonal of a chess board – b7, c6, d5, e4, f3, g2. You are allowed to take any pawn on the chessboard and replace it with two pawns – one on the square above it and one on the square on its right, in case there are empty squares there. If after several moves there are no more pawns on the main diagonal, show that all the squares above it except for h8 are covered by pawns.

Assign the following weights on the squares of the chessboard:

• 1 on the main diagonal a8 – h1
• 1/2 on the diagonal b8 – h2
• 1/4 on the diagonal c8 – h3
• 1/8 on the diagonal d8 – h4
• 1/16 on the diagonal e8 – h5
• 1/32 on the diagonal f8 – h6
• 1/64 on the diagonal g8 – h7

Every time you make the splitting move, the total sum of the numbers of the squares covered by pawns remains a constant. At the beginning that sum is 6. Since 7/2 + 6/4 + 5/8 + 4/16+ 3/32 + 2/64 = 6, all 27 squares above the main diagonal, except the top-right corner (on which you can not place a pawn in any way), must be covered by pawns at the end.