Maths Olympiad Prep

Library / /88 of 397

Combinatorics Difficulty 5.2 AIME, harder Prove it Taiwan

Find all positive integers nn such that we can place one of the four arrows ,,,\uparrow, \downarrow, \leftarrow, \rightarrow into each of the n2n^2 cells of an n×nn \times n chessboard, so that all three of the following conditions are satisfied:
(1) Starting from any cell and moving in the direction of the arrows, we will always return to the starting cell, and along the way we never leave the board.
(2) Except for the topmost and bottommost rows, in any row the number of \uparrow arrows equals the number of \downarrow arrows (but the numbers may differ between different rows).
(3) Except for the leftmost and rightmost columns, in any column the number of \leftarrow arrows equals the number of \rightarrow arrows (but the numbers may differ between different columns).

Solution

The only possibility is n=2n=2 (in which case the arrows form a clockwise or counterclockwise loop.)

Clearly the topmost row cannot contain \uparrow; suppose it has kk arrows \downarrow. By condition (1), this means the second row must have kk arrows \uparrow, but by condition (2) we also know the second row must have kk arrows \downarrow. By the same argument, we know that rows 3 through n1n-1 must each have kk arrows \uparrow and kk arrows \downarrow, while the bottommost row must have kk arrows \uparrow and 00 arrows \downarrow. In other words, over the whole board there are (n1)k(n-1)k arrows \uparrow and (n1)k(n-1)k arrows \downarrow.

By the same reasoning, if the leftmost column has \ell arrows \rightarrow, then by conditions (1) and (3), we know that over the whole board there are (n1)(n-1)\ell arrows \rightarrow and (n1)(n-1)\ell arrows \leftarrow, so the total number of arrows on the whole board is 2(n1)(k+)2(n-1)(k+\ell). But the total number of arrows must equal the number of cells, so we must have
2(n1)(k+)=n2. 2(n-1)(k+\ell) = n^2.
However, since gcd(n,n1)=1\gcd(n, n-1) = 1, this is impossible when n>2n > 2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.