Find a number $n \geq 9$ such that for any $n$ numbers, not necessarily distinct, $a_1,a_2, \ldots , a_n$, there exists 9 numbers $a_{i_1}, a_{i_2}, \ldots , a_{i_9}, (1 \leq i_1 < i_2 < \ldots < i_9 \leq n)$ and $b_i \in {4,7}, i =1, 2, \ldots , 9$ such that $b_1a_{i_1} + b_2a_{i_2} + \ldots + b_9a_{i_9}$ is a multiple of 9.
Problem
Source:
Tags: pigeonhole principle, number theory unsolved, number theory
01.12.2010 08:44
Take $n=10000000000000$. By pigeonhole principle, there exist $a_{i_1},a_{i_2},\ldots,a_{i_9}$ which are congruent in modulo 9, so we can take $b_i=4$ for $i=1,2,\ldots,9$. I think the correct question is to find the smallest such $n$.
02.12.2010 09:54
Johan Gunardi wrote: Take $n=10000000000000$. By pigeonhole principle, there exist $a_{i_1},a_{i_2},\ldots,a_{i_9}$ which are congruent in modulo 9, so we can take $b_i=4$ for $i=1,2,\ldots,9$. I think the correct question is to find the smallest such $n$. Can we find minimal such $n$? I think it must be not so big (because $b_i$ can be $7$ too)
02.12.2010 10:11
By EGZ theorem, the smallest $n$ is at most 17.
02.12.2010 11:45
smallest n is 11. If $a_1=...=a_8=0,a_9=1,a_{10}=3$ we can not chose $b_i=4 \ or \ 7$. Let $n\ge 11$ 1) If $9$ numbers $a_i$ divides 9, then whe can chose them and chose $b_i=cosnt $. 2) If $10$ numbers $a_i$ devides 3, but there are not $9$ numbers $a_i$, suth that $9|a_i$. If we can chose 9 numbers, suth that sum devides 9. We chose them, and chose $b_i=const$. Else we chose 9 of them, suth that at least 2 of them not divides 9. Then we can change one or 2 coefficients from 4 to 9 and makre $9|s$. 3) If we had 11 numbers, were at least 2 is not devides 3, we can chose 9 numbers, were at least 2 of them not devides 3 but sum of them devides 3. If sum of them not devides 9 we change 1 or 2 coefficients $b_i$ from 4 to 7 and make $9|s$.
02.12.2010 12:02
I don't understand your proof, but $n=13$ is still possible: 1, 1, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0.
02.12.2010 13:06
You can chose 9 numbers $a_i=0$ and any chose of $b_i$ give $9|\sum_i b_ia_i=0$.
02.12.2010 13:23
Sorry, I mean $n=12$. Remove one 0.
02.12.2010 14:57
Johan Gunardi wrote: Sorry, I mean $n=12$. Remove one 0. Yes, you are right. My idea is right too, but I didn't release it exactly. 1) Let $s_0=\sum_i a_i$. We note, that $s=\sum_ib_ia_i=s_0\mod 3$, because $4=7=1\mod 3$. Therefore we must chose $a_i$, suth that $3|s_0$ and if $9\not |s_0$ at least one of $a_i$ not divide 3. Statement. Let $3|s_0, 9\not |s_0$ and exist $a_i$, suth that $3\not |a_i$. Then we can chose $b_i =4 \ or \ 7$, suth that $9|s=\sum_i a_ib_i.$ Prove. If $9|s_0$ we can chose $b_i=4$ for all i. At least 2 of $a_i$ not devide 3. Let $3\not|a_1, 3\not |a_2$. If $a_1=a_2$ exist third term $3\not |a_3$. We chose all $b_i=4$, If $9\not |s_0$ we change $b_1$ or $b_2$ or $b_1$ and $b_2$ and make $9|s$. If we have nine numbers $a_i$, suth that $9|a_i$ we chose them and any $b_i$. If exist 11 numbers $a_i$, suth that $3|a_i$ we chose them and except 2, suth that $9|s_0$. If exist 13 numbers $a_i$, but not exist 11 numbers, suth that $3|a_i$, then at least 3 of them not devide 3. Let they are $a_1,a_2,a_3$. We can chose any 7 numbers and except 1 and make $3|s_0.$