The numbers from $1$ to $2000^2$ were written on a board. Vasya choose $2000$ of them whose sum of them equal to two thousandth of the sum of all numbers. Proof that his friend, Petya, will be able to color each of the remaining numbers by one of other $1999$ colors so that the sum of numbers with each of total $2000$ colors are the same.
Problem
Source: St. Petersburg MO 2017 Grade 10 P4
Tags: number theory, combinatorics
Pinko
03.05.2018 15:11
The solution is on 2 rows: We will call two numbers "reflective" if their sum is 2000^2+1. As the number of numbers is even then each number has a "reflective" one. Another thing that we notice is that the sum of 1000 pairs of "reflective" numbers is exactly 1/2000 of the whole sum. So basically what we need to proof is that if Vasya hasn't taken only"reflective" pairs (Let's say that Vasya colored them in color A) then Petya can make a row from all the remaining numbers with their "reflective" number colored in A and if needed, add some"reflective" pairs (that is if Vasya has colored some "reflective pairs in color A). Let's say that Vasya colored K "reflective" pairs in color A and colored Y numbers in color A without their "reflective" one being in the same color. Here 2*K+Y=2000. We know that their sum is 1/2000 of S (With S we denote the sum of all numbers). Now Petya will color all the numbers, with their "reflective" one in color A, in color B and color another K "reflective" pairs in the same color. We get again 2*K+Y=2000. Now let's sum these 2 rows: We have 4000 numbers and 2000 "reflective" pairs, so we know that their sum will be 2/2000 of S. But the sum of the numbers of Vasya's row is 1/2000 of S => the sum of the number's of Petya's row is 1/2000 of S. Now all that Petya needs to do is to construct 1998 rows, where each row consists of 1000 "reflective" pairs.