Быки и коровы (игра для детей). Тема: Быки и коровы - оптимальная стратегия игры Правила игры быки и коровы с цветом

Здравствуйте.
Еще осенью на 2 курсе в качестве лабораторной работы по «Теории автоматов» преподаватель на ходу придумывал нам задания, ориентируяюсь на наши пожелания в оценке. В основном это были игры. Кому-то достался хоккей, кому-то теннис, мне же досталась не столь известная логическая игра «Быки и коровы» .

Нужно было реализовать хоть какое-то обоснованное поведение компьютера в игре с человеком. Но я пошел дальше и уже через месяц компьютер в большинстве случаев легко обыгрывал моих однокурсников. А по предмету был получен автомат. Программу получите после описания алгоритмов.

Суть игры

Игрок и компьютер загадывают четырехзначные числа, используя цифры от 0 до 9 . Игроки пытаются разгадать числа соперника, посылая ему возможные варианты чисел, в ответ получая два числа - число «быков» и число «коров» . Что же это за числа такие?

• «Быки» - правильные цифры на правильных местах. Четыре «быка» - залог победы, мечта каждого фермера.
• «Коровы» - правильные цифры на неправильных местах.

Для понимания приведу пример:

Загадано число 1622 . Если мы предположим 6112 , то в ответ придет: 1 бык (четвертая цифра «2» на своем месте), 2 коровы (шестерка и единица не на своих местах).

Оперируя данными о «скоте» противника, нужно угадать число быстрей него.

Первый же тривиальный алгоритм, который так и напрашивается, - это перебирать наборы «1111», «2222», «3333»... до тех пор, пока не будет получен полный набор, а затем генерировать перемещения этого набора.

Например, загадано то же число 1622 , мы предполагаем «1111» , получаем в ответ «быка» , затем «2222» - получаем в ответ уже 2 «быков» , «3333» - пусто, «4444» - пусто, «5555» - пусто, «6666» - 1 бык .
Дальше продолжать не будем, так как набралось уже 4 быка в сумме. Осталось найти нужную комбинацию. Будем генерировать перестановки, пока не получим Та-дааам: «1226», «1262», «1226», «1262», «1622» . Все.

Очевидно, что алгоритм не очень хорош, зато понятный и не запутаться. Максимальное число ходов для угадывания - 10(«7890»)+24 перестановки. 34 - это в самом худшем случае. Конечно возможно перебор и перестановки всячески оптимизировать, например перебирать поочередно с двух концов - «1111», «0000», «2222», «9999»... так же оптимизировать генерацию перестановок при наличии одинаковых цифр(как в нашем примере - несколько раз спрашиваем одно и то же).
Но не будем этим заниматься. Пусть данная стратегия будет у нас легким уровнем сложности компьютера.

Много я сидел на парах и играл сам с собой, пытаясь придумать какой то свой крутой алгоритм. Но приходили только единичные идеи, из которой я не мог составить единой стратегии. Начал изучать литературу. Наткнулся на статьи, рода «угадывание за 7 ходов». Они меня не привлекли, поскольку там очень много ветвления. Но прочитав книгу нашего Кировского профессора(но не из нашего университета) С.М. Окулова «Программирование в алгоритмах» , я нашел описание довольно простого и достаточно эффективного алгоритма. В нем используется так называемый «метод решета» (примером может служить известное «решето Эрастофена» - классическая задача поиска простых чисел). Мы рассматриваем конечное множество всех возможных чисел и каждый ход исключаем все элементы множества, не представляющие интереса.

Например, для загаданного числа 1234 мы предположили 5678 , и получили 0 быков и 0 коров , чего думать - мы исключаем все числа, содержащие 5, 6, 7, 8 . Сразу можете прикинуть, сколько отнимется из 10000. Не стоит пугаться множества из 10000 элементов. За 5-6 ходов останется всего несколько чисел.

Начнем со структур данных. Код на паскале:

Const Pmax=10000; Type Post=string; Var A:array of Post; //множество B:array of boolean; // массив флажков, 1 - значит подходит, 0 - исключено

Инициализация:

T:=1; for i:=0 to 9 do for j:=0 to 9 do for k:=0 to 9 do for l:=0 to 9 do begin a[t]:=inttostr(i)+inttostr(j)+inttostr(k)+inttostr(l); // формируем множество inc(t); end; for i:=1 to pmax do b[i]:=true; // по умолчанию все числа подходят

Функция, реализующая анализ элемента множества по значениям переменных (bk,kr - быки и коровы)

Function pr(a,b:post;bk,kr:integer):boolean; //b - наш ход, a- элемент "тестируемого" множества var i,x:integer; begin x:=0; for i:=1 to 4 do // проверка по быкам if a[i]=b[i] then inc(x); if x<>bk then begin pr:=false; exit; end; x:=0; for i:=1 to 4 do // проверка по коровам if (a[i]<>b[i]) and (pos(b[i],a)<>0) then inc(x); if x

Таким образом после каждого нашего хода запускаем решето

For i:=1 to Pmax do if b[i] and not pr(a[i],hod,bk,kr) then b[i]:=false;

В заключение можно сказать, что алгоритм затратен к памяти и по сравнению со стандартными алгоритмами будет думать «дольше», но насколько же он проще и вполне оптимизируется.
Ну вот и все, совсем не сложно. Первая моя статья, судить строго.

Эта логическая, комбинаторная игра, придуманная сравнительно недавно, в 70-е годы, завоевала огромную популярность во многих странах. Ее наиболее распространенный вариант выпускается в виде комплекта под названием "Mastermind" (мастермайнд, буквальный перевод - "выдающийся ум"). Но начнем наш рассказ с "быков и коров".

Играют двое. Каждый задумывает четырехзначное число с разными цифрами, которое должен отгадать партнер (на первом месте может стоять и 0). Ход заключается в том, что отгадывающий называет определенное число, также четырехзначное с разными цифрами. Если задуманное и названное числа имеют общие цифры, стоящие на одних и тех же местах, то такую ситуацию называют "быком" (далее обозначается "б"). Если общие цифры есть, но стоят они на разных местах, то это "корова" (обозначается "к").

В ответ на ход партнера загадчик сравнивает свое число с названным и сообщает общее число "быков" и "коров". Например, если задумано 5239, а названо 2735, то ответ будет "1 бык 2 коровы" (16 2к). Цифра 3 имеется в обоих числах и стоит на одинаковых местах (16), цифры 2 и 5 общие, но стоят на разных местах (2к), цифры 7 и 9 не являются общими.

Сделав ход и получив ответ, отгадчик извлекает некоторую информацию о задуманном числе и в конце концов определяет его. Игра заканчивается в тот момент, когда на очередной свой ход он получает ответ 46, то есть задуманное число найдено. Выигрывает тот, кто быстрее отгадает число противника.

Приведем один пример. Ходы и ответы на них будем записывать в табл. 1.

Предположим, что партнер задумал число 3594, которое нам нужно отгадать. Наш первый ход 1568 дал ответ 16. Это означает, что в задуманном числе имеется всего одна цифра из названных, причем стоящая на своем месте. Постараемся отгадать ее, не привлекая пока - чтобы не запутаться - другие цифры. Сделаем второй ход 1586. Ответ 16 говорит о том, что на своем месте стоит цифра 1 или 5. Теперь следует третий ход 1658, и ответ 1к показывает, что в задуманном числе на втором месте стоит 5, а цифр 1, 6, 8 в нем нет. Ходом 2570 постараемся выяснить наличие цифр 2, 7 и 0. Ответ 16 весьма удачен - этих цифр в искомом числе нет. Итак, ясно, что задуманное число состоит из цифр 3, 4, 5, 9, причем на втором месте - 5. Сделаем следующий ход 4539. Ответ 16 3к означает, что задумано одно из чисел - 3594 или 9543. Если первая цифра 3, то 9 может быть только третьей, а если первая 9, то 3 - только четвертой. Ход 3594 и ответ 46 привел нас к цели; ответ 16 3к означал бы, что задумано число 9543, в этом случае партия продлилась бы на ход дольше.

