укажите кратчайшее кодовое слово для буквы г при котором код будет допускать однозначное
Укажите кратчайшее кодовое слово для буквы г при котором код будет допускать однозначное
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Найдём наиболее короткие представления для всех букв. Кодовые слова 01 и 00 использовать нельзя, поскольку тогда нарушается условие Фано. Используем, например, для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано. Следовательно, для оставшихся двух букв нужно использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Тогда суммарная длина всех четырёх кодовых слов равна
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А — 1; Б — 0100; В — 000; Г — 011; Д — 0101. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
Для однозначного декодирования получившееся в результате сокращения кодовое слово не должно быть началом никакого другого. Первый вариант ответа не подходит, поскольку код буквы А является началом кода буквы Г. Второй вариант ответа подходит. Третий вариант ответа не подходит, т. к. в таком случае код буквы Г является началом кода буквы Д.
Правильный ответ указан под номером: 2.
Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Нельзя использовать кодовые слова, которые начинаются с 0 или с 10. 11 также не можем использовать, поскольку тогда мы больше не сможем взять никакое другое кодовое слово, а нам их нужно пять. Поэтому берём трёхзначное 110. 111 опять же не можем использовать, потому что понадобиться ещё одно кодовое слово, а вместе с этим не останется больше свободных. Теперь осталось взять всего два слова и это будут 1110 и 1111. Итого имеем 0, 10, 110, 1110 и 1111 — 14 символов.
Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М – кодовое слово 01. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Условие Фано — никакое кодовое слово не может быть началом другого кодового слова. Так как уже имеется кодовое слово 1, то никакое другое не может начинаться с 1. Только с 0. Также не может начинаться с 01, поскольку у нас уже есть 01. То есть любое новое кодовое слово будет начинаться с 00. Но это не может быть 00, так как иначе мы не сможем взять больше ни одного кодового слова, поскольку все более длинные слова начинаются либо с 1, либо с 00, либо с 01. Мы можем взять либо 000, либо 001. Но не оба сразу, поскольку опять же в таком случае мы больше не сможем взять ни одного нового кода. Тогда возьмём 001. И так как нам осталось всего два кода, то можем взять 0000 и 0001. Итого имеем: 1, 01, 001, 0000, 0001. Всего 14 символов.
Укажите кратчайшее кодовое слово для буквы г при котором код будет допускать однозначное
По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова:
A – 1, B – 010, C – 000.
Укажите кратчайшее кодовое слово для буквы E, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Буква E не может кодироваться как 0, так как кодирование буквы B начинается с 0.
Буква E не может кодироваться как 1, так как это кодирование буквы А.
Буква E не может кодироваться как 10 и 11 − так как кодирование буквы А — 1.
Буква E не может кодироваться как 01 и 00 — так как кодирование буквы B начинается с 01, а кодирование буквы C с 00. Буква E может кодироваться как 001 — это наименьшее возможное значение.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова: А — 000, Б — 1, В — 011.
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Код не может начинаться с 1, так как Б − 1.
0 не подойдёт, так как А и В начинаются с 0.
Двоичные коды 00 или 01 не подходят, поскольку А и В — 000 и 011.
010 и 001 подойдут, так как не конфликтуют ни с каким другим уже имеющимся кодом, из них 001 меньше.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова: А — 010, Б — 1, В — 011.
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Код не может начинаться с 1, так как Б — 1.
Код 0 не подойдёт, так как А и В начинаются с 0.
Код 00 же не включает в себя никакой из кодов и также не является подстрокой какого-либо кода, поэтому подойдёт.
Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.
| Цвет | Кодовое слово |
|---|---|
| Белый | 0 |
| Зелёный | 11111 |
| Красный | 1110 |
| Цвет | Кодовое слово |
|---|---|
| Синий | |
| Фиолетовый | 11110 |
| Чёрный | 10 |
Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Подберём кодовое слово для синего цвета. Слово 0 занято. Слово 1 является началом других кодов. Слово 10 занято. Слово 11 является началом других кодов. Слова 100 и 101 использовать нельзя, так как их начало совпадает с кодом черного цвета. Можно использовать только кодовое слово 110.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Поскольку все однозначные и двузначные слова не подходят по условию Фано, нужно найти трехзначное слово, которое было бы максимально и удовлетряло условию. Так как 111, 101 и 110 нарушают условие Фано, то искомое слово — 010.
Заметим, что двузначное кодовое слово 01 не подходит, поскольку при его использовании нельзя подобрать кодовое слово для буквы Е.
Дублирует задание 13481.
По каналу связи передаются сообщения, содержащие только четыре буквы: М, О, Р, Е; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв О, Р, Е используются такие кодовые слова: О: 111, Р: 0, Е: 100.
Укажите кратчайшее кодовое слово для буквы М. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 — нельзя, Р начинаются с 0.
1 — нельзя, буквы Е и О начинаются с 1.
000 — нельзя из-за Р.
001 — нельзя из-за Р.
101 — можно использовать.
110 — можно использовать.
111 — нельзя из-за О.
Таким образом, наибольшее числовое значение у кодового слова 110 для буквы М.
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
| Буква | Кодовое слово |
|---|---|
| А | 11 |
| Б | 0010 |
| Г | 1011 |
| Е | 0011 |
| Буква | Кодовое слово |
|---|---|
| И | |
| М | 01 |
| Р | 000 |
| Т | 1010 |
Укажите кратчайшее кодовое слово для буквы И. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 — нельзя, Б, Е, М и Р начинаются с 0.
1 — нельзя, буквы А, Г и Т начинаются с 1.
00 — нельзя, Б начинается с 00.
000 — нельзя из-за Р.
001 — нельзя из-за Е.
010 — нельзя из-за М.
011 — нельзя из-за М.
100 — можно использовать.
101 — нельзя из-за Т.
110 — нельзя из-за А.
111 — нельзя из-за А.
Таким образом, наименьшее числовое значение у кодового слова 100 для буквы И.
| Буква | Кодовое слово |
|---|---|
| А | 0101 |
| Б | 1000 |
| Г | |
| Е | 011 |
| Буква | Кодовое слово |
|---|---|
| И | 00 |
| М | 0100 |
| Р | 11 |
| Т | 1001 |
Укажите кратчайшее кодовое слово для буквы Г. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 — нельзя, А, Е, И и М начинаются с 0.
1 — нельзя, буквы Б, Р и Т начинаются с 1.
10 — нельзя из-за Б и Т.
000 — нельзя из-за И.
001 — нельзя из-за И.
100 — нельзя из-за Т.
101 — можно использовать.
110 — нельзя из-за Р.
111 — нельзя из-за Р.
Таким образом, наименьшее числовое значение у кодового слова 101 для буквы Г.
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
| Буква | Кодовое слово |
|---|---|
| А | 11 |
| Б | 0010 |
| Г | 100 |
| Е | 0011 |
| Буква | Кодовое слово |
|---|---|
| И | |
| М | 01 |
| Р | 000 |
| Т |
Укажите кратчайшее кодовое слово для буквы И. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 — нельзя, Б, Е, М и Р начинаются с 0.
1 — нельзя, А и Г начинаются с 1.
00 — нельзя из-за Б и Р.
000 — нельзя из-за Р.
001 — нельзя из-за Е.
010 — нельзя из-за М.
011 — нельзя из-за М.
100 — нельзя из-за Г.
101 — нельзя, поскольку, если закодировать букву И кодовым словом 101, для буквы Т не будет кодовых слов, удовлетворяющих условию Фано.
110 — нельзя из-за А.
111 — нельзя из-за А.
0000 — нельзя из-за Р.
0001 — нельзя из-за Р.
0010 — нельзя из-за Б.
0011 — нельзя из-за Е.
0100 — нельзя из-за М.
0101 — нельзя из-за М.
0110 — нельзя из-за М.
0111 — нельзя из-за М.
1000 — нельзя из-за Г.
1001 — нельзя из-за Г.
1010 — можно использовать.
1011 — можно использовать.
1100 — нельзя из-за А.
1101 — нельзя из-за А.
1110 — нельзя из-за А.
1111 — нельзя из-за А.
Таким образом, наименьшее числовое значение у кодового слова 1010 для буквы И.
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
| Буква | Кодовое слово |
|---|---|
| А | 0101 |
| Б | 101 |
| Г | |
| Е | 011 |
| Буква | Кодовое слово |
|---|---|
| И | 00 |
| М | 0100 |
| Р | 11 |
| Т |
Укажите кратчайшее кодовое слово для буквы Г. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 — нельзя, А, Е, И и М начинаются с 0.
1 — нельзя, Б и Р начинаются с 1.
01 — нельзя из-за А, Е и М.
000 — нельзя из-за И.
001 — нельзя из-за И.
010 — нельзя из-за М.
011 — нельзя из-за Е.
100 — нельзя, поскольку, если закодировать букву Г кодовым словом 100, для буквы Т не будет кодовых слов, удовлетворяющих условию Фано.
101 — нельзя из-за Б.
110 — нельзя из-за Р.
111 — нельзя из-за Р.
0000 — нельзя из-за И.
0001 — нельзя из-за И.
0010 — нельзя из-за И.
0011 — нельзя из-за И.
0100 — нельзя из-за М.
0101 — нельзя из-за А.
0110 — нельзя из-за Е.
0111 — нельзя из-за Е.
1000 — можно использовать.
1001 — можно использовать.
1010 — нельзя из-за Б.
1011 — нельзя из-за Б.
1100 — нельзя из-за Р.
1101 — нельзя из-за Р.
1110 — нельзя из-за Р.
1111 — нельзя из-за Р.
Таким образом, наименьшее числовое значение у кодового слова 1000 для буквы Г.
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 00, 01, 100, 110. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Кодовое слово для буквы П не может начинаться с 0, поскольку кодовые слова начинающиеся с 0, будут либо являться подстрокой кодовых слов для букв К и Л, либо включать в себя кодовые слова для букв К и Л. Кодовые слова 1, 10 и 11 взять не можем, поэтому букву П можно закодировать кодовыми словами 101 или 111. Возьмём кодовое слово с наименьшим числовым значением. Следовательно, букву П можно закодировать кодовым словом 101.
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Укажите кратчайшее кодовое слово для буквы Р, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Заметим, что невозможно подобрать однобуквенное, двухбуквенное, трёхбуквенное кодовое слово, удовлетворяющее условию Фано. Подберём четырёхбуквенное кодовое слово. Таким словом будет 1100.
По каналу связи передаются сообщения, содержащие только десять букв: А, Б, В, Г, Д, Е, И, К, Л, М. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
| Буква | Кодовое слово |
|---|---|
| А | 00 |
| Б | 010 |
| В | 111 |
| Г | 1100 |
| Д | 1011 |
| Буква | Кодовое слово |
|---|---|
| Е | 011 |
| И | 1010 |
| К | 1001 |
| Л | |
| М | 1000 |
Укажите кратчайшее кодовое слово для буквы Л. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 — нельзя, А, Б и Е начинаются с 0.
1 — нельзя, В, Г, Д, И, К и М начинаются с 1.
01 — нельзя из-за Б и Е.
10 — нельзя из-за Д, И, К и М.
11 — нельзя из-за В и Г.
000 — нельзя из-за А.
001 — нельзя из-за А.
010 — нельзя из-за Б.
011 — нельзя из-за Е.
100 — нельзя из-за М и К.
101 — нельзя из-за Д и И.
110 — нельзя из-за Г.
111 — нельзя из-за В.
0000 — нельзя из-за А.
0001 — нельзя из-за А.
0010 — нельзя из-за А.
0011 — нельзя из-за А.
0100 — нельзя из-за Б.
0101 — нельзя из-за Б.
0110 — нельзя из-за Е.
0111 — нельзя из-за Е.
1000 — нельзя из-за М.
1001 — нельзя из-за К.
1010 — нельзя из-за И.
1011 — нельзя из-за Д.
1100 — нельзя из-за Г.
1101 — можно использовать.
1110 — нельзя из-за В.
1111 — нельзя из-за В.
Таким образом, кодовым словом для буквы Л, удовлетворяющим условию Фано, является 1101.
По каналу связи передаются сообщения, содержащие только десять букв: А, Б, В, Г, Д, Е, И, К, Л, М. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
| Буква | Кодовое слово |
|---|---|
| А | 00 |
| Б | 111 |
| В | 010 |
| Г | 1100 |
| Д | 1010 |
| Буква | Кодовое слово |
|---|---|
| Е | 011 |
| И | 1011 |
| К | 1000 |
| Л | |
| М | 1001 |
Укажите кратчайшее кодовое слово для буквы Л. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 — нельзя, А, В и Е начинаются с 0.
1 — нельзя, Б, Г, Д, И, К и М начинаются с 1.
01 — нельзя из-за В и Е.
10 — нельзя из-за Д, И, К и М.
11 — нельзя из-за Б и Г.
000 — нельзя из-за А.
001 — нельзя из-за А.
010 — нельзя из-за В.
011 — нельзя из-за Е.
100 — нельзя из-за М и К.
101 — нельзя из-за Д и И.
110 — нельзя из-за Г.
111 — нельзя из-за Б.
0000 — нельзя из-за А.
0001 — нельзя из-за А.
0010 — нельзя из-за А.
0011 — нельзя из-за А.
0100 — нельзя из-за В.
0101 — нельзя из-за В.
0110 — нельзя из-за Е.
0111 — нельзя из-за Е.
1000 — нельзя из-за К.
1001 — нельзя из-за М.
1010 — нельзя из-за Д.
1011 — нельзя из-за И.
1100 — нельзя из-за Г.
1101 — можно использовать.
1110 — нельзя из-за Б.
1111 — нельзя из-за Б.
Таким образом, кодовым словом для буквы Л, удовлетворяющим условию Фано, является 1101.
Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.
Белый — 0, Зелёный — 11111, Фиолетовый — 11110, Красный — 1110, Чёрный — 10. Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет допускать однозначное декодирование.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Заметим, что кодовые слова, начинающиеся с 0, мы взять не можем, поскольку Белый уже закодирован кодовым словом 0. Кодовое слово 10 занято Чёрным. Кодовые слова, состоящие только из единиц, составить нельзя, иначе однозначное декодирование будет негарантированно. Значит, можем взять кодовое слово 110.
По каналу связи передаются сообщения, содержащие только четыре буквы: З, А, Р, Я; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Я, Р, З используются такие кодовые слова: Я — 0, Р — 101; З — 110.
Укажите кратчайшее кодовое слово для буквы А, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Заметим, что кодовое слово не может начинаться с нуля, поскольку будет нарушено условие Фано. Кодовые слова 10 и 11 взять нельзя, поскольку будет нарушено условие Фано. Можно взять кодовые слова длины 3: 100 и 111. Поскольку числовое значение кодового слова 100 меньше, возьмём кодовое слово 111.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Для двух букв кодовые слова уже известны, осталось подобрать для оставшихся двух букв такие кодовые слова, которые будут являться кратчайшими и удовлетворять условию Фано.
Кодовые слова не могут начинаться с 0, поскольку 0 является кодовым словом для буквы А. Кодовым словом для буквы В будет являться 1100, кодовые слова 11, 110 и 111 использовать нельзя, поскольку не получится закодировать остальные буквы таким образом, чтобы возможная сумма длин кодовых слов для букв В, Г, Д и Е была наименьшей. Кодовым словом для буквы Г будет являться 1101, для буквы Д — 1110, а для буквы Е — 1111.
Таким образом, сумма кратчайших кодовых слов для букв В, Г, Д и е будет равняться 4 + 4 + 4 + 4 = 16.
Два игрока, Петя и Ваня играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочередно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 23, нельзя сделать фишку, на которой написано 32. Первый ход делает Петя, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает.
Будем называть партией любую допустимую правилами последовательность ходов игроков, приводящую к завершению игры. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, указать, какую фишку он должен выставить в любой ситуации, которая ему может встретиться при различной игре противника.
Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.
Пусть первый ход Пети 12.
Ваня может поставить 21, 22 или 23. Предположим, он ставит 21. Получим цепочку 12-21.
Петя может поставить 11 или 13. Предположим, он ставит 11. Получим цепочку 12-21-11.
Ваня может поставить только фишку со значением 13. Получим цепочку 12-21-11-13.
Перед Петей в кучке остались только фишки 22 и 23, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Ваня выиграл.
Выполните следующие три задания при исходном наборе фишек в кучке <12, 14, 21, 22, 24, 41, 42, 44>.
а) Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну.
б) Пусть Петя первым ходом пошел 42. У кого из игроков есть выигрышная стратегия в этой ситуации? Укажите первый ход, который должен сделать выигрывающий игрок, играющий по этой стратегии. Приведите пример одной из партий, возможных при реализации выигрывающим игроком этой стратегии.
Задание 2. Пусть Петя первым ходом пошел 44. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим четвертым ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах — цепочку фишек, получившуюся после этого хода.
Задание 3. Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.
a) Все кратчайшие партии: 12-21-14-41, 14-41-12-21.
Экзаменуемому достаточно указать одну из них.
б) Выигрышная стратегия есть у Вани.
Своим первым ходом он ставит фишку 22. И далее исход игры не зависит от выбора игроков.
Возможная партия: 42-22-21-12-24-41-14-44
Существенный элемент выигрышной стратегии Вани — поставить после фишки 42 фишку 22, а не 21 или 24.
Примечание для проверяющего Стратегию также можно описать при помощи дерева или таблицы.
Существует 8 вариантов возможных партий, экзаменуемому достаточно привести одну из них.
Выигрышная стратегия, позволяющая выиграть своим четвертым ходом, есть у Пети. Дерево всех партий для этой стратегии показано в таблице 1 и на рисунке 1.
Примечание для проверяющего. Оба способа изображения допустимы. Ученику достаточно привести один из них.
Таблица 1. Дерево всех партий при выигрышной стратегии Пети, позволяющей ему выиграть своим четвертым ходом. Над пунктирной чертой указаны ходы игроков. Завершающие игру ходы подчеркнуты. Под пунктирной чертой в скобках приведены цепочки фишек после очередного хода.
Рисунок 1. Дерево всех партий при выигрышной стратегии Пети, позволяющей ему выиграть своим четвертым ходом. В заключительных цепочках подчеркнут последний ход. Примечание для проверяющего. И для таблицы, и для рисунка допускается сокращенная форма записи, когда указываются только ходы или только получающиеся цепочки фишек.
Нужно убрать фишки 22 и 44. Пример партии для сокращенного набора:
Примечание для проверяющего. Ученик может описать последовательность ходов в любой форме, главное, чтобы для приведенной им в качестве примера партии все ходы были указаны явно и в правильной последовательности.
Если убраны фишки 22 и 44, то игроками при любом развитии игры будут выставлены или 4 или 6 фишек. Поскольку 4 и 6 – чётные числа, то последнюю фишку всегда поставит второй игрок – Ваня. Возможны 24 различных партии в зависимости от первого хода Пети:
Остальные партии формируются аналогично. Ученик может не писать такого подробного комментария и привести пример только одной партии.