Suppose that 3≤n is a natural number. Find the maximum value of the natural number k, for which, there are real numbers a1,a2,…,an∈[0,1) (not necessarily distinct) such that for every natural number j satisfying j≤k, there exists a sum of a certain number of ai's equal to j.
Solution
We claim that the answer is n−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 n−1. Suppose the numbers are ai=1−bi.
First solution. Using induction, we will prove that for each n, there exists b1,…,bn satisfying the following properties: ∙∀1<k<n−1,∃i≤k≤n:bi1+⋯+bik=1 ∙b1+⋯+bn=2 The given conditions imply the desired result because: ∀1<k<n−1:ai1+⋯+aik=k−1∈{1,…,n−3} And also: a1+⋯+an=n−2
In other words, we divide all previous terms by 2 and add two new 21. Now we check the correctness of the induction hypothesis:
For the base of induction we use: n=3:31,31,31n=4:21,21,21,21
Second Solution bi1+⋯+bit=1 implies ai1+⋯+ait=t−1. Thus, we should give an example that for 2≤t≤n−1 sum of t of them is 1. Let α=25−1 which is the root of x2+x=1 and 0<α<1. If n=2m is even, take bk=ak for k=1,⋯,2m−2 and b2m−1=b2m=21α2m−3. Now for all 1≤t≤m−1 it follows that b2t+b2t−1+b2t−3+b2t−5+⋯+b1=b2t−2+b2t−3+b2t−5+⋯+b1=⋯=b2+b1=1 Thus the sum of t+1 of bi's is 1. Furthermore, since α2m−2+α2m−3+⋯+α2t=1−αα2t−α2m−1=α2α2t−α2m−1=α2t−2−α2m−3 we have b2m+b2m−1+b2m−2+⋯+b2+b2t−3+b2t−5+⋯+b1=1 Hence sum of 2m−t of bi's is 1. If n=2m−1 is odd, then setting bk=αk for k=1,⋯,2m−2 and b2m−1=α2m−3, we have b2t+b2t−1+b2t−3+⋯+b1=b2m−1+b2m−2+⋯+b2+b2t−3+b2t−5+⋯+b1=1 We proved that for all 2≤t≤2m−2 the sum of t of bi'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.