В этой статье я хотел бы разобрать одну интересную задачку, для решения которой вполне достаточно знаний школьника 8-го класса.
В тихом океане есть загадочный остров, на котором растут только кусты с ягодами. На этот остров поместили 111 львов и одну козу. Львы могут прожить, питаясь только ягодами, но с куда большим удовольствием они предпочли бы съесть козу. Предположим:
А) за один раз один лев может съесть одну козу, и после того, как он съест козу, он сам превращается в козу.
Б) все львы умные и абсолютно рациональные, и хотят выжить.
Подумайте немного над этой задачей самостоятельно. А чтобы вы не сразу начали читать решение, я добавлю картинку... :)
Решение:
Первоначальное и чисто интуитивное рассуждение наталкивает на мысль, что козу никто есть не будет в любом случае. Потому что что каждый лев, кто съест козу, сам превратится в козу, которую съедят, а следовательно лев (уже в теле козы) не выживет.
Однако, не всё так просто. Как и всегда бывает в таких задачках.
Задачу можно отнести к рекурсивным вопросам. Потому что текущее состояние и выбор львов зависит от того, к чему приведет их выбор в случае решительного поедания бедной козы. Почему так происходит? Чтобы разобраться, начнем с самой простой ситуации.
Случай 1. У нас есть 1 лев и 1 коза. Лев благополучно ест козу, превращается в козу, становится единственной козой на острове, поэтому в любом случае выживает. Получается, что для случая "1 лев и 1 коза" -> козу съедят.
Случай 2. У нас есть 2 льва и 1 коза. Каждый лев, если он умный (как в условии задачи), должен просчитать, что если он съест козу, то превратится сам в козу, которая останется наедине с другим одним львом. Т.е. получаем ситуацию из случая 1, когда "1 лев и 1 коза", где козу точно съедят. Итак, это понимают оба льва. Поэтому они не будут есть козу. Получается, что для случая "2 льва и 1 коза" -> козу НЕ съедят.
Случай 3. У нас есть 3 льва и 1 коза. Каждый из трех львов просчитывает все ситуации подобно шахматным ходам, а значит, каждый лев понимает, что если он съест козу, то превратит "случай 3" в "случай 2", когда коза находится в безопасности, т.е. этому льву (уже в образе козы) ничего не будет грозить. Т.е. козу съест тот лев, кто быстрее до неё доберется. Поэтому для случая "3 льва и 1 коза" -> козу съедят.
Случай 4. Думаю, что вы уже догадывайтесь, что наши четыре умных льва понимают, что если кто-то решится съесть козу и превратиться в неё, то они окажутся в "случае 3", когда козу сразу же съедят. Поэтому для случая "4 льва и 1 коза" -> козу НЕ съедят.
Обобщая, мы получаем, что козу едят при нечетном количестве львов и оставляет в живых при четном количестве львов.
В нашем случае количество львов 111. 111 - нечетное число. Поэтому коза будет съедена первым львом, с которым она столкнется.
Очередная задачка, которая показывает, что не всё так просто, как кажется на первый взгляд. С другой стороны холодный просчет достигается довольно простыми рассуждениями.
