Maths Olympiad Prep

Library / /216 of 299

Combinatorics Difficulty 6.9 National Olympiad Prove it Iran

There are 1111 men sitting around a circular table with equal distances and 1111 cards with numbers 1,2,,111,2,\ldots,11 on them are dealt among them. It is possible that one has no cards and the other has more than one. In each step one can give one of his cards to his adjacent individual if the card number ii has the following property: before and after this stage, the places of the cards with numbers i1i-1, ii and i+1i+1 are not the vertices of an acute-angled triangle. (card 00 is the same as card 1111, and card 1212 is the same as card 11) At the beginning the cards 11 to 1111 are dealt among them counter-clockwise. (everyone has exactly one card) Prove that there will never be a man who has all the cards.

Solution

First divide the table into 1111 equal arcs. Now if the cards i,ji, j be on the points A,BA, B on the table, we define the distance between these two cards as the number of arcs between A,BA, B on the table (the smaller one). For example, the distance between i,ji, j is 55 in the following figure:

Figure 1

Now, after each step we sum the distances between every two cards with consecutive numbers. Easily it can be proved that after each step this sum either remains invariant or varies by 22. Because if the place of card ii is between i1i-1 and i+1i+1, this sum doesn't change, otherwise it changes by 22. So the parity of this sum remains invariant. At first it is odd (=11= 11), and if they are all in one place this sum would be even, so it is impossible.

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.