Does there exist an integer $ n > 1$ which satisfies the following condition? The set of positive integers can be partitioned into $ n$ nonempty subsets, such that an arbitrary sum of $ n - 1$ integers, one taken from each of any $ n - 1$ of the subsets, lies in the remaining subset.
Problem
Source: IMO Shortlist 1995, N7
Tags: combinatorics, partition, Additive combinatorics, Additive Number Theory, IMO Shortlist
13.08.2008 02:21
27.07.2011 01:55
03.08.2011 06:57
Am I missing something? Proof sketch:
07.10.2019 12:48
First, assuming there exists such a n with sets $A_1,A_2,A_3,...,A_n$ with set $A_1$ containing elements $a_{11},a_{12},a_{13},...$, $a_{11}<a_{12}<a_{13}<...$, $A_2$ with elements $a_{21}<a_{22}<a_{23}<...$, and so on with $A_n$ having elements $a_{n1}<a_{n2}<a_{n3}<...$. First observe, that if such a partition exists, then each set must contain infinitely many numbers- if, for example set $A_i$ contains finitely numbers with largest number $t$, then just choose the number $t+1$ from the remaining $n-1$ sets and then arbitrarily choose elements from the rest of the $n-2$ sets to get a contradiction. Now consider the sum $S_1=a_{11}+a_{21}+a_{31}+...+a_{n1}$. Notice that $S-a_{11}$ must belong to set $A_1$. Moreover, now consider the set $A_i$ such that $a_{i2}-a_{i1}$ has the least value. Also notice that $a_{i2}-a_{i1} \leq n$. Clearly $S+(a_{i2}-a_{i1})-a_{11}$ must belong to $A_1$. Furthermore, as there was nothing special about choosing $A_1$, we repeat the process with all $A_j$, $1 \leq j \leq n$, getting $S+(a_{i2}-a_{i1})-a_{j1}$ must belong to $A_j$. Now we replace the sum $S_1$ by $S_2=S_1+a_{i2}-a_{i1}$ to generate new numbers in each set- we now again consider $S_2+a_{i3}-a_{i2}$ for a new $i$ such that $a_{i3}-a_{i2}$ is minimum, thus $S_2+a_{i3}-a_{i2}+a_{j1}$ belongs to $A_j$. Now we keep going down "rows" of $A_j$, tweaking $S$ wherever $a_{jt}-a_{j(t+1)}$ is minimum for the $t$ which is not covered- clearly, as $a_{jt}-a_{j(t+1)}$ will always be $\leq n$, thus the elements must become eventually periodic with period $n$- if not, then elements will start to overlap $=>$ Contradiction. Thus, our sets must become divided into modular classes eventually- clearly this can't work as this will require $0+1+2+...+(n-1) -k \equiv k \pmod{n} => n(n-1) \equiv 4k \pmod{n}$ for all $k$. As both $n=2$ (obviously) and $n=4$ ($1+2+3 \not \equiv 0 \pmod{4}$) don't work, and we're done.