Нестандартные задачи по математике

Решение.

Четность числа бананов не меняется, если число бананов было четным, то оставшийся плод ананас, если число бананов было нечетным, то – банан.

14. На прямой стоят две фишки: слева красная, справа синяя. Разрешается производить любую из двух операций: вставку двух фишек одного цвета подряд (между фишками или с краю) и удаление пары соседних одноцветных фишек (между к

оторыми нет других фишек). Можно ли с помощью таких операций оставить на прямой ровно две фишки: слева синюю, а справа красную?

Решение.

Рассмотрим число разноцветных пар (не только соседних), где левая фишка красная, и заметим, что четность этого показателя не меняется. Но в исходной ситуации наш показатель равен 1, а в желаемой ситуации - нулю. Поэтому перейти к желаемой ситуации невозможно.

15. На острове Серобуромалин живут хамелеоны: 13 серых, 15 бурых и 17 малиновых. Если 2 хамелеона разных цветов встречаются, то они оба меняют свой цвет на третий. Может ли случиться, что в некоторый момент все хамелеоны на острове станут одного цвета?

Указание.

Рассмотрите остатки от деления чисел Б бурых, С серых и М малиновых хамелеонов на 3 и проверьте, что попарные разности у этих остатков не меняются.

16. Докажите, что в игре «15» нельзя поменять местами фишки «15» и «14», оставив остальные на месте.

Идея решения.

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

17. На 44 деревьях, расположенных по кругу, сидели по веселому чижу. Время от времени какие-то два чижа перелетают на соседнее дерево - один по часовой стрелке, а другой - против. Могут ли все чижи собраться на одном дереве?

Решение.

Пронумеруем деревья по кругу с 1-го по 44-е. Сумма номеров деревьев, на которых сидят чижи либо не меняется, либо уменьшается на 44, либо увеличивается на 44. Тем самым, остаток от деления этой суммы номеров на 44 не меняется. Изначально этот остаток равен 22, а если все чижи усядутся на одно дерево, то он будет равен нулю. Поэтому чижи не смогут собраться на одном дереве.

18. Можно ли разрезать выпуклый 17-угольник на 14 треугольников?

Общая постановка задачи.

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

Очевидно, описанные ситуации об­ладают следующим свойством: если из позиции a можно перейти в пози­цию р и из p можно перейти в пози­цию h, то из a можно перейти в h. Это свойство называется транзитив­ностью.

Рассмотрим конкретную задачу.

Задача 1. Круг разделен на n секторов, в которых как-то расстав­лены n фишек. Разрешается одно­временно передвинуть любые две фиш­ки: одну — на один сектор по часовой стрелке, другую — на один сектор в противоположном направлении. Мож­но ли из позиции M, в которой в каж­дом секторе стоит' по одной фишке, перейти к позиции V, в которой все фишки собраны в каком-нибудь од­ном секторе?

В данной задаче, кроме свойства транзитивности, имеет место также следующее важное свойство: если из позиции aможно перейти в пози­цию р, то и из р можно перейти в a. Это свойство называется симмет­ричностью.

Свойство симметричности соблю­дается не во всех задачах рассмат­риваемого типа; например, в шах­матах пешки назад не ходят. В этой статье мы ограничимся задачами, для которых условие симметричности выполнено.

Условимся считать, что из любой позиции a можно «перейти» в нее же. Это свойство называется рефлексив­ностью.

Назовем позиции a и p эквива­лентными, если по заданным прави­лам из a можно перейти в p (ввиду предположенной симметричности это равносильно тому, что из pможно пе­рейти в a). Эквивалентность позиций a и p мы будем обозначать так: a~ p; неэквивалентность — так: a ~/ p.

Поскольку эквивалентность позиций рефлексивна, симметрична и транзитивна, исходное множество М разбивается на непустые непересекающиеся подмножества (рис. 1): М = M1UM2UM3U . В каждом из подмножеств Mi, все позиции экви­валентны: если aиз Мi, и p из Mi, то a~ p. Если же позиции a и p принадлежат разным подмножест­вам: aиз Mi pиз Mj ( i отлично от j ), то a и p не эквивалентны ). Подмножества Мi мы будем называть орбитами. Повторим еще раз: если мы находимся в позиции a, принадлежащей какой-нибудь орбите Mi, то мы можем, перемещаясь по этой орбите, пере­браться из позиции a в любую другую позицию, принадлежащую орбите. С другой стороны, сойти с этой орбиты, т. е. перебраться с по­зиции a на позицию p, принадлежа­щую любой другой орбите, мы не можем. Орбит может быть как конечное, так и бесконечное число. Впрочем, если множество М конечно, то, ра­зумеется, и число орбит конечно. Инвариант.Числовая функция f, определенная на множестве «позиций» M, назы­вается инвариантной функцией, или инвариантом, если на эквивалент­ных позициях она принимает одина­ковые значения: если a~ р, то f(а) = f(р). (1)

Задача 1 (продолжение). Пусть п = 2т. Раскрасим секторы через один в серый и белый цвет. Тогда при каждом перемещении число фишек в белых секторах либо не меняется (рис. 2), либо увеличи­вается на 2 (рис. 3), либо умень­шается на 2 (рис. 4). Для произвольной расстановки a фишек по секторам обозначим через б (а) число фишек в белых секторах. Рассмотрим теперь такую функцию g.

0, если б (a) четно,

g(a) =

1, если б (a) нечетно.

Из сказанного выше вытекает, что эта функция g (четность числа фишек в белых секторах) является инвариан­том. Поскольку п = 2т, для конеч­ной позиции v имеем g(v) = 0. Если т = 2k+ 1, то n/2 нечетно. Значит, для начальной позиции w имеем g(w) =1. Из того, что g(w) отлично отg(v) вытекает, что позиции w и v не эквивалентны. Таким образом, в этом случае

(п = 2 т, т = 2 k + 1) из позиции w нельзя перейти в пози­цию v. Ну, а если т =2 k? Тогда n/2 четно и g(w) = g(v) = 0. В этом случае инвариант g не дает возможности установить эквивалентны позиции wи vили нет.

 Скачать реферат