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 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 sufficiently 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

×

Like us on Facebook

%d bloggers like this: