№4.* Бился Иван Царевич со Змеем Горынычем, трехглавым и трехвостым. Одним ударом он мог срубить либо одну голову, либо один хвост, либо две головы, либо два хвоста. Но, если срубить один хвост, то вырастут два, если срубить два хвоста — вырастет новая голова; если срубить голову — вырастет опять новая голова, а если срубить две головы, то не вырастет ничего. Сможет ли Иван Царевич срубить все головы и хвосты Змею Горынычу? Если да, то покажите, как. Если нет, то объясните, почему.

Да, сможет. Будем записывать количество голов и хвостов после каждого удара.

1. Срубить 2 головы: \((3,3)\to(1,3)\).
2. Срубить 1 хвост: \((1,3)\to(1,4)\).
3. Срубить 2 хвоста: \((1,4)\to(2,2)\).
4. Срубить 2 хвоста: \((2,2)\to(3,0)\).
5. Срубить 2 головы: \((3,0)\to(1,0)\).
6. Срубить 1 голову: \((1,0)\to(1,0)\).

Последовательность в пункте 6 не изменяет количество голов, поэтому повторять этот удар бессмысленно. Следовательно, такой путь не приводит к полному уничтожению. Проверим невозможность.

Рассмотрим чётность числа голов. Удар по одной голове уменьшает число голов на 1 и тут же добавляет 1, поэтому чётность не меняется. Удар по двум головам уменьшает число голов на 2, поэтому чётность также не меняется. Удары по хвостам либо не меняют число голов, либо при срубании двух хвостов добавляют одну голову, то есть меняют чётность числа голов на 1. Чтобы убрать все хвосты, нужно срубить нечётное число хвостов одиночными ударами или использовать удары по два хвоста; в любом случае после устранения хвостов число голов окажется нечётным. Удары по головам не изменяют эту чётность. Поэтому получить ноль голов невозможно.

Ответ: нет, Иван Царевич не сможет срубить все головы и хвосты.