Problem A. 856. (May 2023)

A. 856. In a rock-paper-scissors round robin tournament any two contestants play against each other ten times in a row. Each contestant has a favourite strategy, which is a fixed sequence of ten hands (for example, RRSPPRSPPS), which they play against all other contestants. At the end of the tournament it turned out that every player won at least one hand (out of the ten) against any other player.

Prove that at most \(\displaystyle 1024\) contestants participated in the tournament.

Submitted by Dávid Matolcsi, Budapest

(7 pont)

Deadline expired on June 12, 2023.

Let us assign mod 3 remainders 0, 1 and 2 to rock, paper and scissors, respectively.

For every player \(\displaystyle A\) let us define polynomial \(\displaystyle p_A(x_1,x_2,\ldots,x_{10})\) over \(\displaystyle \mathbb{Z}_3\). If player \(\displaystyle A\) plays sequence \(\displaystyle a_1,a_2, \ldots,a_{10}\), then

\(\displaystyle p_A(x_1,\ldots,x_{10})=\prod_{i=1}^{10} (x_i-a_i-1).\)

Observe at this point that \(\displaystyle p_A(a_1,\ldots,a_{10})=(-1)^{10}=1\), which will be useful later.

For sequence \(\displaystyle b_1, \ldots,b_{10}\) of an arbitrary player \(\displaystyle B\) we know that there exists \(\displaystyle i\) for which \(\displaystyle b_i\equiv a_i+1\) mod \(\displaystyle 3\), thus (don't forget that we are working modulo 3)

\(\displaystyle p_A(b_1,\ldots,b_n)=0.\)

Now we will prove that these polynomial are linearly independent over \(\displaystyle \mathbb{Z}_3\). Suppose that we have a linear combination that results in the constant 0 polynomial:

\(\displaystyle c_1p_{A_1}+c_2p_{A_2}+\ldots+c_np_{A_n}=0.\)

Substituting player \(\displaystyle A_k\)'s sequence into this all terms will be 0, except for the \(\displaystyle k^{\text{th}}\), which will be \(\displaystyle c_k\), thus, \(\displaystyle c_k=0\) (for all \(\displaystyle k\)). This proves our claim.

Now observe that our polynomials are contained in the linear space generated by those monoms which contains each variable at most once. The number of such monoms is \(\displaystyle 2^{10}\), and they are clearly linearly independent from each other, thus this is the dimension of this linear space. Since we cannot have more linearly independent vectors in a linear space than the dimension of the space, we have finished our proof.

—

Note: This proof comes from the 1992 paper Aart Blokhuis: On the Sperner Capacity of the Cyclic Triangle.

Statistics:

0 student sent a solution.

Problems in Mathematics of KöMaL, May 2023