Чем отличаются "быки и коровы" от мастермайнда? В комплекте мастермайнда роль цифр выполняют колышки шести цветов (красные, желтые, синие, зеленые, белые, черные), они вставляются в отверстия доски, которая выглядит примерно так, как показано на рис. 1. Задуманный набор кодовых колышков - цифр (вверху доски) шифровальщик загораживает специальными воротами, и он не виден расшифровщику. Для каждого хода также предусмотрены четыре отверстия, а еще четыре отверстия, размером поменьше, расположены слева - для ответа на него. Ход состоит в том, что отгадчик вставляет в отверстия четыре цветных колышка, а загадчик в ответ выставляет маленькие ключевые колышки двух цветов (черные и белые) в отверстие слева от хода (в любом порядке). Черные колышки выполняют роль "быков", а белые "коров". Если угаданы не все цвета, то некоторые отверстия остаются пустыми.

В примере на рис. 1 избран шифр ксбж . При первом ходе зчсж произошло одно полное совпадение (ж) и один цвет (с) оказался не на своем месте. Таким образом, ответ бч (по-старому 16 1к). На втором ходу ответ чбб , на третьем - ббчч (определены все четыре цвета), на четвертом - чччч . Игра закончена. Партия длилась четыре хода. Вообще, как мы видим, доска рассчитана на десять ходов - (только совсем неопытные игроки не укладываются в эти рамки).

В переводе мастермайнда на язык "быков и коров" мы получаем, что задуманное число и числа-ходы разрешается образовывать только из шести цифр (шесть цветов колышков). Правда, цвета колышков в шифре и ходах могут повторяться (в отличие от "быков и коров", где все цифры разные). Так, на рис. 1 в девятой строке сделан ход сскк . Ответ на него чб (синий цвет на своем месте, красный не на своем). Оба цвета считаются только один раз. При шифре ккбж и том же ходе сскк красный цвет считался бы уже дважды, и ответ бб .

Сформулируем более точно, как дается ответ на каждый ход в мастермайнде. Сначала сравниваются цвета первых колышков шифра и хода. Если они совпадают, ставится черный кодовый колышек ("бык"), а первые колышки шифра и хода исключаются из рассмотрения. Если они разные, сравниваются цвета первого колышка шифра и второго колышка хода. При совпадении ставится белый кодовый колышек ("корова"), а первый колышек шифра и второй хода исключаются из рассмотрения. Если цвета разные, сравниваются цвета первого колышка шифра и третьего колышка хода и т. д. Когда первый колышек шифра будет исключен из рассмотрения (либо сам по себе, либо при одном из совпадений цветов - вместе с соответствующим колышком хода), точно так же последовательно сравнивается цвет второго колышка шифра с цветами колышков хода, а затем аналогично третий и четвертый колышки шифра. Очевидно, для шифра и ходов на рис. 1 наша процедура даст те же ответы.

Хотя описание занимает много места, на самом деле ответ формулируется за несколько секунд.

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

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

Для отгадывания числа в "быках и коровах" или шифра в мастермайнде партнер должен как бы придумать тест для разгадывания числа или шифра. Таким образом, обе наши игры относятся к разряду тестовых.

Загадывая число в "быках и коровах", его первую цифру можно выбрать десятью способами, вторую - девятью (одна цифра занята), третью - восемью, наконец, четвертую - семью, всего имеем 10*9*8*7 = 5040 различных чисел. В мастермайнде на любом месте может стоять колышек любого цвета (из шести возможных), то есть всего 6 4 = 1296 вариантов.

