not all sufficiently large integers are clean

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

not all sufficiently large integers are clean

G H J

Reveal topic tags

IMO Shortlist

combinatorics

Additive combinatorics

G H BBookmark kLocked kLocked NReply

Source: 2015 IMO Shortlist C6, Original 2015 IMO #6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ABCDE

1963 posts

ABCDE

#1 h Jul 7, 2016, 7:48 PM • 9 Y

Y by skyletter, muffin_cowee, ValidName, lifeisgood03, yayitsme, jhu08, Kobayashi, Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by ABCDE, Jul 7, 2016, 7:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6870 posts

v_Enhance

#2 h Jul 7, 2016, 7:53 PM • 17 Y

Y by test20, angiland, jmenks, ValidName, mathroyal, v4913, Pascal96, jhu08, megarnie, centslordm, Kobayashi, HamstPan38825, mathleticguyyy, Adventure10, Mango247, bhan2025, Ritwin

Define an odd (resp even) representation to be a sum of an odd (resp even) number of distinct elements of $S$ . Assume all sufficiently large $n$ are clean (have exactly one odd representation).

Of course, $|S| = \infty$ .

Lemma: All sufficiently large integers have exactly one even representation.
Proof: Suppose all $n \ge N$ are clean. Then all $n \ge N$ have at most one even representation; if not, then $n+s$ would not be clean for any $s > n$ , $s \in S$ .

Now we show every element has at least one even representation. Fix an element $s \in S$ . Assume that $n \ge N$ has no even representations. Then:
$\bullet$ Note $n+s = a_1 + \dots + a_{2k-1}$ is clean, and its odd representation cannot contain $s$ by hypothesis.
$\bullet$ Thus $n+2s = (n+s)+s = a_1 + \dots + a_{2k+1} + s$ has a (unique) even representation containing $s$ .
$\bullet$ Next $n+3s = (n+2s) + s$ is clean. Its odd representation cannot contain $s$ , because otherwise we would get an even representation of $n+2s$ not containing $s$ . So we put $n+3s = b_1 + \dots + b_{2j+1}$ .
$\bullet$ Then $n+4s = b_1 + \dots + b_{2j+1} + s$ has a (unique) even representation, and so on.
Now looking at residue classes modulo $2s$ , we deduce the claim, since in any particular residue class every sufficiently large integer has a unique even representation. $\square$

In light of this, let $S = \{s_1 < s_2 < \dots\}$ , and consider the infinite product $\prod_{i \ge 1} (1 - x^{s_i})$ which converges as a formal series (in the combinatorial sense). Since every sufficiently large integer has exactly one even and one odd representation, it follows that it must converge to some finite polynomial. One can then obtain a contradiction by taking $x \to 1^-$ , though the details require significant care.

This post has been edited 1 time. Last edited by v_Enhance, Jul 7, 2016, 8:41 PM
Reason: hyperlink details

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

test20

988 posts

test20

#3 h Jul 7, 2016, 8:16 PM • 2 Y

Y by Kingsbane2139, Adventure10

That's a very beautiful problem.
It mixes number theoretic, algebraic and combinatorial ingredients.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

angiland

364 posts

angiland

#4 h Jul 8, 2016, 3:04 AM • 3 Y

Y by ThE-dArK-lOrD, Adventure10, Mango247

v_Enhance wrote:

Since every sufficiently large integer has exactly one even and one odd representation, it follows that it must converge to some finite polynomial. One can then obtain a contradiction by taking $x \to 1^-$ , though the details require significant care.

