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.

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.

Dinoboy, this is exactly the solution i gave during the tst, for which i got 0p

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

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).

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} $.

Yes, it is corect. In the contest, I gave only a more detailed version of your solution .

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?

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.

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.

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).

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.