|
|
 |
Условие
Две фирмы по очереди нанимают программистов, среди которых есть 4 гения. Первого программиста каждая фирма выбирает произвольно, а каждый следующий должен быть знаком с кем-то из ранее нанятых данной фирмой. Если фирма не может нанять программиста по этим правилам, она прекращает приём, а другая может продолжать. Список программистов и их знакомств заранее известен. Могут ли знакомства быть устроены так, что фирма, вступающая в игру второй, сможет нанять по крайней мере 3 гениев, как бы ни действовала первая фирма?
Решение
Обозначим гениев через G0, G1, G2, G3. Пусть имеются ещё 4 программиста F0 , F1 , F2 , F3, которых мы будем называть "знаменитыми". Пусть каждый знаменитый программист Fi связан с каждым гением Gj цепочкой программистов
где программист Hi,jl знаком с программистом H i,jl+1, а число ki,j — длина цепочки. Пусть эти цепочки исчерпывают набор доступных программистов и существующих между ними знакомств. Мы утверждаем, что вторая фирма сможет гарантировать себе трёх гениев, если
Назовём расстоянием от фирмы до программиста минимальное количество ходов, которое требуется фирме на данном этапе, чтобы взять к себе на работу данного программиста. Опишем стратегию второй фирмы в трёх возможных случаях.
1. Первая фирма выбирает сначала одного из знаменитых программистов. Тогда вторая фирма должна выбрать такого знаменитого программиста, чтобы 3 гения из четырёх были ближе ко второй фирме, чем к первой. Например, если первая берёт F0, то вторая берёт F1 и становится ближе к G0, G1 и G2, чем первая.
2. Первая фирма вначале берёт гения (скажем, G3). Тогда вторая фирма берёт произвольного знаменитого программиста.
3. Первая фирма вначале берёт программиста из цепочки, соединяющей некоторого гения (скажем, G3) и некоторого знаменитого программиста Fi. Тогда вторая фирма берёт программиста Fi.
В обозначениях всех трёх описанных случаев вторая фирма может гарантировать себе гениев G0 , G1,G2, придерживаясь следующей тактики. Если на очередном шаге первая фирма берёт программиста из некоторой цепочки, ведущей к гению Gj, j ≤ 2, вторая фирма сокращает своё расстояние до гения Gj, выбирая очередного программиста из цепочки, ведущей к нему. В противном случае вторая фирма сокращает расстояние до того из трёх гениев, который от неё дальше (если таковых 2 или все 3, выбирает из них произвольно).
Нетрудно видеть, что после каждого хода второй фирмы гении G0, G1, G2 будут ближе ко второй фирме, чем к первой, а значит, первая фирма не сможет ими завладеть.
