Let $n \geq 2$ be an integer. Switzerland and Liechtenstein are performing their annual festive show. There is a field divided into $n \times n$ squares, in which the bottom-left square contains a red house with $k$ Swiss gymnasts, and the top-right square contains a blue house with $k$ Liechtensteiner gymnasts. Every other square only has enough space for a single gymnast at a time. Each second either a Swiss gymnast or a Liechtensteiner gymnast moves. The Swiss gymnasts move to either the square immediately above or to the right and the Liechtensteiner gymnasts move either to the square immediately below or to the left. The goal is to move all the Swiss gymnasts to the blue house and all the Liechtensteiner gymnasts to the red house, with the caveat that a gymnast cannot enter a house until all the gymnasts of the other nationality have left. Determine the largest $k$ in terms of $n$ for which this is possible.
Problem
Source: Swiss Math Olympiad 2022, P4
Tags: combinatorics, combinatorics solved, Swiss Math Olympiad, Switzerland, lattice paths, grid
26.03.2022 05:09
Replace Switzerland and Liechenstein with red and blue, respectively. Replace gymnast with player, and their houses with bases.
26.03.2022 13:25
I believe @above's solve is wrong; here is a motivating counterexample:
29.03.2022 06:45
Hopefully my solution has no flaws . The largest possible value is $k = (n-1)^2$. This is clearly achievable, as the $(n-1)^2$ squares in the top left portion of the grid could contain all $(n-1)^2$ Liechtensteiner gymnasts while the Swiss gymnasts enter the blue house (one at a time) by moving along the empty squares. Now, we will consider $k > (n-1)^2$. WLOG, assume the first gymnast to enter a new house is Swiss. In order to reach our goal, there clearly must be a point in time where all $k$ Liechtensteiner gymnasts are in neither house. (In particular, this must occur before the first Swiss gymnast enters the blue house.) Furthermore, all $k$ Swiss gymnasts must leave the red house before any of the Liechtensteiner gymnasts can enter. Claim: Suppose some Swiss gymnast leaves the red house while all $k$ Liechtensteiner gymnasts are in neither house. Then, as long as the red house is not empty, it is impossible for this gymnast to reach the blue house. Proof. Because none of the Liechtensteiner gymnasts can enter the red house, we know there's at most $$(n^2 - 2) - k \le 2n - 4$$unoccupied squares on the grid. Since all paths from the red house to the blue house require $2(n-1)$ moves, however, any Swiss gymnast must pass through $2n-3$ unoccupied squares along the way. The claim follows readily. $\square$ Now, let $T$ denote the set containing: all $k$ Liechtensteiner gymnasts and all Swiss gymnasts that were still in the red house right after the last Liechtensteiner gymnast left the blue house. Because no Swiss gymnast can enter the blue house until all $k$ Liechtensteiner gymnasts have exited, there are at least $$k - [(n^2 - 2) - k)] = 2k + 2 - n^2$$Swiss gymnasts in $T$ (since all Swiss gymnasts not in $T$ must've been among the $n^2 - 2$ squares without houses immediately after last Liechtensteiner gymnast left the blue house). It's evident that no gymnasts in $T$ can enter a new house until all Swiss gymnasts in the set have exited the red house. This implies at some point in time, there must've been no all gymnasts in $T$ inside a house, so $\lvert T \rvert \le n^2 - 2$ must hold. Hence, $$n^2 - 2 \ge \lvert T \rvert \ge [k] + [2k + 2 - n^2] \ge 3[(n-1)^2 + 1] + 2 - n^2 = 2n^2 - 6n + 8$$must hold so $$0 \ge n^2 - 6n + 10 = (n-3)^2 + 1$$or $(n - 3)^2 \le - 1$, which is a contradiction. Thus, the goal is impossible for $k > (n-1)^2$, which completes our proof. $\blacksquare$ Remarks: I was initially motivated by the construction for $k = (n-1)^2$. In addition, testing small values of $n$ was also helpful. A bit later, I realized that $k > (n-1)^2$ was probably bad because there wouldn't be enough empty squares for Swiss gymnasts to reach the blue house. Unfortunately, I failed to consider that having some Swiss gymnasts leave the red house before all $k$ Liechtensteiner gymnasts left the blue house would affect my bounds. (Thankfully, this possibility was covered in my solution above.)
29.03.2022 07:18
ike.chen wrote: Claim: Suppose some Swiss gymnast leaves the red house while all $k$ Liechtensteiner gymnasts are in neither house. Then, as long as the red house is not empty, it is impossible for this gymnast to reach the blue house. Proof. Because none of the Liechtensteiner gymnasts can enter the red house, we know there's at most $$(n^2 - 2) - k \le 2n - 4$$unoccupied squares on the grid. Since all paths from the red house to the blue house require $2(n-1)$ moves, however, any Swiss gymnast must pass through $2n-3$ unoccupied squares along the way. The claim follows readily. $\square$ Unfortunately, I think this is false, since as mentioned in the counterexample in #3, the Liechtensteiner gymnasts can rearrange themselves and "create space" for the swiss gymnast to go.
29.03.2022 07:45
L567 wrote: ike.chen wrote: Claim: Suppose some Swiss gymnast leaves the red house while all $k$ Liechtensteiner gymnasts are in neither house. Then, as long as the red house is not empty, it is impossible for this gymnast to reach the blue house. Proof. Because none of the Liechtensteiner gymnasts can enter the red house, we know there's at most $$(n^2 - 2) - k \le 2n - 4$$unoccupied squares on the grid. Since all paths from the red house to the blue house require $2(n-1)$ moves, however, any Swiss gymnast must pass through $2n-3$ unoccupied squares along the way. The claim follows readily. $\square$ Unfortunately, I think this is false, since as mentioned in the counterexample in #3, the Liechtensteiner gymnasts can rearrange themselves and "create space" for the swiss gymnast to go. Yeah you're correct, I just found a counterexample for $n = 4$. Well, time to find another approach...