Bump bump

joeym2011 wrote: Clearly $n\ge\log_2{1001}$, so $n\ge10$. Suppose $n=10$ works. We need at least one $x_i\equiv1\pmod2$. We also need some $x_i\equiv2\pmod4$, or all numbers formed are $0$ or $1$ modulo $4$. Similarly, we need some $x_i\equiv2^k\pmod{2^{k+1}}$ up to $k=9$. This means all $x_i$ have different numbers of factors of $2$. Then $1024$ cannot be represented, a contradiction, so $n\ne10$. We have that $n=\boxed{11}$ works from binary Could you explain why $n\ge\log_2{1001}$? If $n=11$, what are $x_1,x_2,...x_{11}$? And how each number from $1000$ to $2000$ is represented?

Sorry about my vague explanation! There are 2^n combinations of sums, which should exceed the number of numbers from 1000 to 2000. For n=11, let each x be a power of 2.

joeym2011 wrote: Clearly $n\ge\log_2{1001}$, so $n\ge10$. Suppose $n=10$ works. We need at least one $x_i\equiv1\pmod2$. We also need some $x_i\equiv2\pmod4$, or all numbers formed are $0$ or $1$ modulo $4$. Similarly, we need some $x_i\equiv2^k\pmod{2^{k+1}}$ up to $k=9$. This means all $x_i$ have different numbers of factors of $2$. Then $1024$ cannot be represented, a contradiction, so $n\ne10$. We have that $n=\boxed{11}$ works from binary. Could you explain the line: "We also need some $x_i\equiv2\pmod4$, or all numbers formed are $0$ or $1$ modulo $4$". I don't think that's true.

anyone ?

The above solution is correct. Here's an alternate approach that uses the same logic:

As for the line "We need some $x_i \equiv 2 \pmod{4}$," consider the set $\{1, 2, 4, 8, \ldots, 1024 \}$, and remove the element $2$ from it. Now, try to create the number $1026$. You will notice very quickly that it's impossible.

tapilyoca wrote: The above solution is correct. Here's an alternate approach that uses the same logic: As for the line "We need some $x_i \equiv 2 \pmod{4}$," consider the set $\{1, 2, 4, 8, \ldots, 1024 \}$, and remove the element $2$ from it. Now, try to create the number $1026$. You will notice very quickly that it's impossible. Still don't get it

I don't think the above solutions are correct,but here is mine: Suppose $x_1,x_2,\dots x_{10}$ work and $x_1<x_2<\dots x_{10}$. We have 2 cases: Case 1: $x_3+x_8<1000$ then look at $x_1,\dots x_8$ and $x_i+x_j$ where $i\le 3$ and $j\le 8$ and $i\neq j$.They are all less than $1000$ and we have at least $23$ such sums which implies at most $2^{10}-1-23=1000$ sums are in $[1000,2000]$,false ! Case 2: $x_3+x_8\ge 1000$ Consider sums of the form $x_3+x_8+x_4+x_9+\sum_{s\in S} x_s$ where $S$ is included in {1,2,5,6,7,10};$|S|=6$ so there are $64$ sums all of which are greater than $2000$ so at most $1023-64=959$ sums are in $[1000,2000]$,false !\ Btw,what is SMO ?

nguyenalex wrote: tapilyoca wrote: The above solution is correct. Here's an alternate approach that uses the same logic: As for the line "We need some $x_i \equiv 2 \pmod{4}$," consider the set $\{1, 2, 4, 8, \ldots, 1024 \}$, and remove the element $2$ from it. Now, try to create the number $1026$. You will notice very quickly that it's impossible. Still don't get it Hopefully this helps Main Solution after we get that n is greater than or equal to 10 : to run through all the remainders $(mod 2^k)$, except $0$, we need the numbers $1(mod 2^k), 2(mod 2^k), 4(mod 2^k) \dots, 2^{k-1} (mod 2^k)$. But just by adding these number we can't get any number $0(mod 2^k)$. So, we need $0(mod 2^k)$ as well. Also, note that if any number from the set $1(mod 2^k), 2(mod 2^k), 4(mod 2^k), \dots, 2^{k-1} (mod 2^k)$ is deleted then as well we can't get all remainders $(mod 2^k)$. And between 1000 to 2000 we have $1024$. Looking at remainders $(mod 1024)$ we want all of them, so we need all the numbers $1(mod 2^{10}), 2(mod 2^{10}), 4(mod 2^{10})$ and so on till $2^9 (mod 2^{10}), 0(mod 2^{10})$ - which is the minimum no numbers needed and are in total $11$ numbers. Construction just follows from binary numbers. Motivation : Lets first look in $(mod 2)$. All numbers are $0,1(mod 2)$. Now, let's extend this to $(mod 4)$. What will be the minimum no of numbers required in $(mod 4)$ to cover all the residues. We require, a number $1,3(mod 4)$, $2(mod 4)$ and $0(mod4)$. Let's take one $1(mod 4)$, $2(mod 4)$, adding them we can get a number $3(mod 4)$. So, we only want a number with residue $0(mod 4)$ - write this as $k \equiv 4(mod 8)$ [highest number diving $k$ be $4$] to extend to $(mod 8)$.Similarly, as we did for $(mod 4)$, we take the number $1(mod 8), 2(mod 8), 4 (mod 8)$ - adding these can run through all the remainders so we only require $0(mod 8)$ - write this as $8(mod 16)$ to extend to $(mod 16)$.

g0USinsane777 wrote: Main Solution after we get that n is greater than or equal to 10 : to run through all the remainders $(mod 2^k)$, except $0$, we need the numbers $1(mod 2^k), 2(mod 2^k), 4(mod 2^k) \dots, 2^{k-1} (mod 2^k)$. But just by adding these number we can't get any number $0(mod 2^k)$. So, we need $0(mod 2^k)$ as well. Also, note that if any number from the set $1(mod 2^k), 2(mod 2^k), 4(mod 2^k), \dots, 2^{k-1} (mod 2^k)$ is deleted then as well we can't get all remainders $(mod 2^k)$. And between 1000 to 2000 we have $1024$. Looking at remainders $(mod 1024)$ we want all of them, so we need all the numbers $1(mod 2^{10}), 2(mod 2^{10}), 4(mod 2^{10})$ and so on till $2^9 (mod 2^{10}), 0(mod 2^{10})$ - which is the minimum no numbers needed and are in total $11$ numbers. Construction just follows from binary numbers. Not all remainders are needed but $1001$ remainders are needed some of which are greater than or equal to $512$, so $2^0(mod\ \ 2^{10}), 2^1(mod\ \ 2^{10}), 2^2(mod\ \ 2^{10}), \dots, 2^{9}(mod\ \ 2^{10})$ are atleast needed. And since, $1024$ is also there $0(mod \ \ 2^{10})$ is also needed, meaning atleast $11$ numbers are needed and smallest possible $n$ is $11$.