# 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$$

• I wonder why should this be closed? – Aqua Apr 6 at 20:30
• FWIW I voted to leave this open. However, I do have the misgiving that this type of a question does not have a "correct" answer. I guess opinions differ whether that makes a question unsuitable. It sounds like you welcome many answers, so may be using the "meta"tag big-list would be a good idea? – Jyrki Lahtonen Apr 6 at 21:03

Let $$(a,b,c)$$ in $$\mathbb{N}$$ such that $$(a^2+b^2)/(1+ab) =c$$

Prove that $$c = p^2$$ with $$p \in \mathbb{N}$$

I don't have a proof though...

Question : 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 is the clip of this specific problem from the movie : https://youtu.be/mYAahN1G8Y8