Логическая задача на расставление костей домино на шахматной доске. Подготовка к олимпиаде

Задачи для самостоятельного

1. Можно ли доску размером 10 × 10 покрыть фигурами

2. В каждой клетке квадрата 9 × 9 сидит жук. По команде каждый жук перелетает на одну из соседних по диагонали клеток. Доказать, что по крайней мере 9 клеток после этого окажутся свободными.

3. Можно ли выложить квадрат 8 × 8, используя 15 прямоугольников 1 × 4 и один

уголок вида ?

4. Можно ли сложить квадрат 6 × 6 с помощью 11 прямоугольников 1 × 3 и одного

уголка вида ?

Ответы к задачам для самостоятельного решения

1. Шахматная раскраска. Каждая такая фигурка занимает нечётное число чёрных клеток, значит все 25 фигурок тоже занимают нечётное число чёрных клеток.

2. В каждой клетке квадрата 9 × 9 сидит жук.

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

3. Раскраска «зеброй». Прямоугольники занимают чётное число чёрных клеток, а уголок – нечётное.

4. Предположим, что квадрат удалось сложить. Раскрасим клетки в три цвета «по диагоналям», причём так, чтобы, две «крайних» клетки уголка оказались одного цвета (синего). Прямоугольники будут занимать ещё 11 синих клеток, значит все фигурки вместе занимают 13 синих клеток, но синих клеток на доске всего 12.

Контактная информация

Создатели: Бондарева Полина и Набиева Зейнаб

Контактные телефоны: 8-905-660-25-23, 8-

Способ раскраски при решении задач

Г. Нижний Новгород

Лицей №180

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

Мы хотим рассказать о разных видах раскрасок. Начнем с вида «Зебра». Она чаще всего используют для задач, где всего два вида данных. Когда раскраску используют в задачах, то как правило пользуются для решения белым и черным цветом или другими противоположными друг для друга цветами.

Бывают такие задачи, для которых характерна

другая раскраска: «в горошек». С помощью данной раскраски можно решать задачи разной сложности. На рисунке каждое данное (разные предметы, используемые в задаче) раскрашивается определенным цветом (цвет можно выбрать любой). На первый взгляд, может показаться, что у этой раскраски нет трудностей, но это не так, когда задается большое количество данных, то такой вид решения задачи будет не оптимальным. По мимо этих видов, существуют еще раскраска «трехцветная» или «по диагоналям», используемая для задач среднего уровня. Смысл этой раскраски заключается в том, что данных обязательно должно быть три. Для данного нужно выбрать цвет и на рисунке

отметить его своим цветом. Для задач не

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

1. Можно ли выложить шахматную доску тридцатью двумя доминошками так, чтобы 17 из них были расположены горизонтально, а 15 – вертикально?

Решение: Можно использовать раскраску «зебра». Горизонтальные доминошки занимают нечётное число чёрных клеток (а именно – 17), а вертикальные – чётное.

2. Фигура «верблюд» ходит по шахматной доске ходом типа (1, 3). Можно ли пройти ходом «верблюда» с произвольного поля на соседнее?

Решение: Ход верблюда не меняет цвета клетки, на которой он стоит, поэтому на соседнюю клетку перейти он не сможет.

3. Замок имеет форму правильного треугольника, разделенного на 25 маленьких залов той же формы. В каждой стене между залами проделана дверь. Путник ходит по

замку, не посещая более одного раза ни один из

залов. Найти наибольшее число залов, которое ему удастся посетить.

Решение: 21 зал. Раскрасим треугольник в шахматном порядке. Залов одного цвета (например чёрного) – 15, а другого цвета (белого) – 10. Заметим, что в чёрном зале путник может находиться с самого начала, или

попасть в него из белого, поэтому он побывает

не более, чем в 11 чёрных залах. Таким образом, не менее 4 чёрных залов останутся не посещёнными. Пример, когда путник не посетит ровно четыре зала, строится без труда.

4. Дана доска 12 × 12. В левом нижнем углу стоят 9 шашек, образуя квадрат 3 × 3. За один ход можно выбрать какие-то две шашки и

переставить одну из них симметрично

относительно другой (не выходя при этом за пределы доски). Можно ли за несколько ходов переместить эти шашки так, чтоб они образовали квадрат 3 × 3 в правом нижнем углу?

Решение: Нет

(шахматная раскраска –

шашки остаются на клетках тех же цветов).

5. Из доски 8 × 8 вырезали угловую клетку. Можно ли оставшуюся часть разрезать на прямоугольники

Решение: трёхцветная раскраска

На этом занятии мы поговорим о раскрасках и том, как они помогают решать задачи. Рассмотрим нестандартные задачи на разрезания и замощения и способы их решения.

Конспект занятия "Разрезания. Замощения. Раскраски."

Раскраски. Разрезания. Замощения.

Задачами на разрезание увлекались многие ученые с древнейших времен. Решения многих простых задач на разрезание были найдены еще древними греками, китайцами, но первый систематический трактат на эту тему принадлежит перу Абул-Вефа, знаменитого персидского астронома Х века, жившего в Багдаде. Геометры всерьез занялись решением задач на разрезание фигур на наименьшее число частей и последующее составление из них той или иной новой фигуры лишь в начале XX века. Одним из основоположников этого увлекательного раздела геометрии был знаменитый составитель головоломок Генри Э. Дьюдени. Особенно большое число существовавших ранее рекордов по разрезанию фигур побил эксперт австралийского патентного бюро Гарри Линдгрен. Он является ведущим специалистом в области разрезания фигур.

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

Чтобы доказать, что решение задачи на разрезание какой-нибудь фигуры на части возможно, достаточно предоставить какой-нибудь способ разрезания. Найти все решения, то есть все способы разрезания, немного труднее. А доказать, что разрезание невозможно, уже достаточно трудно. Сделать это в некоторых случаях нам помогает раскраска фигуры.

Задача 1: Взяли квадрат клетчатой бумаги размером 8×8, отрезали от него две клетки (левую нижнюю и правую верхнюю). Можно ли полученную фигуру полностью покрыть «доминошками» - прямоугольниками 1× 2?

Задача 2. Можно ли выложить шахматную доску тридцатью двумя доминошками так, чтобы 17 из них были расположены горизонтально, а 15 – вертикально?

Задача 3: Можно ли разрезать квадрат клетчатой бумаги размером

4× 4 на один пьедестал, один квадрат, один столбик и один зигзаг?

Задача 4: Можно ли выложить квадрат 8 × 8, используя 15 прямоугольников 1 × 4 и один уголок вида ?

Задача 5: Можно ли выложить прямоугольник 6 × 10 прямоугольниками 1 × 4?

Задача 6: Можно ли сложить квадрат 6 × 6 с помощью 11 прямоугольников 1 × 3 и одного уголка вида ?

Задача 7: На каждой клетке доски 5 × 5 сидит жук. В некоторый момент времени все жуки взлетают и приземляются на соседние по стороне клетки. Докажите, что при этом окажется хотя бы одна пустая клетка.

Задача 8: Из доски 8 × 8 вырезали угловую клетку. Можно ли оставшуюся часть разрезать на прямоугольники 3 × 1?

Задача 9: Фигура «верблюд» ходит по шахматной доске ходом типа (1, 3). Можно ли пройти ходом «верблюда» с произвольного поля на соседнее?

Задача 10: Можно ли доску размером 10 × 10 покрыть фигурами вида ?

Задача 11: Дана доска 12 × 12. В левом нижнем углу стоят 9 шашек, образуя квадрат 3 × 3. За один ход можно выбрать какие-то две шашки и переставить одну из них симметрично относительно другой (не выходя при этом за пределы доски). Можно ли за несколько ходов переместить эти шашки так, чтоб они образовали квадрат 3 × 3 в правом нижнем углу?

Задача 12: В каждой клетке квадрата 9 × 9 сидит жук. По команде каждый жук перелетает на одну из соседних по диагонали клеток. Доказать, что по крайней мере 9 клеток после этого окажутся свободными.

Задача 13: Замок имеет форму правильного треугольника, разделенного на 25 маленьких залов той же формы. В каждой стене между залами проделана дверь. Путник ходит по замку, не посещая более одного раза ни один из залов. Найти наибольшее число залов, которое ему удастся посетить.

