Combinatorics problems that can be solved via infinite descent

I'm looking for high school problems that can be solved with the method of infinite descent. Usually, those problems are from number theory, but I would be very happy if someone could provide a problem(s) from combinatorics and/or any other field of mathematics. Here are some problems from number theory:

Prove that a following equations have no nontrivial solutions in $\mathbb{Z}$:

• $a^3+2b^3 = 4c^3$

• $2a^2+3b^2 = c^2+6d^2$

• $x^2 + y^2 + z^2 = 2xyz$

• $x^4+y^4 = z^2$

Solution 1:

There is no regular pentagon whose vertices are on the lattice points.

Suppose that $ABCDE$ is a regular pentagon where $A,B,C,D,E$ are on the lattice points. Then, let $A',B',C',D',E'$ be the intersection point of $BD$ with $CE$, $AD$ with $CE$, $AD$ with $BE$, $AC$ with $BE$, $BD$ with $AC$ respectively.

Then, since $ABA'E$ is a parallelogram, we see that $A'$ is also on the lattice point. Similarly, we see that $B',C',D',E'$ are on the lattice points.

So, we see that $A'B'C'D'E'$ is a smalller regular pentagon whose vertices are on the lattice points.

Solution 2:

Problem : Twenty random cards are placed in a row all face down. A turn consists of taking two adjacent cards, where the left one is face up and the right one can be face up or face down, and flipping them both. Show that this process must terminate (with all the cards facing up).

Solution : Label each face down card as $0$ and face up card as $1$. Let $a_n$ denote the number obtained by concatenating the numbers of all cards, after the $n^{\text{th}}$ turn. Initially, all cards are are face up, so the number before the first turn, $a_0 = \underbrace{1111...1}_{20 \ \text{times}}$ in binary notation.

Note that after each turn, the number strictly decreases, i.e, $a_{n+1} < a_{n} \ \ \forall n \in \mathbb{N}$. This is because the only options are $x10y \ \to x01y$ or $x11y \ \to x00y$, both decreasing.

Now, if this process didn't terminate, it'd set up an infinite descent on a well ordered set, $S = \{a_{n} \ | \ n \in \mathbb{N}\}$ which is impossible.

Thus, the process terminates with all cards facing up ($\underbrace{0000...0}_{20 \ \text{times}}$).

I first encountered this problem in the movie X+Y. Here's the clip of this specific problem from the movie : https://youtu.be/mYAahN1G8Y8