Пример 1. Из шахматной доски вырезали две противоположные угловые клетки. Докажите, что оставшуюся фигуру нельзя разрезать на «домино» из двух клеток
Решение. Каждая фигура «домино» содержит одну белую и одну чёрную клетку. Но в нашей фигуре 32 чёрных и 30 белых клеток (или наоборот).
Пример 2. Можно ли все клетки доски 9 × 9 обойти конем по одному разу и вернуться в исходную клетку?
Решение. Каждым ходом конь меняет цвет клетки, поэтому, если существует обход, то число чёрных клеток равно числу белых, что неверно.
Пример 3. Дан куб 6 × 6 × 6. Найдите максимально возможное число параллелепипедов 4 × 1 × 1 (со сторонами параллельными сторонам куба), которые можно поместить в этот куб без пересечений.
Идея решения. Легко поместить 52 параллелепипеда внутрь куба. Докажем, что нельзя больше. Разобьем куб на 27 кубиков 2 × 2 × 2. Раскрасим их в шахматном порядке. При этом образуется 104 клетки одного цвета (белого) и 112 другого (чёрного). Осталось заметить, что каждый параллелепипед содержит две чёрных и две белых клетки.
Ответ: 52.
Пример 4. Плоскость раскрашена в два цвета. Докажите, что найдутся две точки одного цвета, расстояние между которыми равно 1.
Решение. Рассмотрим равносторонний треугольник со стороной 1. По принципу Дирихле по крайней мере две из его трёх вершин должны быть покрашены в один цвет.
Игры
Под понятием математической игры мы понимаем игру двух соперников, обладающую следующим свойством. В каждый момент игры состояние характеризуется позицией, которая может изменяться только в зависимости от ходов игроков. Для каждого из игроков некоторые позиции объявляются выигрышными. Добиться выигрышной для себя позиции и есть цель каждого. Иногда игры допускают ничью. Это означает, что ни один из игроков не может добиться выигрышной для него позиции, или некоторые позиции объявлены ничейными.
Например, шахматы, шашки, крестики-нолики являются математическими играми. А игры в кости, домино, большинство карточных игр математическими играми не являются, так как состояние игры зависит не только от ходов соперника, но и от расклада или результата бросания кости.
В математических играх существуют понятия выигрышной стратегии, т. е. набора правил (можно сказать, инструкции или алгоритма), следуя которым, один из игроков обязательно выиграет (не зависимо от того, как играет его соперник), и ничейной стратегии, следуя которой один из игроков обязательно добьётся либо выигрыша, либо ничьей.
В любой математической игре существует либо выигрышная стратегия для одного из игроков, либо ничейные стратегии для обоих (если игра допускает ничью). В зависимости от этого игра называется выигрышной для первого или второго игрока, или ничейной.
Например, крестики-нолики (на доске 3 × 3) являются ничейной игрой. К какому из перечисленных случаев относятся шахматы и шашки неизвестно. Хотя стратегия (либо выигрышная, либо ничейная) в этих играх существует, она не найдена, поэтому соревнования по этим играм пока представляют интерес.
Соответствие. Наличие удачного ответного хода (может обеспечиваться симметрией, разбиением на пары, дополнением числа).
Решение с конца. Последовательно определяются позиции, выигрышные и проигрышные для начинающего. Очередная позиция являются выигрышной, если из неё можно получить ранее определённую проигрышную позицию, и является проигрышной, если любой ход из неё ведёт к попаданию в ранее определённую выигрышную позицию.
Передача хода. Если мы можем воспользоваться стратегией противника, то наши дела не хуже, чем у него. Например, выигрыш (или ничья) обеспечивается, когда можно по своему желанию попасть в некоторую позицию либо заставить противника попасть в неё.
Достарыңызбен бөлісу: |
