Putnam TNG - Chequer & Chess Boards
1: For each positive integer n, let Sn denote the total number of squares in an n×n square grid. Thus, S1 = 1 and S2 = 5, because a 2 × 2 square grid has four 1 × 1 squares and one 2 × 2 square. Find a recurrence relation for Sn and use it to calculate the total number of squares on a chessboard (i.e. determine S8).
2: An n × n chequerboard has 2n chequers on it. Show for some k > 1, there exists a sequence of chequers a1, a2, · · · a2k such that a1 and a2 are in the same row, a2 and a3 are in the same column, · · · a2k-1 and a2k are in the same row and a2k and a1 are in the same column.
3: Find the smallest positive integer n such that if n squares of a 1000 × 1000 chessboard are colored, then there will exist three colored squares whoses centers form a right triangle with sides parallel to the edges of the board.
4: Let n be an even positive integer. Write the numbers 1, 2, . . . , n2 in the squares of an n × n grid so that the k-th row, from left to right, is
(k - 1)n + 1,(k - 1)n + 2, . . . ,(k - 1)n + n.
Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkerboard coloring is one possibility). Prove that for each coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.
5: Does there exist a real number L such that, if m and n are integers greater than L, then an m × n rectangle may be expressed as a union of 4 × 6 and 5 × 7 rectangles, any two of which intersect at most along their boundaries?
6: Two distinct squares of the 8×8 chessboard are said to be adjacent if they have a vertex or side in common. Determine the largest number N such that for every arrangement of the numbers 1, 2, . . . , 64 on the chessboard there exist two adjacent squares whose numbers differ by at least N.
7: (a) Forty-one rooks are placed on a 10×10 chessboard. Prove there must exist five rooks that do not attack each other.
(b) Can forty-one be replaced with forty?