Show that there exists a permutation satisfying a congruence equation.

Question

The problem was phrased to me as a game theory problem:

Anna and Bob are in a classroom playing a game. Anna starts by writing down ten non-negative integers $a_1,a_2,..., a_{10}$ (not necessarily distinct) on the blackboard. Bob then writes down a permutation of $\{0,1,2,3,4,5,6,7,8,9\}$ and labels this permutation $b_1,...,b_{10}$. Bob wins if, at the end, $$a_1b_1+a_2b_2+\dots + a_{10}b_{10}\equiv 0 \pmod k$$ for some specified $k$ and loses otherwise.

a) Who wins if $k=10$? b) What about $k=9$?

If $k=10$, Anna set all her terms equal to $1$ then $a_1b_1+...+a_{10}b_{10}=0+...+9=45$, hence in this case Bob loses.

Playing around with $k=9$, it seems that Bob can always win. I tried looking probabilistically, but I'm not sure how to interpret $\pmod k$ as an expected value sort of thing. Also, I tried playing with small peturbations (e.g. swapping coefficients and seeing what that did to the product sum), but the effects are largely dependent on the numbers given and do not easily generalize.

Answer 1

For the case of $k = 9$, we can always choose a permutation $b_i$, $1 \le i \le 10$, so the sum is a multiple of $9$. After Anna has chosen the $10$ values of $a_i$, $1 \le i \le 10$, we then 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. We then 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, we will now have

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

We 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$, we 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 we 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 we 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 we 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 we can use a somewhat simpler argument for where $k = p$ instead. On the other hand, 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.

Answer 2

A proof that Bob can always win.

First suppose that there is an ordering of the $a_i$ such that there is a solution, $t$, of the equation $$\sum_1^9a_ii+t\sum_1^9a_i\equiv 0\text{ (mod }9)$$ Choose $b_{10}=0$ and $b_{i}\equiv i+t\text{ (mod }9).$ Then $$\sum_1^{10}a_ib_i\equiv\sum_1^9a_ii+t\sum_1^9a_i\equiv 0\text{ (mod }9).$$

Case 1. If not all the $a_i$ are equal modulo $3$ then we can order the $a_i$ so $\sum_1^9a_i$ is not divisible by $3$ and therefore the equation for $t$ can be solved.

Case 2. If all the $a_i$ are equal modulo $3$ then, since the sum of the $b_i$ is divisible by $9$, we can subtract the same number from all the $a_i$ without affecting sums modulo $9$. We can therefore suppose, without loss of generality, that all the $a_i$ are in $\{0,3,6\}$. If all the $a_i$ are equal then an arbitrary choice of the $b_i$ works. Otherwise, we can order the $a_i$ so $\sum_1^9a_i$ is not divisible by $9$ and therefore the equation for $t$ can, again, be solved.