Итак, в "быках и коровах" имеется 5040 различных чисел, которые можно загадывать и которыми можно ходить. А сколько существует различных ответов? Все они указаны во втором столбце табл. 2, их 14 (очевидно, ответ 36 1к невозможен). Горизонтальной чертой в таблице разделены случаи, в которых обнаружены все четыре цифры, три цифры, две, одна и ни одной. В третьем столбце указано количество чисел, которые могут дать соответствующий ответ на первом ходу. Самый приятный ответ, конечно, 46, сразу заканчивающий игру. Как мы видим, наибольшее разнообразие возможных чисел остается при ответе 1к - 1440.

Разумеется, результат игры, то есть количество ходов, за которое отгадывается задуманное число, в какой-то степени зависит от случая. Но многое определяется и искусством играющих. Здесь возникает вопрос: что понимать под мастерством игры в "быки и коровы"? Ведь даже начинающий игрок уже первым ходом может случайно отгадать задуманное число, но это еще не говорит о его умении.

Предположим, игроки А и Б сыграли матч из трех партий. Игрок А во всех трех партиях отгадал число партнера за 5 ходов. Игрок Б в двух партиях отгадал число за 4 хода, а в одной за 9. Кто играет лучше? Игрок Б выиграл матч со счетом 2:1, но ведь общее число ходов у него больше. Если, скажем, в шахматах важна сама победа независимо от продолжительности партии, то в "быках и коровах" именно скорость отгадывания, количество затраченных ходов собственно и составляют результат игры.

Рассмотрим два наиболее интересных подхода к оценке силы игры в "быки и коровы". Обозначим через l i , число ходов, за которое данный игрок отгадывает число с номером i (i пробегает значения от 1 до 5040). Введем две характеристики его силы игры в "быки и коровы":

где l ср - среднее число ходов, за которое игрок отгадывает число, а l макс - число ходов, гарантирующее ему раскрытие шифра. Любое число отгадывается им самое большее за l макс ходов. Каждая из этих двух характеристик, по желанию, может служить для оценки силы. Очевидно, величины l ср и l макс точно так же определяются и для мастермайнда, только в формулах будет фигурировать другое число - 1296.

В игре людей всегда легко разобраться, кто сильнее. Другое дело, когда речь идет об ЭВМ. Для произвольной стратегии игры, сформулированной в виде некоторого алгоритма, можно вычислить числа l ср и l макс и, значит, в зависимости от критерия определить, какая программа для ЭВМ сильнее.

Стоит заметить, что игры, о которых идет речь, представляют собой весьма интересный объект для исследования на компьютере. Достаточно сказать, что в написании программы для "быков и коров" участвовал один из крупнейших в мире специалистов в области программирования американец Д. Кнут. В нашей стране ряд результатов в этой области был получен группой студентов кафедры кибернетики МИСиС под руководством доцента М. Гендлера.

Основная задача, привлекающая математиков и программистов, состоит в нахождении оптимального алгоритма, то есть такой стратегии игры, при которой число l ср или соответственно l макс принимает наименьшее значение. Если говорить об l ср, то здесь полной ясности цока нет. Найдены стратегии, которые для мастермайнда дают значение l ср чуть меньше 4, а для "быков и коров" - чуть больше 5, но вопрос об оптимальных алгоритмах остается открытым.

Что же касается числа l макс, представляющего больший интерес, то проблема полностью решена. Для мастермайнда построен наилучший алгоритм игры, при котором любое число шифровальщика разгадывается на позднее пятого хода, и доказано, что для любого другого алгоритма (стратегии) найдется хотя бы одно число, на разгадку которого уйдет не меньше пяти ходов. Таким образом, l макс = 5.

Для "быков и коров" несколько лет назад студентами МИСиС была разработана стратегия, гарантирующая отгадывание любого числа за семь ходов, и было установлено, что l макс ≥6. Но сомкнуть эти границы никак не удавалось. И вот совсем недавно при помощи весьма хитроумных комбинаторных рассуждений и тонкого использования машинных возможностей они определили, что l макс = 7. Иначе говоря, построен алгоритм игры в "быки и коровы", позволяющий найти любое загаданное число за семь ходов, и доказано, что шестиходовой стратегии не существует.

