Competition problem — Combinatorics

Library / /59 of 60

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Ukraine

Rounded tower has 16 doors, behind each there is a chest with gold of captain Flint. These doors are at equal distances to the neighboring ones, and are numbered clockwise from 1 to 16. 16 pirates come to the tower, each having a key, all keys are numbered from 1 to 16. It is known that key with number $n$ opens doors with number $m$ if and only if $m \neq n$ . Pirates stand one next to each door, but they do not know the number of the door they stand in front of. Jim Hawkins knows which pirate has which key and wants them to take as small an amount of chests with gold as possible. Jim can turn the tower so that doors are situated in front of pirates as he wants – but still all the numbers go clockwise 1-16 starting from some door. What is the maximum amount of chests with gold pirates can definitely take in such conditions?

(Bogdan Rublyov)

Solution

Consider some arrangement of keys. Then for every column there is a corresponding key. Paint gray all the cells of the column that can be opened by the corresponding key. In the column where there is key 2, 8 cells will be painted, where there is key 5 – 3 cells. In total there will be painted

$16 + 8 + 5 + 4 + 3 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 50 \text{ cells.}$

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|----|----|----|----|----|----|----|
| 16| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 15| 16| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 14| 15| 16| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 13| 14| 15| 16| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 12| 13| 14| 15| 16| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 11| 12| 13| 14| 15| 16| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 10| 11| 12| 13| 14| 15| 16| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 9 | 10| 11| 12| 13| 14| 15| 16| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 8 | 9 | 10| 11| 12| 13| 14| 15| 16| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16 | 1 | 2 | 3 | 4 | 5 | 6 |
| 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15 | 16 | 1 | 2 | 3 | 4 | 5 |
| 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14 | 15 | 16 | 1 | 2 | 3 | 4 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13 | 14 | 15 | 16 | 1 | 2 | 3 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12 | 13 | 14 | 15 | 16 | 1 | 2 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11 | 12 | 13 | 14 | 15 | 16 | 1 |

Fig. 43

As there are exactly 16 rows, so according to the Dirichlet's drawer principle there will be such that has not more than three gray cells. Then Jim can turn the tower in a way that corresponds to this row. In this case pirates can open at maximum 3 doors.

Fig. 44

If pirates stand with the keys, as shown in the last row of Fig. 44, they can always open at least three locks.

Looking for a route rather than 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.