Table of Contents

Problem 1. Does equation $x^{2}+y^{2}+z^{2}=2 x y z$ have any non-zero integer solutions?

Problem 1 Solution 1

Insight 1: consider mod 2

Right hand side is even so there are two cases x,y,z are all even or one of them is even.

Case 1: If one of them is even then LHS is 2 (mod 4) and RHS is 0 (mod 4). Contradiction.

Case 2:If all of them are even divide the equation by the highest power of two that divides all of them, i.e. $$x=2^k x_0,y=2^k y_0,z=2^k z_0$$ and at least one of $x_0,y_0,z_0$ is odd, but then dividing equation by $2^{2k}$ we get $$x_0^{2}+y_0^{2}+z_0^{2}=2^{k+1} x y z $$ and you can apply the argument from case 1 obtaining contradiction.

Note: when writting a proof you can skip extra circle of logic and go straight to case 2, hence the proof would just be:

Let $k$ be highest power of 2 dividing $x$,$y$ and $z$, i.e $x=2^k x_0,y=2^k y_0,z=2^k z_0$ and at least one of $x_0,y_0,z_0$ is odd. Dividing equation by $2^{2k}$ we obtain $x_0^{2}+y_0^{2}+z_0^{2}=2^{k+1} x y z $ and since at least one of $x_0,y_0,z_0$ is odd, and RHS is even exactly two of $x_0,y_0,z_0$ must be odd but then LHS is 2 mod 4 and RHS is 0 mod 4. Contradiction.

Problem 1 Solution 2: Solution Trees

The point of this solution is to show how to structure solution for a much larger class of equations like this.

$$x^2+y^2+z^2=1xyz+2xy+3xz+4yz+5x+6y+7z+8$$

where instead of $1,2,3,4,5,6,7,8$ you can have arbitrary integer numbers (that satisfy some mild conditions) and of course this can be generalized to more variables where LHS is sum of squares and right hand side sum of square-less terms i.e. polynomial in these variables without terms that are divisible by the square of any variable.

Which is generalization of Markov Diophantine Equation

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

See https://en.wikipedia.org/wiki/Markov_number for additional information.

Insight 1: Vieta's Formula yields solution trees

\begin{align} 0 &= x^{2}-(2 y z) x +y^{2}+z^{2}=(x-x_1)(x-x_2) \\ x_1+x_2& = 2yz\\ x_1x_2& = y^2+z^2 \end{align}

Hence if you have solution $(x_1,y,z)$ you can obtain $(x_2,y,z)$.

Insight 2: Reduce the benchmark.

There are several benchmarks we can take benchmark b(x,y,z)=max(|x|,|y|,|z|) or b(x,y,z)=|x|+|y|+|z| or b(x,y,z)=min(|x|,|y|,|z|). Let us not choose which benchmark we will use just yet and select it when it is the right time.

It also follows from first insight that $x_i$ are of the same sign (i.e. either both positive or both negative) and hence we can skip the signs and absolute values below focusing only on positive solutions (x,y,z).

So the plan is to show that via solution tree we can always get to a solution with benchmark less than some small number and check those by hand.

\begin{align} x_1+x_2 & = 2yz \\ x_1x_2 & = y^2 + z^2 \end{align}

which gives us \begin{align} x_2 & = 2yz - x_1 \\ x_2 & = \frac{y^{2}+z^{2}}{x_1} \\ \end{align}

Let us deal with case when $x=y$ later and assume without loss of generality that $z <y < x_1, x_2 \leq x_1$ and our goal is to show that $x_2 < y$ that reduces benchmark $b=max(x,y,z)$

So we can try something like this \begin{align} x_2 & = \frac{y^{2}+z^{2}}{x_1} < \frac{2y^{2}}{x_1} < \frac{2y}{x_1} y < \frac 2z y \\ \end{align} where the last inequality comes from bound on $y$ or more precisely $\frac{2y}{x_1}$, which comes from from $x_1 + x_2 = 2yz$ that yiels $ \frac 1z = \frac {2y}{x_1+x_2} \geq \frac{2y}{2x_1} = \frac {y}{x_1}$.

Hence we are done in case $z>1$.

In fact we just showed that all solutions must either have two of $x,y,z$ equal or $z=1$, as otherwise we can keep descending benchmark ad infinitum. The rest is just dealing with these two cases:

