|
|
 |
Условие
Две фирмы по очереди нанимают программистов, среди которых есть 11 гениев. Первого программиста каждая фирма выбирает произвольно, а каждый следующий должен быть знаком с кем-то из ранее нанятых данной фирмой. Если фирма не может нанять программиста по этим правилам, она прекращает приём, а другая может продолжать. Список программистов и их знакомств заранее известен, включая информацию о том, кто гении. Могут ли знакомства быть устроены так, что фирма, вступающая в игру второй, сможет нанять 10 гениев, как бы ни действовала первая фирма?
Решение 1
Пусть множество программистов описывается множеством всевозможных строк из 11 неотрицательных целых чисел с суммой 100. Гении – те, у кого все эти числа, кроме одного – нулевые (а ненулевая равна 100). Ясно, что гениев ровно 11. Объявим знакомыми тех, у которых две "координаты" отличаются на 1 (одна больше, другая меньше на 1), а остальные совпадают.Покажем, как Второй фирме нанять 10 гениев. Пусть A = (A1, A2, ..., A11) – первый программист, нанятый Первой фирмой. В этой строке есть число не меньше 10 (пусть это A11). Тогда Вторая фирма нанимает программиста B = (A1 + 1, A2 + 1, ..., A10 + 1, A11 – 10).
Пусть Mi = max Ci по всем строкам программистов С, нанятых на данный момент Второй фирмой, а mi – то же, но для Первой фирмы. Наняв B, Вторая фирма обеспечила неравенство Mi > mi для каждого i ≤ 10. Если Вторая фирма сможет поддерживать своими ходами такие неравенства, то она раньше Первой фирмы достигнет Mi = 100 (при всех i ≤ 10), то есть наймёт тем самым 10 гениев. Покажем, почему это возможно.
Из-за необходимости нанимать знакомых Первая фирма может на каждом ходу увеличить не более одного из чисел mi (i ≤ 10), причём не больше чем на 1, то есть только одно из mi может "догнать" Mi. Пусть такое равенство случилось, и Mi = mi = d < 100. Значит, Второй фирмой уже нанята строка S с Si = d. Так как d < 100,
Sj > 0 для некоторого j ≠ i. Пусть T – знакомый S, у которого Ti = Si + 1, Tj = Sj – 1. Так как Ti > d, T еще никем не нанят. Наняв T, Вторая фирма увеличит Mi и восстановит неравенство Mi > mi.
Равенство mi = Mi = 100 невозможно, так как i-я "кордината" равна 100 только у одной строки.
Если равенства не случилось, то Вторая фирма может ответным ходом увеличить на 1 любое Mi < 100 (для i ≤ 10). Если таких Mi нет, то 10 гениев уже наняты.
Решение 2
Кроме гениев G1, ..., G11 рассмотрим 11 ключевых программистов K1, ..., K11. Соединим каждую пару (Gi, Kj) цепочкой из 70 + rij рядовых программистов, где rij – остаток от деления i – j на 11 ("внутренние" члены цепочек знакомы только с двумя своими соседями по цепочке).
Покажем как действовать Второй фирме. У первой фирмы есть три варианта первого хода.
1) Первая фирма нанимает одного из ключевых программистов (например, K1). Тогда Вторая фирма нанимает K2, который находится ближе к G2, ..., G11, чем K1. Поэтому если Первая фирма пытается двигаться по "своим" цепочкам к одному из этих гениев, то Вторая, двигаясь к тем же гениям, её опережает. Если же Первая двигается к G1 (до него – 71 ход), то Вторая использует это время для уменьшения всех "расстояний" до остальных гениев до 70 (для этого ей нужно не более 2 + ... + 11 = 65 ходов). Поэтому гораздо раньше, чем Первая сможет использовать ведущие к гениям более короткие цепочки, Вторая будет её опережать на 10 "направлениях".
2) Первая фирма нанимает гения (G1). Тогда Вторая нанимает K1. Прежде, чем Первая фирма сможет нанять ключевого программиста (только через него можно выйти на другого гения), Вторая, как и в 1-м случае, сможет укоротить 10 цепочек до 70 и снова опередит Первую.
3) Первая фирма нанимает рядового программиста из цепочки, соединяющей K1 с Gi. Тогда Вторая нанимает K1. Первой остаётся только двигаться к Gi, и получается ухудшенный (для Первой) 2-й случай.
Ответ
Могут.
Замечания
1. 11 баллов.
2. См. также задачу 116225 из Московской олимпиады для четырёх гениев.
3. См. также задачу М2230 из Задачника "Кванта" ("Квант", 2011, №4).
