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

5. Из доски 9 × 9 вырезан угловой квадрат. Можно ли уложить эту доску прямоугольниками 1 × 5?
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

Задача 1: Можно ли квадрат 5 × 5 разрезать на прямоугольники 1 × 2 (доминошки).Задача 2: Из шахматной доски 8 × 8 вырезаны противоположные угловые клетки. Можно ли остаток разрезать на прямоугольники 1 × 2 (доминошки)? Решение: Нет. Каждая доминошка занимает одну чёрную и одну белую клетки, а на доске без углов чёрных и белых клеток разное число.Задача 3: Из противоположных углов доски 10 × 10 вырезаны два квадрата 3 × 3. Можно ли остаток разрезать на доминошки?Задача 4: Придумать связную фигуру на шахматной доске, в которой поровну черных и белых клеток, но которую нельзя разбить на доминошки.Задача 5: Можно ли разрезать квадрат 10 × 10 на 25 фигур ?Задача 6: Решение: Раскрасьте доску в шахматном порядке. Чёрных клеток окажется чётное число, а в каждую фигурку их попадёт одна или три.Задача 7: Можно ли разрезать квадрат 10 × 10 на 25 фигур ? Решение:

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

Задача 8: Можно ли разрезать квадрат 10 × 10 на 25 фигур ? Решение: Покрасьте вертикаличерез одну.Задача 9: Доказать, что доску 8 × 8 без угловой клетки нельзя разрезать на прямоугольники 1 × 3.Задача 10: Можно ли доску 8 × 8 разрезать на один квадрат 2 × 2 и 15 фигур вида ?Задача 11: Квадрат a)5 × 5b)8 × 8 разбили на несколько прямоугольников 3 × 1 и один квадрат 1 × 1. Где может стоять квадрат 1 × 1? Решение: а) В центре, b) На третьей клетке по диагонали от любого угла.

Указание: раскрасьте доску в три цвета.

Задача 12: Какое максимальное количество брусков 1 × 1 × 4 можно вырезать из куба 6 × 6 × 6?Задача 13: Прямоугольник разбит на фигурки и . Одну из потеряли, но заменили ее на . Доказать, что новым набором покрыть исходный прямоугольник нельзя.Задача 14: Можно ли квадрат 16 × 16 разбить на 64 прямоугольника 1 × 4, из которых 31 будут стоять вертикально, а остальные 33 - горизонтально? Решение: Покрасьте каждую четвёртую вертикаль.Задача 15: При каких n квадрат n × n можно разбить на a) ;

b) ? Решение: При n, кратных четырём.

Задача 16: Прямоугольник m × k разбит на прямоугольники 1 × n. Доказать, что m делится на n или k делится на n.

c) для любого n. Решение:

Раскрасьте в n цветов.

Задача 17: Доказать, что прямоугольник m × n можно разбить на прямоугольники a × b, тогда и только тогда, когда выполняются следующие условия:

1) m и n представляются в виде ka + lb (k и l - целые неотрицательные числа)

2) m и n делится на a.

3) m или n делится на b.

Задача 18: Прямоугольник m × n называется прочным, если его можно разбить на доминошки так, что любой разрез прямоугольника пересекает хотя бы одну доминошку. Доказать, что:

a) прямоугольник 2 × n - непрочный

b) прямоугольник 3 × n - непрочный

c) прямоугольник 4 × n - непрочный

d) прямоугольники 5 × 6 и 6 × 8 - прочные

e) если прямоугольник m × n - прочный, то и прямоугольник m × (n + 2) - прочный.

f) * прямоугольник 6 × 6 - непрочный

g) Какие прямоугольники являются прочными, а какие нет? Решение: f) Подсказка: каждая линия в квадрате 6 × 6 пересекает чётное число доминошек.

g) Все прямоугольники m × n, где mn чётно, m,n ≥ 5, кроме 6 × 6.

Задача 19:

Уголком называется фигура вида .

a) Можно ли прямоугольник 5 × 9 разбить на уголки?

b) Доказать, что прямоугольник со сторонами,большими 100 и площадью, делящейся на 3, можно разбить на уголки.

c) Какие прямоугольники можно разбить на уголки, а какие - нет?

Задача 20:

Можно ли доску 2 n × 2 n без угловой клетки разбить на уголки? Решение: Да, можно. Разбиение строится по индукции.

Задача 21: При каких n доску (2n + 1) × (2n + 1) без угловой клетки можно разбить на доминошки, среди которых поровну вертикальных и горизонтальных? Решение: При чётных n.

Доказать, что клетчатую доску 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 одинаковых треугольных залов. В середине каждой стены сделана дверь. Сколько залов может осмотреть человек, не желающий нигде побывать больше одного раза?

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

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

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

Задачами на разрезание увлекались многие ученые с древнейших времен. Решения многих простых задач на разрезание были найдены еще древними греками, китайцами, но первый систематический трактат на эту тему принадлежит перу Абул-Вефа, знаменитого персидского астронома Х века, жившего в Багдаде. Геометры всерьез занялись решением задач на разрезание фигур на наименьшее число частей и последующее составление из них той или иной новой фигуры лишь в начале 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, но в другом углу.