Let $n\ge 3$ be an integer. Put $n^2$ cards, each labelled $1,2,\ldots ,n^2$ respectively, in any order into $n$ empty boxes such that there are exactly $n$ cards in each box. One can perform the following operation: one first selects $2$ boxes, takes out any $2$ cards from each of the selected boxes, and then return the cards to the other selected box. Prove that, for any initial order of the $n^2$ cards in the boxes, one can perform the operation finitely many times such that the labelled numbers in each box are consecutive integers.
Problem
Source: CGMO 2016 Q1
Tags: combinatorics
roughlife
13.09.2016 09:52
It's easy if one can switch just one card. So, we should know how to move which can be like one-card switching. i. $n=2k+1$ let the boxes be $B_{1},B_{2},...B_{n}$. if we want to switch $x\in B_{i}$, $y\in B_{j}$, we just switch other $2k$ elements between $B_{i}$ and $B_{j}$. done. ii. $n=2k$ It's sufficient to prove in case of $n=4$. Assume that $B_{i}=\{x,1,2,3\}, B_{j}=\{y,4,5,6\}$. let's switch $x$ and $y$, First, switch $(x,1)$ and $(4,5)$. then $(4,5)$ and $(1,y)$. after operation, we get $B_{i}=\{y,1,2,3\}, B_{j}=\{x,4,5,6\}$. done.
bobthesmartypants
14.02.2017 20:43
Given two boxes (columns):
$$
\begin{array}{cc}
a & c\\
b & \cdot\\
\cdot & \cdot
\end{array} \to \begin{array}{cc}
c & a\\
\cdot & b\\
\cdot & \cdot
\end{array}
\to \begin{array}{cc}
a & \cdot\\
b & \cdot\\
c & \cdot
\end{array}$$Thus we may switch any one element with any other element, as long as $n\ge 3$. It is obvious how to restore the boxes now.