AoPS - Problem

Problem

Source: Swiss Math Olympiad 2022, P4

Tags: combinatorics, combinatorics solved, Swiss Math Olympiad, Switzerland, lattice paths, grid

bora_olmez

26.03.2022 01:53

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.

CANBANKAN

26.03.2022 05:09

Replace Switzerland and Liechenstein with red and blue, respectively. Replace gymnast with player, and their houses with bases.

Tanini_Panini

26.03.2022 13:25

I believe @above's solve is wrong; here is a motivating counterexample:

Imagine we have a very large $n$, and this is what our structure looks like zoomed in on the $4 \times 4$ region around the bottom left square. B B E E B B E E B E B B H E E B Here, H is the Swiss house, B are Liechtensteiner gymnasts standing in the field and E are emply spaces. Here, $|T|$ is initially 3 but after a Swiss gymnasts moves across, the region may now look like this: B B E E B B E E B B E B H E E B which has clearly increased the value of $|T|$. Of course, you can argue that the Liechtensteiner gymnast artificially reducing the value of $|T|$ by disconnecting the two empty spaces could just have moved to increase $|T|$ before the Swiss gymnast moves across, but my point is rather that whilst $|T|$ clearly goes downwards over time it is not a monovariant (if examined on a small window of time it can go upwards) and proving it goes to 0 quickly enough to argue that not enough Swiss gymnasts can cross is very, very difficult to do so rigorously. You can also argue that there are currently "far too many" empty squares in the small area I am looking at, and that for the Swiss gymnast to eventually make it across the rest of the field that I am not looking at, some of these empty spaces will need to be filled (and eventually enough to reduce the value of $|T|$) but again, my point is about lack of justification rather than providing a condemnatory counterexample - I also believe $|T|$ goes down over time too; I just don't think it's something you can prove easily (and certainly not simple enough to just say "Observe that [...] $|T|$ is decreasing..."). I do note that your argument seems to be primarily based on $|S|$ rather than $|T|$, but I would argue there is likely similar edge cases for which you cannot immediately state that $|S|$ increases without a more rigorous explanation that I fear would quickly devolve into some fairly nasty case-bashing. Furthermore, I am not even sure by your definition that $|S|$ always increases; the set of squares that can be attained by blue gymnasts moving down and to the left would go down for me, as the empty squares around their house are no longer in $S$ after a while. Did you mean to define $S$ as the connected component of empty squares attainable from the blue house instead? In that case it would make more sense (but I think counterexamples still apply, and even if there are none I do not think it is something that can be dismissed as trivial either). When trying to find solutions for this problem we (the Swiss Mathematical Olympiad) considered both the approach of analysing the connected empty components around both houses, or the convex connected empty components (being the set of empty spaces from which all down-left or up-right paths to the house remain empty) and we concluded that both these approaches were too vulnerable to falling prey to the aforementioned unappetising case-bashing. Rest assured, though, that we do know of at least one nice solution.

ike.chen

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.)

L567

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.

ike.chen

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...