Show that there exists a permutation satisfying a congruence equation.

Solution 1:

You can always choose a permutation $b_i$, $1 \le i \le 10$, for the case of $k = 9$, so the sum is a multiple of $9$. After Anna has chosen the $10$ values of $a_i$, $1 \le i \le 10$, then you have

$$\sum_{i=1}^{10}a_i \equiv m \pmod 9, \; 0 \le m \le 8 \tag{1}\label{eq1A}$$

Check if there's any $1 \le j \le 10$ such that

$$m - a_j \equiv n \pmod 9, \; n \not\equiv 0 \pmod 3 \tag{2}\label{eq2A}$$

There are $2$ cases to consider of whether or not there is such a $j$.

Case 1:

There is such a $j$. Have $b_j = 9$, and initially let the other $9$ permutations be in any order. Then you get

$$\sum_{i=1}^{10}a_i b_i \equiv q \pmod 9, \; 0 \le q \le 8 \tag{3}\label{eq3A}$$

If $q \equiv 0 \pmod 9$, then we're done. Otherwise, consider "rotating" the permutation values of each $b_i$, with $1 \le i \le 10$ and $i \ne j$, so each permutation value increases by $1$, but with $8$ going to $0$ instead of $9$. Call this new permutation $b_i^{'}$. This will cause, modulo $9$, the equivalent of adding all the $a_i$ except for $a_j$ to the sum. This addition, as indicated from \eqref{eq2A}, is equivalent to adding $n$ modulo $9$. Thus, you will now have

$$\sum_{i=1}^{10}a_i b_i^{'} \equiv q + n \pmod 9 \tag{4}\label{eq4A}$$

You can repeat this procedure $r$ times so the sum would then be equivalent to $q + rn \pmod 9$. Consider the modulo equation

$$q + rn \equiv 0 \pmod 9 \tag{5}\label{eq5A}$$

Since $\gcd(n,9) = 1$, then $n$ has a multiplicative inverse modulo $9$, i.e., there's a $1 \le s \le 8$ such that $ns \equiv 1 \pmod 9$. Thus, \eqref{eq5A} can be solved for $r$ by

$$rn \equiv -q \pmod 9 \implies r \equiv -(n^{-1})q \equiv -sq \pmod 9 \tag{6}\label{eq6A}$$

Using this $r$ number of "rotations" will then cause the sum to be a multiple of $9$.

Case 2:

There's no such $j$ which satisfies \eqref{eq2A}. This means that for some $0 \le t \le 2$, you have $a_i \equiv t \pmod 3, \; 1 \le i \le 10$. Now, consider $2$ sub-cases. The first sub-case is where there's no $j$ such that $m - a_j \not\equiv 0 \pmod 9$. This can occur only if all $a_i$ are equivalent to each other modulo $9$. In that situation, any permutation of $b_i$ will work.

The second sub-case is where there is a $j$ such that $m - a_j \equiv 3 \pmod 9$ or $m - a_j \equiv 6 \pmod 9$. In this situation, do as before and choose $b_j = 9$ and have the permutations be in any order so you get \eqref{eq3A} again. However, in this case, $q$ is a multiple of $3$, i.e., it's $0$, $3$ or $6$. This is because all $a_i \equiv t \pmod 3$ and $\sum_{i=0}^{8}i = 36 \equiv 0 \pmod 3$. Now, if $q$ is $0$ in \eqref{eq3A}, we're done. Otherwise, if it's $3$, then if $n = 3$, apply the permutation values "rotation" as before twice, else if $n = 6$, apply it just once. Similarly, if $q = 6$, then if $n = 3$, apply the "rotation" once, else apply it twice.

This shows you can also always determine a permutation in this case such that the sum will be a multiple of $9$. In summary, regardless of which integers (non-negative or otherwise) Anna picks, there's always a permutation that Bob can choose which will allow him to win.

Note you can also show that Bob can always win in more general cases such as where the number of integers, call it $u$, is $1$ more than $k$, with $k = p^2$ for any odd prime $p$, plus you can use a somewhat simpler argument for where $k = p$ instead. For prime $p = 2$ giving $k = p^2 = 4$ or $k = p = 2$, Anna can choose all $a_i \equiv 1 \pmod k, \; 1 \le i \le u$ to have Bob always lose.