Пираты алекс и боб сидят в темнице. им предстоит испытание: есть n стаканов, стоящих в ряд, причем k из них отравлены. узники будут по очереди (начиная с алекса) выпивать один из стаканов, и если они смогут выпить все неотравленные стаканы с водой, то их отпустят. в начале испытания знакомый стражник может сообщить алексу, в каких стаканах яд, но передать эту информацию бобу уже не удастся. пока испытание не началось, узники хотят придумать стратегию по спасению обоих (n и k им известны).

238

246

Посмотреть ответы 2

Ответы на вопрос:

Mooz

Математика

4,6(13 оценок)

Для произвольных 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 - выпивать стакан следующий за стаканом алекса. т.к. все чистые дуги теперь имеют четную длину, кроме быть может одной, то они благополучно выпивают все чистые стаканы. одну нечетную дугу, если таковая имеется, алекс оставляет напоследок, и в ней последний неотравленный стакан он выпивает сам. наверняка, здесь есть какие-то более удачные стратегии, но пока придумалось только это.

новинький2

Математика

4,5(30 оценок)

28 рубля

Пошаговое объяснение:

(24+27+33):3

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Математика

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.