# Proving that there infinitely positive integer that are not clean (unique representation)

Solution IMO 2015 (combinatoric shortlist problem )

Problem 6:

Let S be a nonempty set of positive integers. We say that a positive integer n is clean if it has a unique representation as a sum of an odd number of distinct elements from S. Prove that there exist infinitely many positive integers that are not clean

Solution 1.

Define an odd (respectively, even) representation of n to be a representation of n as a sum of an odd (respectively, even) number of distinct elements of S. Let Z > 0 denote the set of all positive integers.

Suppose, to the contrary, that there exist only finitely many positive integers that are not clean. Therefore, there exists a positive integer N such that every integer n > N has exactly one odd representation.

Clearly, S is infinite. We now claim the following properties of odd and even representations.

Property 1.

Any positive integer n has at most one odd and at most one even representation.

Proof. We first show that every integer n has at most one even representation. Since S is infinite, there exists $x\in S$ such that x > max{n, N}. Then, the number n + x must be clean, and x does not appear in any even representation of n. If n has more than one even representation, then we obtain two distinct odd representations of n + x by adding x to the even representations of n, which is impossible. Therefore, n can have at most one even representation.

Similarly, there exist two distinct elements $y,z\in S$ such that y, z > max{n, N}. If n has more than one odd representation, then we obtain two distinct odd representations of n + y + z by adding y and z to the odd representations of n. This is again a contradiction.

Property 2.

Fix $s\in S$. Suppose that a number n > N has no even representation. Then n + 2as has an even representation containing s for all integers $a\geqslant 1$.

Proof. It is sufficient to prove the following statement: If n has no even representation without s, then n + 2s has an even representation containing s (and hence no even representation without s by Property 1).

Notice that the odd representation of n + s does not contain s; otherwise, we have an even representation of n without s. Then, adding s to this odd representation of n + s, we get that n + 2s has an even representation containing s, as desired.

Property 3.

Every suﬃciently large integer has an even representation.

Proof. Fix any $s\in S$, and let r be an arbitrary element in {1, 2,…,2s}. Then, Property 2 implies that the set Zr = {r + 2as; $a\geqslant 0$ } contains at most one number exceeding N with no even representation. Therefore, Zr contains finitely many positive integers with no even representation, and so does $\mathbb{Z}_{>0}=\bigcup _{r=1}^{2s}Z_r$.

In view of Properties 1 and 3, we may assume that N is chosen such that every n > N has exactly one odd and exactly one even representation. In particular, each element s > N of S has an even representation.

Property 4.

For any $s,t\in S$ with N < s < t, the even representation of t contains s.

Proof. Suppose the contrary. Then, s+t has at least two odd representations: one obtained by adding s to the even representation of t and one obtained by adding t to the even representation of s. Since the latter does not contain s, these two odd representations of s + t are distinct, a contradiction.

Let s1 < s2 < … be all the elements of S, and set $\sigma _n=\sum_{i=1}^{n}s_i$

for each nonnegative integer n. Fix an integer k such that sk > N. Then, Property 4 implies that for every i > k the even representation of si contains all the numbers sk, sk+1, … , si-1. Therefore,

where Ri is a sum of some of s1, …, sk-1. In particular, $0\leqslant R_i\leqslant s_1+...+s_{k-1}=\sigma_{k-1}$

Let j0 be an integer satisfying j0 > k and $\sigma_{j0}>2\sigma_{k-1}$. Then (1) shows that, for every j > j0.

Next, let p > j0 be an index such that Rp = mini>j0 Ri. Then,

Therefore, there is no element of S larger than sp but smaller than 2sp. It follows that the even representation t of 2sp does not contain any element larger than sp. On the other hand, inequality (2) yields 2sp > s1 + …+ sp-1, so t must contain a term larger than s. Thus, it must contain sp. After removing sp from t , we have that sp has an odd representation not containing sp, which contradicts Property 1 since sp itself also forms an odd representation of sp.

Also Read : combinatoric shortlist problem in IMO 2015