$x=y$ case

The equation becomes $2x^2+z^2=2x^2z$ which $z^2=(2z-1)x^2$ which we can show via various methods including looking at mod 2 which brings us back to solution 1.

The tricky part here is that in most of that solutin of generalized Markov Diophantine Equation where $xyz$ term has coefficient 2 is the most tricky one, where the number of trees might be infinite. For case where this coefficient is greater than 2 , the solutions are rather well structured.

$z=1$ case

The equation becomes $0=x^2+y^2+1-2xy=(x-y)^2+1$ which obviously impossible as RHS is greater than 1, since squares are positive.

Problem 6. The kingdom of Mathlandia contains 2016 airports. Each airport is connected by a direct flight with at least 100 others. It's known that you can fly from each airport to any other, perhaps, with stopovers. Prove that, in fact, you can fly from any airport to any other making fewer than 65 connections.

Problem 6 Solution 1: Direct approach

Insight 1: do by induction

Let us consider airport $a$ and let $A_i$ be airports that are connected to it by exactly $i$ connections, i.e. you can reach it via $i$ connections but cannot reach it via $i-1$ connections.

Note: Special case $A_0$ just consists of a for the consistency of below calculations.
Since all airports are connected it is enough to prove that $A_{65}=0$ as this would imply that all airports are within $A_0,A_1,A_2...A_{65}$. In fact we will show $A_{58}=0$

Note that airports that for $i<j$, $a_1 \in A_i$ and $a_2 \in A_j$ can only be connected if $j-i \leq 1$; as otherwise you can reach $a_2$ via going to $a_1$ in n flights and then flying to $a_1$ which would be $i+1$ connections which is less than $j$ which implies $a_2 \notin A_j$.

From this we get that each airport in $A_i$ can only be connected to airports in $A_{i-1}, A_{i}$ or $A_{i-1}$. Hence since each airport has at least $100$ connections from each airport we get $A_i>0$ implies $|A_{i-1}|+|A_{i}|+|A_{i-1}| \geq 101$.

If $|A_{57}| \neq 0$ hence $A_{3k}+A_{3k+1}+A_{3k+2} \geq 101$ for $k=0,1,...19$ and hence $$|A_0+A_1+...+A_{59}|=|(A_0+A_1+A_2)+(A_4+A_5+A_6)+...(A_{57}+A_{58}+A_{59})| \geq 20 \cdot 101=2020$$ which contradicts the fact that there are only 2016 towns.

Note: we can start this sum from $|A_0+A_1| \geq 101$ prove in same way $|A_{57}|=0$

Since it is $2021$, what if this question was asked with $2021$ airports above would you need 57 connections?

Indeed: here is a counterexample and in fact you need 58.

[1, 100, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 1, 99, 1, 100, 1]
length: 59
sum: 2021
minimum sum: 101.0

In fact this is an optimal counterexample for these problems starting from $1,100$ then a sequence of $1,1,99$ possibly truncated in the last triple, and then finishing with 100,1.

More generaly in a $\it{connected}$ $\it{graph}$ $G$ if each $vertex$'s $valency$ $(degree)$ is at least $V$, then the number of vertecies that are distance $D$ from any vertex is at least $min(|G|,f(D,V))$, where:

\begin{align} f(0,V)&=1=1 \\ f(1,V)&=1+V&=V+1 \\ f(2,V)&=1+V+1&=V+2 \\ f(3,V)&=1+V+V+1&=2V+2 \\ f(4,V)&=1+V+1+V+1&=2V+3 \\ f(5,V)&=1+V+1+1+V+1&=2V+4 \\ f(6,V)&=1+V+1+1+(V-1)+V+1&=3V+3 \\ f(7,V)&=1+V+1+1+(V-1)+1+V+1&=3V+4 \\ f(8,V)&=1+V+1+1+(V-1)+1+1+V+1&=3V+5 \\ f(3k-3,V) &=& k \cdot (V + 1) \\ f(3k-2,V) &=& k \cdot (V + 1) + 1 \\ f(3k-1,V) &=& k \cdot (V + 1) + 2 \\ \cdots \end{align}

where the term in the middle represents counterexample which can be proven optimal by the fact that $|A_i|>0$ implies $|A_{i-1}+A_{i}+A_{i+1}| \geq V+1$ and that $A_i$ in the middle are at least of size 1.