Competition problem — Combinatorics

Library / /15 of 19

Combinatorics Difficulty 6.9 National Olympiad Prove it Canada

The integers $1$ , $2$ , $3$ , $\ldots$ , $2016$ are written on a board. You can choose any two numbers on the board and replace them with their average. For example, you can replace $1$ and $2$ with $1.5$ , or you can replace $1$ and $3$ with a second copy of $2$ . After $2015$ replacements of this kind, the board will have only one number left on it.

a. Prove that there is a sequence of replacements that will make the final number equal to $2$ .

b. Prove that there is a sequence of replacements that will make the final number equal to $1000$ .

Solution

a.
First replace $2014$ and $2016$ with $2015$ , and then replace the two copies of $2015$ with a single copy. This leaves us with $\{1, 2, \ldots, 2013, 2015\}$ . From here, we can replace $2013$ and $2015$ with $2014$ to get $\{1, 2, \ldots, 2012, 2014\}$ . We can then replace $2012$ and $2014$ with $2013$ , and so on, until we eventually get to $\{1, 3\}$ . We finish by replacing $1$ and $3$ with $2$ .

b.
Using the same construction as in (a), we can find a sequence of replacements that reduces $\{a, a + 1, \ldots, b\}$ to just $\{a + 1\}$ . Similarly, we can also find a sequence of replacements that reduces $\{a, a + 1, \ldots, b\}$ to just $\{b - 1\}$ .

In particular, we can find sequences of replacements that reduce $\{1, 2, \ldots, 999\}$ to just $\{998\}$ , and that reduce $\{1001, 1002, \ldots, 2016\}$ to just $\{1002\}$ . This leaves us with $\{998, 1000, 1002\}$ . We can replace $998$ and $1002$ with a second copy of $1000$ , and then replace the two copies of $1000$ with a single copy to complete the construction.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.