Задача 14: На какое наибольшее количество ромбов можно разрезать равносторонний треугольник, разбитый на 36 равносторонних треугольников?

Задача 15. В квадрате 7×7 клеток размещено 16 плиток размером 1×3 и одна плитка 1×1. Докажите, что плитка 1×1 либо лежит в центре, либо примыкает к границам квадрата.

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

взявший последнюю спичку. Кто выигрывает при правиль- ной игре?
62

7. Из доски 8 × 8 вырезан угловой квадрат. Можно ли уложить доску прямоугольниками 1 × 3?
8. Из 30 спичек двое игроков берут по своему усмотрению от 1
до 6 спичек. Выигрывает тот, кто берет последнюю спичку.

9. Имеется три кучи камней. Состоянием назовем тройку чисел
(x
1
, x
2
, x
3
), где x i
- число камней в i-й куче. Ходом является операция переноса из кучи в кучу числа камней, равного числу камней в той куче, куда осуществляется перенос. Из исходного состояния (11, 7, 6) получить состояние (8, 8, 8).
10. Четырьмя прямыми разбить круг на максимальное количе- ство частей.
11. Двумя прямыми линиями разрезать греческий крест так,
чтобы из получившихся частей сложить прямоугольник, од- на сторона которого в два раза больше другой.
12. Имеется 12-литровый запас жидкости и пустые сосуды в 9

и 5 л. Требуется отмерить в точности 6 л. Сколько литров могут быть отмерены такими сосудами из запаса в 12 л?
13. Определить число последовательностей длины n из {0, 1, 2},
в которых отсутствуют две, подряд стоящих единицы.
14. Можно ли покрыть квадрат 10 × 10 фигурами вида
15. Можно ли покрыть квадрат 10 × 10 фигурами вида
63

16. Можно ли покрыть квадрат 8×8 с вырезанной угловой клет- кой фигурами вида
17. Можно ли покрыть фигурами вида шахматную доску 8 × 8, в которой вырезан квадрат:
18. Можно ли уложить шахматную доску с вырезанной угловой клеткой фигурами вида
19. Можно ли совершить переправу четырех пар рыцарь-ору- женосец с помощью двухместной лодки, если оруженосец не может находиться на одном берегу с чужим(и) рыца- рем(ями) в отсутствие своего хозяина?
20. Разработать алгоритм поиска двух наименьших чисел в не- упорядоченной последовательности из n чисел.
21. Из 27 спичек, лежащих на столе, двое играющих поочеред- но берут не менее одной и не более четырех спичек. Выиг- равшим считается тот, у кого по окончании игры окажется четное число спичек. Разработать алгоритм игры первого игрока.
64

22. Два участника игры по очереди называют число от 1 до 10.
Называя число, игрок прибавляет его к уже имеющейся сум- ме чисел (называя первое число, игрок прибавляет его к ну- лю). Выигрывает тот из игроков, кто набирает число 100.
Разработать алгоритм игры первого игрока.
23. Найти за минимальное число вопросов (возможные ответы:
«да», «нет») загаданное 5-значное число, если сумма первых трех цифр равна 17.
24. Найти за минимальное число вопросов (возможные ответы:
«да», «нет») загаданное 4-значное число, если сумма второй и четвертой цифры равна 7.
25. Сколькими способами можно разменять 100 р. монетами в

5, 10, 20 и 50 р.?
26. Вычислить рекурсивно число шестизначных чисел, у кото- рых сумма первых четырех цифр равна 26, а сумма послед- них двух равна 14.
27. Вычислить рекурсивно количество разбиений числа 37 пя- тью слагаемыми, первое из которых не превышает 7, второе
- 5, а третье и четвертое принимают значения из множества
{5, 6, 7, 8}.
28. Вычислить рекурсивно число семизначных чисел , у которых сумма первых четырех чисел равна 21, а сумма последних пяти равна 19.
29. Вычислить рекурсивно количество разбиений числа 27 че- тырьмя слагаемыми, первое из которых не превышает 7,
второе - 8, а третье и четвертое принимают значения из множества {3, 5, 7}.
30. Вычислить рекурсивно число пятизначных чисел, у кото- рых сумма первых трех цифр равна 21, а сумма последних равна 12.
65