Кстати, в приведенном в самом начале примере задуманное число было отгадано именно за семь ходов (хотя пример носил учебный характер и не ставилась цель играть оптимально).

Конечно, нас не должен удивлять тот факт, что для "быков и коров" числа l ср и l макс больше, чем для мастермайнда,- ведь в первом случае возможных вариантов шифра почти в 4 раза больше. Впрочем, известен усложненный вариант игры - супермастермайнд, в котором вместо четырех отверстий используются пять и вместо шести цветов кодовых колышков - восемь.

Рассмотрим теперь несколько партий (точнее было бы сказать, пользуясь шахматной терминологией,- окончаний или этюдов), представленных в виде задач. Разобрав их, вы получите неплохую иллюстрацию тонкостей игры в "быки и коровы". Будут изучены все ситуации, когда ответ противника на наш первый ход - для определенности число 1234 - совпадет с одним из первых пяти в табл. 2. При ответе 46 партия продолжается всего один ход, а для каждого из четырех других случаев мы укажем способ игры, гарантирующий отгадывание задуманного числа за наименьшее количество ходов. Другими словами, за столько ходов мы точно отгадаем число противника, каким бы оно ни было, а при меньшем количестве нам всегда может не повезти - шифр не будет раскрыт.

Партия 1. На первый ход 1234 противник ответил 2б 2к. Какое наименьшее количество ходов гарантирует отгадывание задуманного числа?

Легко проверить, что только шесть задуманных чисел в ответ на первый ход 1234 могут дать ответ 2б 2к (табл. 3, первый столбец), и при любом втором ходе по крайней мере три из них дадут одинаковый ответ.

Вторым ходом сыграем 1356 (вместо цифр 5 и 6 можно было бы взять и другие, отличные от 1, 2, 3, 4). Все возможные ответы находятся во втором столбце таблицы. Ответ 2б сразу определяет задуманное число - 1324 (у других чисел иной ответ), ответ 1б 1к оставляет два варианта, а ответ 2к - три. Третий ход 3256 (с учетом второго) вносит полную ясность - все пять чисел-кандидатов дают разную пару ответов. Прочерк в табл. 3 (и всех последующих таблицах) означает, что при соответствующем ходе "реакция" на него данного числа нас уже не интересует. Таким образом, на четвертом ходу гарантирован ответ 4б и партия длится не более четырех ходов.

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

Партия 2. Тот же вопрос, что и в первой партии, но ответ на первый ход 1б 3к.

На первый ход 1234 восемь чисел могут дать ответ 1б 3к (табл. 4). При любом втором ходе хотя бы одна четверка

чисел дает один и тот же ответ, и для выяснения ситуации понадобятся еще два хода. При втором ходе 1256 числа разделяются на две группы; для чисел первой группы (ответ 1б 1к) сделаем третий ход 1563, а для чисел второй группы (ответ 2к) - ход 2564. После этого остаются две пары чисел в каждой группе, требующие еще одного хода, и четвертый ход 1564 полностью проясняет картину. Таким образом, вторая партия длится не более пяти ходов.

Партия 3. Тот же вопрос, что и в предыдущих двух партиях, но при ответе на первый ход 4к.

В ответ на первый ход 1234 девять чисел могут дать ответ 4к (табл. 5). Второй ход 3102 расшифровывает два числа, а остальные семь делит на две группы, в одной из которых решает ход 4153, а в другой - 2456. Четвертый ход завершит партию (будет получен ответ 4б).

Партия 4. Тот же вопрос, что и в предыдущих трех партиях, но при ответе на первый ход 3б.

Ответ 3б на первый ход 1234 дают 24 числа. Действительно, три цифры можно зафиксировать на своих местах четырьмя способами, а для четвертой имеется шесть возможностей: О, 5, 6, 7, 8, 9, то есть всего 4*6 = 24 варианта. Любопытно, что найти задуманное число среди 24 чисел в данной партии удается за столько же ходов, за сколько восемь чисел во второй партии.

