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$


Here is a problem from Cut The Knot:
Pennies in Boxes

Suppose $N \ge 3$ pennies are distributed into several (at least three) boxes. 
  Take any two boxes $A$ and $B$ with $p$ and $q$ pennies, respectively. If $p$ ≥ $q$ you are allowed to remove $q$ pennies from box $A$ and put them into box $B$, and this action is called an operation.
Show that regardless of the original distribution of pennies, a finite number of such operations can move all the pennies into two boxes. 
If $N = 2^n$, the pennies can be moved into a single box.


Solution

Here we give a proof that can be compared to the Explanation given at the Cut The Knot site. We will use the Principle of Infinite Descent to show that a proposed algorithm must terminate in a finite number of steps.

$1^{st}$ Part:
It is easy to see that we can assume that we start with $N$ pennies in three boxes, and can represent the necessity of an algorithm by writing
$$\tag 1 b_1 + b_2 + b_3 = N, \text{ where } 1  \le b_1 \lt b_2 \lt b_3$$
with $b_i$ pennies in $\text{Box}_i$.
Recall (this is needed to specify the algorithm) that for any integer $m \ge 1$ we can write
$$\tag 2 m + \sum_{k=0}^n m\, 2^k = m\, 2^{n+1}$$
With the setup $\text{(1)}$, using Euclidean division we can write
$\tag 3 b_2 = \, \sum_{k=0}^{n-1} b_1 y_k 2^k + b_1 2^n +  r \text{ where } 0 \le r \lt b_1$
$\tag 4 \quad \quad   \;b_3 = \, \sum_{k=0}^{n-1} b_1 z_k 2^k \quad \quad \quad  +  s \text{ where } s \gt 0\quad \quad \quad \quad \quad  $
where $y_k, z_k \in \{0,1\}$ and $\text{XOR}(y_k,z_k) = 1$.
The algorithm checks which of the coefficients $y_k, x_k$ is equal to $1$:
$\quad \text{If } y_k = 1 \text{ move } b_1 2^k \text{ pennies from } \text{Box}_2 \text{ to } \text{Box}_1$
$\quad \text{If } z_k = 1 \text{ move } b_1 2^k \text{ pennies from } \text{Box}_3 \text{ to } \text{Box}_1$
The last step of the algorithm is to move  $b_1 2^n$ pennies from $\text{Box}_2$ to  $\text{Box}_1$.
After the completion of these operations $\text{Box}_2$ contains $r$ pennies which is strictly less than $b_1$. 
By the Principle of Infinite Descent, using the redistributive operator, the   pennies can be put into two boxes.
$\text{ }$
$2^{nd}$ Part:
The $N = 2^n \ge 1$ pennies can always be be put into either one or two boxes.
So we assume two boxes and write
$$\tag 5 b_1 + b_2  = 2^n, \text{ where } 1  \le b_1 \lt b_2$$
with $b_i$ pennies in $\text{Box}_i$.
Observe that with this setup there is one and only one way to apply the redistribution operation.
It is not difficult to argue that when both $b_1$ and $b_2$ are divisible by $2$, the operation can be equivalently 'checked out' by working on $\frac{N}{2}$, which is strictly less than $N$.
The only other possibility is that both $b_1$ and $b_2$ are odd. But if the operation is applied in this instance, each box will then contain an even number of pennies. So again, the termination of the algorithm is equivalent to it terminating on $\frac{N}{2}$.
By the Principle of Infinite Descent, the specified algorithm must terminate.
