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

ИГ И ГОЛОВОЛОМКИ ИГРЫ Р Ы ИГОЛОВОЛОМКИ

41

Отгадать слово
Е.ГИК

Э

шаяся в 70-е годы, богаче и глубже большинства словесных игр. Для успеха в ней важна не только эрудиция играющих, но и умение логически мыслить. Можно сказать, что игра отгадать слово представляет собой некоторую смесь словесной игры с логической. Играют двое. Один игрок задумывает слово из пяти разных букв, а другой должен его отгадать. С этой целью он называет одно за другим разные слова,

ТА УВЛЕКАТЕЛЬНАЯ игра, появив-

состоящие из любого числа букв, не обязательно разных, на каждое из которых партнер дает ответ. А именно он сообщает число вхождений букв задуманного слова в названное, при этом каждая буква задуманного учитывается в ответе столько раз, сколько содержится в названном.1 Приведем пример. Пусть наш парт1 Эта игра сходна с числовой игрой 'быки и коровы', где нужно отгадывать задуманное число, называя различные комбинации цифр.

нер задумал слово колба, а мы назвали слово оборона. Тогда он должен ответить числом 5. В самом деле, буквы к и л не входят в названное слово, буква о входит 3 раза, буквы а и б по 1 разу. Итого: 0 + 3 + 0 + 1 + 1 = 5. Называя слово и получая ответ, мы всякий раз делаем определенные выводы относительно задуманного слова. Так, ответ 5 на слово оборона означает, что в задуманном слове есть о (иначе наибольший ответ равен 4), а также две буквы из четырех б, р, н, а. Ответ 0 означал бы, что в слове нет ни одной из пяти букв названного; ответ 1 или 2 что содержится только одна или две буквы из четверки и нет о; ответ 3 что есть о, но нет букв этой четверки, или, наоборот, есть три буквы из этих четырех, но нет о; наконец, при ответе 4 делаем вывод, что в задуманном слове есть о, а также одна из четырех букв

Иллюстрация М.М.Константиновой


42
б, р, н, а, или все эти четыре буквы вместе, но тогда отсутствует о. Извлекая на каждом ходу некую информацию о слове партнера, мы делаем ход за ходом, пока не получим ответ: 'отгадал'. Естественно, слова задумывают оба игрока, а побеждает тот, кто отгадывает слово противника за меньшее число ходов. Как обычно, и задуманное слово, и ходы должны быть существительными нарицательными, в единственном числе. Делать ходы не обязательно по очереди, важно лишь общее число слов. При большом количестве партий в каждой из них можно учитывать не только, кто раньше отгадал слово, но и на сколько ходов быстрее. Разберем несколько партий. Будем всюду исходить из того, что слово задумывает партнер, а нам надо его отгадать. Рядом со словами указаны ответы противника на них.

КВАНТ

1998

/?

3
сконструировать слово, которого, к сожалению, нет ни в одном словаре, хотя смысл его совершенно прозрачен: бесшинность. В нем есть е, которая встречается во всех словах-кандидатах, но вовсе нет э, всего одна б, ш вместе с и и два н вместе с ь. Ответ 1 в этом случае будет означать, что нужная нам буква э (фуэте), 2 что это б (буфет), 3 ш и и (фетиш ), 4 н и ь (нефть).

Партия 1
1. перевал 2 В начале игры имеет смысл ходить словами, в которых много гласных их в русском языке меньше, чем согласных, и значит, есть шансы быстрее отгадать. Для определения одной конкретной буквы лучше воспользоваться словом с большим числом ее вхождений. Например, на слово обороноспособность ответ, меньший 7, означает, что буква о отсутствует, а ответ 7 или больше что она почти наверняка есть. Конечно, вопрос о букве о решает и ход око (или боб), но он дает нам меньше информации о других буквах. В данной партии первый ход позволил сделать следующий вывод: либо в задуманном слове есть буква е и нет букв п, р, в, а, л, либо есть две буквы из этой пятерки, но нет е. Цель второго хода разобраться в ситуации. 2. свалка 0 Ответ 0 всегда радует, так как дает возможность выбросить из рассмотрения сразу несколько букв. В данном случае мы видим, что в задуманном слове нет букв в, а, л (и, очевидно, с и к), значит, с учетом первого хода, оно содержит либо е, либо одновременно п и р. 3. поп 0 Итак, второй вариант отпадает, буквы п, а значит, и р, нет, а есть е. 4. факультатив 4 Так как мы уже знаем, что букв а, к, л, в нет, последний ответ означает, что по сути нам надо проанализировать следующую ситуацию с фиктивным словом: фуьтти 4

Пусть в задуманном слове нет т, тогда оно содержит все оставшиеся буквы, т.е. ф, у, ь, и. Поскольку е уже найдена раньше, искомое слово должно состоять из букв ф, у, ь, и, е. Но собрать из них какое-нибудь слово невозможно (это уже не логический, а чисто словесный анализ). Таким образом, в задуманном слове обязательно присутствует т и, кроме того, есть е и две буквы из четырех: ф, у, ь, и. Очередными ходами мы могли бы найти две эти буквы и недостающую пятую. Но попробуем получить больше информации, не делая ходов (самое тонкое место партии!). Две буквы из четырех можно выбрать шестью способами. Добавляя к каждой паре буквы е и т, получаем шесть возможных комбинаций: 1) ф, у, е, т; 2) ф, ь, е, т; 3) ф, и, е, т; 4) у, ь, е, т; 5) у, и, е, т; 6) ь, и, е, т. Внимательный анализ показывает, что последние три из них при любом возможном добавлении пятой буквы не могут образовать слова 2 . Что же касается трех первых комбинаций, то добавляя к первой б или э, ко второй н или к третьей ш, получаем четыре возможных слова: буфет или фуэте, нефть и фетиш. Конечно, анализ потребовал большого перебора вариантов, но зато мы не сделали ни одного лишнего хода! Итак, осталось выяснить, какая из четырех букв б, э, н, ш входит в задуманное слово. Хотелось бы справиться с этой задачей в один ход. Для этого надо подобрать слово, в котором одна из этих букв не содержится вовсе, а три другие содержатся, но в разном количестве. К сожалению, буквы, которые должны входить в это слово, встречаются вместе нечасто, а в нужных пропорциях, по-видимому, не встречаются вовсе. Так что одним ходом не обойтись. 5. банан 1 Нам повезло! Ответ показывает, что в слове есть б, и следующий ход завершает игру. 6. буфет отгадал При ответе на пятом ходу 0 нельзя было бы выбрать, какая из двух букв, э или ш, входит в задуманное слово, и потребовался бы еще один ход.
Замечание. В ситуации, сложившейся на 4-м ходу, могло бы помочь такое наблюдение: в искомом слове ш может встречаться только в компании с и (в других вариантах нет ни той, ни другой буквы), а н только в сочетании с ь. Учитывая это, удалось 2 Мы здесь различаем е и е, иначе варианты 4) и 6) дадут соответственно дутье и житье.

Партия 2
1. карел 3 2. креол 2 Поскольку четыре буквы у этих двух слов общие, а ответы разные, делаем вывод, что буква а в задуманном слове есть, а буквы о нет. Кроме того, из ответа на второй ход следует, что из четырех букв к, р, е, л в нем есть две. Шесть возможных вариантов запишем следующим образом: 1) а, к, р (е, л, о); 2) а, к, е (р, л, о); 3) а, к, л (р, е, о); 4) а, р, е (к, л, о); (1) 5) а, р, л (к, е, о); 6) а, е, л (к, р, о). Здесь перед скобками записаны буквы, которые искомое слово может содержать, а внутри скобок буквы, которых в этом случае точно нет. 3. бекон 3 Три буквы из четырех (о отсутствует) можно выбрать четырьмя способами: 1) б, е, к (о, н); 2) б, е, н (к, о); (2) 3) б, к, н (е, о); 4) е, к, н (б, о). Комбинируя шесть вариантов (1) с четырьмя вариантами (2), получаем 6 Ч 4 = 24 комбинации. Однако не все они совместны. Так, не могут сочетаться первые возможности в (1) и (2): с одной стороны буквы е в искомом слове нет, а с другой есть. Анализ показывает, что из 24 вариантов совместными являются только шесть: 1) к, а, р, б, н (е, л, о); 2) к, а, е, б (р, л, о, н); 3) к, а, е, н (б, р, л, о); (3) 4) к, а, л, б, н (р, е, о); 5) а, р, е, б, н (к, л, о); 6) а, е, л, б, н (к, р, о). 4. абрис 1 Учитывая, что в слове есть а, делаем вывод, что в нем нет б, и значит, из шести вариантов остается только третий. 5. брошь 1 Букв б, р, о в слове нет, и получаем, что есть ш или ь. Итак, имеем две возможные пятерки: к, а, е, н, ь или к, а, е, н, ш. Из первой слово образо-


ИГРЫ

И

ГОЛОВОЛОМКИ

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. За какое наименьшее число ходов можно определить, содержится ли данная буква в задуманном слове? Оказывается, любую букву (исключая ъ) можно 'вычислить' не более чем за два хода. Как мы видели, двад-


44
цать букв находятся за один ход. Для отгадывания еще 12 букв можно брать пару слов: одно из них состоит из букв второго плюс искомая буква (см. таблицу). Одинаковые ответы на эти слова скажут, что в задуманном слове данной буквы нет, а разные что есть. Например, один и тот же ответ на ходы рай и ар (0, 1 или 2) означает, что буква й отсутствует, а разные (ответы могут отличаться только на 1) что присутствует. Для ъ удалось найти только трехходовое решение. Интересно, что если буквы е и е не различать, то и для ъ достаточно пары из двух слов мопед, подъем. Каждый читатель может составить свою собственную таблицу для отгадывания букв в слове противника. На практике, конечно, редко гонятся за одной буквой, а делая ход, пытаются извлечь больше информации о задуманном слове. В следующем примере определить задуманное слово совсем легко. 1. парапет 7 Полученный ответ сразу дает нам пять букв: а, п, р, е, т и, стало быть, слово патер. Теперь можно сформулировать еще одну задачу.
Задача 4. Придумайте как можно более длинное слово, сыграв которым на первом ходу, мы сразу же определим (при удачном ответе) задуманное. Поскольку семибуквенное слово мы уже знаем, надо вести поиски более длинных слов. Задача 5. Придумайте как можно более короткое слово, сыграв которым на первом ходу, мы сразу определим (при удачном ответе) задуманное. Эта задача как бы противоположна предыдущей и напоминает ситуацию в 'балде'. В самом деле, уже на первом ходу, сыграв коротким словом, мы должны отгадать несколько букв задуманного противником, чтобы затем однозначно дополнить их до самого слова.

КВАНТ

1998

/?

3
из букв о, и, е, либо одна из букв у, ы. Возникает следующая задача.
Задача 8. Придумайте партию, в которой на первом ходу отгадываются четыре буквы, для пятой остается как можно больше возможностей, но все они расшифровываются на втором ходу (в задаче 6 это было не обязательно). В отличие от предыдущей задачи здесь требуется не просто распознать как можно больше букв за один ход, а сделать это так, чтобы соответствующий набор возник как бы в процессе игры, после первого хода.

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

Задачи 4 и 5 связаны с отгадыванием слова за один ход. Предположим теперь, что первым ходом мы отгадали четыре его буквы. Например, такое начало: 1. атлет 5 Ответ показывает, что в задуманном слове есть буквы а, т, л, е. Осталось определить пятую букву. Разумеется, не стоит использовать для этой цели нашу таблицу. Анализ показывает, что из 29 оставшихся букв алфавита вместе с четырьмя найденными слово могут образовать целых десять: б (балет), в (валет, анаграмма ветла), м (метла), н (лента), п (лепта), р (талер), у (алеут), ф (лафет), г

В последнем примере после первого хода не удается сразу установить, какая из десяти букв искомая. Получаем еще одну задачу. Задача 7. Какое наибольшее число букв можно расшифровать одним ходом, т.е. определить, какая из них входит в задуманное слово? Достаточно найти такое слово, в которое бы одна из подозреваемых букв не входила совсем, вторая входила 1 раз, третья 2, четвертая 3 и т.д. Очевидно, мы считаем, что четыре буквы нам уже известны. Пусть, например, надо установить, какая из четырех букв у, е, н, о входит в задуманное слово. Задачу решает слово озеленение, в которое у не входит, о входит 1 раз, н 2 раза, е 4 раза. Получив ответ, мы немедленно определяем недостающую пятую букву (зная, конечно, информацию о вхождении в задуманное слово букв з, л, и). Буквы у, о, н, е в последнем примере выбраны не случайно. Пусть нами сделан такой первый ход: 1. кабала 6 Тогда слово противника содержит все четыре буквы данного к, а, б, л. Какая же буква пятая? Анализ показывает, что найденные буквы можно дополнить до слова пятью способами: булка, колба (или бокал), белка, бланк, балык. Итак, остается выяснить, какая из букв у, о, н, е, ы пятая в искомом слове, и мы приходим к рассмотренному примеру. Если на второй ход озеленение следует ответ 1, то искомой буквой будет у или ы (так как есть вхождение л, то букв о, н, е в слове нет), задумано слово булка или балык. Следующим ходом игра завершается. При ответе 2 получаем букву о, а следующим ходом разбираемся с анаграммами (колба или бокал). При ответе 3 имеем букву н и слово бланк, наконец при ответе 5 букву е и слово белка. В задаче 6 мы имели 10 возможных пятых букв, и их, по-видимому, можно однозначно распознать не менее чем за три хода. В последнем случае у нас пять возможных пятых букв, но уже после следующего хода картина почти полностью проясняется либо это одна

Предположим теперь, что мы догадались, какое слово задумал противник, назовем его словом-гипотезой. Будем считать, что самим этим словом ходить нельзя. Тогда получаем еще одну задачу.
Задача 9. Для р = 2, 3... придумать такое слово-гипотезу (играть им запрещено), что убедиться в ее правильности нельзя быстрее чем за р ходов. Для р = 2, 3, 4, 5, 6 задача решается легко. В качестве слова-гипотезы достаточно взять любого представителя блока анаграмм, содержащего (р + 1) слово. Так, слово автор, как мы знаем, с гарантией определяется только после пяти ходов. А при меньшем числе ходов гипотеза еще не будет подтверждена. Для больших значений р блоки из (р + 1)-й анаграммы неизвестны.

Можно придумать и другие остроумные задачи для игры отгадать слово. Многие из них вряд ли удастся решить без серьезного привлечения компьютера к тем или иным словарям русского языка. Во всяком случае, про последнюю задачу, связанную со стратегией игры, это можно сказать с определенностью.
Задача 10. Какое наименьшее число слов достаточно назвать, чтобы наверняка отгадать задуманное слово противника? Опыт игры показывает, что при тонких и внимательных действиях слово удается определить за 5 7 ходов, но доказать это мы не беремся.