Maths Olympiad Prep

Library / /61 of 61

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it Ukraine

Eleven linguists were instructed to learn eleven foreign languages (initially, none of the linguists knew any of those languages). It became necessary to invite a Foreign Consultant who is able to teach (by means of hypnosis, of course!) any two linguists any two languages during one session (so that each one of those two linguists learns each one of those two languages). What is the minimal number of sessions required to teach all the eleven linguists all the eleven languages (a linguist may attend a session even if he has learnt one of the appropriate languages already)?

Solution

Кожен лінгвіст має взяти участь щонайменше в 66 сеансах, інакше він не оволодіє всіма 1111 мовами. Оскільки в одному сеансі беруть участь два лінгвісти, то кількість сеансів не менша за 33=611233 = \frac{6 \cdot 11}{2}. Покажемо, що 3333 сеансів Консультантові насправді вистачить. Кожний сеанс будемо зображати у вигляді (a,bc,d)(a,b|c,d), де aa і bb — номери лінгвістів, cc і dd — номери мов (1a,b,c,d11)(1 \leq a,b,c,d \leq 11). Для 1k51 \leq k \leq 5 (2k1)(2k-1)-го й (2k)(2k)-го лінгвістів запрошуємо на сеанси (2k1,2k2l,2l+1)(2k-1,2k|2l,2l+1), де kl5k \leq l \leq 5. Маємо вже 5+4+3+2+1=155+4+3+2+1=15 сеансів. Далі, для кожного з цих сеансів розглянемо "доповняльний" для сеансу (a,bc,d)(a,b|c,d) розглянемо сеанс (12a,12b12c,12d)(12-a,12-b|12-c,12-d). Після цих 3030 сеансів лінгвісти з парними номерами опанують усі 1111 мов, а лінгвісти з непарними номерами опанують усі мови, номер яких не співпадає з номером відповідного лінгвіста. Отже, потрібні ще такі сеанси (4m3,4m14m3,4m1)(4m-3,4m-1|4m-3,4m-1), 1m31 \leq m \leq 3.

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.