Логическая задача на расставление костей домино на шахматной доске. Математические олимпиады и олимпиадные задачи
Дана шахматная доска размером 8×8, из которой были вырезаны два противоположных по диагонали угла, и 31 кость домино; каждая кость домино может закрыть два квадратика на поле. Можно ли вымостить костями всю доску? Дайте обоснование своему ответу.
Решение
С первого взгляда кажется, что это возможно. Доска 8×8, следовательно, есть 64 клетки, две мы исключаем, значит остается 62. Вроде бы 31 кость должна поместиться, правильно?
Когда мы попытаемся разложить домино в первом ряду, то в нашем распоряжении только 7 квадратов, одна кость переходит на второй ряд. Затем мы размещаем домино во втором ряду, и опять одна кость переходит на третий ряд.
В каждом ряду всегда будет оставаться одна кость, которую нужно перенести на следующий ряд, не имеет значения сколько вариантов раскладки мы опробуем, у нас никогда не получится разложить все кости.
Шахматная доска делится на 32 черные и 32 белые клетки. Удаляя противоположные углы (обратите внимание, что эти клетки окрашены в один и тот же цвет), мы оставляем 30 клеток одного и 32 клетки другого цвета. Предположим, что теперь у нас есть 30 черных и 32 белых квадрата.
Каждая кость, которую мы будем класть на доску, будет занимать одну черную и одну белую клетку. Поэтому 31 кость домино займет 31 белую и 31 черную клетки. Но на нашей доске всего 30 черных и 32 белых клетки. Поэтому разложить кости невозможно.
Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу
6. В коробке 235 спичек. Два игрока берут их по очереди. За один ход можно взять от 1 до 6 спичек. Выигрывает игрок,
взявший последнюю спичку. Кто выигрывает при правиль- ной игре?
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
Доказать, что клетчатую доску 10
х
10 нельзя разрезать по линиям сетки на прямоугольники 1
х
4. (Решения по Д.Ю. Кузнецову.)
Решение 1 . Разделим доску на квадраты 2х2 и раскрасим их в шахматном порядке (рис.1). Заметим, что любой прямоугольник 1х4 содержит поровну (по 2) чёрных и белых клеток, но при данной раскраске на доске 52 чёрных клетки и 48 белых, т.е. не поровну. Значит, разрезать доску 10х10 на прямоугольники 1х4 не удастся.
Решение 2 . Раскрасим доску диагональной раскраской в 4 цвета (рис.2). Заметим, что любой прямоугольник содержит по одной клетке каждого из четырёх цветов, но при данной раскраске на доске по 25 клеток 1-го и 3-го цветов, 26 клеток – 2-го и 24 клетки – 4-го, т.е. не поровну. Значит, разрезать доску 10х10 на прямоугольники 1х4 не удастся.
1. Из шахматной доски вырезали нижнюю правую и левую угловые клетки. Можно ли полученную фигуру разрезать на доминошки 1х2? А если вырезать нижнюю правую и верхнюю левую?
2. Можно ли доску 6х6 разрезать на доминошки, так чтобы среди них было ровно 11 горизонтальных? (Горизонтальная раскраска в два цвета.)
3. Раскрасьте рисунок в четыре цвета так, чтобы соседние части были покрашены в разные цвета. Можно ли обойтись тремя цветами? (См. Занятие 6: Раскраска географической карты - 5-6 класс).
4. В квадрате 4x4 клетки левой половины покрашены в чёрный цвет, а остальные в белый. За одну операцию разрешается перекрасить в противоположный цвет все клетки внутри любого прямоугольника. Как за три операции из первоначальной раскраски получить шахматную?
5. Несколько кузнечиков сидят на одной прямой, причём расстояния между соседями - одинаковы. Каждую минуту один из них прыгает в точку, симметричную ему относительно другого кузнечика. Может ли через некоторое время кузнечик Саша оказаться на том месте, где в начале сидел его сосед Лёша?
6. а) Можно ли разрезать шахматную доску на фигурки, состоящие из 4 клеток в форме буквы "Т"?
б) Можно ли разрезать на такие фигурки шахматную доску 10x10?
7. Можно ли разбить квадрат 8×8 с отрезанным уголком на прямоугольники 1×3?
8. Можно ли доску 10×10 разрезать на фигурки из четырёх клеток в форме буквы"Г"? (Горизонтальная раскраска в два цвета.)
9. Доска 8×8 разрезана на доминошки размером 2×1. Может ли быть 15 вертикальных и 17 горизонтальных доминошек?
10. Треугольник разбит на треугольнички (25 штук), как показано на рисунке. Жук может ходить по треугольнику, переходя между соседними (по стороне) треугольничками. Какое максимальное количество треугольничков может пройти жук, если в каждом он побывал не больше одного раза?
11. Какое наибольшее количество ромбов, каждый из которых составлен из двух равносторонних треугольников со стороной 1, можно вырезать из равностороннего треугольника со стороной 5 (см. рис. предыдущей задачи).
12. Треугольный замок разделён на 100 одинаковых треугольных залов. В середине каждой стены сделана дверь. Сколько залов может осмотреть человек, не желающий нигде побывать больше одного раза?
Глава 2. Задачи о шахматной доске
Подробный рассказ о шахматной математике, к которому мы сейчас приступаем, естественнее всего начать с математических задач о самой доске, пока что не расставляя на ней никаких фигур. Именно этой теме и посвящена настоящая глава.
Рассмотрим прежде всего несколько задач о покрытии доски костями домино размером 2×1. Всюду предполагается, что каждое домино покрывает два поля доски, а каждое поле покрыто одной половиной домино. Начнем со следующей старинной задачи.
Можно ли покрыть домино квадрат размером 8×8, из которого вырезаны противоположные угловые клетки (рис. 2,а)?
Мы могли бы воспользоваться алгебраическими рассуждениями , однако «шахматное» решение и проще, и изящнее. Окрасим наш урезанный квадрат в черно-белый цвет, превратив его в шахматную доску без двух угловых полей a8 и h1 (рис. 2,б). При любом покрытии доски каждое домино покрывает одно белое и одно черное поле. У нас же белых полей на два меньше, чем черных (вырезанные поля - белые), и поэтому необходимого покрытия не существует! Как мы видим, раскраска доски не только позволяет шахматисту легче ориентироваться во время игры, но и служит средством решения математических задач.
В рассмотренной задаче существенным было не то, что из доски вырезаны угловые поля, а то, что они одного цвета. Ясно, что какую пару одноцветных полей ни вырезать, покрыть домино оставшуюся часть доски не удастся. Таким образом, возникает следующая задача.
Пусть теперь на шахматной доске вырезаны два поля разного цвета. Всегда ли можно покрыть оставшуюся часть доски 31 домино?
Оказывается, что всегда. Эффектное доказательство нашел известный американский математик Р. Гомори. Проведем на шахматной доске границы между вертикалями и горизонталями так, как показано на рис. 3. В лабиринте между этими границами черные и белые поля следуют друг за другом, чередуясь, как пуговицы двух цветов на замкнутой нити (путь, по которому можно обойти этот лабиринт, является замкнутым). Какие бы два поля разного цвета мы ни вырезали из доски, нить разорвется: в одном месте, если вырезанные поля находятся рядом, и в двух местах - в противном случае. При этом каждый кусок нити будет состоять из четного числа полей. Следовательно, эти куски, а значит - и всю доску, покрыть домино можно!
Рис. 3. Лабиринт Гомори |
Любопытные идеи, связанные с пуговицами и нитями, мы еще встретим в главе 11.
Предположим, что из шахматной доски вырезаны некоторые поля так, что на оставшуюся ее часть нельзя поместить ни одного домино. Нетрудно проверить, что наименьшее число вырезанных полей, обладающих таким свойством, равно 32 - это все поля одного цвета (белые или черные).
Задачи о шахматной доске и домино составляют лишь небольшую часть огромной серии задач такого сорта. Американский математик С. Голомб создал целую науку, которую назвал полимипо, а его книга, посвященная этой теме, переведена во многих странах мира, в том числе у нас . В общем случае полимино представляет собой односвязную фигуру, состоящую из квадратов. С точки зрения шахматиста односвязность означает, что все квадраты полимино можно обойти ходом ладьи. В зависимости 07 числа квадратов, полимино бывают различного тига. Мономино содержит один квадрат, домино - два, тримино - три, тетрамино - четыре, пентамино - пять, гептамино - шесть квадратов и т. д. В задачах о полимино покрываются разнообразные доски, не обязательно прямоугольные. Мы остановимся еще на нескольких вопросах, связанных с обычной шахматной доской. Очевидно, покрыть дсску только прямыми тримино, т. е. домино 3×1, невозможно, так как 64 не делится на 3. Возникает следующая задача.
Можно ли покрыть шахматную доску 21 прямым тримино и одним мономино? Если это возможно, то какие поля может занимать мономино?
Одно из необходимых покрытий дапо на рис. 4,а. Для определения возможных расположений мономино проведем на доске две системы параллельных прямых, как показано на рис. 4,б.
Легко убедиться, что при любом покрытии каждое тримино покрывает ровно одно поле, через которое проходит сплошная линия, и ровно одно, через которое проходит пунктирная линия. Поскольку число полей, пересекаемых сплошными прямыми, равно 22, так же как и число полей, пересекаемых пунктирными прямыми, а тримино имеется 21, то мономино может покрывать лишь поля, пересекаемые обоими семействами прямых. А таких полей - всего четыре: c3, c6, f3 и f6! Поворачивая доску на 90, 180 и 270°, можно получить соответствующие покрытия для каждого из этих четырех полей.
Следующая задача несколько отличается от рассмотренных выше.
Можно ли шахматную доску покрыть домино так, чтобы на ней нельзя было провести ни одной границы между вертикалями и горизонталями, не пересекая домино?
Если представить себе, что доска - это стенка, а домино - кирпичи, то существование указанной границы (шва) свидетельствует о непрочной кладке. Иначе говоря, в задаче спрашивается, можно ли расположить «кирпичи» так, чтобы «стенка» не рухнула. Прямоугольник, который удается покрыть необходимым образом, называется «прочным». В «прочности» шахматной доски можно убедиться на рис. 5. В общем случае Гарднер показывает, что из домино можно сложить «прочный» прямоугольник, если его площадь четна, а длина и ширина больше четырех, при этом исключение составляет лишь квадрат 6×6.
Ниже мы будем часто иметь дело с прямоугольными шахматными досками того ила иного размера. При этом всегда считается, что доска m×n имеет m вертикалей и n горизонталей (шахматных). Мы говорим, что доска «четна», если число ее полей четно, и «нечетна» - в противном случае. Всюду, где размеры доски не указаны, имеется в виду стандартная шахматная доска, для которой m = n = 8.
Доска 100×4 покрыта домино. Доказать, что ее можно распилить по одной из границ между вертикалями и горизонталями, не затрагивая ни одного домино.
Любая из указанных границ делит доску на две части, состоящие из четного числа полей. Поля каждой части разобьем на два класса: покрытые домино, целиком лежащими в этой части, и покрытые домино, пересекаемыми границей. Так как число полей каждой части четно (быть может, нуль), равно как и число полей первого класса (каждое домино покрывает два поля), то и число полей второго класса четно. А это и значит, что число домино, пересекаемых границей, четно. Всего разделяющих границ существует 102 (99 вертикальных и 3 горизонтальных), н если каждая из них пересекает домино, то в покрытии участвует не менее 102×2 = 204 домино. В нашем же распоряжении их только 200! Фактически мы показали, что прямоугольник 100×4 является «непрочным».
Вопрос о возможности покрытия произвольной прямоугольной доски линейными k-мино (домино k×1) решается следующей теоремой .
Доску m×n можно покрыть линейными k-мино в том и только в том случае, если хотя бы одно из чисел m или n делится без остатка на k.
Проиллюстрируем теорему на следующем примере.
Можно ли покрыть доску 10×10 (на такой доске играют в стоклеточные шашки) прямыми тетрамино?
Прямое тетрамино имеет размеры 4×1, и, значит, в принципе 25 костей могли бы покрыть все поля нашей доски. Однако из теоремы следует, что это невозможно - 10 не делится на 4.
Рассмотрим еще несколько задач о шахматной доске. В решении следующей задачи виовъ используется ее раскраска.
Пусть доска состоит из нечетного числа полей. На каждом ее поле поставим какую-нибудь шахматную фигуру. Можно ли сдвинуть все эти фигуры на соседние поля (по вертикали или горизонтали), чтобы при этом никакие две из них не попали на одно поле?
Задание невыполнимо. Действительно, если бы указанное смещение фигур существовало, то каждая «белая» фигура (стоящая на белом поле) стала бы «черной» (попала на черное поле), а каждая «черная» - «белой».
Таким образом, доска состояла бы из одинакового числа белых и черных полей, а это противоречит ее «нечетности».
Популярными являются задачи о разрезании шахматной доски. Самой известной из них является следующая, принадлежащая С. Лойду.
На полях a1, b2, c3, d4 стоят четыре коня. Разрезать доску на четыре конгруэнтные части (совпадающие при наложении) так, чтобы на каждой из них оказалось по коню.
В задачах на разрезание всегда предполагается, что разрезы производятся только по границам между вертикалями и горизонталями доски. Решение данной задачи показано на рис. 6. Со времен Лойда появилось много новых и более трудных задач на эту тему. В частности, решались задачи о разрезании доски на четыре конгруэнтные части при различных расположениях коней (кони, конечно, играют здесь лишь символическую роль). В этом вопросе имеется еще много нерешенных проблем. Например, до сих пор не известно число способов, которыми можно разрезать обычную доску (без фигур) на две конгруэнтные части.
Рис. 6. Задача Лойда о четырех конях |
Пусть после нескольких разрезов доски образовавшиеся части разрешается перекладывать так, чтобы следующий разрез мог рассечь не одну, а сразу несколько частей. Сколько разрезов потребуется для получения 64 отдельных полей доски (квадратов 1×1)?
Сначала разрежем доску пополам, затем обе половины положим рядом и разрежем доску на четыре одинаковые части и т. д. Всего понадобится 6 разрезов (2 е = 64) и меньшим числом не обойтись.
Пусть теперь части доски разрешается резать только отдельно. Сколько разрезов понадобится для получения 64 полей в этом случае?
Как правило, эта задача (особенно, если она предлагается после предыдущей) вызывает определенные трудности. Видимо, это связано с некоторой инерционностью нашего мышления. Ведь сразу видно, что понадобится 63 разреза! Действительно, каждый разрез увеличивает число частей на единицу; при этом в начальный момент мы имеем одну часть (саму доску), а в конечный - 64 (все поля доски).
Рис. 7. Три задачи на необычной доске |
В задаче на рис. 7,а требуется выполнить три задания, причем одно математическое и два чисто шахматных:
а) разрезать доску на четыре конгруэнтные части;
б) заматовать черного короля кратчайшим путем при ходе белых;
в) заматовать черного короля кратчайшим путем при ходе черных верные играют кооперативно).
Решения: а) как нужно разрезать доску, показано на рис. 7,б; б) при ходе белых мат дается на 12-м ходу:
1-12. Сe1-b4, Крe3-d3-c4, Сe4-c2-b3, Крc4-c3, Сb4-d6, Сb3-d5, Крc3-c2, Сd6-c5, Сd5-c4, Сd6-b4
мат (все ходы черного короля вынуждены и не приводятся); в) при
правильной игре после 1. … Крe6-e7 мат невозможен, так как черный
король скрывается на e8 - 2. Сe1-b4+ Крe7-e8, и чернопольный слон
вынужден уйти с диагонали a3 - e7 ввиду угрозы пата. Однако если черные
играют кооперативно (помогают белым дать мат), то цель достигается всего
через три хода:
1. … Крe6-d6
2. Крe3-d4 Крe6-e7
3. Сe1-b4+ Крe7-e6
4. Сe4-d5 мат.
Ряд полей нашей доски при матовании не используется, но при их исключении не было бы задачи на разрезание доски.
Рис. 8. Парадокс с разрезанием шахматной доски: а) 8×8 = 64; б) 13×5 = 65 |
Рассмотрим теперь один известный парадокс, связанный с разрезанием шахматной доски. Разрежем доску на четыре части, как показано на рис. 8,а (в данном случае нам невыгодно раскрашивать ее поля), и из образовавшихся частей сложим прямоугольник (рис. 8,б). Площадь доски равна 64, а площадь полученного прямоугольника равна 65. Таким образом, при разрезании доски откуда-то взялось одно лишнее поле!
Разгадка парадокса состоит в том, что наши чертежи выполнены не совсем точно (мы умышленно провели толстые линии, чтобы скрыть неточности). При аккуратном построении чертежа на рис. 8,б вместо диагонали прямоугольника появится ромбовидная, чуть вытянутая фигура со сторонами, которые кажутся почти слившимися. Площадь этой фигуры как раз будет равна «лишней» единице.
Известный популяризатор математики начала века Е. Игнатьев придумал «метод шахматной доски», позволяющий выводить различные формулы . Приведем два несложных примера на эту тему.
Найдем сумму n первых натуральных чисел «методом шахматной доски». Для этого на доске (n + 1)×n (на
рис. 9,а n = 8) окрасим в чериый цвет все поля первой вертикали, все
поля второй вертикали (кроме верхнего), третьей вертикали (кроме двух
верхних) и т. д., наконец - нижнее поле n-й вертикали. В результате
белых и черных полей на нашей доске будет поровну, а именно 1 + 2 + … +
n. Поскольку вся доска состоит из п (n + 1) полей, получаем
2 (1 + 2 + … + n) = n(n + 1),
откуда вытекает известная формула для суммы арифметической прогрессии:
1 + 2 + … + n = n(n + 1)/2.
Теперь докажем такую формулу:
8(1 + 2 + … + n) + 1 = (2n + 1)².
Для этого возьмем доску (2n + 1)×(2n + 1) и закрасим ряд ее полей черным цветом так, как показано на рис. 9, 6 (для случая n = 5). Очевидно, каждая черная часть содержит (1 + 2 + … + n) полей. Без учета центрального поля мы имеем здесь четыре одинаковые белые и черные части. Необходимая формула следует из того, что наша доска содержит (2n + 1)² полей и состоит из центрального поля и восьми одинаковых частей (четырех белых и четырех черных - рис. 9,б).
При разгадке парадокса, а также знакомстве с «методом шахматной доски» саму доску можно благополучна заменить листом клетчатой бумаги или таблицей. Существует огромное множество задач с такими объектами, однако их подробное рассмотрение слишком далеко увело бы нас от шахмат.
В заключение главы приведем одно старинное доказательство на шахматной доске… теоремы Пифагора. Нарисуем на доске квадрат, как показано на рис. 10,а. Доска разбивается на этот квадрат и четыре конгруэнтных прямоугольных треугольника. На рис. 10, 6 мы видим те же четыре треугольника, а также два квадрата. Итак, треугольники в обоих случаях занимают одну и ту же площадь. Следовательно, одну и ту же площадь занимают и оставшиеся части доски без треугольников, на рис. 10,а - одного квадрата, а на рис. 10,б - двух. Поскольку большой квадрат построен на гипотенузе прямоугольного треугольника, а маленькие - на его катетах, то «пифагоровы штаны во все стороны равны»!
Разумеется, если говорить строго, наши рассуждения не доказывают теорему Пифагора (исследован лишь некоторый частный случай), а лишь иллюстрируют ее. Но такое доказательство проходит и без использования шахматной доски - для любого прямоугольного треугольника можно подобрать квадрат, который разбивается подобным образом.
Именно такое решение дано в книге Т. Саати «Целочисленные методы оптимизации и связанные с ними экстремальные проблемы» (М., «Мир», 1973).
С. Голомб. Полимино. М., «Мир», 1974.
Она доказана А. Сойфером в статье «Клетчатые доски и полимипо» («Квант», 1972, № 11); там же приведен ряд новых задач о полимино.
Е. Игнатьев. В царстве смекалки, или арифметика для всех. Кн. 1 - 3. М. - Пг., Госиздат, 1923.
На этом занятии мы поговорим о раскрасках и том, как они помогают решать задачи. Рассмотрим нестандартные задачи на разрезания и замощения и способы их решения.
Конспект занятия "Разрезания. Замощения. Раскраски."
Раскраски. Разрезания. Замощения.
Задачами на разрезание увлекались многие ученые с древнейших времен. Решения многих простых задач на разрезание были найдены еще древними греками, китайцами, но первый систематический трактат на эту тему принадлежит перу Абул-Вефа, знаменитого персидского астронома Х века, жившего в Багдаде. Геометры всерьез занялись решением задач на разрезание фигур на наименьшее число частей и последующее составление из них той или иной новой фигуры лишь в начале 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, но в другом углу.
