Four people in a square with hats

I heard of this problem from here, which was also solved in this paper. 

Four people are trying to escape from a room. Guards have placed a hat on each person’s head, and each hat is one of three colors: red, yellow or blue. The four people are arranged at the vertices of a square, with an obstacle in the middle. Each person can see the hats on the heads of those on adjacent vertices of the square, but they cannot see the hat of the person diagonally across from them. They also do not know the color of the hat on their own head.

Each person must guess the color of the hat on their own head. If at least one person guesses correctly, they can all escape the room together. No communication is allowed once the hats are placed on their heads, but they can coordinate on a strategy beforehand. They also know how they will be arranged in the square.

How can they be guaranteed to escape the room?

==========================================

Below is my solution.

Suppose the four people are $a, x, b,$ and $y$ in circular order. These letters could also refer to the colors of their hats i.e. $0, 1,$ or $2$. Let $\hat{a}$ and $\hat{b}$ be how $a$ and $b$ guess their own hat colors given $(x,y)$, which is depicted below. The first of each pair of bold digits is $\hat{a}$ and the second is $\hat{b}$. 

Now, imagine as $x$ and $y$ we know $(a,b)$. For every possible $(a,b)$, assume the worst that they both got it wrong. For example if $(a,b)=(1,2)$ then assume $(\hat{a},\hat{b})\in\{(0,0),(0,1),(2,0),(2,1)\}$. Clearly, $(\hat{x},\hat{y})=(1,0)$ makes sure at least $x$ or $y$ gets it right. The same conclusion holds for all other possibilities of $(a,b)$, which we now prove below using algebra in $Z_3$ i.e. $-1=2$.

Strategies of $a$ and $b$ above are actually $\hat{a}=x+y$ and $\hat{b}=x-y+1$. From $x$'s and $y$'s perspective, $x=2(\hat{a}+\hat{b}+2)$ and $y=2(\hat{a}-\hat{b}+1)$. So $x$ wants to know $\hat{a}+\hat{b}$ and $y$ wants to know $\hat{a}-\hat{b}$. They can guarantee to get exactly one right: on the $\hat{a}\hat{b}$ plane, the four grid points that differ with $(a,b)$ at both coordinates are vertices of a $1\times 1$ square. Two of them have the same $\hat{a}+\hat{b}$ and the other two have the same $\hat{a}-\hat{b}$. Therefore $x$ and $y$ can guess accordingly and exactly one of them will be right.

IMO 2021 Problem 5

Two squirrels, Bushy and Jumpy, have collected $2021$ walnuts for the winter. Jumpy numbers the walnuts from 1 through $2021$, and digs $2021$ little holes in a circular pattern in the ground around their favorite tree. The next morning Jumpy notices that Bushy had placed one walnut into each hole, but had paid no attention to the numbering. Unhappy, Jumpy decides to reorder the walnuts by performing a sequence of $2021$ moves. In the $k$-th move, Jumpy swaps the positions of the two walnuts adjacent to walnut $k$.

Prove that there exists a value of $k$ such that, on the $k$-th move, Jumpy swaps some walnuts $a$ and $b$ such that $a<k<b$.

===============================

Sketch of proof:

Equivalently, we want to show the following is impossible to achieve. In a circle of $2021$ cells which are initially all unmarked, we mark them one by one sequentially, such that each cell, when marked, is adjacent to either two marked or two unmarked cells.

IMO 2021 Problem 1

Let $n \geqslant 100$ be an integer. Ivan writes the numbers $n, n+1, \ldots, 2 n$ each on different cards. He then shuffles these $n+1$ cards, and divides them into two piles. Prove that at least one of the piles contains two cards such that the sum of their numbers is a perfect square.

====================================

Proof:

There must be an integer $k$ such that $2k^2-4k$, $2k^2+1$, and $2k^2+4k$ are all within $[n, 2n]$. Any two of them sum up to a perfect square.

Q.E.D.

IMO 1995 Problem 6

Let $ p$ be an odd prime number. How many $ p$-element subsets $ A$ of $ \{1,2,\dots,2p\}$ are there, the sum of whose elements is divisible by $ p$?

=============================

Solution:
Consider set $P=\{0,1,\ldots,p-1\}$ and its two equal-sized subsets $B$ and $C$ such that their sums are identical modulo $p$. We claim that there's bijection between $(B,C)$ and $A$ as follows. For any $x\in B\cap C$, we add $x$ to $A$; for any $x\in B-C$, we add both $x$ and $x+p$ to $A$; for any $x\notin B\cup C$, we add $x+p$ to $A$. Clearly $|A|=p$ and sum up to $0$ modulo $p$. So we count $(B,C)$ below.

Let $k\notin\{0, p\}$ be the size of $B$ and $C$, and $K$ be the set of $k$-element subsets. Because $p$ is prime, $K$ is equally divided into $p$ disjoint partitions by subset sum modulo $p$. Each subset has size $\frac{1}{p}\binom{p}{k}$ and contributes $\frac{1}{p^2}\binom{p}{k}^2$ to count of ordered pair $(B,C)$. So each $k\notin\{0,p\}$ contributes $\frac{1}{p}\binom{p}{k}^2$, and the total sum is

$$
\frac{1}{p}\sum_{k=0}^{p}\binom{p}{k}^2-\frac{2}{p}+2=\frac{1}{p}\binom{2p}{p}-\frac{2}{p}+2
$$

USAMO 2021 Problem 2

The Planar National Park is a subset of the Euclidean plane consisting of several trails which meet at junctions. Every trail has its two endpoints at two different junctions whereas each junction is the endpoint of exactly three trails. Trails only intersect at junctions (in particular, trails only meet at endpoints). Finally, no trails begin and end at the same two junctions.

A visitor walks through the park as follows: she begins at a junction and starts walking along a trail. At the end of that first trail, she enters a junction and turns left. On the next junction she turns right, and so on, alternating left and right turns at each junction. She does this until she gets back to the junction where she started. What is the largest possible number of times she could have entered any junction during her walk, over all possible layouts of the park?

=========================================

Solution:

The answer is $3$. Let a junction $v$ be endpoint of trails $A$, $B$, and $C$. There are $3\times 2=6$ ways of visiting $v$: $A$ followed by $B$, $A$ followed by $C$, etc. Obviously none of them should be repeated before the visitor stops. Moreover, the following two visits to $v$ before the visitor stops cannot both happen: $A$ followed by $B$ and $B$ followed by $A$. So the maximum number of repeated visits is at most $3$, and it is not hard to construct one.