On a square board divided into $15 \times 15$ little squares there are $15$ rooks that do not attack each other. Then each rook makes one move like that of a knight. Prove that after this is done a pair of rooks will necessarily attack each other.
Problem
Source: ToT - 2001 Spring Junior O-Level #5
Tags: combinatorics unsolved, combinatorics, ToT, Tournament of Towns
10.07.2016 16:25
Let little squares are (1,1)-(15,15) and 15 rooks are (x1,y1)-(x15,y15). From assumption, x1-x15 are 1-15, y1-y15 are 1-15.So S=∑(1≦i≦15)xi+yi=2(1+...+15) is even.Let 15 rooks after one move are (x'1-y'1)-(x'15-y'15).If we suppose contrary to conclusion, similarly above, T=∑(1≦i≦15)x'i+y'i is even.On the other hand, (x'i+y'i)-(xi+yi) is odd.So T-S is odd.This is contradiction.Therefore the conclusion holds. Apparently we can change 15 to 2n+1.
31.03.2018 01:13
The sum of the coordinates of the pieces is $2(1+2+3+\cdots+15)$. When a rook moves, its sum changes by $(\pm2\pm1)$ which is always odd. When all the rooks move the sum will change by the sum of $15$ odd numbers, which is odd, so it can not be $2(1+2+3+\cdots+15)$.
12.06.2022 03:44
Place the chessboard on the first quadrant of the coordinate plane, with squares at $(1, 1), (1, 2), \cdots, (1, 15), (2, 1), \cdots, (15, 15)$. Consider the sum of the sum of the coordinates across all squares which are occupied by a rook. Upon one such move, the total number changes by $\sum_{i=1}^{15} a_i$, where each $a_i$ is $-3, -1, 1$, or 3. Either way, the value changes by an odd amount. However, for the rooks to be non-attacking, the sum must be $15 \cdot 16$, which is obviously even. This leads to a contradiction.
03.04.2023 16:44
Label the squares with coordinates and note each knight move changes the coordinates by $(\pm 1,\pm 2)$ or $(\pm 2,\pm 1)$. Either way, the sum of the coordinates changes parity. The sum of the coordinates must start and end at $2(1+2+\dots+15)$ since each row/column can only have one rook, so we have a parity contradiction since the final sum should be odd. $\square$
23.08.2023 19:02
Color the rows black and white alternating. The number of rooks that change colors when they move must be even, i.e. number of rooks that go two horizontal and one vertical must be even. Repeating the same reasoning on columns gives us a contradiction.
10.09.2023 21:07
15.10.2023 23:04
18.10.2023 00:31
Label the squares from $(1,1)$ in the bottom left corner to $(15,15)$ in the top right corner. The sum of the coordinates of the squares that the rooks are on is $240$ and must stay constant in order for the rooks to be non-attacking. However, each knight move shifts the sum of the coordinates by an odd number, so the difference over $15$ rooks is still odd. Thus, it is impossible for the difference to equal $0$, so two rooks must attack each other after the moves. $\square$
31.10.2023 01:18
Label the $15$ rows from $1$ to $15$ and similarly with the columns. Note that if all rooks are non-attacking, the sum of the rows and the column values of all the rooks must be $(1+2+\dots+15)+(1+2+\dots+15)=480$, since for each row and column there is exactly one rook. However, applying knight move on rook $R$ changes the parity the row-column sum of $R$, because a knight move is $2$ in one direction and $1$ in the other. Summing this over all $15$ rooks, we get that the overall sum of all the rows and columns changes parity also (meaning it becomes odd), which is impossible, because if all the rooks are non-attacking, then the sum should be even. Therefore, at least two of the rooks must attack each other, finishing the problem.
03.11.2023 17:44
08.12.2023 19:56
Out of the fifteen knight moves, categorize them as "more horizontal" or "more vertical". One of these is odd, assume WLOG that there are an odd number of "more vertical" moves. Then color the chessboard with the parity of the column. An odd number of rooks changed parity, impossible. $\blacksquare$
26.12.2023 03:29
Label the rows and columns from 1 through 15, and the "value" of a square as the sum of its row and column value. The sum of the values of the positions of the rook must start and end as $2(1+2+3+\ldots+15)$. However, the "change" when rook makes a knight move will always be odd (or more precisely, -3, -1, 1, or 3). Thus the total change will be odd, contradiction. $\blacksquare$
26.12.2023 05:48
Assume ftsoc after all rooks make their move, no two of them are attacking. Number the columns and rows $1, 2, \ldots, 15$, and let $(x, y)$ denote the square in the $x$th column and $y$th row. Let the rooks be $1, 2, \ldots, 15$, and let rook $i$ start at $(x_i, y_i)$ and then move to $(x_i', y_i')$. Note that $x_i' + y_i' \equiv x_i + y_i + 1 \pmod 2$.Then, by assumption, we must have $$\sum_{i = 1}^{15} (x_i + y_i) = (1 + 2 + \cdots + 15) + (1 + 2 + \cdots + 15) = \sum_{i = 1}^{15}(x_i' + y_i') \equiv \sum_{i = 1}^{15}(x_i + y_i) + 1 \pmod 2,$$contradiction.
08.07.2024 03:54
The sum of the $x$ and $y$ coordinates of all the rooks will be $2(1+2+\cdots+15) = 240$. However, each move changes the sum of the $x$ and $y$ coordinates of a rook by either $-3$, $-1$, $1$, or $3$, meaning that doing this fifteen times would result an odd change, which cannot happen since it must be even to not change the sum of $240$.
29.07.2024 02:09
Consider the sum of the $x$ and $y$ coordinates. It stays invariant through the moves, but for each knight it changes by $-3, -1, 1, 3$, all of which are odd. Since there are $15$ knights the sum changes by an odd amount which is a contradiction.
08.10.2024 19:46
03.11.2024 22:52
Place this on a coordinate plane with $1\le x,y\le 15$. Let $(x_i,y_i)$ denote the coordinates of the $i$th rook. If none of the rooks attack each other, we have $$x_1+x_2+\dots+x_{15}+y_1+y_2+\dots+y_{15}=2(1+2+\dots+15).$$The knight moves will change the total sum by an odd number, so the total sum cannot stay the same.
06.12.2024 18:33
Place the chessboard on the Cartesian plane with each squaring correpsonding to a $(x_i, y_j)$ with $1 \leq x_i, j_j \leq 15$. Consider the $15$ rooks $r_1, r_2, \dots r_{15}$. $$\sum_{r} x_i+y_j = 2(1+2+\dots+15) = 15 \cdot 16$$Each move the rook either travels $(1, 2) (-1, 2) (-2, 1) (-2, -1)$ or a sum of $(3, 1, -1, -3)$. After $15$ moves of this the sum changes parity. But this arrives at a contradiction so we are done.