Combinatorics problems that can be solved via infinite descent

Question

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$

Answer 1

What about this one :

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

Answer 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

Answer 3

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.

Answer 4

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.

Answer 5

This is a generalization of a slightly different proof of @mathlove's answer.

There are no polygons having an odd number of sides, all of whose sides are equal, and all of whose vertices are lattice points.

Let $d$ be the square of the common side length. It must be an integer as all the vertices are lattice points. There must be a smallest value of $d$ for which there exists a lattice polygon with an odd number of edges all of length $d$, call this minimum value $d'$. Now color all the vertices of the lattice either black or white in a checkerboard pattern. In other words color a vertex white if the sum of the coordinates is even and color it black if the sum of the coordinates is odd. Now if $d$ is odd each edge connects a white vertex to a black vertex, and so any cycle must be even. So $d'$ must even, and therefore all the vertices are the same color. If all the points are white then if we map each point $(x,y)$ to $((x+y)/2,(x-y)/2)$ then each vertex of our path maps to an integer lattice point, and the square of the distances between the transformed points is $d'/2$, therefore $d'$ cannot be the smallest distance. If the vertices are black then mapping $(x,y)$ to $((x+y+1)/2,(x-y+1)/2)$ shows that there exists a polygon with shorter edges. Therefore no smallest length for a polygon with an odd number of sides exists, and so no such polygon exists.

Note that this proof easily generalizes to paths in arbitrary dimensional lattices.

Answer 6

The Fundamental Theorem of Arithmetic

Existence

The following can be proven using the Principle of Infinite Descent - see this link.

Proposition 1: Every integer $n \ge 2$ can be factored into primes:
There exists a nonempty family $(p_i)_{\, 1 i \le i \le u }$ of primes such that

$$\tag 1 n = p_1 p_2 \dots p_u$$

Uniqueness

Proposition 2: If an integer $n \ge 2$ is written as

$$\tag 2 n = p_1 p_2 \dots p_u$$

and

$$\tag 3 n = q_1 q_2 \dots q_v$$

with two nonempty families of primes, $(p_i)_{\, 1 i \le i \le u }$ and $(q_i)_{\, 1 i \le i \le v }$,
then $u = v$ and the families can be brought into a $1:1$ correspondence.

Proof
To get a contradiction, assume the proposition is false.

An easy factoring argument presents us with an integer $n \ge 2$ satisfying $\text{(2)}$ and $\text{(3)}$ with $p_i \ne q_j$ for any subscripts. Also, both $u$ and $v$ must be greater than $1$ and we can insist that $p_1 \lt q_1$.

The number

$$\tag 4 n' = (q_1 - p_1) q_2 \dots q_v \ge 2$$

is divisible by $p_1$. If $q_1 - p_1 \ge 2$, by proposition 1 we can factor it into primes and it is impossible for $p_1$ to appear in this factorization. Since we also have $p_1 \ne q_i$ for $i \ge 2$, the integer $n' \lt n$ can now also be presented as an integer with two different prime factorizations.

So by the Principle of Infinite Descent, the proposition is true. $\quad \blacksquare$

Combined Statement

Theorem 3: Every integer greater or equal to $2$ has one and only one
(up to a rearrangement) prime factorization.

Answer 7

Does there exist such a lattice rectangle which can be decomposed into lattice pentagons congruent to the one shown in the Figure? (KöMaL A.344., April 2004)

Answer 8

Here is a problem from Cut The Knot:

Ambassadors at a Round Table

$2n$ ambassadors are invited to a banquet. Every ambassador has at most $n-1$ enemies. Prove that the ambassadors can be seated around a table, so that nobody sits next to an enemy.

Solution

The analysis at the Cut The Knot site takes a 'shallow dive' into graph theory (nodes and edges) and geometry (circles, regular polygons, and vertices) to describe the algorithmic solution. Here we derive it using the language of elementary set theory, although many of the details will be left for the reader to fill in.

In the next section we develop some general theory. In the last section an algorithm is constructed that can be applied to the seating problem (it is left to the reader to understand why this model works).

---

General Theory

Let $A$ be a set with $n \ge 2$ elements. Recall that bijective transformations of $A$ are also called permutation of $A$.

