|
Название задачи: Паук и бабочка. |
 |
Условие
Паук в лесу сплёл паутину. Длинные нити привязал к веткам. И в эту паутину залетела бабочка. За один ход бабочка или паук могут передвинуться по отрезку нити в соседнюю точку пересечения нитей; бабочка также может выбраться на конец нити (ветку), если перед этим находилась в соседней точке пересечения. Они ходят по очереди, начинает бабочка. Если бабочка смогла добраться до веток, она спаслась (это её победа). Если паук добрался до бабочки, он её съедает (и это его победа). Возможен и такой исход, когда никто не побеждает, а игра длится бесконечно.
б) Чем закончится игра, если колец три, а радиусов семь?
в) Чем закончится игра, если колец четыре, а радиусов десять?
г) Разберите общий случай: K ≥ 2 колец и R ≥ 3 радиусов.
Решение
г) Заметим, что у бабочки всегда есть ничейная стратегия. Она состоит в том, что бабочка делает ход по своему кольцу в сторону от паука. При R > 3 очевидно, что пауку надо делать ход по своему кольцу в ту же сторону, иначе бабочка выходит по тому радиусу, на котором сейчас находится. При этом положение членистоногих относительно паутины и друг относительно друга не
меняется, поэтому бабочка снова может сделать аналогичный ход, и так далее до бесконечности.
При R = 3 у паука есть ещё один ход – по своему кольцу в противоположную сторону, когда он оказывается на одном радиусе с бабочкой. Но и тогда бабочку он не поймает. Та делает ход в любую сторону по своему кольцу, паук – по своему (идти вглубь паутины он не может – упускает бабочку), и так до бесконечности.
Рассмотрим следующую стратегию бабочки: двигаться в центр паутины, а потом уходить по радиусу, наиболее удалённому от паука. При этом паук через центр её не догонит (отстаёт по крайней мере на ход), а перехватить, двигаясь по кольцу (естественно, наружному, остальные менее выгодны), сможет только если ему хватит ходов. Это будет при K ≥ R/2 при чётном R и при K ≥ R–1/2 при нечётном R.
Пусть такое неравенство выполнено. Если бабочка двигается по своему кольцу, паук преследует её, не давая вылететь. Как только бабочка делает ход к центру паутины, паук встаёт на её радиус. Далее он сохраняет это свойство по отношению к ней (например, перемещаясь со внешнего кольца на следующее и обратно), тем самым, не давая ей вылететь, пока бабочка не попадает в центр (тут пауку надо выйти на внешнее кольцо, а если он на нём – сместиться по нему куда
угодно). Далее пауку нужно посмотреть, куда двинулась бабочка, и идти ей наперехват по внешнему кольцу (в ту сторону, где путь короче). Вскоре они снова окажутся на одном радиусе (если бабочка будет двигаться не только наружу, она тем более потеряет время, если снова вернётся в центр – паук должен снова действовать так, как описано выше). Далее действия паука повторяются. Итак, в этом случае никто не имеет выигрышной стратегии.
Ответ
а), б) Ничья; в) бабочка выиграет; г) при K ≥ [R/2] ничья, в остальных случаях бабочка выиграет.
