Let n1,…,nk be positive integers, and define d1=1 and di=(n1,…,ni−1)(n1,…,ni), for i∈{2,…,k}, where (m1,…,mℓ) denotes the greatest common divisor of the integers m1,…,mℓ. Prove that the sums k∑i=1aini with ai∈{1,…,di} for i∈{1,…,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.