Рассмотрим табл. 6 а. В ее первых четырех строках а обозначает любую из цифр 8, 9, 0. Таким образом, здесь представлены все 24 возможности. Сделаем второй ход 1567. Ответ Об Ок оставляет выбор из трех неразгаданных чисел, для которых годится третий ход 8934 (табл. 6 б). При ответе 26 можно сыграть 1506 (табл. 6 в), а при ответе 1к - 5634 (табл. 6 г).

Для девяти чисел с ответом 16 в табл. 6 а составим табл. 6 д (вновь а может принимать одно из трех значений - 8, 9, 0). Третий ход 3564 разделяет их на три равные группы, четвертым ходом числа идентифицируются, и пятый ход завершит игру (ответ 4б). У нас осталось еще шесть чисел, расположенных в нижних строках табл. 6 а, выпишем их отдельно (табл. 6 е). И с этой шестеркой удается разобраться за два дополнительных хода. Итак, вновь партия длится не более пяти ходов.

Результаты всех рассмотренных партий собраны в табл. 7. Строгое доказательство того, что в каждом случае меньшим количеством ходов не обойтись, мы опускаем.

Разобранные примеры показывают, что искусная игра в "быки и коровы" требует тонкого математического расчета.

Правила игры

Играют двое. Каждый задумывает и записывает тайное 4-значное число с неповторяющимися цифрами . Игрок, который начинает игру по жребию, делает попытку отгадать число. Попытка - это 4-значное число с неповторяющимися цифрами, сообщаемое противнику. Противник сообщает в ответ, сколько цифр угадано без совпадения с их позициями в тайном числе и сколько угадано вплоть до позиции в тайном числе. Например:

Задумано тайное число «3219».

Попытка номер: «2310».

Результат: две «коровы» (две цифры: "2" и "3" - угаданы на неверных позициях) и один «бык» (одна цифра "1" угадана вплоть до позиции).

Игроки делают попытки угадать по очереди. Побеждает тот, кто угадает число первым.

Вариации игры

В случае варианта с повторениями количество вариантов будет равно .

В классическом случае игры с четырьмя не повторяющимися цифрами для отгадывания любого номера требуется не более семи ходов. Средняя минимальная длина игры составляет 26274/5040=5.2131 попытки .

Реализации

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

Настольные игры Mastermind популярны во всём мире. Наиболее распространены вариации:

Ссылки

• Кандидат технических наук Е. Гик. Быки и коровы. «Наука и жизнь», № 2, 1978, с. 150-151; № 8, 1978, с. 142-143.
• Чарльз Уэзерелл. Этюды по программированию, Великий комбинатор. М.: 1982, с. 140.

Примечания

Wikimedia Foundation . 2010 .

Смотреть что такое "Быки и коровы" в других словарях:

Домашняя корова Научная классификация Царство: Животные Тип: Хордовые … Википедия

Настощие быки (Bos), род парнокопытных. Дл. тела 180 325 см, хвоста 70 140 см, выc. в холке 62 180 см; масса 325 1200 кг. Самки значительно меньше самцов. 5 видов (иногда относимых к 3 родам): бантенг, гаур, купрей, тур (вымерший к 17 в.) и як; в … Биологический энциклопедический словарь

Быки самые крупные из полорогих. Это могучие и сильные животные. Массивное тело их покоится на крепких конечностях, тяжелая, широкая, низкопосажен ная голова как у самцов, так и у самок увенчана рогами, толстыми и короткими у одних видов … Биологическая энциклопедия

Рассмотрим теперь несколько партий (точнее было бы сказать, пользуясь шахматной терминологией, - окончаний или этюдов), представленных в виде задач. Разобрав их, вы получите неплохую инструкцию как выиграть , которая иллюстрирует тонкости игры в «быки и коровы» .

Будут изучены все ситуации, когда ответ противника на наш первый ход - для определенности число 1234 - совпадет с одним из первых пяти в таблице на рис. 2 (предыдущая страничка). При ответе 4б партия продолжается всего один ход, а для каждого из четырех других случаев мы укажем способ игры, гарантирующий отгадывание задуманного числа за наименьшее количество ходов.

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

