The soccer splitting problem in arbitrary ring

176 Views Asked by At

There's a folklore problem:

Let $x_1, \cdots, x_{23} \in \mathbb{Z}$ be the weights of $23$ soccer players. Now Master Yoda want's to form two soccer teams with $11$ players each. Turns out for any $1 \leq i \leq 23$, one can partition $\{1, \cdots, 23 \} - \{ i \}$ into two disjont sets $A, B$ with $|A| = |B| = 11$ such that $\displaystyle \sum_{k \in A} x_k = \sum_{k \in B} x_k$. Prove that all numbers must be equal.

The solution is well known and is not very hard for $\mathbb{Z}$.

I'm wondering replacing $\mathbb{Z}$ by which commutative ring with unit $R$ makes the problem false.

If $R = \mathbb{Q}$, then it's also same as $\mathbb{Z}$ (and the answer is affirmative), just multiply everything by the LCM of the numerators to reduce it to the case $R = \mathbb{Z}$.

If $R = \mathbb{R}$, then also the problem is true, but you need a lemma by Dirichlet (which is proven by PHP) to reduce it to the case $R = \mathbb{Z}$.

If $R = \mathbb{C}$, then also the problem is true. Because if $\displaystyle \sum_{k \in A} z_k = \sum_{k \in B} z_k \Rightarrow \sum_{k \in A} \text{Re}(z_k) = \sum_{k \in B} \text{Re}(z_k)$, and by the previous one $R = \mathbb{R}$ applied to the real components, you get $\text{Re}(z_i) = \text{Re}(z_j)$ for all $i, j$. Similarly you prove the imaginary componenets are same, so all numbers are same.

If $R = \mathbb{Q}[x], \mathbb{C}[x], \mathbb{R}[x], M_{m,n}(\mathbb{Q}), M_{m,n}(\mathbb{Z}), M_{m,n}(\mathbb{C}), M_{m,n}(\mathbb{R}) $, even then the problem is true since you can look at the problem "component wise" and reduce it to the above cases.

However I have no idea whether the problem is true when $R = \mathbb{Z}_p$ for some prime $p$ or in some other rings. Is it true for all rings, or are there some rings for which this problem doesn't hold ? If it's false for some rings, are there any characterizations for such rings ?

2

There are 2 best solutions below

3
On

So I think $\mathbb{Z}_3$ provides a counterexample. If you choose the weights of the players as 12 x 1 and 11 x -1 it breaks.

Proof.: You can only make two choices as to what gets taken away.

Case 1) the player left out has weight 1. Then you get $11 \times 1$ and $11 \times -1$. Choosing a split of $10$ players with weight $1$ and one with weight $-1$ and $10$ players with weight $-1$ and one with weight $1$, gives $(9\times 1)+ 1+(-1)=0+0$ and $(9 \times -1)+(-1)+1=0+0$.

Case 2) the player left out has weight -1. Then you get $12 \times 1$ and $10 \times -1$. But than you can split them evenly into $6\times 1$ and $5\times -1$ on each side.

Edit: so turns out you can come up with a much easier counterexample which works for all $\mathbb{Z}_k$ where $k\leq 11$ and odd.

Choose the weights to be $23-k$ times $0$ and $k$ times $a\neq 0$. Then if you leave out a $0$ weight players then all the $a$ weight players on the same team have weight $ka=0$ and if you leave out an $a$ weight player you put $(k-1)/2$ $a$-weight players on each team.

Edit 2: Ok so if you specify only ring with unit then you're out of luck with a bound. There exist arbitrarily large rings where counterexamples exist. Namely all rings of the form $\mathbb{Z}_{pk}$ where $p\leq 11$ is odd and $k>1$ is arbitrary. The counterexample then is $23-p$ zeroes and $p$ many $k$'s. The argument is the same as in edit 1. Choose a $0$ and you make a team of $p$ $k$'s padded with zeroes, choose $k$ and you have even number of $k$'s to split between the two teams.

Obviously this type of (large) example goes away if you require not a ring but an integral domain.

7
On

I couldn't write this in the comment but $Z_{13}$ provides another counterexample: Eight 1s, one 5, and fourteen 0s. Similarly for $Z_{17}$ take ten 1's, one 7, and twelve 0s.