Find all positive integers $ n $ with the following property: It is possible to fill a $ n \times n $ chessboard with one of arrows $ \uparrow, \downarrow, \leftarrow, \rightarrow $ such that 1. Start from any grid, if we follows the arrows, then we will eventually go back to the start point. 2. For every row, except the first and the last, the number of $ \uparrow $ and the number of $ \downarrow $ are the same. 3. For every column, except the first and the last, the number of $ \leftarrow $ and the number of $ \rightarrow $ are the same.
Problem
Source: 2019 Taiwan TST Round 1
Tags: combinatorics
stroller
27.06.2020 02:04
Solved with Aryan-23 and naman12 We claim that the answer is $n = 2$ only. It is easy to see that $n = 2$ works. Now we show that this is the only possibility. Label the columns $1,2,...,n$ from left to right. Suppose such an assignment of arrows exist. Draw a directed edge from $u$ to $v$ if the arrow in square $u$ point from $u$ to $v$ for any two squares $u,v$ that share an edge. The directed edges form a union of disjoint cycles whence $2|n$. Now write $n =2m$. By considering cycles that enter/exit a column, we see that the number of rightwards-pointing arrows in column $c$ is equal to the number of leftwards-pointing arrows in column $c+1$. This combines with condition 3 tells us that the number of rightward arrows in each column besides the rightmost one is the same, and this number is equal to the number of leftward arrows in each column besides the leftmost one. Call this quantity $k$, then the total number of left arrows is $(2m-1)k$. Similarly, let $l$ be the number of upward arrows in each row besides the topmost one we obtain that the number of up arrows in the board is $(2m-1)l$. Therefore the number of all arrows is $(2m-1)(k+l)\cdot 2$ but is also $4m^2$. Whence $2m-1 | (2m)^2$ but $(2m-1,2m) = 1$, hence $2m-1 = 1$, i.e. $n = 2m = 2$, as desired.
TheUltimate123
31.12.2020 04:45
It is easy to see that \(n=2\) works. We will show \(n=2\) is the only answer. Consider a graph on \(n^2\) vertices, with each vertex representing a cell of the grid. Draw an directed edge from every cell to the (adjacent) cell its arrow points to. Then every vertex has outdegree 1, and the graph is composed of disjoint cycles. Let \(u(i)\), \(d(i)\) be the number of up arrows and down arrows in row \(i\). We are given that \(u(2)=d(2)\), \(u(3)=d(3)\), \ldots, \(u(n-1)=d(n-1)\). But by analyzing each cycle, it is easy to determine that \(d(1)=u(2)\), \(d(2)=u(3)\), \ldots, \(d(n-1)=u(n)\). It follows that \[d(1)=u(2)=d(2)=u(3)=d(3)=\cdots=u(n).\]Since \(u(1)=d(n)=0\), the total number of up/down arrows is \(2(n-1)\cdot d(1)\), i.e.\ a multiple of \(2(n-1)\). Analogously the number of left/right arrows is a multiple of \(2(n-1)\), so \(2(n-1)\mid n^2\). This implies \(n=2\).