Пираты алекс и боб сидят в темнице. им предстоит испытание: есть n стаканов, стоящих в ряд, причем k из них отравлены. узники будут по очереди (начиная с алекса) выпивать один из стаканов, и если они смогут выпить все неотравленные стаканы с водой, то их отпустят. в начале испытания знакомый стражник может сообщить алексу, в каких стаканах яд, но передать эту информацию бобу уже не удастся. пока испытание не началось, узники хотят придумать стратегию по обоих (n и k им известны).
Будем считать, что за последним стаканом в ряду следует первый, т.е. ряд стаканов можно представлять себе расставленным по окружности. При k=1 и любом n, есть стратегия если занумеровать стаканы на окружности, допустим, по часовой стрелке, считая, что отравленный стакан имеет номер 1, то первых ходом Алекс пьет 2-ой стакан, затем Боб пьет 3-ий, Алекс - 4-ый и т.д. Так, двигаясь по кругу, они выпьют все "чистые" стаканы и будут
При k=2 и любом нечетном n также есть стратегия два отравленных стакана делят окружность на две дуги из подряд идущих "чистых" стаканов. Причем в одной дуге обязательно четное количество стаканов, а в другой нечетное. Перед началом, Алекс и Боб договариваются, что Боб всегда пьет стакан следующий за стаканом Алекса по ходу часовой стрелки. Тогда Алекс начинает с первого стакана в "четной" дуге, они по очереди выпивают все стаканы на этой дуге. Последний стакан в "четной" дуге выпивает Боб, и следующим ходом Алекс выпивает первый стакан в "нечетной" дуге. Боб, соответственно, пьет соседний и т.д. - так они выпивают все "чистые" стаканы. Если два отравленных стакана стояли рядом (т.е. всего одна дуга), то стратегия сохраняется и действует как в случае с k=1. Алекс начинает с первого не отравленного стакана в дуге. Боб пьет соседний. и т.д.
Также, понятно, что в случае n=2 и k=2 нет стратегии Все возможные расстановки стаканов по окружности сводятся к расстановке 1100 или 1010 (0 - чистый стакан, 1 - отравленный). Первым ходом Алекс обязан выбрать 0, а следующим ходом Боб должен взять либо соседний стакан, либо "прыгнуть" через один, причем ошибиться он не должен. Т.е. совершив только первый ход, Алекс должен как-то сообщить Бобу о конфигурации отравленных стаканов. Но т.к. отравленные стаканы неотличимы от обычных, то первый ход никак не может что-то сказать о положении отравленных стаканов.
Если k не велико по сравнению с n, то также есть стратегия Я ее опишу в общих чертах. На окружности обязательно есть непрерывная дуга из неотравленных стаканов длиной не меньше [n/k]-1 стаканов, (а если k не делит n, то как минимум из [n/k] стаканов). Количество непрерывных дуг из неотравленных стаканов не превосходит k, поэтому, если k<[n/k]-1 (т.е. k<=(√n)-1), то Алекс и Боб могут договориться так, что первым ходом Алекс обозначает начало самой длинной чистой дуги, Боб последовательно стакан за стаканом "выпивает" эту дугу, а Алекс в свои ходы выпивает все одиночные неотравленные стаканы (т.е. неотравленные дуги длиной 1) и пьет по одному допустим первому стакану из всех дуг нечетной длины. После того, как все дуги стали четными, кроме быть может одной, Алекс выпивает стакан вплотную к стакану Бобу (который еще не допил самую длинную неотравленную дугу, т.к. ее длина была достаточно велика), и это является сигналом для Боба, что теперь он начинает следовать стратегии как в случае k=2 - выпивать стакан следующий за стаканом Алекса. Т.к. все чистые дуги теперь имеют четную длину, кроме быть может одной, то они благополучно выпивают все чистые стаканы. Одну нечетную дугу, если таковая имеется, Алекс оставляет напоследок, и в ней последний неотравленный стакан он выпивает сам.
Наверняка, здесь есть какие-то более удачные стратегии, но пока придумалось только это.