Problem:
Let n>1 be an integer. Find, with proof, all sequences x1β,x2β,β¦,xnβ1β of positive integers with the following three properties:
(1) x1β<x2β<β―<xnβ1β;
(2) xiβ+xnβiβ=2n for all i=1,2,β¦,nβ1;
(3) given any two indices i and j (not necessarily distinct) for which xiβ+xjβ<2n, there is an index k such that xiβ+xjβ=xkβ.
Solution:
Solution from RΔzvan Gelca: There is a unique sequence 2,4,6,β¦,2nβ 2 satisfying the conditions of the problem.
Note that (b) implies xiβ<2n for all i. We will examine the possible values of x1β.
If x1β=1, then (c) implies that all numbers less than 2n should be terms of the sequence, which is impossible since the sequence has only nβ1 terms.
If x1β=2, then by (c) the numbers 2,4,6,β¦,2nβ2 are terms of the sequence, and because the sequence has exactly nβ1 terms we get xiβ=2i,i=1,2,β¦,nβ1. This sequence satisfies conditions (a) and (b) as well, so it is a solution to the problem.
For x1ββ₯3, we will show that there is no sequences satisfying the conditions of the problem. Assume on the contrary that for some n there is such a sequence with x1ββ₯3. If n=2, the only possibility is x1β=3, which violates (b). If n=3, then by (a) we have the possibilities (x1β,x2β)=(3,4), or (3,5), or (4,5), all three of which violate (b). Now we assume that n>3. By (c), the numbers
x1β,2x1β,β¦,βxiβ2nβββ
x(1)
are terms of the sequence, and no other multiples of x1β are. Because x1ββ₯3, the above accounts for at most 32nβ terms of the sequence. For n>3, we have 32nβ<nβ1, and so there must be another term besides the terms in (1). Let xjβ be the smallest term of the sequence that does not appear in (1). Then the first j terms of the sequence are
x1β,x2β=2x1β,β¦,xjβ1β=(jβ1)x1β,xjβ(2)
and we have xjβ<jx1β. Condition (b) implies that the last j terms of the sequence must be
xnβjβ=2nβxjβ,xnβj+1β=2nβ(jβ1)x1β,β¦,xnβ2β=2nβ2x1β,xnβ1β=2nβx1β.β
But then x1β+xnβjβ<x1β+xnβ1β=2n, hence by condition (c) there exists k such that x1β+xnβjβ=xkβ. On the one hand, we have
xkββ=x1β+xnβjβ=x1β+2nβxjβ=2nβ(xjββx1β)>2nβ(jx1ββx1β)=2nβ(jβ1)x1β=xnβj+1ββ
One the other hand, we have
xkβ=x1β+xnβjβ<x1β+xnβj+1β=xnβj+2β
This means that xkβ is between two consecutive terms xnβj+1β and xnβj+2β, which is impossible by (a). (In the case j=2,xkβ>xnβj+1β=xnβ1β, which is also impossible.) We conclude that there is no such sequence with x1ββ₯3.
Remark. This problem comes from the study of Weierstrass gaps in the theory of Riemann surfaces.
Alternate Solution from Richard Stong: Assume that x1β,x2β,β¦,xnβ1β is a sequence satisfying the conditions of the problem. By condition (a), the following terms
x1β,2x1β,x1β+x2β,x1β+x3β,x1β+x4β,β¦,x1β+xnβ2β
form an increasing sequence. By condition (c), this new sequence is a subsequence of the original sequence. Because both sequences have exactly nβ1 terms, these two sequences are identical; that is, 2x1β=x2β and x1β+xjβ=xj+1β for 2β€jβ€nβ2. It follows that xjβ=jx1β for 1β€jβ€nβ1. By condition (b), we conclude that (x1β,x2β,β¦,xnβ1β)= (2,4,β¦,2nβ2).
Remark. The core of the second solution is a result due to Freiman:
Let A be a set of positive integers. Then the set A+A= {a1β+ a2ββ£a1β,a2ββA} has at least 2β£Aβ£β1 elements and equality holds if and only if A is a set of an arithmetic progression.
Freiman's theorem and its generalization below are very helpful in proofs of many contest problems, such as, USAMO 2009 problem 2, IMO 2000 problem 1, and IMO 2009 problem 5.
Let A and B be finite nonempty subsets of integers.
Then the set A+B={a+bβ£aβA,bβB} has at least β£Aβ£+β£Bβ£β1 elements. Equality holds if and only if either A and B are arithmetic progressions with equal difference or β£Aβ£ or β£Bβ£ is equal to 1 .
This problem was suggested by RΔzvan Gelca.
The problems on this page are the property of the MAA's American Mathematics Competitions