Maths Olympiad Prep

Library / /31 of 32

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Netherlands

In a room there are 20232023 vases numbered from 11 to 20232023. In each vase we want to put a note with a positive integer from 1,2,,20231, 2, \ldots, 2023 on it. The numbers on the notes do not necessarily have to be distinct. The following should now apply to each vase. Look at the note inside the vase, find the (not necessarily different) vase with the number written on the note, and look at the note inside this vase. Then the average of the numbers on the two notes must be exactly equal to the number of the first selected vase. For example, if we put a note with the number 55 in vase 1313, then vase 55 should contain a note with the number 2121 on it: after all, the average of 55 and 2121 is 1313.

Determine all possible ways to provide each vase with a note.

Solution

A possible way to provide each vase with a note is to put in vase 11 a note with 11, in vase 22 a note with 22, in vase 33 a note with 33, \ldots, and in vase 20232023 a note with 20232023. We will use induction to show that this is the only distribution. Note that for a valid distribution it does not matter in which order we fill the vases.

Take a look at vase 11. Suppose we put a note in it with aa. Then in vase aa we put a note with bb, such that (a+b)/2=1(a + b)/2 = 1 or a+b=2a + b = 2. Since aa and bb are positive integers, it must hold that a=b=1a = b = 1. So the two vases here were the same and vase 11 contains a note with 11.

For the induction step, we assume that the first n1n-1 vases each contain a note with the number of the vase. We want to show that in vase nn we have to put a note with nn. Suppose in vase nn we put a note with aa. If a<na < n, then vase aa also contains a note with aa because of the induction hypothesis. It must then hold that (a+a)/2=n(a+a)/2 = n, but this contradicts a<na < n. We conclude that ana \ge n.
If a>na > n, we do not know yet which number has to go on the note in vase aa. Call this number bb. Then it must hold that (a+b)/2=n(a+b)/2 = n, and so b<nb < n. But then we find a contradiction if we were to consider vase aa first: in it we find a note with bb, and in vase bb we then find, because of the induction hypothesis, another note with bb. However, (b+b)/2a(b+b)/2 \ne a, because a>na > n and b<nb < n.
We conclude that a=na = n must hold: in vase nn we also put a note with nn on it. Induction now gives that in each vase we put a note with the number of the vase on it. So this is the only possible distribution of the notes.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.