Problem #PRU-78578

Problems Number Theory Divisibility Division with remainders. Arithmetic of remainders Arithmetic of remainders Methods Pigeonhole principle Pigeonhole principle (other) Proof by contradiction
 13–15  3.0

Problem

All integers from 1 to 2n are written in a row. Then, to each number, the number of its place in the row is added, that is, to the first number 1 is added, to the second – 2, and so on.

Prove that among the sums obtained there are at least two that give the same remainder when divided by 2n.