1
$\begingroup$

Assume that there are $n$ number of positive integers written on a paper. And the difference of any pair of those numbers is not divisible by $n$.

We erase two numbers and write the sum of them. If we repeat this until we get a single number, can we conclude the following statements?

  1. If $n$ is Odd, The final number we will get will be divisible by $n$.
  2. If $n$ is Even, After dividing The final number by $n$ the remainder will be $n/2$.
  3. There is a $n$ value that makes the final number less than ${n(n+1)}/2$.
$\endgroup$
2
  • $\begingroup$ The hypothesis tells us that the numbers are all different modulo $n$ $\endgroup$ – vadim123 Feb 16 '16 at 1:34
  • $\begingroup$ @vadim123 What's the mean of "different modulo n"? Can you explain it simply? $\endgroup$ – Tharindu Sathischandra Feb 16 '16 at 2:13
1
$\begingroup$

"Different modulo n", by definition means that the difference of no two of them is divisible by n. Equivalently, we can say that each one of them leaves a different remainder on division by $n$.

The hypothesis thus implies that the numbers are $$x_{1}\equiv0,x_{2}\equiv1,x_{3}\equiv2,...,x_{n}\equiv n-1 \mod n$$ (we "replace" each one of them by its remainder on division by $n$). Consequently, their sum reads: $$x_{1}+x_{2}+x_{3}+...+x_{n}\equiv \frac{(n-1)n}{2} \mod n$$ Thus:

  • If $n$ is odd, $n-1$ is even and thus $\frac{(n-1)n}{2}$ is divisible by $n$
  • If $n$ is even, $\frac{(n-1)n}{2}=\frac{(n-2)n}{2}+\frac{n}{2}\equiv\frac{n}{2}\mod n$, because $\frac{(n-2)n}{2}$ is divisible by $n$, since $n-2$ is even
  • Regarding the third statement, I do not think it is true: since the initial numbers are only specified $\mod n$, their sum is unbounded.
$\endgroup$
2
  • $\begingroup$ The answer seems like great. But I can't understand this part, $x_1≡0,x_2≡1,x_3≡2,...,x_n≡ n−1 mod n$ $\endgroup$ – Tharindu Sathischandra Feb 16 '16 at 9:29
  • 1
    $\begingroup$ The possible remaiders on division by $n$, are the $n$ integers $$0\leq r\leq n-1$$ So if we have $n$ numbers, such that, each one of them leaves a different remainder on division by $n$, the only possibility is that $$x_{1}\equiv0,x_{2}\equiv1,x_{3}\equiv2,...,x_{n}\equiv n-1 \mod n$$ (with a suitable rearrangement of the numbers) $\endgroup$ – KonKan Feb 16 '16 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.