Maths Olympiad Prep

Library / /42 of 48

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

Determine all positive integers kk for which there exist a positive integer mm and a set SS of positive integers such that any integer n>mn>m can be written as a sum of distinct elements of SS in exactly kk ways.

Solutions — 2

Solution 1

We claim that k=2ak=2^{a} for all a0a \geq 0.
Let A={1,2,4,8,}A=\{1,2,4,8, \ldots\} and B=N\AB=\mathbb{N} \backslash A. For any set TT, let s(T)s(T) denote the sum of the elements of TT. (If TT is empty, we let s(T)=0s(T)=0.)
We first show that any positive integer k=2ak=2^{a} satisfies the desired property. Let BB' be a subset of BB with aa elements, and let S=ABS=A \cup B'. Recall that any nonnegative integer has a unique binary representation. Hence, for any integer t>s(B)t>s\left(B'\right) and any subset BBB'' \subseteq B', the number ts(B)t-s\left(B''\right) can be written as a sum of distinct elements of AA in a unique way. This means that tt can be written as a sum of distinct elements of BB' in exactly 2a2^{a} ways.
Next, assume that some positive integer kk satisfies the desired property for a positive integer m2m \geq 2 and a set SS. Clearly, SS is infinite.

Lemma: For all sufficiently large xSx \in S, the smallest element of SS larger than xx is 2x2x.

Proof of Lemma: Let xSx \in S with x>3mx>3m, and let x<y<2xx<y<2x. We will show that ySy \notin S. Suppose first that y>x+my>x+m. Then yxy-x can be written as a sum of distinct elements of SS not including xx in kk ways. If ySy \in S, then yy can be written as a sum of distinct elements of SS in at least k+1k+1 ways, a contradiction. Suppose now that yx+my \leq x+m. We consider z(2xm,2x)z \in (2x-m, 2x). Similarly as before, zxz-x can be written as a sum of distinct elements of SS not including xx or yy in kk ways. If ySy \in S, then since m<zy<xm<z-y<x, zyz-y can be written as a sum of distinct elements of SS not including xx or yy. This means that zz can be written as a sum of distinct elements of SS in at least k+1k+1 ways, a contradiction.
We now show that 2xS2x \in S; assume for contradiction that this is not the case. Observe that 2x2x can be written as a sum of distinct elements of SS including xx in exactly k1k-1 ways. This means that 2x2x can also be written as a sum of distinct elements of SS not including xx. If this sum includes any number less than xmx-m, then removing this number, we can write some number y(x+m,2x)y \in (x+m, 2x) as a sum of distinct elements of SS not including xx. Now if y=y+xy=y'+x where y(m,x)y' \in (m, x) then yy' can be written as a sum of distinct elements of SS including xx in exactly kk ways. Therefore yy can be written as a sum of distinct elements of SS in at least k+1k+1 ways, a contradiction. Hence the sum only includes numbers in the range [xm,x)[x-m, x). Clearly two numbers do not suffice. On the other hand, three such numbers sum to at least 3(xm)>2x3(x-m)>2x, a contradiction.
From the Lemma, we have that S=TUS=T \cup U, where TT is finite and U={x,2x,4x,8x,}U=\{x, 2x, 4x, 8x, \ldots\} for some positive integer xx. Let yy be any positive integer greater than s(T)s(T). For any subset TTT' \subseteq T, if ys(T)0(modx)y-s\left(T'\right) \equiv 0 \pmod{x}, then ys(T)y-s\left(T'\right) can be written as a sum of distinct elements of UU in a unique way; otherwise ys(T)y-s\left(T'\right) cannot be written as a sum of distinct elements of UU. Hence the number of ways to write yy as a sum of distinct elements of SS is equal to the number of subsets TTT' \subseteq T such that s(T)y(modx)s\left(T'\right) \equiv y \pmod{x}. Since this holds for all yy, for any 0ax10 \leq a \leq x-1 there are exactly kk subsets TTT' \subseteq T such that s(T)a(modx)s\left(T'\right) \equiv a \pmod{x}. This means that there are kxkx subsets of TT in total. But the number of subsets of TT is a power of 22, and therefore kk is a power of 22, as claimed.

Solution 2

Solution 2. We give an alternative proof of the first half of the lemma in the Solution 1 above.
Let s1<s2<s_{1}<s_{2}<\cdots be the elements of SS. For any positive integer rr, define Ar(x)=n=1r(1+xsn)A_{r}(x)=\prod_{n=1}^{r}\left(1+x^{s_{n}}\right). For each nn such that mn<sr+1m \leq n<s_{r+1}, all kk ways of writing nn as a sum of elements of SS must only use s1,,srs_{1}, \ldots, s_{r}, so the coefficient of xnx^{n} in Ar(x)A_{r}(x) is kk. Similarly the number of ways of writing sr+1s_{r+1} as a sum of elements of SS without using sr+1s_{r+1} is exactly k1k-1. Hence the coefficient of xsr+1x^{s_{r+1}} in Ar(x)A_{r}(x) is k1k-1.
Fix a tt such that st>2(m+1)s_{t}>2(m+1). Write
At1(x)=u(x)+k(xm+1++xst1)+xstv(x) A_{t-1}(x)=u(x)+k\left(x^{m+1}+\cdots+x^{s_{t}-1}\right)+x^{s_{t}} v(x)
for some u(x),v(x)u(x), v(x) where u(x)u(x) is of degree at most mm.
Note that
At+1(x)=At1(x)+xstAt1(x)+xst+1At1(x)+xst+st+1At1(x) A_{t+1}(x)=A_{t-1}(x)+x^{s_{t}} A_{t-1}(x)+x^{s_{t+1}} A_{t-1}(x)+x^{s_{t}+s_{t+1}} A_{t-1}(x)
If st+1+m+1<2sts_{t+1}+m+1<2 s_{t}, we can find the term xst+1+m+1x^{s_{t+1}+m+1} in xstAt1(x)x^{s_{t}} A_{t-1}(x) and in xst+1At1(x)x^{s_{t+1}} A_{t-1}(x). Hence the coefficient of xst+1+m+1x^{s_{t+1}+m+1} in At+1(x)A_{t+1}(x) is at least 2k2k, which is impossible. So st+12st(m+1)>st+m+1s_{t+1} \geq 2 s_{t}-(m+1)> s_{t}+m+1.
Now
At(x)=At1(x)+xstu(x)+k(xst+m+1+x2st1)+x2stv(x). A_{t}(x)=A_{t-1}(x)+x^{s_{t}} u(x)+k\left(x^{s_{t}+m+1}+\cdots x^{2 s_{t}-1}\right)+x^{2 s_{t}} v(x) .
Recall that the coefficent of xst+1x^{s_{t+1}} in At(x)A_{t}(x) is k1k-1. But if st+m+1<st+1<s2ts_{t}+m+1<s_{t+1}<s_{2 t}, then the coefficient of xst+1x^{s_{t+1}} in At(x)A_{t}(x) is at least kk, which is a contradiction. Therefore st+12sts_{t+1} \geq 2 s_{t}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.