Maths Olympiad Prep

Library / /186 of 189

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 nn opens doors with number mm if and only if m≠nm \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 cells. 16 + 8 + 5 + 4 + 3 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 50 \text{ cells.}

12345678910111213141516
16123456789101112131415
15161234567891011121314
14151612345678910111213
13141516123456789101112
12131415161234567891011
11121314151612345678910
10111213141516123456789
91011121314151612345678
89101112131415161234567
78910111213141516123456
67891011121314151612345
56789101112131415161234
45678910111213141516123
34567891011121314151612
23456789101112131415161

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.

12345678910111213141516
16123456789101112131415
15161234567891011121314
14151612345678910111213
13141516123456789101112
12131415161234567891011
11121314151612345678910
10111213141516123456789
91011121314151612345678
89101112131415161234567
78910111213141516123456
67891011121314151612345
56789101112131415161234
45678910111213141516123
34567891011121314151612
23456789101112131415161
No of key2412836116149751511

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.

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.