Team selection tests 2021

For each integer $x$, let $[x]$ denote the remainder of $x$ divided by $p$. For each subset $X$ of $\mathbb{Z}$ and integers $a,b$, denote $$aX+b:=\{[ax+b]\mid x\in X\}.$$ Every integer is coprime with $p$, has an inverse modulo $p$, therefore, if $a$ is coprime with $p$, it's easy to verify that $X$ is special if and only if $aX+b$ is special. Our solution is based on the following lemmas.

Lemma 1. The set $S$ of $n\ge 3$ natural numbers that are at most $\frac{p}{3}$ is special.

Proof. Let $i,j$ be the two largest numbers and $k$ be the smallest in $S$. Choose $c=i+j-k>0$, therefore, for any triple $(x,y,z)\in S^3$ with distinct elements, we have $$0\ge x-y+z-c>-\frac{p}{3}-c>-\frac{p}{3}-\frac{2p}{3}=-p.$$ Hence, $$p\mid x-y+z-c⟺x-y+z=c⟺\{x,z\}=\{i,j\}\text{ and }y=k.$$

Lemma 2. If $p>5.6^{n-2}$, for any set $S$ of $n\ge 3$ natural numbers, there exists integers $a,b$, where $a$ is coprime with $p$, such that all elements of $aS+b$ is at most $\frac{p}{3}$.

Proof. Assume that $0\in S$, since we can choose arbitrary integer $b_0$ such that $0\in S+b_0$. For each $i\in \mathbb{Z}$, let $S_i=\left[\frac{pi}{6},\frac{p(i+1)}{6}\right)\cap \mathbb{Z}$.

Consider $S$ as a $n-1$-tuple $(x_1,x_2,\dots ,x_{n-1})$, where $x_i\in S$ and $x_i\ne 0$. Each integer $a$ corresponds to $n-2$-tuple $(a_1,a_2,\dots ,a_{n-2})$, where $a_i$ is the index $k$ such that $[a{x}_i]\in S_k$. By Pigeonhole principle, there exists the set $A$ with 6 integers $a$, corresponding to the same $n-2$-tuple. By the same argument, there exist $a_1,a_2\in A$ such that $$[a_1{x}_{n-1}]-[a_2{x}_{n-1}]\in \left(-\frac{p}{6},\frac{p}{6}\right).$$ Choose $a=a_1-a_2$, then $[ax]\in \left[0,\frac{p}{6}\right)\cup \left(\frac{5p}{6},p\right)$ for all $x\in S$. It's easy to verify that if $b=\lfloor \frac{p}{6}\rfloor$ then $aS+b\subset \left[0,\frac{p}{3}\right]$. Since $p>6^{n-1}-2^n+1$ then $p\ge 6^{n-1}-2^n+3>5.6^{n-2}$, holds for all integer $n\ge 3$. Hence, our proof is completed. $\square$