31. Вычислить рекурсивно число семизначных чисел, у которых сумма первой и третьей цифр равна 12, а сумма остальных пяти равна 19.
32. Вычислить рекурсивно
(2n − 2)(2n − 4) × . . . × 2
(n + 1)(n + 3) × . . . × (n + 2n − 1)
a n−5
b
−(n+3)
33. Вычислить рекурсивно число семизначных чисел, у которых сумма первых четырех цифр равна 17, а сумма последних трех равна 16.
34. Вычислить рекурсивно количество разбиений числа 17 че- тырьмя слагаемыми, первое из которых не превышает 4, вто- рое - 8, а третье и четвертое принимают значения {3, 4, 8}.
35. Вычислить рекурсивно число семизначных чисел, у которых сумма квадратов первых четырех чисел равна 17, а сумма квадратов последних двух равна 16.
36. Вычислить рекурсивно количество разбиений числа 25 че- тырьмя слагаемыми, первое из которых не превышает 8,
второе - 3, а третье и четвертое принимают значения из множества {2, 5, 9}.
37. Вычислить рекурсивно число расстановок N ладей на доске
N × N таких, что ладьи симметричны относительно обеих диагоналей и не бьют друг друга.
38. Вычислить рекурсивно число двоичных последовательностей из n элементов, в которых отсутствуют две рядом стоящие единицы.
39. Дана решетка N × M:
66

M
N
A
B
Вычислить рекурсивно число путей из A в B. Путь - по- следовательность ходов по решетке, ведущих слева направо и снизу вверх.
40. Даны числа a
1
, . . . , a n
, стоящие в определенном порядке. Для вычисления произведения a
1
·. . .·a n
при сохранении порядка сомножителей существует множество способов расстановки скобок между сомножителями. Вычислить рекурсивно чис- ло способов расстановки скобок.
41. Вычислить рекурсивно число 8-значных чисел, у которых сумма первых пяти цифр равна 29, а сумма последних трех цифр равна 21.
67

3
. методы анализа алгоритмов
3.1. Классы алгоритмов
В предыдущих разделах рассмотрены разные подходы, кото- рые могут быть использованы при построении алгоритмов. Для нахождения решения, для анализа эффективности этого решения можно выдвигать различные предположения, использовать уже известные другие алгоритмы, переформулировать условие зада- чи и т.п. Можно искать некие похожие задачи с уже известным решением и использовать это решение для нахождения алгоритма для требуемой задачи.
Однако частных задач, для которых найдены решения, суще- ствует очень много. Еще больше задач нерешенных или решенных с какими-то ограничениями и условиями. Искать похожие задачи среди всего множества задач, оценивать существующие решения по степени их «подходящести» может быть трудной, трудоемкой и не всегда разрешаемой проблемой. Было бы более полезным и про- дуктивным попробовать определить классы задач, объединенных общей проблемой, общими методами и подходами к решению, и затем искать тот класс, к которому можно отнести нашу частную задачу, требующую решения. Конечно, таких классов не должно быть слишком много , но с другой стороны, их и не должно быть слишком мало, чтобы не требовалось для каждой новой задачи определять свой, новый класс, который затем вряд ли будет ис- пользован для решения других задач.
В качестве примера задачи, принадлежащей определенному классу, рассмотрим известную задачу об определении фальшивой монеты.
Задача 3.1 (задача о фальшивой монете). Имеется n монет,
среди которых возможно находится одна фальшивая. Фальшивая монета отличается от остальных по весу, и в нашем распоряжении находятся весы с двумя чашками. Требуется определить фальши- вую монету за минимальное число взвешиваний или установить,
что фальшивых монет нет.
68