Here we are interested in the cyclic permutations on $A$ and $k\text{-cycles}$. where $2 \le k \le n$.
We'll call any cycle of maximum length $n$ a seating arrangement of $A$.

Let $\sigma$ be a seating arrangement $A$. If $a \in A$ the injective function $\sigma'$ restricted to $A \setminus \{a\}$ is a partial function. The function can be understood as a trajectory

$$\tag 1 {\sigma}^1(a) \mapsto {\sigma}^2(a) \mapsto \dots \mapsto {\sigma}^{n-1}(a) \mapsto {\sigma}^{n}(a) = a$$

The trajectory is of length $n$, starting at ${\sigma}^1(a)$ (not in the range of ${\sigma'}$) and ending at $a$ (not in the domain of ${\sigma'}$).

In general, an injective sequence $(a_i)_{\, 1 \le i \le k}$ with $2 \le k \le n$ defines a trajectory $\tau$ in a natural way,

$$\tag 2 \tau(a) = a_{i+1}, \text{when } a = a_i, \text{ for } i \lt k$$

The transition ${\tau}^{j}(a) \mapsto {\tau}^{j+1}(a)$ in a trajectory is called a step to the right. The same terminology can be used when working with cycles and we can also take steps to the left (but not always possible with a trajectory). Also, we can extend the cycle notation to trajectories,

$$\tag 3 \tau = Œ|\, a_1 a_2 \dots a_k \,þ \text{ where } a_1 \text{not in range and } a_k \text{ not in domain of } \tau $$

We have the following result.

Proposition 1: Every injective partial transformation on a finite set $A$ with no fixed points defines a partition on $A$ that corresponds to a decomposition of the transformation into $k\text{-cycles and/or trajectories}$.

Now consider a symmetric homogeneous relation $\rho$ on $A$. If $\sigma$ is a permutation of $A$, let $\Gamma(\sigma, \rho)$ denote the number of elements that belong to both the graphs of $\sigma$ and $\rho$. We have the following,

$$\tag 4 \Gamma(\sigma, \rho) = \Gamma(\sigma^{-1}, \rho)$$

---

The Algorithm

Let $A$ be a finite set with $2n$ elements with $n \ge 2$ and $\rho$ a symmetric homogeneous relation on $A$ that does not intersect the diagonal $\Delta_A$. Suppose that for every $a \in A$, the set $\rho(a)$ has at most $n - 1$ elements.

Let $\sigma$ be any cyclic permutation of $A$ of length $2n$, i.e. a seating arrangement.

If $\Gamma(\sigma, \rho) \gt 0$, using cyclic notation we can write

$$\tag 5 \sigma = \big ( \; a \, \sigma(a) \dots \sigma^{2n-1}(a) \; \big ) \text{ where } (a,\sigma(a)) \in \rho$$

Taking steps to the right of $\sigma(a)$ look for $\sigma^k(a)$ with $(a,\sigma^k(a)) \notin \rho$ and $(\sigma(a),\sigma^{k+1}(a)) \notin \rho$. A simple counting argument shows that such a $2 \le k \lt 2n-1$ can be found.

The trajectory

$$\tag 6 Œ|\, \sigma(a) \dots \sigma^k(a) \,þ $$

can be inverted

$$\tag 7 Œ|\, \sigma^k(a) \dots \sigma(a) \,þ $$

With

$\quad J = \big\{(a,\sigma^k(a)), (\sigma(a),\sigma^{k+1}(a))\big\} \cup [Œ|\, \sigma^k(a) \dots \sigma(a) \,þ]$

and

$\quad R = \big\{(a,\sigma(a)), (\sigma^k(a),\sigma^{k+1}(a))\big\} \cup [Œ|\, \sigma(a) \dots \sigma^k(a) \,þ]$

define

$$\tag 8 \sigma' = \big [ \sigma \cup J \big ] \setminus R$$

It is not difficult to demonstrate that $\sigma'$ is a permutation and is also in fact a seating arrangement. It can also be shown that

$$\tag 9 \Gamma(\sigma', \rho) = \Gamma(\sigma, \rho) -1 \text{ OR } \Gamma(\sigma', \rho) = \Gamma(\sigma, \rho) -2$$

By the Principle of Infinite Descent the algorithm terminates with $\Gamma = 0$.