Let $a_1, a_2, \ldots, a_{11}$ be integers. Prove that there exist numbers $b_1, b_2, \ldots, b_{11}$ such that $b_i$ is equal to $-1,0$ or $1$ for all $i \in \{1, 2,\dots, 11\}$. all numbers can't be zero at a time. the number $N=a_1b_1+a_2b_2+\ldots+a_{11}b_{11}$ is divisible by $2024$.
Problem
Source: BdMO 2024 Secondary National P4 Higher Secondary National P4
Tags: combinatorics, Sequence, modular arithmetic, pigeonhole principle
18.03.2024 23:15
$2^{11}>2024$ so there are two sets $x_1,x_2,...,x_{11}$ and $y_1,y_2,...,y_{11}$ such that $x_i \neq 0, y_i \neq 0$ and $x_1a_1+x_2a_2+...+x_{11}a_{11} \equiv y_1a_1+y_2a_2+...+y_{11}a_{11} \pmod {2024}$ If $x_i=y_i$ then replace them with $0$ After such replacement it is still $x_1a_1+x_2a_2+...+x_{11}a_{11} \equiv y_1a_1+y_2a_2+...+y_{11}a_{11}$ and $(x_i,y_i)$ is $(-1,1), (1,-1)$ or $(0,0)$ In all cases $x_i+y_i=0$ so $x_1a_1+x_2a_2+...+x_{11}a_{11} \equiv\frac{1}{2}( (x_1+y_1)a_1+...+(x_{11}+y_{11})a_{11}) \equiv 0 \pmod{2024}$
27.11.2024 14:58
Why not just put all $b_i=0$, and $2024|0$
28.11.2024 19:30
rudransh61 wrote: Why not just put all $b_i=0$, and $2024|0$ The question says all the numbers can't be zero at a time.
28.11.2024 22:09
Slightly better way to write RagvaloD's argument: Consider sums $S(\boldsymbol{c}):=\textstyle \sum_{1\le i\le 11}c(i) a_i$, where $\boldsymbol{c} = (c(i):1\le i\le 11)\in\{0,1\}^{11}$. As $2^{11}>2024$, there exists two distinct $\boldsymbol{c}_1,\boldsymbol{c}_2\in\{0,1\}^{11}$ for which $S(\boldsymbol{c}_1)\equiv S(\boldsymbol{c}_2)\pmod{2024}$. Now set $b_i = c_1(i) - c_2(i)$ for $1\le i\le 11$. Clearly $b_i\in\{-1,0,1\}$; moreover, not all $b_i$ are zero as $\boldsymbol{c}_1\ne \boldsymbol{c}_2$, completing the construction.