Consider a $ n \times n$ checkerboard with $ n > 1, n \in \mathbb{N}.$ How many possibilities are there to put $ 2n - 2$ identical pebbles on the checkerboard (each on a different field/place) such that no two pebbles are on the same checkerboard diagonal. Two pebbles are on the same checkerboard diagonal if the connection segment of the midpoints of the respective fields are parallel to one of the diagonals of the $ n \times n$ square.
Problem
Source: MEMO 2008, Single, Problem 2
Tags: analytic geometry, combinatorics unsolved, combinatorics
JBrere
13.09.2008 15:56
Place the $ n$ X $ n$ checkerboard on the coordinate plane such that the bottom left corner is on $ (1,1)$ bottom right is on $ (n,1)$ and the top corners are on $ (n,1)$ and $ (n,n)$ Consider the following $ 2n-2$ diagonals: $ (1,1) (2,2) ... (n,n)$ $ (2,1) (1,2)$ $ (3,1) (2,2) (1,3)$ ... $ (n-1,1) (n-2,2) ... (3, n-1) (2,n)$ $ (n,1) (n-1,2) ... (2, n-1) (1,n)$ $ (n,2) (n-1,3) ... (3, n-1) (2,n)$ ... $ (n, n-2) (n-1,n-1) (n-2,n)$ $ (n,n-1) (n-1,n)$ These $ 2n-2$ diagonals span the entire board, so each diagonal must contain exactly one pebble. But, there can be no pebble on an overlapping square. In the $ (1,1) (2,2) ... (n,n)$ diagonal, there are two places where the pebble can go. In the $ (2,1) (1,2)$ diagonal, there are two places where the pebble can go, and the placement of this pebble uniquely determines the placement of the pebble in the $ (n,n-1) (n-1,n)$ diagonal. In the $ (3,1) (2,2) (1,3)$ diagonal there are two possible placement, since the $ (2,2)$ square is on the same diagonal as the $ (1,1)$ square which already contains a pebble. Each placement uniquely determines the placement of the pebble in the $ (n, n-2) (n-1,n-1) (n-2,n)$ diagonal. Clearly we can repeat this process for all $ n$ diagonals containing squares in the bottom row, and the placement of pebbles in the other $ (n-2)$ diagonals will be uniquely determined. So the number of ways to place the pebbles is $ 2^n$.
HansV
26.12.2021 11:14
2^(n+1) if n odd.