Партия 1.

На первый ход 1234 противник ответил 2б 2к. Как выиграть? Какое наименьшее количество ходов гарантирует отгадывание задуманного числа?

Легко проверить, что только шесть задуманных чисел в ответ на первый ход 1234 могут дать ответ 2б 2к (табл. 3, первый столбец), и при любом втором ходе по крайней мере три из них дадут одинаковый ответ.

Вторым ходом сыграем 1356 (вместо цифр 5 и 6 можно было бы взять и другие, отличные от 1, 2, 3, 4). Все возможные ответы находятся во втором столбце таблицы. Ответ 2б сразу определяет задуманное число - 1324 (у других чисел иной ответ), ответ 1 б 1 к оставляет два варианта, а ответ 2к - три.

Третий ход 3256 (с учетом второго) вносит полную ясность - все пять чисел-кандидатов дают разную пару ответов. Прочерк в табл. 3 (и всех последующих таблицах) означает, что при соответствующем ходе «реакция» на него данного числа нас уже не интересует. Таким образом, на четвертом ходу гарантирован ответ 4б и партия длится не более четырех ходов.

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

Партия 2.

Тот же вопрос, что и в первой партии, но ответ на первый ход 1б Зк. На первый ход 1234 восемь чисел могут дать ответ 16 Зк (табл. 4).

При любом втором ходе хотя бы одна четверка чисел дает один и тот же ответ, и для выяснения ситуации понадобятся еще два хода. При втором ходе 1256 числа разделяются на две группы; для чисел первой группы (ответ1б 1к) сделаем третий ход, а для чисел второй группы (ответ 2к) ход 2564 . После этого остаются две пары чисел в каждой гpynne, требующие еще одного хода, и четвертый ход 1564 полностью проясняет картину.

Таким образом, вторая партия длится не более пяти ходов.

Рассмотрим, как выиграть в «быки и коровы» , анализируя еще две партии.

Партия 3.

Тот же вопрос, что и в предыдущих двух партиях, но при ответе на первый ход 4к.

В ответ на первый ход 1234 девять чисел могут дать ответ 4к (табл. 5). Второй ход 3102 расшифровывает два числа, а остальные семь делит на две группы, в одной из которых решает ход 4153 , а в другой - 2456 . Четвертый ход завершит партию (будет получен ответ 4б).

Партия 4.

Тот же вопрос, что и в предыдущих трех партиях, но при ответе на первый ход 3б.

Ответ 3б на первый ход 1234 дают 24 числа. Действительно, три цифры можно зафиксировать на своих местах четырьмя способами, а для четвертой имеется шесть возможностей: 0, 5, 6, 7, 8, 9, то есть всего 4X6 = 24 варианта. Любопытно, что найти задуманное число среди 24 чисел в данной партии удается за столько же ходов, за сколько восемь чисел во второй партии.

Рассмотрим табл. 6 а. В ее первых четырех строках а обозначает любую из цифр 8, 9, 0. Таким образом, здесь представлены все 24 возможности. Сделаем второй ход 1567. Ответ 0б 0к оставляет выбор из трех неразгаданных чисел, для которых годится третий ход 8934 (табл. 6 б). При ответе 2б можно сыграть 1506 (табл. 6 в), а при ответе 1к - 5634 (табл. 6 г).

Для девяти чисел с ответом 1б в табл. 6 а составим табл. 6 д (вновь а может принимать одно из трех значений - 8, 9, 0). Третий ход 3564 разделяет их на три равные группы, четвертым ходом числа идентифицируются, и пятый ход завершит игру (ответ 4б).

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

Результаты всех рассмотренных партий собраны в табл. 7. Строгое доказательство того, что в каждом случае меньшим количеством ходов не обойтись, мы опускаем.

Эта инструкция, как выиграть и разобранные примеры показывают, что искусная игра в «быки и коровы» требует тонкого математического расчета.