Is the following correct? Since every large integer has two representations, the infinite product converges absolutely for $|x| < 1$ . Taking natural log, we have for any $|x| < 1$ that
$\sum_{i} \ln (1-x^{s_i}) = \ln (p(x)),$ where the LHS converges uniformly. Next we take derivatives and obtain
$\sum_{i} \frac{s_i \cdot x^{s_i - 1}}{1-x^{s_i}} = \frac{-p'(x)}{p(x)}.$ Again equality is justified because the partial sums on the LHS are uniformly convergent. Letting $x \to 1-$ , we see that $p(x)$ must be divisible by $1-x$ . Thus we must have
$\sum_{i} \frac{s_i \cdot x^{s_i - 1}}{1-x^{s_i}} = \frac{u(x)}{(1-x)v(x)},$ where $u, v$ are polynomials not divisible by $1-x$ . Multiplying both sides by $1-x$ , we conclude that
$\sum_{i} \frac{s_i \cdot x^{s_i - 1}}{1+ x + \cdots + x^{s_i-1}} = \frac{u(x)}{v(x)}.$ But this is impossible because the LHS is arbitrarily large as $x \to 1-$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6870 posts

v_Enhance

#5 h Jul 8, 2016, 3:51 PM • 6 Y

Y by ThE-dArK-lOrD, v4913, megarnie, HamstPan38825, Diorite, Adventure10

I'm a non-expert on this and may be wrong, but the basic trouble is that you're treating a formal series (which is just a formal sequence of coefficients) as a functional series (which allows you to substitute values of $x$ ). These are different types of objects and there is widespread confusion about the distinction between them.

The notions of limit do not coincide when transferring from one type of series to the other. As a trivial example, $\lim_{N \to \infty} (1 - x^N) = 1$ holds as formal series, but you run into obvious problems if you try to substitute $x=1$ .

When we write $P(x) = \prod_{j \ge 1} (1 - x^{s_j})$ we really mean $\lim_{N \to \infty} \prod_{j=1}^N (1 - x^{s_j}) = P(x)$ , where the limit is as formal series. This does not admit any interpretation as "functions in $x$ ", so you have trouble in the very first line: when you say "the infinite product converges for certain $x$ ", you've changed the type of $\prod_{j \ge 1} ( 1 - x^{s_j} )$ from a formal series to a functional series, thus breaking the limit.

In other words, to deal with convergence issues correctly, you have to either (a) do an argument that *only* involves the coefficients, as Qiaochu does in this math.SE answer, or (b) demonstrate some sort of result that limits are preserved when changing from a formal series to a functional series. I'm not aware of any results of the latter form.

I'll probably write up a full blog post explaining all this in more detail, since the issues at hand are extremely subtle.

This post has been edited 1 time. Last edited by v_Enhance, Jul 8, 2016, 3:51 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

angiland

364 posts

angiland

#6 h Jul 8, 2016, 4:52 PM • 3 Y

Y by v_Enhance, Adventure10, Mango247

v_Enhance wrote:

When we write $P(x) = \prod_{j \ge 1} (1 - x^{s_j})$ we really mean $\lim_{N \to \infty} \prod_{j=1}^N (1 - x^{s_j}) = P(x)$ , where the limit is as formal series. This does not admit any interpretation as "functions in $x$ ", so you have trouble in the very first line: when you say "the infinite product converges for certain $x$ ", you've changed the type of $\prod_{j \ge 1} ( 1 - x^{s_j} )$ from a formal series to a functional series, thus breaking the limit.

This is a legitimate concern, so I should elaborate more. The formal series identity gives $\prod_{j=1}^{N} (1 - x^{s_j}) = P(x) + Q_N(x)$ , where $Q_N(x)$ has coefficients in $\{-1, 0, 1\}$ and its lowest degree goes to infinity with $N$ (because each large integer has exactly one even and one odd representation). Thus for any $|x| < 1$ , $Q_N(x) \to 0$ as $N \to \infty$ . This way we obtain the functional series identity.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6870 posts

v_Enhance

#7 h Jul 8, 2016, 8:05 PM • 3 Y

Y by v4913, HamstPan38825, Adventure10

Yes, with that comment made it looks fine to me: we're here using the key fact that the partial products have coefficients eventually supported on $\pm 1$ . Nice.

This post has been edited 1 time. Last edited by v_Enhance, Jul 8, 2016, 8:06 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

angiland

364 posts

angiland

#8 h Jul 8, 2016, 8:57 PM • 2 Y

Y by Adventure10, Mango247

True. But even if these coefficients are not bounded, they are sub-exponential (e.g. by the Hardy-Ramanujan asymptotic result for the partition function). Then the same argument goes through.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DVDthe1st

340 posts

DVDthe1st

#10 h Jul 17, 2016, 2:53 PM • 3 Y

Y by Imayormaynotknowcalculus, Adventure10, Mango247

Alright, whose question is this? Own up please

But seriously, I offer my sincere congratulations to the proposer. This would have been an amazing problem 6 if not for the administrative lapse (and also very much aligned with the latest trend of hybrid-subject, multi-approach problems like 2016 Q3).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rterte

209 posts

rterte

#11 h Dec 27, 2016, 11:25 AM • 2 Y

Y by Adventure10, Mango247

What if $S=\mathbb{Z}^+$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6870 posts

v_Enhance

#12 h Dec 27, 2016, 4:48 PM • 3 Y

Y by v4913, HamstPan38825, Adventure10

rterte wrote:

What if $S=\mathbb{Z}^+$ ?

ABCDE wrote:

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$ .

So no contradiction --- every integer $n \ge 6$ has multiple representations, for example $n$ and $(n-3)+2+1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bern-1-16-4-13

28 posts

bern-1-16-4-13

#13 h Jan 22, 2017, 4:52 PM • 3 Y

Y by danepale, Adventure10, Mango247

Here is a very elementary approach to this problem, also easy to understand graphically.
Let's suppose for the sake of contraddiction that there is $S$ such that there exists $k$ which is the last not clean number.

Lemma $1$ : each number $n$ has at most one even representation and at most one odd representation. Infact if it had two even representations then let's take $a\in S$ such that $a>k\wedge a>n$ ( $a$ exists because $S$ must be an infinite set), so the number $a+n$ has two odd representations and it's greater than $k$ , contraddiction. Similarly if $n$ had two odd representation then let's take $\left\{a,b\right\}\subset S$ such that $a,b>k\wedge a,b>n$ , so the number $a+b+n$ has two odd representation and it's greater than $k$ , contraddiction.

Now let's defiine $A_1=S\cap\left\{1,...,k\right\}$ .
Let's define two binary strings (we will call them $O_1$ and $E_1$ ) with lenght $2+\sum_{i\in A_1}i$ : string $O_1$ will have a $1$ in the $j$ -th position iff we can obtain the number $j-1$ as sum of an odd number of elements of $A$ ; string $E_1$ will have $1$ in the $j$ -th position iff we can obtain the number $j-1$ as sum of an even number of elements of $A_1$ (in particular $O_1$ has a $0$ in $k+1$ position, $O_1$ starts with $0$ , $E_1$ starts with $1$ and both strings end with $0$ ). Now let's suppose that $r+1>k+1$ is the first position containing a $0$ after the $k+1$ -th position, then $r$ is the minimum of the set $S\setminus A_1$ (this follows by the lemma $1$ and by how we defined $k$ ). So we can define the set $A_2=S\cap\left\{1,...,r\right\}=A_1\cup\left\{r\right\}$ . Let's also define strings $O_2$ , $E_2$ in the same way we defined $O_1$ and $E_1$ (considering $A_2$ instead of $A_1$ ). Then it's easy to see that we can obtain $O_2$ by overlapping $O_1$ and $E_1$ in such a way that the $r+1$ -th position of $O_1$ coincides with the first position of $E_1$ , instead $E_2$ can be obtained overlapping $O_1$ and $E_1$ in such a way that the $r+1$ -th position of $E_1$ coincides with the first position of $O_1$ . In general let's define $A_{t}=A_{t-1}\cup\left\{l\right\}$ where $l+1$ is the first position containing a $0$ after the $k+1$ -th position in $O_{t-1}$ . The string $O_t$ will contain $1$ in the generic $j$ -th position iff we can obtain the number $j-1$ as sum of an odd number of elements of $A_t$ . The string $E_t$ will contain $1$ in the generic $j$ -th position iff we can obtain the number $j-1$ as sum of an even number of elements of $A_t$ . Besides the definitions of $O_t$ and $E_t$ are equivalent to the following: $O_t$ is obtained overlapping $O_{t-1}$ and $E_{t-1}$ in such a way that the $l+1$ -th position of $O_{t-1}$ coincides with the first position of $E_{t-1}$ ; $E_t$ is obtained overlapping $O_{t-1}$ and $E_{t-1}$ in such a way that the $l+1$ -th position of $E_{t-1}$ coincides with the first position of $O_{t-1}$ .

By the lemma $1$ we can say that $O_{t}$ and $E_{t}$ are binary strings for all $t$ .

Lemma $2$ : if in $O_1$ there are at most $x$ consecutive $0$ s and in $E_1$ there are at most $y$ consecutive $0$ s, then in $O_t$ and in $E_t$ there will be no more than $x+y-1$ consecutive $0$ s, for all $t$ .
I don't demonstrate this lemma because it's quite easy.

Lemma $3$ : in $O_t$ with $t\ge 2$ the positions $k+2,...,k+t$ are all filled by the digit $1$ .
This simply and directly follows by how we recursively defined $O_t$ and by the fact that the strings of type $E$ start with $1$ .

Lemma $4$ : if $t\ge x+y+1$ then when we overlap $O_t$ and $E_t$ to obtain $O_{t+1}$ and $E_{t+1}$ , the lenght of the overlapped part will be no more than $k+x+y$ .
This follows by lemma $3$ , lemma $2$ and lemma $1$ . I won't formalize it but the main idea is that by lemma $3$ since $t\ge x+y+1$ , in $O_t$ the positions $k+2,...,k+x+y+1$ are filled with the digit $1$ , so when we overlap $O_t$ and $E_t$ to obtain $E_{t+1}$ , this block of $x+y$ consecutive $1$ s must be placed at the right of the last $1$ in $E_t$ , in order not to contraddict lemma $1$ (it would be contraddicted because of lemma $2$ ).

Lemma $5$ : if $t\ge x+y+1$ , then neither $O_t$ nor $E_t$ will contain $0$ s between the $k+x+y$ -th position from left and the $k+x+y$ -th position from right, extremes excluded (we'll call this interval of positions "internal zone").
Case $1$ . If there was a $0$ in the internal zone of $O_t$ then by lemma $4$ also $O_{t+1},O_{t+2},...$ will contain that $0$ in that position, contraddiction with the definition of $k$ .
Case $2$ . If there was a $0$ in the internal zone of $E_t$ , then by lemma $4$ when we overlap $O_t$ and $E_t$ to obtain $O_{t+1}$ this $0$ will become a $0$ in the internal zone of $O_{t+1}$ , and this is the case $1$ .

Now we are almost done. Let $t\ge x+y+1$ . Let's call right part of $O_t$ (abbreviated $RO_t$ ) its right extremity which starts with the first $0$ after the internal zone of $O_t$ . The left part of $O_t$ (abbreviated $LO_t$ ) will be its left extremity which ends with the last $0$ before the internal zone of $O_t$ . $RE_t$ and $LE_t$ are defined similarly.
By lemma $5$ we can say that when we overlap $O_t$ and $E_t$ to obtain $O_{t+1}$ , $RO_t$ and $LE_t$ must fit perfectly (each $0$ of $RO_t$ must be overlapped with a $1$ of $E_t$ , and each $0$ of $LE_t$ must be overlapped with a $1$ of $O_t$ ). Similarly when we overlap $O_t$ and $E_t$ to obtain $E_{t+1}$ , $LO_t$ and $RE_t$ must fit perfectly. So if $LO_t$ starts with exactly $a\ge 1$ digits $0$ , if $RE_t$ has lenght $q$ , then the lenght of the overlapped part will be $a+q$ . Besides since the lenght of the overlapped part must be the same whether when we compose $O_{t+1}$ , or when we compose $E_{t+1}$ , then if $RO_t$ has lenght $p$ , since $E_t$ doesn't start with $0$ , the lenght of the overlapped part will be $p$ , so $p=a+q$ .
Now, since $LO_t$ is also $LO_{t+1}$ , since $RO_t$ becomes $RE_{t+1}$ and $RE_t$ becomes $RO_{t+1}$ , we can repeat the same reasoning when we overlap $O_{t+1}$ and $E_{t+1}$ composing $O_{t+2}$ and $E_{t+2}$ , arriving to obtain the equality $q=a+p$ . But since we already got $p=a+q$ , we must have $a=0$ , contraddiction, because as we said at the beginning, strings of type $O$ always starts with at least one $0$ .

This post has been edited 1 time. Last edited by bern-1-16-4-13, Jan 23, 2017, 6:40 AM
Reason: I defined $p$ and $q$ in the correct way

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dgrozev

2459 posts

dgrozev

#14 h Apr 2, 2017, 4:56 PM • 2 Y

Y by Adventure10, Mango247

The same idea as in post #2 by v_Enhance, but in order to avoid technical issues connected with the infinite product, we take $\prod_{i =1}^{n} (1 - x^{s_i})$ .
That's, let us assume such set $S = \{s_1 < s_2 < \dots\}$ exists and all positive integers greater than $N$ are clean. The plan is to take $P_n(x) := \prod_{i =1}^{n} (1 - x^{s_i})$ , where $x\in (0,1)$ , then to set $y=1-x$ , hence $y\in (0,1)$ and to estimate this product when $y$ is close to $0$ .

Using the Bernulli's inequality, $(1-y)^{s_i}\geq 1-s_i y$ we get $(1 - (1-y)^{s_i})\leq s_i y$ , and:
$(*)\,\,\,\,\,\,\,\,P_n(y)=\prod_{i =1}^{n} (1 - y^{s_i}) \leq \left(\prod_{i=1}^n s_i\right) y^{n}$ On the other hand:
$(**)\,\,\,\,\,\,\,\, P_n(y) =Q_N(y)+ \sum_{i=m}^M \varepsilon_i y^i$ where $Q_N$ is a polynomial of degree $N$ , $m =s_n, M=s_1+\dots +s_n$ and $\varepsilon_i\in \{-1,0,1\}$ .

Let $Q_N(y)=y^k Q^*(y)$ , where $Q^*(0)=C > 0$ . By $(**)$ and providing $0<y<1/2$ it easily follows:
$P_n(y) \geq Q_N(y) - 2y^n =y^k Q^*(y)-2y^n$ For small enough $y$ , it yields
$P_n(y)\geq \frac{C}{2}y^k-2y^n\geq \frac{C}{2}y^N-2y^n$
Taking into account $(*)$ , we get:
$\left(\prod_{i=1}^n s_i\right) y^{n} \geq \frac{C}{2}y^N-2y^n$ Since $n>N$ , plugging $y>0$ small enough, we get a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lifeisgood03

388 posts

lifeisgood03

#15 h Aug 16, 2018, 8:52 PM • 7 Y

Y by Delray, MelonGirl, mijail, mathroyal, Infinityfun, Adventure10, Mango247

Absolutely gorgeous problem! Here is an elementary, purely combinatorial solution, by myself and Delray:

We assume for the sake of contradiction that there are finitely many unclean numbers. Note that this means there exists a maximum unclean number.

Let's order the elements of $S$ , such that $a_i$ is the ith element of $S$ in increasing order.

1. $S$ is infinite

Proof: Assume otherwise. Now all numbers $x>\sum_{i\in S} i$ are unclean, contradiction. $\square$

Define an odd representation of a number $n$ to be a set of S such that the sum of the elements in the set is $n$ and there is an even number of elements in the set. Define an even representation likewise.

2. A number cannot have two distinct odd or even representations.

Proof: If $n$ has two distinct odd representations, it is unclean. Now, consider any $a_i$ and $a_j$ not in either representation of $n$ . By (1), there are infinitely many such pairs, and we have that $n+a_i+a_j$ is unclean for each of these pairs. For even, this is the same logic except we only add one number instead of two. $\square$

3. There exists a number after which all subsequent numbers have an even representation.

Proof: Consider an number $n$ that doesn't have an even representation, but is clean. Then, we have that the odd representation of $n+a_i$ doesn't contain $a_i$ , because if it did that would mean $n$ has an even representation. Then an even representation for $n+2a_i$ would be $a_i$ plus the odd representation for $n+a_i$ .

We can continue this process to get that $n+2ka_i$ must have an even representation for all positive integers $k$ , which proves the statement, as we can find an infinite string of numbers that have an even representation for each residue modulo $2a_i$ . $\square$

Now that we have (3), we know there exists a number $m$ after which all numbers have a unique even and odd representation. Let $n_o$ denote the set corresponding to the odd representation of $n$ , and likewise for $n_e$ . Let $a_k$ denote the smallest element of $S$ such that $a_k>m$

4. If $a_i>a_j>m$ , then $\{a_j\}\subset (a_i)_e$

Proof: Assume otherwise. Then we have $\{a_i\}\cup(a_j)_e$ and $\{a_j\}\cup (a_i)_e$ are two distinct odd representations for $a_i+a_j$ , contradiction.

This means we can say $a_i=a_{i-1}+a_{i-2}+\dots+a_k+\epsilon_i$ for $i>k$ , where $\epsilon_i$ is a finite sum of numbers in $S$ less than $a_k$ . $\square$

5. There exists infinitely many $i$ such that $a_{i+1}\ge 2a_i$

Proof: Note that $(2a_i)_e=(a_i)_e\cup \{a_i\}$ , so we have $2a_i=a_i+a_{i-1}+a_{i-2}+\dots+a_k+\epsilon_i$

But we also have $a_{i+1}=a_i+a_{i-1}+a_{i-2}+\dots+a_k+\epsilon_{i+1}$

If there exists a point after which there doesn't exist $i$ such that $a_{i+1}\ge 2a_i$ , $\epsilon_i$ is a strictly decreasing sequence. However, this is clearly impossible as $m$ is finite. $\square$

6. Magic.

Consider $x$ such that $a_{x+1}\ge 2a_x$ , and $a_x>\sum_{i=1}^{k-1} a_i$ . The even representation for $2a_x$ cannot contain $a_x$ ; that would imply there would be two distinct odd representations for $a_x$ .

Thus, we have the maximum element in $(2a_x)_e$ is less than $a_x$ . However, we clearly have

$2a_x=a_x+a_{x-1}\dots+a_k+\epsilon>\sum_{i=1}^{x-1} a_i$
where the right hand side is the maximum value of a number which has a representation with maximum element less than $a_x$ .

This means it is impossible for $(2a_x)_e$ to have a maximum element less than $a_x$ . But we also know that $a_x$ is not an element of $(2a_x)_e$ , and $2a_x<a_{x+1}$ , which means $2a_x$ has no even representation.

This is a contradiction, so we are done!

$\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Contradiction

62 posts

Contradiction

#16 h Feb 9, 2020, 3:13 PM • 4 Y

Y by for63434, mathroyal, Adventure10, Mango247

I have a different approach to this problem. I hope it is correct enough.

Assume the contrary, there exists $N$ so that every positive integer larger than it is uniquely expressed in odd terms of $S$ .
We define the following matrix-coefficient polynomial.
$X(S)=\prod_{s\in S}^{}\left(I+\begin{bmatrix} 1&-1\\1&-1 \end{bmatrix} x^s \right)$ where $I$ is the $2\times 2$ identity matrix and let $A=\begin{bmatrix} 1&-1\\1&-1 \end{bmatrix}$ .

Then it easy to see that $A^2=O$ . So if you expand the terms out, only the expression of an integer with distinct odd number of $S$ 's elements survive. Furthermore, the odd-number-of-terms expression is unique, so the coefficient of $x^n$ for $n>N$ is all $A$ . which leads to the following.
$\prod_{s\in S}^{}\begin{bmatrix} 1+x^s & -x^s \\ x^s& -1+x^s \end{bmatrix}= \begin{bmatrix} f(x) & g(x) \\ h(x)& t(x) \end{bmatrix} +\begin{bmatrix} 1& -1 \\ 1& -1\end{bmatrix}\{ x^N+x^{N+1}+\cdots \}$ where $f,g,h,t$ are all polynomials that have degree less than $N$
Now note that this equation holds for all real $x$ , and we take the determinant on both sides.

Since determinants are multiplicative, we get: $\prod_{s\in S}^{}\left(-1+2x^{2s}\right)=\left(f(x)+\frac{x^N}{1-x}\right)\left(t(x)-\frac{x^N}{1-x}\right)-\left(g(x)-\frac{x^N}{1-x}\right)\left(h(x)+\frac{x^N}{1-x}\right)$

Expanding, the right hand becomes $f(x)t(x)-g(x)h(x)+\frac{x^N}{1-x}\left(t(x)-f(x)-g(x)+h(x)\right)$ and the coefficients of this polynomial is bounded (since $f,g,h,t$ are all polynomials with bounded degree) while the coefficients of the polynomial in the left hand side isn't. This leads to a contradiction

This post has been edited 2 times. Last edited by Contradiction, Feb 10, 2020, 2:52 AM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SnowPanda

186 posts

SnowPanda

#17 h May 19, 2020, 1:03 AM • 1 Y

Y by mathroyal

Solution?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#18 h Jan 4, 2021, 11:27 AM • 1 Y

Y by mathhotspot

Clearly the problem is true if $S$ is finite, so let $S=\{x_1<x_2<\cdots\}$ . Suppose for the sake of contradiction that there exists $N$ such that $n\ge N$ implies that $n$ has a unique odd representation.

Claim: There exists $M\ge N$ such that $n\ge M$ implies that $n$ has a unique even representation.

Proof: First note that every $n$ has at most one even representation - if not, then for $i$ such that $x_i\ge N$ , we see that $n+x_i$ has two odd representations, a contradiction.

Let $A$ be the set of numbers at least $N$ whose unique odd representation includes $x_1$ , and let $B$ be the set of numbers at least $N$ whose unique odd representation does not include $x_1$ . Note that $A\sqcup B = \{N,N+1,N+2,\ldots,\}.$ We see that all numbers in $A-x_1$ have an even representation, and the representation does not include $x_1$ , and all numbers in $B+x_1$ have an even representation, and the representation includes $x_1$ . This means all the former representations are distinct from the latter, and since no even number has two representations, we have $(A-x_1+\cap (B+x_1)=\emptyset$ .

Now, for any $T>N$ $|(A-x_1)\cap[N,T]|\ge |A\cap[N+x_1,T+x_1]|\ge |A\cap[N+x_1,T-x_1]|$ and $|(B+x_1)\cap[N,T]|\ge |B\cap[N-x_1,T-x_1]|\ge |B\cap[N+x_1,T-x_1]|,$ so $|((A-x_1)\sqcup(B+x_1))\cap[N,T]|\ge |(A\sqcup B)\cap[N+x_1,T-x_1]| = T-N-2x_1+1.$ So if arbitrarily large $n$ don't have an even representation, then $T-N+1-|((A-x_1)\sqcup(B+x_1))\cap[N,T]|$ should grow arbitrarily large as $T$ increases, which we saw was not the case. Therefore, every arbitrarily large $n$ has an even representation. We showed above that this representation is unique, so the claim is proved. $\blacksquare$

This in fact implies that every $n\ge M$ can be represented as sums of distinct elements of $S$ in exactly two ways. We now use this to pin down the structure of $S$ .

Lemma: We have $x_{i+1}=2x_i$ for all large enough $i$ .

Proof: Note that $x_i\le x_1+\cdots x_{i-1}$ simply because $x_i$ must have another representation besides $\{x_i\}$ . We now claim $x_{i+1}\ge x_i+M$ . Indeed, if not, then $x_{i+1}-M<x_i\le x_1+\cdots+x_{i-1},$ so any representation of $x_{i+1}-M$ cannot contain only $x_1,\ldots,x_{i-1}$ , so must contain $x_i$ , which can't happen as $x_{i+1}-M<x_i$ . Thus, $x_{i+1}-M$ has no representation, so is less than $M$ , which is a contradiction for large enough $i$ .

Now, suppose that $x_{i+1}-x_i<x_i$ . Then, since $x_{i+1}-x_i\ge M$ , it has two unique representations, each containing numbers at most $x_{i-1}$ . Thus, by adding on $x_i$ to these, we have two representations of $x_{i+1}$ besides just $\{x_{i+1}\}$ , which is a contradiction. Therefore, $x_{i+1}\ge 2x_i$ .

We now have that for sufficiently large $i$ , $2x_i\le x_{i+1}\le x_1+\cdots+x_i.$ Let $d_i = (x_1+\cdots+x_i)-2x_i$ denote the gap in this bound. We see that $d_{i+1}\le d_i\iff x_{i+1}\ge 2x_i$ , which is true, so $d_{i+1}\le d_i$ . Thus, $d_i\ge d_{i+1}\ge d_{i+2}\ge\cdots$ , so eventually this stabilizes at $d_i=d$ for large enough $i$ . We now see $d_{i+1}=d_i$ implies $x_{i+1}=2x_i$ , so this is true for large enough $i$ , as desired. $\blacksquare$

This implies that $S = A\sqcup\{x,2x,4x,\ldots\}$ for some finite set $A$ and positive integer $x$ . Now focus on $n=kx$ for large enough positive integers $k$ . There is an odd representation of $n$ given by $\{kx\}$ , and since there is exactly one even representation, there is exactly one subset $B\subseteq A$ of even size such that $x\mid\Sigma(B)$ . The even representation of $kx$ is given by writing $k-\Sigma(B)/x$ in binary. However, we can choose $k$ large enough so that $k-\Sigma(B)/x$ has an odd number of binary digits, thus making the second representation of $kx$ actually have odd size, a contradiction. This completes the solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheUltimate123

1740 posts

TheUltimate123

#19 h Aug 18, 2021, 3:29 AM • 2 Y

Y by PHSH, bhan2025

Of course we assume $S=\{s_1<s_2<\cdots\}$ is infinite. Say an odd representation of a number is a representation as a sum of an odd number of distinct elements of $S$ , and an even representation is a representation with an even number of elements of $S$ . Assume for contradiction there is an integer $N$ such that all $n\ge N$ have a unique odd representation.

Claim: Every positive integer has at most one odd representation and at most one even representation.

Proof. If $n$ has two representations of the same parity, add arbitrarily large elements of $S$ to both representations to produce arbitrarily large numbers with two odd representations. $\blacksquare$

Claim: There is an integer $N'\ge N$ such that all $n\ge N'$ have a unique even representation.

Proof. For each $m\ge N$ , suppose $m$ does not have an even representation. Then:

the odd representation of $m+s_1$ does not contain $s_1$ , else $m$ would have an even representation;
$m+2s_1$ has an even representation containing $s_1$ , by adding $s_1$ to the above;
the odd representation of $m+3s_1$ does not contain $s_1$ , else $m+2s_1$ would have two odd representations;
$m+4s_1$ has an even representation containing $s_1$ , by adding $s_1$ to the above;
and so on.

Thus for each $m\ge N$ without an even representation, all of $m+2s_1$ , $m+4s_1$ , $m+6s_1$ , $\ldots$ have even representations, so each of the $2s_1$ residue classes modulo $2s_1$ have at most one number $\ge N$ without an even representation. This proves the claim. $\blacksquare$

Claim: For sufficiently large $k$ , we have $s_{k+1}\ge2s_k$ .

Proof. If we had $N'\le s_{k+1}-s_k<s_k$ , then $s_{k+1}=s_k+(s_{k+1}-s_k)$ has two representations of both parity, so if $s_{k+1}-s_k<s_k$ we must have $s_{k+1}-s_k<N'$ .

But then if $k$ is large enough so that $s_k\ge2N'$ , then $s_{k+1}+N'=s_k+(s_{k+1}-s_k+N')$ has two representations of both parity since $s_{k+1}-s_k+N<2N'\le s_k$ . $\blacksquare$

Claim: For sufficiently large $k$ , we have $s_{k+1}=2s_k$ .

Proof. Consider $a_r=(s_1+s_2+\cdots+s_{r-1})-s_r$ for each $r$ . For large $r$ we have $a_r\ge0$ , since if $s_1+s_2+\cdots+s_{r-1}<s_r$ then $s_r$ only has one representation. But also $a_{r+1}\le(s_1+\cdots+s_r)-2s_r=a_r,$ so $(a_r)$ is eventually constant.

From here, if $a_k=a_{k+1}$ then $s_{k+1}=s_1+\cdots+s_k-a_{k+1}=s_k+(s_1+\cdots+s_{k-1}-a_k)=2s_k$ as needed. $\blacksquare$

It is easy to finish from here: we must have $S=S'\sqcup\{n,2n,4n,\ldots\}$ for some $n$ .

Now for large $\ell$ , the odd representation of $2^\ell n$ is $\{2^\ell n\}$ . Let $T$ be the subset of $S'$ appearing in the even representation, so that the sum of the elements of $T$ is $tn$ . Then $2^\ell-t$ has an odd number of nonzero binary digits.

But each $2^kn$ with $k\ge\ell$ has an even representation for which the terms in $S'$ appearing in the even representation are exactly $T$ . It then follows that $2^k-t$ has an odd number of nonzero binary digits for all $k\ge\ell$ . This is a clear contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

InvertedDiabloNemesisXD

6 posts

InvertedDiabloNemesisXD

#20 h Sep 2, 2021, 9:57 PM • 3 Y

Y by thepsserby, Danie1, SK_pi3145

@alexiaslexia this one for you my drillah.
\documentclass{article}
\usepackage[utf8]{inputenc}

\usepackage{amsthm}
\usepackage{amsmath}
\theoremstyle{definition}
\newtheorem{defn}{Definition}[section]
\newtheorem*{defn*}{Definition}
\newtheorem{claim}{Claim}[section]
\newtheorem*{claim*}{Claim}

\title{2015 C6}
\author{InvertedDiabloNemesisXD, \_Danie1}
\date{}
\begin{document}
\maketitle

\section{Solution}

\begin{defn}[Dirty numbers]
We call a number $n$ \emph{dirty} if it can be written as a sum of an odd number of distinct elements from $S$ in more than one way.
\end{defn}

\begin{defn}[Unsmelly numbers]
We call a number $n$ \emph{unsmelly} if it can be written as a sum of an even number of distinct elements from $S$ in a unique way.
\end{defn}

\begin{defn}[Smelly numbers]
We call a number $n$ \emph{smelly} if it can be written as a sum of an even number of distinct elements from $S$ in more than one way.
\end{defn}

\begin{claim}[Infinitude of S]
The set $S$ is unbounded.
\end{claim}

\begin{proof}
Suppose $S$ was bounded. Then $|S|$ is finite, so the sum is bounded, hence any number larger than this sum is not clean.
\end{proof}

\begin{claim}[Recursive breakdown of the problem]
The existence of a single dirty or smelly number implies the existence of infinitely many dirty numbers.
\end{claim}

\begin{proof}
Let $x,y$ be a dirty number and a smelly number respectively. Consider $a,b \in \mathrm{S}$ such that $a,b > x,y$ . Consider $x+a+b$ and $y+a$ . These are both dirty numbers since both $x$ and $y$ have more than one representation.
\end{proof}
\bigskip
\noindent We will now proceed by contradiction. Assume that there are only finitely many numbers that are not clean. Therefore there exists a number $k$ such that for all $n>k$ , $n$ has a unique odd representation.
\bigskip
\begin{claim}[Bounding the density of $S$ ]
If $y$ is in $S$ and is larger than all unclean numbers, then for all $y < z < 2y - x - 1$ , $z \not \in S$ .
\end{claim}
\bigskip
\begin{proof}
Let $x$ denote the largest unclean number. Then note that
$2y - 1 = y + (y - 1) = z + (2y - 1 - z) ,$ hence $2y - 1$ is smelly. By Claim 1.2, this implies the existence of infinitely many unclean integers.
\end{proof}

\noindent Let the elements of $S$ be $z_1 < z_2 < z_2 < \cdots$ . In particular, by Claim 1.3 we have that
$z_{n + 1} > 2z_n - x - 1 .$ Let $f(n) = \sum_{i = 1}^{n - 1} z_n$ . Let $g(n) = f(n) - z_n$ .
\begin{claim}[Unimodality]
$g(n) = \mathcal{O}(n)$ .
\end{claim}
\begin{proof}
Let $x$ be the largest unclean number. We will prove that $g(n + 1) - g(n) < x + 5$ for sufficiently large $n$ , which clearly implies the claim. The proof is pure computation:
$\begin{align*} g(n + 1) - g(n) &= f(n + 1) - f(n) - z_{n + 1} + z_n \\ &= z_n - z_{n + 1} + z_n \\ &< x + 5 \end{align*}$ The claim is proven.
\end{proof}

\begin{claim}
All sufficiently large numbers are unsmelly.
\end{claim}

\begin{proof}
Let $n$ be a large integer. Now note that all numbers greater than $f(n)$ and less than $z_{n + 1}$ must use $z_n$ in their clean representation. Hence all numbers between $f(n) - z_n = g(n)$ and $z_{n + 1} - z_n > z_n - x - 1$ are unsmelly numbers. Since the lower bound is $\mathcal{O}(n)$ and the upper bound is $\Omega(1.69^n)$ we deduce that for sufficiently large numbers, these intervals cover all numbers.
\end{proof}

\bigskip
\noindent \textbf{\LARGE The FINAL Blow}

\bigskip
\noindent Let $x \in S$ be sufficiently large. Claim 1.5 gives us that there exists an even representation of $2x$ . This representation contains $x$ . Removing $x$ , we obtain an odd representation for $x$ that is not just $x$ . Hence, $x$ has at least $2$ odd representations and therefore is a dirty number. By Claim 1.2, there are therefore infinitely dirty numbers and therefore infinitely many numbers that are not clean.

\section{Motivation}
\begin{itemize}
\item Do I even need to say anything about claim 1.1 (I really think it is a pseudo-triviality)... like I thought about it before I even read the whole problem.
\item Motivation for claim 1.2 was like it asks for odd stuff and thats like kinda weird innit. It makes you think why even stuff isnt considering so you'd also like to think about that. Also also sometimes when you want to prove infinite stuff, you like consider trying to make it recursively. So from there, a little bit of deepage gives us claim 1.2.
\item So claim 1.3, it was like basically that APMO problem where it asks you to do the same thing. So it was a solve by recognition.At this point, I was like we're probably half way through the problem and its been pretty trivial so far, maybe like 5-10 MOHS if you've seen the 25-30 MOHS problem thats basically the same as this before.
\item Now we move to the algebruh part of this problem. Nothing too fancy, basically we know what we want and we just do it. Theres quite a few details that stand in the way, but I'm not bad at alg so its not hard.
\item Finally the crux of the problem. Pretty standard stuff. Literally the first thing I thought of.
\item Really obvious Finnish I guess. Like you want stuff you know about and we know about $x$ , so we use $x$ . Simple.
\end{itemize}

\end{document}

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CANBANKAN

1301 posts

CANBANKAN

#21 h Jul 3, 2022, 12:06 AM

Y by

Clearly $S=\{s_1<\cdots\}$ is an infinite set. Call an odd representation the sum of a number as $s_{x_1}+\cdots+s_{x_{2k+1}}$ , and define an even representation similarly. Assume for all sufficiently large integers $n>N$ , $n$ has a unique odd representation.

The main claim is as follows: every sufficiently large number that is not in $S$ has a unique even representation. The key idea now is to force a number with two representations with the same parity,

Clearly, a number $t>2N$ cannot have two even representations, for adding an element of $s\in S, s>2N$ (which exists since $S$ is infinite, or we are clearly done) larger than the number, then $s+t$ has two odd representations.

On the other hand, if $x>2N$ has an odd representation with more than one term $s_{x_1}+\cdots+s_{x_{2k+1}}$ then $x-s_{x_1} > N$ has an even and an odd representation.

Consider $B=s_{w_1}+s_{w_2}=s_{t_1}+\cdots+s_{t_{2k+1}}$ where $w_1, w_2 > N^{N^N}$ . If $\{w_1,w_2\} \cap \{t_1,\cdots,t_{2k+1}\}$ is not empty, we cut the duplicate element. Otherwise, let $M_1=\max\{w_1,w_2\}, M_2=\max\{t_1,\cdots,t_{2k+1}\}$ , then $M_1\ne M_2$

For $1\le j\le 2k+2$ , pick $A_j=s_{N+3j}+s_{N+3j+1}+s_{N+3j+2} = s_{u_1}+\cdots+s_{u_{2m_j}}$
Note the indices in these representations are much smaller than $w_1,w_2,\max\{t_1,\cdots,t_{2k+1}\}$ .

There exists $j$ such that $\{t_1,\cdots,t_{2k+1}\} \cap \{N+3j,N+3j+1, N+3j+2\} = \emptyset$ .

Therefore, consider $A_j+B=s_{w_1}+s_{w_2}+s_{u_1}+\cdots+s_{u_{2m_j}}=s_{N+3j}+s_{N+3j+1}+s_{N+3j+2}+s_{t_1}+s_{t_2}+\cdots+s_{t_{2k+1}}$
Since $u_i<N^{N^N}, \{t_1,\cdots,t_{2k+1}\} \cap \{N+3j, N+3j+1, N+3j+2\}=\emptyset$ , these two are even representations of $A_j+B$ without duplicates. To show they are different representations, note the max index of the first representation is $M_1$ while the max of the second is $M_2$ , and $M_1\ne M_2$ . Thus this number has two different representations of the same parity, absurd!

This post has been edited 3 times. Last edited by CANBANKAN, Jul 3, 2022, 12:32 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

L567

1184 posts

L567

#23 h Nov 9, 2022, 7:01 PM

Y by

This is extremely nice!

First, I claim that every big enough number also has a unique even representation. Clearly, it has at most one (otherwise adding a big enough number of $S$ makes two odd representations), so it suffices to show that it does have one. Fix an element of the sequence, say $\ell$ . For a big enough number $n$ with no even representation, the odd representation of $n + \ell$ cannot contain $\ell$ . This means that adding $\ell$ to this gives an even representation of $n + 2 \ell$ . Now, the odd representation of $n + 3 \ell$ cannot contain $\ell$ because otherwise, we would remove it to get a second even representation of $n + 2 \ell$ . So by induction, we get that all numbers of the form $n + 2k \ell$ have an even representation. Repeating this for $n$ in every residue class mod $2 \ell$ finishes. So assume now that every number at least $M$ has a unique odd and even representation.

Now, assume the terms of $S$ are $a_1, a_2, \cdots$ in increasing order. Let $N$ be sufficiently large and consider $a_{N+1}$ . If it is smaller than $2a_N$ , then write $a_{N+1} = a_n + (a_{N+1} - a_N)$ . If $a_{N+1} - a_N \geqslant M$ , then since it has an even representation and is smaller than $a_N$ , this whole thing is a second odd representation of $a_{N+1}$ , apart from itself. So we must have that $a_{N+1} - a_N$ is smaller than $M$ . But then consider $a_{N+1} + M$ , which is an even representation, but can also be written as $a_N + (a_{N+1} - a_N + M)$ , giving it a second even representation, which is impossible. Therefore, we have $a_{N+1} \geqslant 2a_N$ for all big enough $N$ .

Reindex the elements so that some sufficiently large $a_i$ equals $b_1$ . Then, let $b_{k} = a_{i+k-1}$ and $c_k = b_{k+1} - 2b_{k}$ . By the previous paragraph, $c_i \geqslant 0$ for all $i$ . If the sum of elements before $a_i$ is $S$ , then since we also have that $a_{k+1} \leqslant a_1 + a_2 + \cdots + a_i$ (otherwise that number has only one representation), we get that $c_1 + c_2 + \cdots$ is bounded. This means that eventually, the $c_i$ just become $0$ , so $a_{N+1} = 2a_N$ for all sufficiently large $N$ .

Let $K = a_k$ be the first such $a_N$ , so we have a bunch of "small terms" (say $a_1, a_2, \cdots, a_m$ ) and the "big terms", which are $K, 2K, 4K, \cdots$ . Fix a residue class, then since after the small terms of the representation, the remaining can be written uniquely as the sum of big terms, there must be exactly two subsets of small terms, one with an odd number of terms and one with an even number of terms. Since there are a total of $2^m$ subsets and $K$ residue classes, we must have that $K = 2^{m-1}$ , so all the big terms of the sequence are powers of two.

Let $S'$ be the subset of small terms part of the even representation of a big power of two. Then we have that if their sum is $z$ , then $2^t - z$ has an odd number of digits in binary always (since it uses an odd number of big terms), which is not possible if $t,t+1 >> z$ , a contradiction. Therefore, it is not possible for every sufficiently large number to be clean. So there are infinitely many positive integers that are not clean.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5000 posts

IAmTheHazard

#24 h Oct 3, 2023, 9:02 PM

Y by

Here is a solution with lots of algebra but no generating functions. I'm not entirely sure this is correct.

Suppose otherwise. Let $C$ be the least positive integer such that all $n \geq C$ are clean. Let the elements of $S$ be $a_1<a_2<\cdots$ ; clearly $S$ is infinite. Furthermore, no positive integer can have two same-parity representations, otherwise we can add some (an opposite parity) large elements to both and get a contradiction. We use the following fact.

Lemma: For any $i>j$ and positive integer $k$ , if both $k$ and $k+a_i-a_j$ are clean, then at least one of their representations has to contain $a_i$ or $a_j$ .
Proof: Suppose neither does. Then $k+a_i$ has two different representations as the sum of an even number of elements: one containing $a_i$ , and one containing $a_j$ . Then for some large enough $N$ $k+a_i+a_N$ has two different representations too (formed by appending $a_N$ ) but should be clean: contradiction. $\blacksquare$

This allows us to prove the key size estimate.

Claim 1: We have $a_{i+1} \geq 2a_i-C$ for all $i$ .
Proof: Any number at most $a_i-1$ cannot have $a_i$ or $a_{i+1}$ in any representation. Therefore consider $a_i-1$ and $2a_i-a_{i+1}-1<a_i-1$ . By our lemma this means that one of these should not be representable. Therefore $2a_i-a_{i+1}-1 \leq C-1 \implies a_{i+1} \geq 2a_i-C$ . $\blacksquare$

Let $s_i=a_1+\cdots+a_i$ , with $s_0=0$ . We prove more size estimates.

Claim 2: We have $a_i \geq s_{i-1}-Ci$ for all $i$ .
Proof: Induct on $i$ with base case $i=1$ obvious. Now if the claim is true for $i$ , we have
$a_{i+1} \geq 2a_i-C=a_i+a_i-C \geq a_i+s_{i-1}-C(i+1)=s_i-C(i+1).~\blacksquare$
Claim 3: We have $2^{i-2}-Ci-1 \leq a_i \leq 2^{i-2}+C$ for all $i$ .
Proof: Consider the $2^{i-2}$ sums of an odd number of elements at most $a_{i-1}$ . By the previous result, at most $Ci+1$ of these are at least $a_i$ , so we need $a_i \geq 2^{i-2}-Ci-1$ . For the right inequality, if $a_i>2^{i-2}+C$ then the $2^{i-2}$ sums cannot cover every odd number between $C$ and $a_i-1$ . $\blacksquare$

Using these rather strong inequalities, we can get an even stronger version of claim 1.

Claim 4: For large enough $i$ , we have $a_{i+1} \geq 2a_i+1$ .
Proof: Consider $a_{i+2}>C$ and $a_{i+2}+a_{i+1}-a_i$ and apply the lemma. $a_{i+2}$ should be clean, so this is its unique odd representation. Thus $a_{i+2}+a_{i+1}-a_i$ should contain either $a_i$ or $a_{i+1}$ in its odd representation. This number is asymptotically $(5/4)2^i$ , but $s_{i+1}$ is asymptotically $2^i$ , hence $a_{i+2}+a_{i+1}-a_i$ needs to contain $a_{i+2}$ in any representation. Thus it cannot contain $a_{i+1}$ for size reasons, and if it contains $a_i$ then we require $a_{i+1}-a_i \geq a_i$ . Equality cannot hold, because $a_{i+2}+a_i$ is an even representation.

This final claim implies that $s_{i-1}-a_i$ is strictly decreasing for large enough $i$ , since if $s_{i-1}-a_i=m$ then $a_{i+1}\geq 2a_i+1=a_i+s_{i-1}-m+1=s_i-(m-1)$ , hence $s_i-a_{i+1} \leq m-1$ . On the other hand, for large enough $i$ we should have $s_{i-1} \geq a_i-1$ , else $a_i-1$ has no representation at all and is thus not clean, which is a contradiction. Thus no such $S$ exists. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Oct 10, 2023, 1:45 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blackbluecar

302 posts

blackbluecar

#25 h Jan 30, 2024, 3:30 PM

Y by

Assume for the sake of contradiction that all $k>N$ are clean. Note that $S$ is trivially infinite, and let $S=\{a_1<a_2< \cdots \}$ .

Claim: All sufficiently large $k$ has a unique representation as a sum of an even number of distinct elements from $S$ .

Let $s_M = a_1+a_2+ \cdots +a_{2M-1}$ . Notice that by choosing $M$ large enough, we derive $s_M-k>N \implies s_M-k$ is clean. If $X \subseteq [2M-1]$ is the unique size of odd size satisfying $\sum_{i \in X} a_i = s_M-k$ then $\overline{X} \subseteq [2M-1]$ has even size and obeys $\sum_{i \in \overline{X}} a_i = s_M - \sum_{i \in X} a_i = s_M-(s_M-k) = k$ Now, assume there are two sets $X$ and $Y$ where $\sum_{i \in X} a_i = \sum_{i \in Y} a_i = k$ Trivially, there is some $M$ where $X,Y \in [2M-1]$ . Thus, $\overline{X}$ and $\overline{Y}$ both have oss size and obey $\sum_{i \in \overline{X}} a_i = \sum_{i \in \overline{Y}} a_i = s_M-k>N$ which contradicts the uniqueness of $s_M-k$ being clean. $\square$

Now, consider the generating function $F(x) = \prod_{s \in S} (1-x^s) = c_0 + c_1x + c_2x^2 + \cdots$ If we let $A_m$ denote the number of ways to represent $m$ with the sum of an odd number of $S$ and $B_m$ same for even, our generating function gives $c_m = A_m-B_m$ . Recall that for all sufficiently large $m$ we have $A_m=B_m=1 \implies c_m = A_m-B_m=0$ . Thus, the $c_i$ 's are eventually all $0$ , implying that $F$ is a polynomial.

Let $\varepsilon_n = e^{\frac{2\pi i}{n}} \implies (\varepsilon_n)^n=1$ and $\varepsilon_i \not = \varepsilon_j$ for all $i \not = j$ . Note that for any $s \in S$ we have $F(\varepsilon_s)=0$ since it is divisible by $x^s-1$ . Thus, $F$ has infinitely many distinct roots $\implies F(x)=0$ . But this is trivially false since $F(100) \not = 0$ . $\blacksquare$

This post has been edited 2 times. Last edited by blackbluecar, Jan 30, 2024, 3:31 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomehuman

496 posts

awesomehuman

#26 h Jul 22, 2024, 8:02 PM

Y by

Assume towards a contradiction that all sufficiently high numbers are clean. Note $S$ is infinite.
Say an "odd representation" of $n$ is a subset of elements of $S$ that has an odd number of elements and adds up to $n$ . Define an "even representation" similarly.
Assume toward a contradiction some positive integer has two odd representations or two even representations. Then, take some set $E\subset S$ that is disjoint from both representations such that $|E|$ has opposite parity from the representations. By adding $E$ to both representations, we can get infinitely many numbers with $2$ odd representations, a contradiction.

Let $M$ be a positive integer such that each $n>M$ has an odd representation.

Claim: If $n$ has an odd representation that does not include $k$ , then so does $n+2k$ .
Proof: Then, $n+k$ has an even representation that includes $k$ . If the odd representation of $n+2k$ includes $k$ , we can remove the $k$ to get an even representation of $n+k$ that doesn't include $k$ , a contradiction.

Thus, for each $k$ , for sufficiently high $n$ , whether or not $k$ is in the odd representation of $n$ only depends on $n\pmod{2k}$ .

Claim: All sufficiently high integers have an even representation.
Proof: Consider some $k\in S$ and some sufficiently high $n$ .
Case 1: $n+k$ has $k$ in its odd representation
Remove the $k$ to get an even representation of $n$ .
Case 2: $n+k$ doesn't have $k$ in its odd representation
Then, neither does $n-k$ . So, we can add $k$ to the odd representation of $n-k$ to get an even representation of $k$ .

Let $N$ be a positive integer such that each $n>N$ has an odd representation and an even representation. Let $n>N$ .

Claim: If $n$ has an odd representation that includes $k$ , so does $n+2k$ .
Proof: If $n+k$ has an even representation with $k$ , then $n$ has an odd representation without $k$ , a contradiction. Thus, $n+k$ has an even representation without $k$ . By adding $k$ to it, we get an odd representation of $n+2k$ that includes $k$ .

Therefore, for all $n>N$ , whether or not $k$ is in the odd representation of $n$ only depends on $n\pmod{2k}$ . Similar logic applies if we replace "odd" with "even".

Let $k>N$ . Then, for all $n$ such that $n\equiv k\pmod{2k}$ , $k$ is in the odd representation of $n$ and $k$ is not in the even representation of $n$ . If we add $k$ to the even representation, we get an odd representation of $n+k$ that includes $k$ . Thus, all multiples of $k$ have an odd representation that includes $k$ .

Let $X$ be the set of elements of $S$ that are greater than $N$ . Then, $X$ has the property that for all $x\in X$ , there is no way to add an odd number of other elements of $X$ to get a multiple of $x$ . We claim it is impossible for any infinite set of positive integers to have this property.

Assume WLOG $X$ has some odd element $k$ . By pigeonhole, there is some $m$ such that for infinitely many $n\in X$ , $n\equiv m\pmod{k}$ . Then, we can add $k$ of these numbers to get a multiple of $k$ , a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1727 posts

OronSH

#27 h Sep 14, 2024, 3:39 AM

Y by

uh does this work

Suppose otherwise. Clearly $S$ is infinite. Let $S=\{a_1,a_2,\dots\}$ with $a_i$ a sequence in increasing order. Then construct the zero-indexed sequence $X$ where the $i$ th term in $X$ is the number of representations of $i$ as a sum of an odd number of elements of $S$ , and let $Y$ be the same sequence but as a sum of an even number of elements. We are assuming that $X$ consists of some (minimal) finite string $N$ followed by only ones. Let $N$ have length $n$ .

First $Y$ cannot have numbers greater than one, as if the $i$ th term of $Y$ is $>1$ then the $i+a_j$ th term of $X$ is $>1$ for arbitrarily large $j$ . Likewise, $X$ cannot have numbers greater than one, because now if the $i$ th term of $Y$ is $>1$ then the $i+a_j$ th term of $Y$ is $>1$ for large enough $j$ . In particular, $N$ consists of only zeros and ones, and we may assume that the first and last terms of $N$ are both zeros.

Fix some $k$ so that $a_k>n$ . Define $S_k=\{a_1,a_2,\dots,a_k\}$ and $X_k,Y_k$ similar to $X,Y$ but with $S_k$ instead of $S$ , and truncated past $a_1+\dots+a_k$ . Define $\Sigma_k=1+a_1+a_2+\dots+a_k$ . We know that all sums of subsets with an odd number of elements of $\{a_1,a_2,\dots,a_k\}$ are distinct and between $0$ and $\Sigma_k-1$ inclusive, implying $\Sigma_k\ge2^{k-1}$ .

Additionally, $a_{k+1}$ must equal the index of the first zero in $X_k$ past $N$ , as if it were before, it would overlap and if it were after, the zero would not be filled. In particular the first zero is $\le\Sigma_k$ , so $a_{k+1}\le\Sigma_k$ . This also gives $\Sigma_{k+1}\le2\Sigma_k$ .

When $k$ is even, $j$ is representable by an odd number of $a_i\le a_k$ iff $a_1+a_2+\dots+a_k-j$ is, and similarly for even numbers. When $k$ is odd, the reverse happens. Thus we get that when $k$ is even, $X_k,Y_k$ are palindromes, and when $k$ is odd, $X_k,Y_k$ are reverses of each other.

In particular, consider $k$ even. If $X_k$ is not of the form $N$ followed by ones followed by $N'$ , where $N'$ is the reverse of $N$ , then by symmetry the first zero past $N$ , which is $a_{k+1}$ , is $\le\frac12(a_1+\dots+a_k)<\frac12\Sigma_k$ , so $\Sigma_{k+1}\le\frac32\Sigma_k$ .

However, consider the monovariant $2^{-k}\cdot\Sigma_k$ . We know it is $\ge\frac12$ always, but it is nonincreasing. Additionally, the previous multiples this monovariant by $\frac34$ , so this can only happen a finite number of times. Thus eventually $X_k$ is of the form $N,[1],N'$ where $[1]$ is a string of ones.

Consider a large $k$ odd, and let $X_k$ be of the form $N,[1],P$ for some string $P$ . We know $Y_k$ is of the form $P',[1],N'$ and $Y_{k+1}$ will be the sum of $Y_k$ and $X_k$ translated by $a_{k+1}$ , which is the position of the first element of $P$ in $X_k$ .

Now the key is that the two $[1]$ strings cannot overlap when adding. If the $[1]$ from the translated $X_k$ is entirely before the $[1]$ from $Y_k$ , we have that two copies of $N$ and two copies of $[1]$ are shorter than $P$ . We know $P$ must have length $\Sigma_k-a_{k+1}$ , and $N$ with $[1]$ has length $a_{k+1}$ . This implies $3a_{k+1}\le\Sigma_k$ , or $\Sigma_{k+1}\le\frac43\Sigma_k$ . Again this multiplies our monovariant by $\frac23$ , so this can only happen a finite number of times.

Otherwise the $[1]$ from the translated $X_k$ is entirely after the $[1]$ from $Y_k$ , which implies that two copies of $N$ with one $[1]$ is longer than $P$ with one $[1]$ , so the length of $P$ is $\le 2n$ .

Now we have that $Y_k$ must be of the form $P',[1],N'$ , and $P'$ must be fixed by choosing $a_{k+1}>2n$ . Thus taking arbitrarily large odd $k$ only increases the length of the $[1]$ , so we know that the structure of $Y$ must be $P'$ followed by only ones. Similar to $N$ , we know the last term of $P'$ is zero, since the first term of $P$ was defined to be zero.

Again fixing $k$ odd, we have $X_k$ is of the form $N,[1],P$ and $Y_k$ is of the form $P',[1],N'$ . We know $Y_{k+1}$ must be the sum of $Y_k$ and $X_k$ translated by $a_{k+1}$ . Let $p$ be the length of $P$ . If $p<n$ then the first term of $N'$ , which is zero, is before and thus does not overlap with the translated $X_k$ , creating a zero between the initial $P'$ and final $P$ in the resulting $Y_{k+1}$ , which is impossible since it is before the symmetry line of $Y_{k+1}$ and not reachable by $a_{k+1}$ for large $k$ .

Thus $p\ge n$ . Fix $k$ even, and we have $X_k$ is $N,[1],N'$ and $Y_k$ is $P',[1],P$ . The sum of $X_k$ and $Y_k$ translated by $a_{k+1}$ is $X_{k+1}$ , which is of the form $N,[1],P$ . However, the last term of the $P'$ in the translated $Y_k$ , which is zero, either overlaps the last term of $N'$ from $X_k$ , which is zero, or overlaps nothing. This hole is also not reachable by $a_{k+1}$ for large enough $k$ , so we have a contradiction. We are done.

This post has been edited 1 time. Last edited by OronSH, Sep 14, 2024, 3:49 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

golue3120

54 posts

golue3120

#28 h Nov 10, 2024, 4:53 PM • 3 Y

Y by Leo.Euler, OronSH, peace09

This one is similar in spirit to some previous analytic solutions except that it is short and purely formal.

Suppose for the sake of contradiction that such a set $S=\{s_1,s_2,\dotsc\}$ existed. Note that $S$ must be infinite. Furthermore, every sufficiently large integer can have at most one representation as a sum of an even number of distinct elements of $S$ because if $n$ has two such representations, $n+s$ is not clean for all sufficiently large $s\in S$ .

In terms of generating functions, this means that $\textstyle[x^n]\prod_{s\in S}(1-x^s)$ is $0$ or $-1$ for all sufficiently large $n$ . For any positive integer $k$ , we have $\textstyle(1-x)^{-k}\prod_{s\in S}(1-x^s)=\prod_{i\le k}\frac{1-x^{s_i}}{1-x}\prod_{i>k}(1-x^{s_i})$ . All sufficiently large coefficients of the second product are $0$ , $-1$ , or $1$ , and the first product is a polynomial. hence the coefficients of $\textstyle(1-x)^{-k}\prod_{s\in S}(1-x^s)$ are bounded.

If infinitely many coefficients of $\textstyle\prod_{s\in S}(1-x^s)$ are $-1$ , then the coefficients of $\textstyle(1-x)^{-1}\prod_{s\in S}(1-x^s)$ would be unbounded below, a contradiction. Otherwise, $\textstyle\prod_{s\in S}(1-x^s)$ is a polynomial. Then there exists some integer $k$ such that $(1-x)^k$ does not polynomially divide $\textstyle\prod_{s\in S}(1-x^s)$ . Then the coefficients of $\textstyle(1-x)^{-k-1}\prod_{s\in S}(1-x^s)$ are unbounded, a contradiction.

Thoughts

This post has been edited 1 time. Last edited by golue3120, Nov 10, 2024, 5:42 PM
Reason: \textstyle the products to fix aesthetics

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathfun07

33 posts

mathfun07

#29 h Mar 23, 2025, 10:22 PM

Y by

Not sure if this is correct.

Note $S$ is infinite. Let $T_x$ be the finite subset of the first $x$ elements of $S$ , and let $T_x^{odd}, T_x^{even}$ be the multisets of all odd/even (including 0) sums of numbers from $T_x$ . Let $s_x$ denote the xth smallest term in $S$ .

We can construct sets for $x+1$ from $x$ easily as follows:
- $T_{x+1}^{even} = T_{x}^{even} + \{ s_{x+1} + n : n \in T_{x}^{odd} \}$
- $T_{x+1}^{odd} = T_{x}^{odd} + \{ s_{x+1} + n : n \in T_{x}^{even} \}$
And these sets obviously form subset chains.
Hence for finite $x$ we can inductively form $T_x$ .

Claim: There are no repeats in $T_x^{odd}, T_x^{even}$
Proof: If there exists repeats, then we can easily create infinite non-clean numbers.

There exists some big $M$ such that eventually every $m \geq M$ is clean: it's eventually in $T_{x}^{odd}$ for some large $x$ . Now choose big enough $x$ so that $[M, N) \subset T_x^{odd}$ and $N \not\in T_X^{odd}$ , and $N > 2M$ .

This forces $s_{x+1} = N$ , which gives $\{N + k : k \in [M, N) \} \subset T_{x+1}^{even}$ , but then noting that there can't be repeats in $T^{odd}$ sets, we must have $s_{x+2} \geq 2N-M$ . Hence eventually asymptotically there is some really big $x$ such that $N \sim 2^x$ , but then there can't be enough elements in $S_x^{odd}$ to fill in everything between $M$ (which remains fixed) and $2^x$ .

This post has been edited 3 times. Last edited by mathfun07, Mar 23, 2025, 10:27 PM

Z K Y

N Quick Reply