Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1998/03/43.pdf Дата изменения: Fri Dec 23 19:24:35 2005 Дата индексирования: Tue Oct 2 00:27:18 2012 Кодировка: Windows-1251 Поисковые слова: р п р п р п р п р п р п р п

ИГРЫ

И

ГОЛОВОЛОМКИ

43
А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я РОТАТОР БОБ ДОВОД НАГАН ДЕД ДЕД ЕЛКА, ЛАК ЖАР, АР КАЗАК МИМ РАЙ, АР ОКО ШАЛАШ МИМ КОКОН ОКО ПОП ТРАТА КОКОС ПОТОП ПУП ТОРФ, ТОР ДОХОД ЦЕЛЬ, ЕЛЬ ЧЕСТЬ, СЕТЬ ШИШ ЩЕЛЬ, ЕЛЬ ВЪЕЗД, ЗЕВ, ДЕД ДЫРА, ДАР КОНЬ, КОН ЭРА, АР ЮБКА, БАК ЯБЕДА, БЕДА

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

Партия 3
1. тапок 5 2. капот 5 3. покат 5 4. топка отгадал В этом примере, который можно считать эндшпилем более длинной партии, определив пять букв задуманного слова, мы вынуждены сделать еще три хода, чтобы завершить игру: дела сложились не лучшим образом. Может показаться, что загадывать слова-анаграммы выгодно, поскольку при отгадывании всех букв дальнейшие действия партнера придется вести наобум от него уже ничего не зависит. Но надо учесть, что в больших блоках анаграмм содержится меньше редких букв, и сама пятерка находится быстро. Напомним, что рекордный блок пятибуквенных анаграмм содержит шесть слов: автор, товар, тавро, отвар, рвота, втора. Чтобы разобраться с ним, может понадобиться пять слов. В игре отгадать слово возникают интересные и оригинальные задачи. Рассмотрим десять таких задач и заметим, что решение большинства из них нам неизвестно. По правилам игры ходы представляют собой слова русского языка. А что изменится, если снять это ограничение и разрешить ходить 'абстрактными словами', т.е. любым набором букв? Удивительно, но при таком условии игра сильно упрощается... Задача 1. За сколько ходов можно угадать слово (или пять букв анаграммы), если разрешается ходить абстрактными словами? Эта задача носит скорее математический характер, ответ на нее довольно неожиданный какое бы слово ни было задумано, для его разгадки требуется всего один ход! Он может быть таким: KK б 4 4 a б4 4 вKK вKK яKK я 12 3 123 12 3 44
1 раз 10 4 раз
{

10

2

раз

10

32

раз

Данное 'слово' содержит все 33 буквы алфавита, причем а 1 раз 100 ,

ej

1 б 10 раз и т.д., ... я 10 32 раз. Ответ позволяет сразу определить пятерку букв задуманного слова. Действительно, если в нем есть а, то последней цифрой ответа будет 1, а если а нет, то на конце стоит 0. Если слово содержит б, то на втором месте справа в ответе стоит 1, в противном случае 0, и т.д. Очевидно, число-ответ состоит из многих нулей (28, если в слове есть буква Я) и ровно пяти единиц, которые и определяют однозначно пять нужных букв. Приведем пример. Пусть в ответ на наше абстрактное слово получено число 100 101 011. Это значит, что в задуманном слове имеются буквы: а (1 на правом конце), б(1 на втором месте справа), г (1 на четвертом месте справа), е(1 на шестом месте справа) и з (1 на девятом месте справа). Итак, задумано слово забег. Конечно, наше волшебное слово имеет астрономическую длину, но в данном случае важно лишь само существование такого универсального хода. Часто в процессе игры возникает необходимость выяснить, содержится ли в задуманном соперником слове та или иная конкретная буква. В связи с этим любопытна следующая задача. Задача 2. Для каких букв алфавита можно определить за один ход, содержится ли она в задуманном слове или нет? Предполагается, что никакой информацией мы пока не располагаем. Тем не менее почти две трети алфавита 20 букв из 33 требуют всего одного хода (см. таблицу). Идея проста подозреваемая буква должна выделяться числом своих вхождений в названное слово. Проще всего взять слово, состоящее из двух букв одна содержится два раза, а другая один. По любому ответу мы сразу определяем, есть ли две эти буквы в слове (или одна из них) или нет. Пусть сделан первый ход дед. Если ответ 0, то в искомом слове нет ни д, ни е. Если ответ 2, то есть д, а е отсутствует. Наконец, если ответ 3, то в слове есть обе буквы д и е. Трехбуквенными словами такого типа можно определить 10 букв. А еще для десяти используются слова большей длины. Девять из них устроены так: они содержат подозреваемую букву и две пары других букв. В результате нечетный ответ (1, 3 или 5) свидетельствует о наличии этой буквы, а четный (0, 2 или 4) об отсутствии. Для отгадывания буквы а тот же прием потребовал семибуквенного слова (с тремя парами посторонних букв). Можно использовать и более короткое, пятибуквенное слово атака. Здесь ответ

3 или больше говорит о том, что буква а в слове есть, а меньший ответ что нет. Конечно, пятибуквенное слово, служащее для разгадки одной из букв, может не помочь для других букв. Так, если ответом на ход довод служит число 2, то мы знаем, что в задуманном слове нет буквы в, а есть д или о, но какая именно неизвестно. Другое дело, если пятибуквенное слово содержит только две буквы (одну 2 раза, другую 3), но такого слова нам найти не удалось. Даже если все буквы имеют разное число вхождений, слово может быть непригодно для их определения. Так, слово баобаб содержит три буквы в разном количестве, но при неудачном ответе мы не определим точно, какая из букв содержится в задуманном слове. Действительно, ответ 0 говорит, что нет букв а, б, о, ответ 1 что есть о, но нет а и б, однако ответ 3 не вносит ясности из него следует, что либо в слове есть б и нет а и о, либо, наоборот, нет б, но есть а и о. Задача 3. За какое наименьшее число ходов можно определить, содержится ли данная буква в задуманном слове? Оказывается, любую букву (исключая ъ) можно 'вычислить' не более чем за два хода. Как мы видели, двад-