56th International Mathematical Olympiad Shortlisted Problems

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 ${\mathbb{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⩾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,\dots ,2s\}$. Then, Property 2 implies that the set $Z_r=\{r+2as:a⩾0\}$ 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 ${\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 $s_1<s_2<\cdots$ 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 $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},\dots ,s_{i-1}$. Therefore, $$\begin{array}{c}{s}_i=s_k+s_{k+1}+\cdots +s_{i-1}+R_i={\sigma }_{i-1}-{\sigma }_{k-1}+R_i\end{array}\text{\hspace{1em}(1)}$$ where $R_i$ is a sum of some of $s_1,\dots ,s_{k-1}$. In particular, $0⩽R_i⩽s_1+\cdots +s_{k-1}={\sigma }_{k-1}$.

Let $j_0$ be an integer satisfying $j_0>k$ and ${\sigma }_{j_0}>2{\sigma }_{k-1}$. Then (1) shows that, for every $j>j_0$, $$\begin{array}{c}{s}_{j+1}⩾{\sigma }_j-{\sigma }_{k-1}>{\sigma }_j/2\end{array}\text{\hspace{1em}(2)}$$ Next, let $p>j_0$ be an index such that $R_p={\min }_{i>j_0}{R}_i$. Then, $$s_{p+1}=s_k+s_{k+1}+\cdots +s_p+R_{p+1}=(s_p-R_p)+s_p+R_{p+1}⩾2s_p.$$ Therefore, there is no element of $S$ larger than $s_p$ but smaller than $2s_p$. It follows that the even representation $\tau$ of $2s_p$ does not contain any element larger than $s_p$. On the other hand, inequality (2) yields $2s_p>s_1+\cdots +s_{p-1}$, so $\tau$ must contain a term larger than $s_{p-1}$. Thus, it must contain $s_p$. After removing $s_p$ from $\tau$, 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$.

---

Alternative solution.

We will also use Property 1 from Solution 1.

We first define some terminology and notations used in this solution. Let ${\mathbb{Z}}_{⩾0}$ denote the set of all nonnegative integers. All sums mentioned are regarded as sums of distinct elements of $S$. Moreover, a sum is called even or odd depending on the parity of the number of terms in it. All closed or open intervals refer to sets of all integers inside them, e.g., $[a,b]=\{x\in \mathbb{Z}:a⩽x⩽b\}$.

Again, let $s_1<s_2<\cdots$ be all elements of $S$, and denote ${\sigma }_n={\sum }_{i=1}^n{s}_i$ for each positive integer $n$. Let $O_n$ (respectively, $E_n$) be the set of numbers representable as an odd (respectively, even) sum of elements of $\{s_1,\dots ,s_n\}$. Set $E={\bigcup }_{n=1}^{\infty }{E}_n$ and $O={\bigcup }_{n=1}^{\infty }{O}_n$. We assume that $0\in E_n$ since 0 is representable as a sum of 0 terms.

We now proceed to our proof. Assume, to the contrary, that there exist only finitely many positive integers that are not clean and denote the number of non-clean positive integers by $m-1$. Clearly, $S$ is infinite. By Property 1 from Solution 1, every positive integer $n$ has at most one odd and at most one even representation.

Step 1. We estimate $s_{n+1}$ and ${\sigma }_{n+1}$.

Upper bounds: Property 1 yields $|O_n|=|E_n|=2^{n-1}$, so $|[1,2^{n-1}+m]\setminus O_n|⩾m$. Hence, there exists a clean integer $x_n\in [1,2^{n-1}+m]\setminus O_n$. The definition of $O_n$ then yields that the odd representation of $x_n$ contains a term larger than $s_n$. Therefore, $s_{n+1}⩽x_n⩽2^{n-1}+m$ for every positive integer $n$. Moreover, since $s_1$ is the smallest clean number, we get ${\sigma }_1=s_1⩽m$. Then, $${\sigma }_{n+1}=\sum _{i=2}^{n+1}{s}_i+s_1⩽\sum _{i=2}^{n+1}(2^{i-2}+m)+m=2^n-1+(n+1)m$$ for every positive integer $n$. Notice that this estimate also holds for $n=0$.

Lower bounds: Since $O_{n+1}\subseteq [1,{\sigma }_{n+1}]$, we have ${\sigma }_{n+1}⩾|O_{n+1}|=2^n$ for all positive integers $n$. Then, $$s_{n+1}={\sigma }_{n+1}-{\sigma }_n⩾2^n-(2^{n-1}-1+nm)=2^{n-1}+1-nm$$ for every positive integer $n$.

Combining the above inequalities, we have $$\begin{array}{c}{2}^{n-1}+1-nm⩽s_{n+1}⩽2^{n-1}+m\text{ and }{2}^n⩽{\sigma }_{n+1}⩽2^n-1+(n+1)m,\end{array}\text{\hspace{1em}(3)}$$ for every positive integer $n$.

Step 2. We prove Property 3 from Solution 1.

For every integer $x$ and set of integers $Y$, define $x\pm Y=\{x\pm y:y\in Y\}$.

In view of Property 1, we get $$E_{n+1}=E_n\bigsqcup (s_{n+1}+O_n)\text{ and }{O}_{n+1}=O_n\bigsqcup (s_{n+1}+E_n)$$ where $\bigsqcup$ denotes the disjoint union operator. Notice also that $s_{n+2}⩾2^n+1-(n+1)m>2^{n-1}-1+nm⩾{\sigma }_n$ for every sufficiently large $n$. We now claim the following.

Claim 1. $\left({\sigma }_n-s_{n+1},s_{n+2}-s_{n+1}\right)\subseteq E_n$ for every sufficiently large $n$.

Proof. For sufficiently large $n$, all elements of $\left({\sigma }_n,s_{n+2}\right)$ are clean. Clearly, the elements of $\left({\sigma }_n,s_{n+2}\right)$ can be in neither $O_n$ nor $O\setminus O_{n+1}$. So, $\left({\sigma }_n,s_{n+2}\right)\subseteq O_{n+1}\setminus O_n=s_{n+1}+E_n$, which yields the claim.

Now, Claim 1 together with inequalities (3) implies that, for all sufficiently large $n$, $$E\supseteq E_n\supseteq \left({\sigma }_n-s_{n+1},s_{n+2}-s_{n+1}\right)\supseteq \left(2nm,2^{n-1}-(n+2)m\right)$$ This easily yields that ${\mathbb{Z}}_{⩾0}\setminus E$ is also finite. Since ${\mathbb{Z}}_{⩾0}\setminus O$ is also finite, by Property 1, there exists a positive integer $N$ such that every integer $n>N$ has exactly one even and one odd representation.

Step 3. We investigate the structures of $E_n$ and $O_n$.

Suppose that $z\in E_{2n}$. Since $z$ can be represented as an even sum using $\{s_1,s_2,\dots ,s_{2n}\}$, so can its complement ${\sigma }_{2n}-z$. Thus, we get $E_{2n}={\sigma }_{2n}-E_{2n}$. Similarly, we have $$\begin{array}{c}{E}_{2n}={\sigma }_{2n}-E_{2n},O_{2n}={\sigma }_{2n}-O_{2n},E_{2n+1}={\sigma }_{2n+1}-O_{2n+1},O_{2n+1}={\sigma }_{2n+1}-E_{2n+1}\end{array}\text{\hspace{1em}(4)}$$

Claim 2. For every sufficiently large $n$, we have $$[0,{\sigma }_n]\supseteq O_n\supseteq (N,{\sigma }_n-N)\text{ and }[0,{\sigma }_n]\supseteq E_n\supseteq (N,{\sigma }_n-N)$$

Proof. Clearly $O_n,E_n\subseteq [0,{\sigma }_n]$ for every positive integer $n$. We now prove $O_n,E_n\supseteq (N,{\sigma }_n-N)$. Taking $n$ sufficiently large, we may assume that $s_{n+1}⩾2^{n-1}+1-nm>\frac{1}{2}(2^{n-1}-1+nm)⩾{\sigma }_n/2$. Therefore, the odd representation of every element of $(N,{\sigma }_n/2]$ cannot contain a term larger than $s_n$. Thus, $(N,{\sigma }_n/2]\subseteq O_n$. Similarly, since $s_{n+1}+s_1>{\sigma }_n/2$, we also have $(N,{\sigma }_n/2]\subseteq E_n$. Equations (4) then yield that, for sufficiently large $n$, the interval $(N,{\sigma }_n-N)$ is a subset of both $O_n$ and $E_n$, as desired.

Step 4. We obtain a final contradiction.

Notice that $0\in {\mathbb{Z}}_{⩾0}\setminus O$ and $1\in {\mathbb{Z}}_{⩾0}\setminus E$. Therefore, the sets ${\mathbb{Z}}_{⩾0}\setminus O$ and ${\mathbb{Z}}_{⩾0}\setminus E$ are nonempty. Denote $o=\max ({\mathbb{Z}}_{⩾0}\setminus O)$ and $e=\max ({\mathbb{Z}}_{⩾0}\setminus E)$. Observe also that $e,o⩽N$.

Taking $k$ sufficiently large, we may assume that ${\sigma }_{2k}>2N$ and that Claim 2 holds for all $n⩾2k$. Due to (4) and Claim 2, we have that ${\sigma }_{2k}-e$ is the minimal number greater than $N$ which is not in $E_{2k}$, i.e., ${\sigma }_{2k}-e=s_{2k+1}+s_1$. Similarly, $${\sigma }_{2k}-o=s_{2k+1},{\sigma }_{2k+1}-e=s_{2k+2},\text{ and }{\sigma }_{2k+1}-o=s_{2k+2}+s_1.$$ Therefore, we have $$\begin{array}{rl}{s}_1& =(s_{2k+1}+s_1)-s_{2k+1}=({\sigma }_{2k}-e)-({\sigma }_{2k}-o)=o-e\\ & =({\sigma }_{2k+1}-e)-({\sigma }_{2k+1}-o)=s_{2k+2}-(s_{2k+2}+s_1)=-s_1\end{array}$$ which is impossible since $s_1>0$.