# 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

Also Read:

**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 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 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 . Suppose that a number n > N has no even representation. Then n + 2as has an even representation containing s for all integers .

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 , and let r be an arbitrary element in {1, 2,…,2s}. Then, Property 2 implies that the set Z_{r} = {r + 2as; } contains at most one number exceeding N with no even representation. Therefore, Z_{r} contains finitely many positive integers with no even representation, and so does .

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 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 s_{1} < s_{2} < … be all the elements of S, and set

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

where R_{i} is a sum of some of s_{1}, …, s_{k-1}. In particular,

Let j_{0} be an integer satisfying j_{0} > k and . Then (1) shows that, for every j > j_{0}.

Next, let p > j_{0} be an index such that R_{p} = min_{i>j0} R_{i. }Then,

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

**Also Read : combinatoric shortlist problem in IMO 2015**