Integers $1,2, ...,2n$ are arbitrarily assigned to boxes labeled with numbers $1, 2,..., 2n$. Now, we add the number assigned to the box to the number on the box label. Show that two such sums give the same remainder modulo $2n$.
Problem
Source: JBMO 2008 Shortlist C3
Tags: JBMO, combinatorics, remainder
10.08.2018 21:58
Assume the contrary. Then all the remainders from 0 to $2n-1$ appear exactly once as a sum. Thus the sum of these sums equals $ 1+2+...+2n \equiv n$ modulo $2n$ However the sum of the numbers on the box labels and the sum of the assigned numbers equals $2(1+2+...+2n) = 2n(2n+1) \equiv 0$ modulo $2n.$ Therefore we have reached a contradiction.
12.03.2024 21:41
It is worth noting that the statement is not true if the number of boxes is odd. Indeed, if in boxes with labels $1$, $2$, $\ldots$, $k$ we put respectively the numbers $1$, $2$, $\ldots$, $k$, then for odd $k$ the remainders upon division by $k$ of the sums would be $2$, $4$, $\ldots$, $k-1$, $1$, $3$, $\ldots$, $k-2$, $0$. Another (from a large variety) example is to put $2$, $3$, $\ldots$, $k$, $1$, and in this case the remainders are $3$, $5$, $\ldots$, $0$, $2$, $4$, $\ldots$, $1$.
27.12.2024 22:17
FTSOC, assume all remainders from $0$ to $2n-1$ appear exactly once. Then the sum of the labels plus number assigned to them would be $2n(2n+1)$. However, this must be equal to $0+1+2+....+2n-1$ which is $(2n-1)n$. Hence the two quantities must be equal which is clearly a contradiction.
29.12.2024 20:28
Let the numbers assigned to the boxes be $1, 2, \dots, 2n$. Assume that all the sums are distinct mod 2n. Then we have $$1+2+\dots+2n \equiv n(2n+1) \equiv n \not\equiv 0 \equiv a_1 + a_2 + \dots + a_{2n} + 1 + 2 + \dots + 2n \pmod{2n},$$contradiction.
29.12.2024 20:33
o ye so if they were all diff then the total sum would be 1+2+...+2n=2n(2n+1)/2=n(2n+1)=n mod 2n but the total sum of sums is actually 2n(2n+1)=0 mod 2n therefore they are not all diff