Решение. Задачу о фальшивой монете решали в подразд. 2.2,
но тогда было известно, что фальшивая монета обязательно лег- че. Теперь попробуем решить эту задачу для более общего слу- чая. Любое решение данной задачи (не обязательно оптимальное)
можно трактовать как последовательность взвешиваний. Однако ясно, что выбор монет для взвешивания на каком-то шаге зави- сит от того, какие монеты использовались, и результатов взвеши- вания на предыдущих шагах. Будем изображать последователь- ность взвешиваний следующим образом. Перенумеруем монеты и зададим их множеством S = {1, 2, . . . , n}. Множества номеров мо- нет, взвешиваемых на левой и правой чашах весов, можно обозна- чить через S
L
и S
R
соответственно. Ясно, что взвешивание имеет смысл, только если мощности множеств S
L
и S
R
совпадают, т.е. на каждой чаше весов лежит одинаковое количество монет. Взвеши- вание будем обозначать знаком «:», тогда у каждого взвешивания
(S
L
) : (S
R
) могут быть три возможных исхода. Множество монет
S
L
может быть легче, тяжелее или одинаково по весу с множе- ством S
R
. Тогда будем обозначать эти исходы взвешивания как
«» или «=», соответственно. Пример взвешиваний для че- тырех монет приведен на рис. 3.1. Овалы обозначают взвешива- ния, квадраты - исходы с указанием номера фальшивой монеты и является ли она более легкой или более тяжелой, чем остальные.
Случай отсутствия фальшивой монеты обозначен как «0», пере- черкнутые квадраты соответствуют случаям, которые не могут произойти.
Будем оценивать максимальное число взвешиваний , необхо- димое для решения задачи, т.е. худший случай. Как видно из рис. 3.1, решена задача за 3 взвешивания в худшем случае. За- метим, что даже в лучшем случае нам нужно как минимум 2

взвешивания. Можно ли достичь лучшего результата?
На рис. 3.1 представлено другое решение задачи о взвешива- нии четырех монет. На первом шаге взвешиваем не пару монет, а все монеты, разбив их на два множества. В результате добились того, что в лучшем случае понадобится всего одно взвешивание,
однако в худшем случае число взвешиваний опять равно 3.
69

(1) : (2)
(1) : (3)
(1) : (4)
0 4 Т
4 Л
3 Т
3 Л
(1) : (4)
2 Т
1 Л
(1) : (4)
2 Л
1 Т
=
=
=
>
>
>
>
>
=
=
Рис. 3.1. Решение задачи о фальшивой монете
Отметим, что в отличие от первого варианта взвешиваний,
изображенного на рис. 3.1, во втором варианте не только опре- делили схему взвешивания, но и ввели новое понятие кандидатов в фальшивые монеты. Действительно, рассмотрим результат пер- вого взвешивания, (1, 2) : (3, 4). Пусть (1, 2) L
= (1, 2), и S
R
= (3, 4). Тогда
S
L
R
. По этому результату нельзя судить, является ли фаль- шивая монета более легкой или более тяжелой, чем все остальные,
и в каком множестве она находится. Однако можно предположить
(и даже более точно - можно утверждать), что если фальшивая монета принадлежит множеству S
L
, то фальшивая монета легче остальных, обозначим такое множество с помощью буквы Л. В на- шем случае, если монеты с номерами 1 или 2 фальшивы, то они легче настоящих. Если же фальшивы монеты с номерами 3 или
4, то они тяжелее настоящих, будем обозначать соответствующее множество с помощью буквы Т. На рис. 3.2 легкие и тяжелые кан- дидаты в фальшивые монеты обозначаются с помощью пометок на ребрах дерева.
Очевидно, можно ответить на вопрос об оптимальном числе взвешиваний, продолжая перебирать по возможным схемам выбо- ра монет. Так как число монет конечно, то рано или поздно такой перебор может быть завершен. Пока остановимся на полученных двух решениях и попробуем проанализировать, что же они дали
70

