Maths Olympiad Prep

Library / /197 of 299

Combinatorics Difficulty 6.8 National Olympiad Prove it Iran

Suppose that 3n3 \le n is a natural number. Find the maximum value of the natural number kk, for which, there are real numbers a1,a2,,an[0,1)a_1, a_2, \dots, a_n \in [0, 1) (not necessarily distinct) such that for every natural number jj satisfying jkj \le k, there exists a sum of a certain number of aia_i's equal to jj.

Solution

We claim that the answer is n2n-2. First, note that since the sum of a number of variables (at least 2) is one, and the rest of the numbers are less than one, the sum of all the variables is less than n1n-1. Suppose the numbers are ai=1bia_i = 1-b_i.

First solution. Using induction, we will prove that for each nn, there exists b1,,bnb_1, \dots, b_n satisfying the following properties:
1<k<n1,ikn:bi1++bik=1 \bullet \quad \forall 1 < k < n-1, \exists i \le k \le n : b_{i_1} + \dots + b_{i_k} = 1
b1++bn=2 \bullet \quad b_1 + \dots + b_n = 2
The given conditions imply the desired result because:
1<k<n1:ai1++aik=k1{1,,n3} \forall 1 < k < n-1 : a_{i_1} + \dots + a_{i_k} = k-1 \in \{1, \dots, n-3\}
And also:
a1++an=n2 a_1 + \dots + a_n = n - 2

In other words, we divide all previous terms by 2 and add two new 12\frac{1}{2}. Now we check the correctness of the induction hypothesis:

1.
k=2:bn+1+bn+2=1 k = 2 : b'_{n+1} + b'_{n+2} = 1

2.
3k<n:bi1++bik1=1    b1++bik1+bn+1=1 3 \le k < n : \exists b_{i_1} + \cdots + b_{i_{k-1}} = 1 \implies b_1' + \cdots + b_{i_{k-1}}' + b_{n+1} = 1

3.
k=n:b1++bn=1 k = n : b_1' + \cdots + b_n' = 1

4.
b1++bn+2=1+b1++bn2=2 b_1' + \cdots + b_{n+2}' = 1 + \frac{b_1 + \cdots + b_n}{2} = 2

For the base of induction we use:
n=3:13,13,13n=4:12,12,12,12 n = 3 : \frac{1}{3}, \frac{1}{3}, \frac{1}{3} \quad n = 4 : \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}

Second Solution
bi1++bit=1b_{i_1} + \cdots + b_{i_t} = 1 implies ai1++ait=t1a_{i_1} + \cdots + a_{i_t} = t - 1. Thus, we should give an example that for 2tn12 \le t \le n - 1 sum of tt of them is 1.
Let α=512\alpha = \frac{\sqrt{5}-1}{2} which is the root of x2+x=1x^2+x=1 and 0<α<10 < \alpha < 1. If n=2mn=2m is even, take bk=akb_k = a^k for k=1,,2m2k=1, \cdots, 2m-2 and b2m1=b2m=12α2m3b_{2m-1} = b_{2m} = \frac{1}{2}\alpha^{2m-3}. Now for all 1tm11 \le t \le m-1 it follows that
b2t+b2t1+b2t3+b2t5++b1=b2t2+b2t3+b2t5++b1==b2+b1=1 b_{2t}+b_{2t-1}+b_{2t-3}+b_{2t-5}+\cdots+b_1 = b_{2t-2}+b_{2t-3}+b_{2t-5}+\cdots+b_1 = \cdots = b_2+b_1 = 1
Thus the sum of t+1t+1 of bib_i's is 1.
Furthermore, since α2m2+α2m3++α2t=α2tα2m11α=α2tα2m1α2=α2t2α2m3\alpha^{2m-2}+\alpha^{2m-3}+\cdots+\alpha^{2t} = \frac{\alpha^{2t}-\alpha^{2m-1}}{1-\alpha} = \frac{\alpha^{2t}-\alpha^{2m-1}}{\alpha^2} = \alpha^{2t-2}-\alpha^{2m-3} we have
b2m+b2m1+b2m2++b2+b2t3+b2t5++b1=1 b_{2m} + b_{2m-1} + b_{2m-2} + \cdots + b_2 + b_{2t-3} + b_{2t-5} + \cdots + b_1 = 1
Hence sum of 2mt2m-t of bib_i's is 1. If n=2m1n=2m-1 is odd, then setting bk=αkb_k = \alpha^k for k=1,,2m2k=1, \cdots, 2m-2 and b2m1=α2m3b_{2m-1} = \alpha^{2m-3}, we have
b2t+b2t1+b2t3++b1=b2m1+b2m2++b2+b2t3+b2t5++b1=1 b_{2t}+b_{2t-1}+b_{2t-3}+\cdots+b_1 = b_{2m-1}+b_{2m-2}+\cdots+b_2+b_{2t-3}+b_{2t-5}+\cdots+b_1 = 1
We proved that for all 2t2m22 \le t \le 2m-2 the sum of tt of bib_i's is 1. ■

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 reproduced verbatim; metadata (topic, difficulty) added by this project.