Suppose that $n\ge3$ is a natural number. Find the maximum value $k$ such that there are real numbers $a_1,a_2,...,a_n \in [0,1)$ (not necessarily distinct) that for every natural number like $j \le k$ , sum of some $a_i$-s is $j$. Proposed by Navid Safaei
Problem
Source: Iran TST 2023 ; Exam 1 Problem 1
Tags: al, algebra
Shayan-TayefehIR
16.03.2023 00:01
We'll show that the answer is $n-2$ for each number $n \ge 3$. First note that if we can produce all numbers $1 , 2 , ... , n-1$ with $0 \le a_1 , ... , a_n < 1$ , then since the sum of each $n-1$ numbers between $a_1 , ... , a_n$ is less than $n-1$ , we must have $a_1+a_2+...+a_n=n-1$ and similary , one can see that there is an index $i$ such that $a_1+a_2+...+a_n-a_i=n-2$ which means $a_i=1$ , which is a contradiction. Now , for each natural number $n$ , we define the number $k_n$ as follows : $$k_n=\frac{2^{n}-1}{2^n}$$And we'll show by induction on $n$ that for each even number $2n$ and $2n+1$ , this configurations for $a_1 , ... , a_n$ work for the case $k=n-2$ : $$k_{n-1} , k_{n-1} , k_{n-1} , k_{n-1} , k_{n-2} , k_{n-2} , ... , k_1 , k_1$$$$k_n , k_n , k_{n-1} , k_{n-1} , k_{n-1} , k_{n-2} , k_{n-2} , ... , k_1 , k_1$$We also show something stronger , that for the $2n$ case and for making numbers $1 , 2 , ... , n-2$ we don't need to use any of the four numbers $k_{n-1}$ in our configuration and also for showing $n$ , we need at most two numbers $k_{n-1}$ . First note that if we show the sum of all numbers for $n$ as $S_n$ , one can see that : $$S_{2n+1}=S_{2n}+2k_{n}-k_{n-1}=2n-2+\frac{2^n-2^{n-1}}{2^{n-1}}=2n-1$$And by our induction case for $2n$ , we can make all numbers $1 , 2 , ... , n-1$ with these $2n+1$ numbers without using $k_n$ or more that two $k_{n-1}$ and since $S_{2n+1}=2n-1$ , we can show all numbers $n , n+1 , ... , 2n-1$ too. Now similary we have $S_{2n+2}=2n$ and we can show all the numbers $1 , 2 , ... , n-1$ by our induction case for $2n+1$ without using any of the four numbers $k_n$ since we still have two numbers $k_{n-1}$ in our configuration and for making $n$ whit using at most two number from four numbers $k_n$ , one can see that : $$k_1+k_2+...+k_n+k_n=n$$which is obvious since $2k_{n}-k_{n-1}=1$. So we're done.
hakN
18.03.2023 14:53
Solved with Cookierookie and sevket12.
The answer is $n-2$.
First, assume that $k=n-1$ works, we must have $a_1+\dots+a_n=n-1$, and $\sum_{i\neq j} a_i = n-2$ for some $j\in \{1,2,\dots,n\}$, but these two would imply $a_j=1$, contradiction.
Now we show $k=n-2$ works.
For $n=4$, we take $a_1=1-a, a_2=a, a_3=1-\frac{a}{2}, a_4=1-\frac{a}{2}$ for small $a>0$.
For $n=6$, we take $a_1=1-a, a_2=a, a_3=a_4=1-\frac{a}{2}, a_5=a_6=\frac{1+a}{2}$ for small $a>0$.
For $n=2k$ where $k\geq 4$, we take $a_1=a_2=1-\frac{\varepsilon}{2^{k-3}} , a_3=1-\frac{\varepsilon}{2^{k-4}} , a_4=1-\frac{\varepsilon}{2^{k-5}} , \dots , a_{k-2} = 1-\frac{\varepsilon}{2} , a_{k-1}=\frac{1}{2}+\varepsilon , a_k=a_{k+1}=\frac{1}{2}, a_{k+2}=1-\varepsilon, a_{k+3}=1-\frac{\varepsilon}{2}, \dots, a_{2k-2}=1-\frac{\varepsilon}{2^{k-4}}, a_{2k-1}=a_{2k}=\frac{3}{4}+\frac{\varepsilon(2^{k-3}-1)}{2^{k-3}}$ for sufficiently small $\varepsilon>0$.
This works because $a_k+a_{k+1}=1, a_{k-1}+a_k+a_{k+2}=2, a_{k-2}+a_{k-1}+a_k+a_{k+3}=3, \dots, a_3+a_4+\dots+a_k+a_{2k-2}=k-2, a_1+a_2+\dots+a_k=k-1, a_{k+1}+a_{k+2}+\dots+a_{2k}=k-1$ and we can take the complements to get sums $k,k+1,\dots,2k-3$.
For $n=3$, take $a_1=a, a_2=1-a, a_3=b$ for any $1>a,b>0$.
For $n=5$, take $a_1=a, a_2=1-a, a_3=a_4=1+\frac{a}{2}, a_5=1-2a$ for small $a>0$.
For $n=7$, take $a_1=a_2=a_3=\frac{5}{6}, a_4=a_5=\frac{1}{2}, a_6=a_7=\frac{3}{4}$.
For $n=2k+1$ where $k\geq 4$, take $a_1=a_2=a_3=1-\frac{\varepsilon}{3\cdot 2^{k-4}} , a_4=1-\frac{\varepsilon}{2^{k-4}}, a_5=1-\frac{\varepsilon}{2^{k-5}}, \dots, a_{k-1}=1-\frac{\varepsilon}{2}, a_k=\frac{1}{2}+\varepsilon, a_{k+1}=a_{k+2}=\frac{1}{2}, a_{k+3}=1-\varepsilon, a_{k+4}=1-\frac{\varepsilon}{2},\dots, a_{2k-1}=1-\frac{\varepsilon}{2^{k-4}}, a_{2k}=a_{2k+1}=\frac{3}{4}+\frac{\varepsilon(2^{k-3}-1)}{2^{k-3}}$ for sufficiently small $\varepsilon>0$.
This works because $a_{k+1}+a_{k+2}=1, a_k+a_{k+1}+a_{k+3}=2, a_{k-1}+a_k+a_{k+1}+a_{k+4}=3, \dots, a_4+\dots+a_{k+1}+a_{2k-1}=k-2, a_{k+2}+a_{k+3}+\dots+a_{2k+1}=k-1, a_1+a_2+\dots+a_{k+1}=k$, and we can get complements to get sums $k+1,k+2,\dots,2k-2$.
This completes the proof. $\square$
Tintarn
22.03.2023 14:49
Actually, there is a nice construction without any case distinction: If we write $b_k=1-a_k$, it suffices to find $b_1,\dots,b_n \in (0,1)$ such that for any $2 \le m \le n-1$, the sum of $m$ of the $b_i$ is equal to $1$. But because the sequence $1,1,1,2,3,5,8,13,\dots,F_{n-1}$ clearly has this property with sum $F_n$ (just start with $F_n=F_{n-1}+F_{n-2}$ and use repeatedly the Fibonacci sequence to add one more term), we can simply take $\frac{1}{F_n},\frac{1}{F_n},\frac{1}{F_n},\frac{2}{F_n},\frac{3}{F_n},\frac{5}{F_n},\dots,\frac{F_{n-1}}{F_n}$ for the $b_i$.
M11100111001Y1R
26.06.2023 00:47
Here is another solution: We claim that the answer is $n-2.$ Let define $S_r,$ the sum of $r$ terms of $a_i$ that construct an integer. First we prove that if we have $S_r=1$ then we don't have $S_j=n-1$ and vice versa. Suppose that there exist $r$ such that $S_r=n-1$ then if we have $S_j=1,$ there exist at least two terms such that $S_j=a_m+a_n=1$ now $n-3$ other terms have max value of $n-3$ so $S_j+n-3 <n-1$ and we are done. For the construction take $n=3$ base with $\{\frac{0}{3}, \frac{1}{3}, \frac{2}{3}\}$ every time sum numerator with $1$ same thing for denominator and take your $a_n=\frac{(n-2)n-K_{n-1}}{n}$ where $K_{n-1}$ is the sum of the other $n-1$ terms. So we are done