(1,2) Л
(3,4) Т
(1,2) Т
(3,4) Л
(1,2) : (3,4)
(3) : (4)
4 Т
3 Т
(1) : (2)
1 Л
=
=
>
>
>
=
0 2 Л
(3) : (4)
3 Л
4 Л
(1) : (2)
2 Т
=
>
>
=
1 Т
Рис. 3.2. Другое решение задачи о фальшивой монете нам с точки зрения общего подхода к решению задачи.
Как известно, любая стратегия взвешивания монет может быть описана с помощью тернарного, или троичного дерева. Другими словами, рассматриваемая задача принадлежит к классу задач ,
описываемых тернарными деревьями. Подобная классификация задачи дает возможность проводить анализ не каждого конкрет- ного решения, а всех решений в целом, опираясь на известные свойства деревьев.
Таким образом, перебор по возможным способам взвешивания фактически является перебором по различным тернарным дере- вьям, которых, конечно, экспоненциально много. С другой сторо- ны, попробуем определить, что вообще возможно достигнуть при решении данной задачи, используя ее принадлежность именно к данному классу.
Из рис. 3.1 и 3.2 видно, что, изображая последовательность взвешиваний с помощью дерева, приписываем каждое взвешива- ние вершине дерева, не являющейся листом (изображено с помо- щью овалов), в то время как исходы, в том числе и невозможные,
соответствовали листьям дерева (изображено с помощью квадра- тов). Все вершины дерева могут быть упорядочены по уровням,
71

В
а
=
=
>
В
а
И
И
И
=
>
В
а
И
И
И
=
>
В
а
И
И
И
=
>
В
а
И
И
И
=
>
В
а
=
>
В
а
=
>
В
а
>
К
В
Л
У
0
У
1
У
l
- 1
У
l
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
Г
а =
l
Рис.
3.3.
Т
ернарное дерево взвешиваний
72

т.е. по их удаленности от корня дерева. Номер уровня равен чис- лу ребер, которые должны пройти от корня, чтобы попасть в вер- шину данного уровня (рис. 3.3). Если глубина дерева - уровень самого удаленного от корня листа, то эта величина равна числу взвешиваний в худшем случае.
Сколько всего возможных исходов в нашей задаче? Каждая из n монет может оказаться фальшивой легкой или фальшивой тяжелой, кроме того, фальшивых монет может не оказаться вовсе.
Таким образом, имеем 2n + 1 исходов. Это означает, что в дереве,
соответствующем схеме взвешиваний, должно быть не менее, чем
2n + 1 листьев. Троичное дерево глубины l содержит не более,
чем 3
l листьев. Отсюда можно оценить минимально возможную глубину дерева
3
l
≥ 2n + 1,
и следовательно,
l ≥ log
3
(2n + 1).
(3.1)
Таким образом, при n = 4 минимально возможное число взве- шиваний больше или равно 2. Здесь имеется в виду не минималь- ное число взвешиваний для данной схемы - как на рис. 3.2, а воз- можны случаи, когда решение задачи находится уже после перво- го взвешивания, - оцениваем худший вариант, т.е. максимальное число взвешиваний для данной схемы, другими словами, ищем минимум среди максимальных глубин всех деревьев, имеющих не менее, чем 2n + 1 листьев.
Однако можно показать, что не существует способа взвешива- ния, который дал бы равенство в оценке (3.1).
Т е о р е м а 3.1
Число взвешиваний в худшем случае для задачи о фальшивой монете оценивается как l > log
3
(2n + 1).
Доказательство. Как уже говорили, для n монет возмож- но 2n + 1 исходов. Каждое взвешивание может иметь три воз- можных результата и для каждого результата формируется своя
73

схема дальнейших взвешиваний. При этом схема имеет свое коли- чество возможных исходов, учитывающих результат последнего взвешивания. Пусть при первом взвешивании |S
L
| = |S
R
| = k, т.е.
используется k монет на одной чаше весов и k монет - на другой,
где k ≤ n/2 . Если при этом S
L
R
, то монеты из S
L
объяв- ляем кандидатами в легкие фальшивые монеты, а монеты из S
R
- кандидатами в тяжелые фальшивые монеты. Таким образом,
при этом результате первого взвешивания возможно 2k исходов.
Аналогично, при S
L
> S
R
возможно 2k других исходов. Следова- тельно, при S
L
= S
R
возможны оставшиеся 2n + 1 − 4k исхода.
Если в (3.1) выполняется равенство, это значит, что тернарное дерево является полным и все его листья находятся на l-м уровне.
Но для этого необходимо, чтобы после каждого взвешивания воз- можные исходы распределялись по трем ветвям равномерно и вы- полнялось равенство
2k = 2n + 1 − 4k,
что невозможно, так как 2k является всегда четным числом, а
2n + 1 − 4k всегда нечетно.
При доказательстве теоремы 3.1 использовали важную идею:
чтобы дерево взвешиваний было оптимальным или, по крайней мере, возможно ближе к оптимальному нужно, чтобы исходы рас- пределялись равномерно по всем результатам каждого взвешива- ния.
Итак, получили оценку для худшего числа взвешиваний в за- даче о фальшивой монете, связав эту задачу с классом задач,
описываемых тернарными деревьями. Теперь рассмотрим немно- го модифицированную задачу.
Задача 3.2 (задача о фальшивой монете при наличии этало- на). Имеется n монет, среди которых возможно находится одна фальшивая, и еще одна монета, про которую точно известно , что она настоящая. Требуется определить фальшивую монету за ми- нимальное число взвешиваний или установить, что фальшивых монет нет.
74

