Pigeonhole principle based algorithm

Question

I was trying to solve this problem. http://olympiads.hbcse.tifr.res.in/olympiads/wp-content/uploads/2016/09/inmosol-15.pdf

INMO-2015 P6. From a set of $11$ square integers, show that one can choose $6$ numbers $a^2, b^2, c^2, d^2, e^2, f^2$ such that $a^2 + b^2 + c^2 \equiv d^2 + e^2 + f^2 \mod 12$.

I came up with the following solution.

---

We note that there are 4 distinct residues modulo $12$, namely $\{0,1,4,9\}$.

LEMMA:

Among any 5 squares we can find a pair that is congruent modulo 12. Since there are atmost 4 unique residues mod 12, by the Pigeonhole Principle we must have two squares with the same residue.

---

We describe the following algorithm for finding $a,b,c,d,e,f$.

1. Label the set of given 11 squares $\mathbf{Z}=\{Z_1,Z_2,Z_3\ldots\}$ and let $\mathbf{R}=\{\},\mathbf{L}=\{\}$.
2. Consider the set of the last 5 elements. Among these elements, we may choose two elements with the same residue. Put one of these in $\mathbf{R}$ and the other in $\mathbf{L}$
3. Remove the elements from $\mathbf{Z}$.
4. Repeat step 2 two more times. We can do this because each step removes two elements, and we need remove only 6 elements so at each step we still have 5 elements to work with.

In fact by my count, we can do this one more time and end up with 4 integers in $\mathbf{R},\mathbf{L}$ each.

---

My issues

1. Is an algorithm a valid proof style?
2. If it is, any tips on writing it better?
3. Is the 4th integer possible?

Thanks in advance!

Answer 1

1. Your argument is correct and nice.

2. I would generalize it: "Let $S$ be a finite set. Let $d$ and $k$ be two nonnegative integers. Let $\sim$ be an equivalence relation on $S$ such that there are at most $d$ equivalence classes with respect to $\sim$. Assume that $\left|S\right| \geq d + 2k-1$. Then, we can find $2k$ distinct elements $s_1, s_2, \ldots, s_k, t_1, t_2, \ldots, t_k$ of $S$ such that $s_1 \sim t_1$, $s_2 \sim t_2$, ..., $s_k \sim t_k$." Now that you have turned the $k$ into a proper variable, you can do induction over $k$; this gives a clearer writeup than the algorithm (but of course is just a recursive rewording of the latter).

3. Yes, because $11 \geq 4 + 2 \cdot 4 - 1$. Note that introducing a $4$-th integer into the original problem does not make it stronger, because $a^2 + b^2 + c^2 + d^2 \equiv e^2 + f^2 + g^2 + h^2 \mod 12$ does not imply $a^2 + b^2 + c^2 \equiv e^2 + f^2 + g^2 \mod 12$. Only once you have strengthened $a^2 + b^2 + c^2 \equiv e^2 + f^2 + g^2 \mod 12$ to $a \equiv e \mod 12,\ b \equiv f \mod 12,\ c \equiv g\mod 12$ does the $4$-th integer become an obvious boon.

Answer 2

Once you know where you are going you can rewrite the proof to be cleaner and crisper.

Point 1: As there are only $4$ distinct square residues $\mod 12$ ($0^2\equiv 6^2\equiv 0; 1^2\equiv5^2 \equiv 7^2 \equiv 11^2\equiv 1; 2^2\equiv 4^2 \equiv 8^2 \equiv 10^2 \equiv 4; 3^2\equiv 9^2 \equiv 9$) then

Point 2: Given any group of $5$ or more integers at least $2$ when squared will belong to the same residue (one of four possible residues) by the pigeon hole principal.

Point 3: Of the eleven integers we can label and sort them as $\{x_{11},x_{10}, x_9, .... , x_1\}$ so that $x_{11}$ and $x_{10}$ are selected from $\{x_{11},x_{10}, x_9, .... , x_1\}$, which has more than $5$, so that $x_{11}^2 \equiv x_{10}^2\mod 12$. And so long as $2m + 1\ge 5$ (i.e. $m \ge 2$), $x_{2m+1}$ and $x_{2m}$ are chosen from $\{x_{2m+1} ,...., x_1\}$ so that $x_{2m+1}^2 \equiv x_{2m}^2 \mod 12$.

Conclusion: So for $m=2,3,4,5$ we have $x_{2m+1}^2 \equiv x_{2m}^2$ and therefore:

$x_4^2 + x_6^2 + x_8^2 \equiv x_5^2 + x_7^2 + x_9^2$;

$x_4^2 + x_6^2 + x_8^2+x_{10}^2 \equiv x_5^2 + x_7^2 + x_9^2+x_{10}^2$