Let $n_1,\ldots,n_k$ be positive integers, and define $d_1=1$ and $d_i=\frac{(n_1,\ldots,n_{i-1})}{(n_1,\ldots,n_{i})}$, for $i\in \{2,\ldots,k\}$, where $(m_1,\ldots,m_{\ell})$ denotes the greatest common divisor of the integers $m_1,\ldots,m_{\ell}$. Prove that the sums \[\sum_{i=1}^k a_in_i\] with $a_i\in\{1,\ldots,d_i\}$ for $i\in\{1,\ldots,k\}$ are mutually distinct $\mod n_1$.
Problem
Source: Romania TST 1 2012, Problem 1
Tags: induction, number theory, greatest common divisor, geometry, number theory proposed
03.05.2012 18:59
I will assume $d_i = \frac{\gcd(n_1,n_2,...,n_{i-1})}{\gcd(n_1,n_2,...,n_i)}$. WLOG let $\gcd(n_1,n_2,...,n_k) = 1$ (dividing every number by a constant clearly does not change the problem) So let's prove this problem by induction on $k$. The base case of $k=1$ is obviously true since there is only one sum $a_1$. Suppose the problem holds for all $k \le M-1$. I claim it holds for $k=M$ then. To show this, first suppose $d_M = 1$. But then the problem is obviously true, because the sum is simply $\sum_{i=1}^{M-1} a_in_i + n_M$ which are distinct modulo $n_1$ by the inductive hypothesis on $k=M-1$. Hence suppose $d_M$ is not $1$. This means that since $\gcd(n_1,n_2,...,n_k) = 1$, we have $\gcd(n_1,n_2,...,n_{k-1})$ is not one. Call the gcd $z$. Then our sum is: $z \sum_{i=1}^{M-1} \left ( \frac{n_i}{z} \right )a_i + a_Mn_M$ where $1 \le d_M \le z$. Suppose two of these sums are equivalent modulo $n_1$. This means that $z$ must divide their difference. As $z$ divides the first terms, it follows we need $z|(a_M - b_M)n_M$ where $a_M, b_M$ are the coefficients on $n_M$ in each summation. But as $\gcd(z,n_M) = 1$ it follows $z|(a_M - b_M) \implies a_M = b_M$. Hence two summations are equivalent modulo $n_1$ iff the summation of the first $M-1$ $a_in_i$ terms are equivalent modulo $n_1$. However, by the inductive hypothesis this never happens and thus we are done.
03.05.2012 19:28
Let $\gcd(n_1, \ldots, n_k) = c$ and $\gcd(n_1, \ldots, n_{k-1} ) = rc$. We will induct on $k$. The case $k=2$ is easy. Assume on the contrary that $\sum_{i=1}^{k} a_i n_i \equiv \sum_{i=1}^{k} a'_i n_i \mod n_1$. Define for all $i$, $\alpha_i = a_i - a'_i$. So we need $\sum_{i=1}^{k-1}\alpha_in_i \equiv cr\left ( \sum_{i=1}^{k-1} \alpha_i t_i \right ) + \alpha_n n_k \equiv 0 \mod n_1$. So $r\left ( \sum_{i=1}^{k-1} \alpha_i t_i \right ) + \alpha_n \frac{n_k}{c} \equiv 0 \mod r$. So $r \mid \alpha_n$(Since $\gcd(\frac{n_k}{c}, r)=1)$. But $|\alpha_n| < r$. So $\alpha_n = 0$. So we must have $\sum_{i=1}^{k-1} a_i n_i \equiv \sum_{i=1}^{k-1} a'_i n_i \mod n_1$, which is impossible from inductive hypothesis. So done.
06.05.2012 19:48
Dinoboy, this is exactly the solution i gave during the tst, for which i got 0p
06.05.2012 23:36
paul1703 wrote: Dinoboy, this is exactly the solution i gave during the tst, for which i got 0p Clearly either you wrote it wrong, or the graders were incompetent
07.05.2012 00:03
Sadly, dinoboy, I think it's the second variant . Anyway, don't worry Paul, because ALL the papers from the first test are going to be checked again (Mr. Gologan said that).
08.05.2012 23:10
is it ok? suppose that there exist two sets of numbers $ a_{1},a_{2},....,a_{k} $ and $ b_{1},b_{2},...,b_{k} $ such that the defined sums for these ones are congruent modulo $ n_{1} $. note $ c_{i}=b_{i}-a_{i} $. then $ n_{1} $ divides $ c_{1}n_{1}+...+c_{k}n_{k} $. but $ d_{k} $ divides $ n_{1},...,n_{k-1} $ and is coprime with $ n_{k} $ so this divides $ c_{k} $. but this number has the modulus strictly smaller than $ d_{k} $ so $c_{k}=0$. in a similar way we obtain that $ c_{i}=0 $ for $ i=2,3,...,k $. but $ a_{1}=b_{1}=1 $ so the initial sets are equal. that means that every two sets are different modulo $ n_{1} $.
09.05.2012 21:46
Yes, it is corect. In the contest, I gave only a more detailed version of your solution .
10.05.2012 01:50
Actually, this very attempt at a solution, in even more detail and precision, was first marked a $4$ out of $7$, only later to be downgraded to a $2$ out of $7$. The flaw is that the claim "$ d_{k} $ ... is coprime with $ n_{k} $" may in general be false; it is true though that $ d_{k} $ is coprime with $ \frac {n_{k}} {(n_1,n_2,\ldots,n_{k})} $, and that is enough for a full proof (similar reasoning for $d_j$, $2\leq j \leq k-1$). Quite a harsh grading scheme, eh? What do you think, Drytime?
10.05.2012 17:45
Indeed, it is quite harsh. I remember that last year we had a "beautiful" geometry problem (probably it would be fairer to call it an algebra problem) in which $2$ or $3$ points were given only to check that three simple equations in $a$, $b$ and $c$ were linearly dependent. But the grading scheme for this problem is not only harsh, but also unfair.
15.01.2015 14:28
Pardon me but I do not think it is unfair.In fact it is not even harsh and I would be one of the happiest persons if checking here in our country is "unfair" like this.
16.01.2015 00:26
Any grading scheme that does not reward good ideas, and nitpicks on foibles wich could be (easily) repaired, is harsh - and unfair. Most of the seminal mathematical original papers where chockfull of computational errors and "holes", but what mattered most was the breakthrough idea(s).
09.05.2019 11:50
WLOG assume that $d_k\neq 1.$ Suppose that $\sum_{i=1}^k{a_in_i} \equiv\sum_{i=1}^k{b_in_i} \pmod{n_1}$ for some $a_i$'s and $b_i$'s. Denote by $c_i=a_i-b_i$. Note that $\mid c_i \mid<d_i,$ this implies that $d_{k-1}$ can't divide $c_kn_k,$ unless $c_k=0.$ However $d_{k-1}$ divides $n_1$ and $c_in_i$ for any $i<k,$ implying that $c_k=0.$ Similarly we get that $c_i=0$ for any other $i,$ hence the conclusion.