Решение. Данная задача отличается от предыдущей наличи- ем дополнительной эталонной монеты, но оказывается, что эта дополнительная монета позволяет строить оптимальные деревья взвешиваний, для которых в (3.1) выполняется равенство. Обо- значим через n l
число, для которого выполняется равенство
3
l
= 2n l
+ 1.
(3.2)
При рассмотрении предыдущей задачи в теореме 3.1 получи- ли: для выполнения равенства (3.1) нужно, чтобы дерево взвеши- ваний являлось полным. Следовательно, если удастся построить такое оптимальное дерево из l уровней, то оно задаст схему из l взвешиваний для n l
монет. Заметим, что справедливо следующее соотношение:
n l
= 3n l−1
+ 1.
(3.3)
Так как при n
0
= 0 в (3.2) получаем равенство, 3 0
= 2 · 0 + 1,
то отсюда с использованием (3.3) можно получить n
1
= 1, n
2
=
4, n
3
= 13 и т.д. Решением (3.2) является последовательность
0, 1, 4, 13, 40, . . ..
Таким образом, при выполнении равенства (3.2) множество из n
l монет разбивается на три равные части по n l−1
монет и еще остается одна монета. Рассмотрим разные ситуации, которые мо- гут возникать в процессе взвешивания.
Схема 1. Пусть в начале взвешивания имеем n i
монет, где n i
принадлежит последовательности (3.3) для некоторого i. Поло- жим на каждую чашу весов по n i−1
монет, где n
i
= 3n i−1
+ 1,
далее добавим на левую чашу весов эталонную монету, а на пра- вую - одну из оставшихся n i−1
+ 1 монет. Обозначим взвешивае- мые множества, как и ранее, через S
L
и S
R
Теперь пусть в результате взвешивания S
L
= S
R
. Так как эта- лонная монета участвовала во взвешивании, очевидно, что фаль- шивая монета, если она есть, находится среди неиспользованных n
i−1
монет, и задача сводится к задаче с n i−1
монетами. При этом
75

