Let $m,n,a_1,a_2,\dots,a_n$ be positive integers and $r$ be a real number. Prove that the equation \[\lfloor a_1x\rfloor+\lfloor a_2x\rfloor+\cdots+\lfloor a_nx\rfloor=sx+r\]has exactly $ms$ solutions in $x$, where $s=a_1+a_2+\cdots+a_n+\frac1m$. Linus Tang
Problem
Source: ELMO Shortlist 2024/A1
Tags: Elmo, algebra
23.06.2024 12:29
Apparently a good solution exists but here is the bad solution. In general, it should be true that the equation \[ a_1 \{ b_1x \} + a_2 \{b_2 x \} + \dots + a_n \{ b_n x \} + x = r \]has $a_1b_1 + a_2b_2 + \dots + a_nb_n + 1$ solutions. Consider the graph of \[ y = f(x) = m \cdot (\{ a_1x \} + \{ a_2x \} \dots + \{ a_nx \}) + x \]This consists of a bunch of line segments. Call the lower endpoint of each line segment the start, and the larger one the end. We show that this graph in fact consists of a finite number of families of line segments, such that when a line segment of one family ends, exactly one starts immediately there, combining to one whole line of slope $sm$. This then finishes because this forces $sm$ such lines greedily due to slope. The key claim are then that we have the same number of starts and ends. Claim: The $\varphi(a_i)$ fractional values of $f\left(\frac{1}{a_i}\right), \dots, f\left(\frac{a_i-1}{a_i}\right)$ consist of $\frac{\varphi(a_i)}{t}$ copies of the $\varphi(t)$ values $0, 1, \dots, \frac{t-1}{t}$ for some $t \mid \varphi(a_i)$. Proof. Note that \[ \{m \cdot (\{ a_1x \} + \{ a_2x \} \dots + \{ a_nx \}) + x\} = \{(m(a_1 + a_2 + \dots + a_n) + 1)x \} \]Then it remains to show that \[ (c \cdot \ell) \pmod{k}, (\gcd(\ell, k) = 1) \]remains as such $\pmod{\frac{k}{\gcd(c, k)}}$. This follows because the set $\{\ell\}$ is fixed under multiplication by some constant. $\blacksquare$ Claim: For $\varepsilon < \frac{1}{ma_1 \dots a_n}$, the $\varphi(a_i)$ fractional values of \[ f\left(\frac{1}{a_i} - \varepsilon\right) + sm\varepsilon, \dots, f\left(\frac{a_i-1}{a_i} - \varepsilon\right) + sm\varepsilon \]are in fact the exact same. Proof. Jumping integer values does not change the fractional values. $\blacksquare$ We now construct our broken lines as followed. Do the following for each $i$. Split the set $T_i = \{\frac{1}{a_i}, \dots, \frac{a_i-1}{a_i}\}$ into $t$ subsets $S_k$ which consisting of the $C = \frac{\varphi(a_i)}{t}$ values that map to $\frac{k}{t} \pmod{1}$ and so forth. Do the same for ends as $E_k$. Since $f(x) = x + 1$, there exist exactly $2C$ values $s_1 + m_1, s_2 + m_2, \dots, s_{C} + m_C$ and $e_1 + n_1, s_2 + n_2, \dots, s_{C} + n_C$ which are starts/ends in $T_i$ and have some fixed image $\frac{k}{t} + n_0$. where $m_i, n_i$ are some integers and $s_1, s_2, \dots$ is a fixed ordering. Then put the line segment with start $s_i + m_i$ with the line segment with end $e_i + n_i$ in the same family. Since every line segment's start or end is in some $T_i$, the result follows.
Attachments:

06.07.2024 15:21
Difficult than A3 The anwser(sketch) : 1/writ x in other form : x=(b-r)/s with b is an integer 2/prove that the possible number that b can take is exactly the number of residues mod (ms) Q. E. D
31.08.2024 23:49
Almost identical to 2023 OMMC Sample Set 2 Problem 2 Rewrite as $\{a_1x\}+\cdots+\{a_nx\}=-\frac1mx+r$, so if $y=\frac xm$, then $\{a_1my\}+\cdots+\{a_nmy\}=r-y$. The difference between the two sides is an integer plus $yms$, so $yms$ must be an integer, giving $ms$ different possible fractional parts $y$. Replacing $y$ with $y+1$ keeps the left side the same while the right side decreases by $1$, so each fractional part has exactly one possible value of $y$, giving a total of $ms$ different values of $y$, so there are exactly $ms$ solutions in $x$.
16.12.2024 22:08
Hamzaachak wrote: Difficult than A3 The anwser(sketch) : 1/writ x in other form : x=(b-r)/s with b is an integer 2/prove that the possible number that b can take is exactly the number of residues mod (ms) Q. E. D could you elaborate more on your solution since the hardest thing is to prove that the b forms the complete risidual set
09.01.2025 11:31
Let $R_{n}=\{x \in \mathbb{N} \mid 0 \leq x \leq n-1\}$ be the set of the remainder when dividing an integer by $n$, and let $r_{n}(x)$ be the remainder when dividing an integer $x$ by $n$. Replace $s$ by $a_{1}+a_{2}+\cdots+a_{n}+\frac{1}{m}$ in the original equation and using the property $\{x\}=x-\lfloor{x}\rfloor$ give us $$\{a_{1}x\}+\{a_{2}x\}+\cdots+\{a_{n}x\}=-\frac{x}{m}-r, (1)$$Let $a=\frac{x}{m}$, then from equation $(1)$, we have $$\{a_{1}ma\}+\{a_{2}ma\}+\cdots+\{a_{n}ma\}=-a-r, (2)$$Therefore $$a_{1}ma+a_{2}ma+\cdots+a_{n}ma+a+r \in \mathbb{Z}$$In other word, we have $$ams+r=a(a_{1}m+a_{2}m+\cdots+a_{n}m+1)+r \in \mathbb{Z}$$Let $b=ams+r \in \mathbb{Z}$, then we have $a=\frac{b-r}{ms}$ We have a property $$\{a\}=\left\{\frac{r_{ms}(b)-r}{ms}\right\}$$Since the expression of $(2)$ just varies in $\{a\}$, for each value of $r_{ms}(b)$, we get exactly one value of $\{a\}$ and from equation $(2)$ we get exactly one value of $a$, corresponds to exactly one value of $m$. From here, we concluded that the number of solutions for the original equation is equal to the number of elements in $R_{ms}$, which is equal to $ms$.