Олимпиадная задача: Можно ли второй фирме забрать 10 гениев среди программистов?

Решение 1:  Пусть множество программистов описывается множеством всевозможных строк из 11 неотрицательных целых чисел с суммой 100. Гении – те, у кого все эти числа, кроме одного – нулевые (а ненулевая равна 100). Ясно, что гениев ровно 11. Объявим знакомыми тех, у которых две "координаты" отличаются на 1 (одна больше, другая меньше на 1), а остальные совпадают.   Покажем, как Второй фирме нанять 10 гениев. Пусть  A= (A₁,A₂, ...,A₁₁)  – первый программист, нанятый Первой фирмой. В этой строке есть число не меньше 10 (пусть этоA₁₁). Тогда Вторая фирма нанимает программиста  B= (A₁+ 1,A₂+ 1, ...,A₁₀+ 1,A₁₁– 10).   Пусть  M_i= maxC_i  по всем строкам программистовС, нанятых на данный момент Второй фирмой, аm_i– то же, но для Первой фирмы. НанявB, Вторая фирма обеспечила неравенство  M_i > m_i  для каждого  i≤ 10.  Если Вторая фирма сможет поддерживать своими ходами такие неравенства, то она раньше Первой фирмы достигнет  M_i= 100  (при всех  i≤ 10),  то есть наймёт тем самым 10 гениев. Покажем, почему это возможно.   Из-за необходимости нанимать знакомых Первая фирма может на каждом ходу увеличить не более одного из чиселm_i (i≤ 10),  причём не больше чем на 1, то есть только одно изm_iможет "догнать"M_i. Пусть такое равенство случилось, и  M_i = m_i = d< 100.  Значит, Второй фирмой уже нанята строкаSс  S_i = d.  Так как  d< 100, S_j> 0  для некоторого  j ≠ i.  ПустьT– знакомыйS, у которого  T_i = S_i+ 1, T_j = S_j– 1.  Так как  T_i > d,  Tеще никем не нанят. НанявT, Вторая фирма увеличитM_iи восстановит неравенствоM_i > m_i.   Равенство  m_i = M_i= 100  невозможно, так какi-я "кордината" равна 100 только у одной строки.   Если равенства не случилось, то Вторая фирма может ответным ходом увеличить на 1 любое  M_i< 100  (для  i≤ 10).  Если такихM_iнет, то 10 гениев уже наняты.

Решение 2:   Кроме гениев G₁, ..., G₁₁ рассмотрим 11 ключевых программистов K₁, ..., K₁₁. Соединим каждую пару  (G_i, K_j)  цепочкой из  70 + r_ij  рядовых программистов, где r_ij – остаток от деления  i – j  на 11 ("внутренние" члены цепочек знакомы только с двумя своими соседями по цепочке).

  Покажем как действовать Второй фирме. У первой фирмы есть три варианта первого хода.

  1) Первая фирма нанимает одного из ключевых программистов (например, K₁). Тогда Вторая фирма нанимает K₂, который находится ближе к G₂, ..., G₁₁, чем K₁. Поэтому если Первая фирма пытается двигаться по "своим" цепочкам к одному из этих гениев, то Вторая, двигаясь к тем же гениям, её опережает. Если же Первая двигается к G₁ (до него – 71 ход), то Вторая использует это время для уменьшения всех "расстояний" до остальных гениев до 70 (для этого ей нужно не более  2 + ... + 11 = 65 ходов).  Поэтому гораздо раньше, чем Первая сможет использовать ведущие к гениям более короткие цепочки, Вторая будет её опережать на 10 "направлениях".

  2) Первая фирма нанимает гения (G₁). Тогда Вторая нанимает K₁. Прежде, чем Первая фирма сможет нанять ключевого программиста (только через него можно выйти на другого гения), Вторая, как и в 1-м случае, сможет укоротить 10 цепочек до 70 и снова опередит Первую.

  3) Первая фирма нанимает рядового программиста из цепочки, соединяющей K₁ с G_i. Тогда Вторая нанимает K₁. Первой остаётся только двигаться к G_i, и получается ухудшенный (для Первой) 2-й случай.

Могут.