результате взвешивания у нас остаются возможными 2n i−1
+ 1 =
3
i−1
исходов. Теперь, пусть S
L
R
. Это означает, что фальши- вая монета находится либо в множестве S
L
и при этом она легче остальных, либо в множестве S
R
и тогда она тяжелее остальных.
При этом есть n i−1
подозрительных легких монет и n i−1
+ 1 по- дозрительных тяжелых и вместе это снова дает 2n i−1
+ 1 = 3
i−1
возможных исходов.
Наконец, пусть S
L
> S
R
. Тогда у нас есть n i−1
кандидатов в тяжелые монеты и n i−1
+1 кандидатов в легкие и всего 2n i−1
+1 =
3
i−1
исходов. Итак, при такой схеме первого взвешивания действи- тельно получаем, что 3
i изначальных исходов равномерно распре- делились по результатам взвешивания. Чтобы определить, можно ли задать схему взвешиваний так, чтобы после каждого взвеши- вания исходы разбивались на равное число частей, рассмотрим результаты взвешивания. Очевидно, при S
L
= S
R
приходим к той же задаче, только с меньшей размерностью, и всегда снова можем выполнить взвешивание по схеме 1, но при меньшем значении i.
Схема 2. Пусть теперь S
L
R
. В этом случае определим стратегию взвешивания следующим образом. Исходными данны- ми является то, что на каком-то шаге i в последовательности взве- шиваний имеем 3
i
= 2n i
+ 1 монет, среди которых n i
кандидатов в легкую фальшивую монету и n i
+ 1 кандидатов в тяжелую, при этом число n i
является числом вида (3.3)
n i
= 3n i−1
+ 1.
Положим на каждую чашу весов по n i−1
легких кандидатов и n
i−1
+1 тяжелых. Так как всего 2n i
+1 = 2(3n i−1
+1)+1 = 6n i−1
+3
монет, а взвешиваем
2n i−1
+ 2n i−1
+ 2 = 4n i−1
+ 2
монет, то остается еще 2n i−1
+ 1 монет, среди которых n i−1
+ 1
легких и n i−1
тяжелых. Так как на обеих чашах весов одинаковое число легких и тяжелых монет , то если весы не уравновешены,
это дает n i−1
кандидатов в легкие монеты (с чаши, оказавшей- ся легче) и n i−1
+ 1 кандидатов в тяжелые (с чаши, оказавшейся
76

тяжелее). Это приводит нас к исходным данным этой же схемы
(схемы 2), но для 3
i−1
= 2n i−1
+ 1 монет. Если чаши весов уравно- вешены, то это значит, что надо искать фальшивую монету среди невзвешивавшихся n i−1
+ 1 легких и n i−1
тяжелых монет, что со- ответствует схеме 3. Очевидно, во всех результатах взвешивания возможными остается 2n i−1
+1 исходов, т.е. снова множество всех возможных исходов разбивается на три равные части.
Схема 3. Пусть теперь S
L
> S
R
. В этом случае имеем 3
i
=
2n i
+ 1 монет, среди которых n i
+ 1 кандидатов в легкую фаль- шивую монету, и n i
кандидатов в тяжелую. Все рассуждения ана- логичны схеме 2, с той разницей, что при взвешивании нужно на каждую чашу весов положить n i−1
+ 1 легких кандидатов, и n i−1
тяжелых. Если весы не уравновешены, это снова дает нам схе- му 3 для 3
i−1
монет, в противном случае получаем условия для взвешивания, соответствующие схеме 2. Снова во всех случаях множество возможных исходов разбивается на три равные части по 2n i−1
+ 1.
Таким образом, имеем три раз-
1 2
3
=
>
=
=

Рис. 3.4. Переходы между схемами взвешиваний в за- даче о фальшивой монете личных состояния, описанных вы- ше и правило взвешивания для каж- дого состояния. В зависимости от результата взвешивания переходим в другое состояние (или остаемся в том же), но для меньшего чис- ла монет. При каждом взвешива- нии число возможных исходов рав- номерно распределяется по резуль- татам взвешивания. Схема перехо- дов между состояниями показана на рис. 3.4. Пример взвешиваний для 27 монет приведен на рис. 3.5.
77

Дана шахматная доска размером 8×8, из которой были вырезаны два противоположных по диагонали угла, и 31 кость домино; каждая кость домино может закрыть два квадратика на поле. Можно ли вымостить костями всю доску? Дайте обоснование своему ответу.

Решение

С первого взгляда кажется, что это возможно. Доска 8×8, следовательно, есть 64 клетки, две мы исключаем, значит остается 62. Вроде бы 31 кость должна поместиться, правильно?

Когда мы попытаемся разложить домино в первом ряду, то в нашем распоряжении только 7 квадратов, одна кость переходит на второй ряд. Затем мы размещаем домино во втором ряду, и опять одна кость переходит на третий ряд.

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

Шахматная доска делится на 32 черные и 32 белые клетки. Удаляя противоположные углы (обратите внимание, что эти клетки окрашены в один и тот же цвет), мы оставляем 30 клеток одного и 32 клетки другого цвета. Предположим, что теперь у нас есть 30 черных и 32 белых квадрата.

Каждая кость, которую мы будем класть на доску, будет занимать одну черную и одну белую клетку. Поэтому 31 кость домино займет 31 белую и 31 черную клетки. Но на нашей доске всего 30 черных и 32 белых клетки. Поэтому разложить кости невозможно.

Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу