Reference no: EM131084644

Putnam TNG - Chequer & Chess Boards

1: For each positive integer n, let S_n denote the total number of squares in an n×n square grid. Thus, S₁ = 1 and S₂ = 5, because a 2 × 2 square grid has four 1 × 1 squares and one 2 × 2 square. Find a recurrence relation for S_n and use it to calculate the total number of squares on a chessboard (i.e. determine S₈).

2: An n × n chequerboard has 2n chequers on it. Show for some k > 1, there exists a sequence of chequers a₁, a₂, · · · a_2k such that a₁ and a₂ are in the same row, a₂ and a₃ are in the same column, · · · a_2k-1 and a_2k are in the same row and a_2k and a₁ 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, . . . , n² in the squares of an n × n grid so that the k-th row, from left to right, is

(k - 1)ⁿ + 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?