Инварианты. Разрезания. Раскраски. Игры.

Олимпиадные задачи на инварианты можно условно разбить на два вида: те, в которых требуется доказать некий инвариант, т. е. он явно определен, и те, в которых инвариант используется при решении и сразу не очевиден. Существует также класс задач, при решении которых используются полуинварианты – значения точной верхней и нижней граней для некоторой величины. Наиболее часто они используются в задачах на доказательство экстремума какой - либо величины. Рассмотрим способ решения задач по методу “Инвариант”.

В некоторых задачах по математике дается набор преобразований исходного объекта и спрашивается: можно ли, используя эти преобразования, получить из одного состояния объекта другое? Перебором вариантов часто легко убедиться в правильности ответа “нельзя”, однако обосновать этот ответ бывает трудно. Методом, позволяющим во многих случаях решать доказательную часть таких задач, является метод инвариант. Инвариантом называется нечто, не меняющееся в преобразованиях, например, число, набор чисел, четность какого – либо числа и другое. Если значение инварианта в двух состояниях объекта различно, то одно из них нельзя получить из другого. Придумать инвариант должен ученик, самостоятельно решающий задачу; обычно это вызывает у него затруднения. В качестве инварианта чаще всего рассматриваются четность (нечетность) чисел и остаток от деления. Причем применение четности – одна из наиболее встречающихся идей при решении олимпиадных задач.

Задачи Инварианты.

Задача 1. На вешалке висят 20 платков. 17 девочек по очереди подходят к вешалке и либо снимают, либо вешают платок. Может ли после ухода девочек остаться ровно 10 платков?

Решение.

 После подхода первой девочки количество оставшихся платков либо 19, либо 21 (нечетное количество); после подхода второй девочки – либо 18, либо 20, либо 22 (четное количество); после подхода третьей девочки – либо 17, либо 21, либо 23, либо 19 (нечетное количество). После подхода 17 девочки остается нечетное количество платков. Получается противоречие. Значит, 10 платков остаться не может.

Задача 2. В таблице, где имеются 15 чисел (-1), можно производить следующую операцию: одновременно изменить знак двух (не более, не меньше) чисел в таблице. Можно ли, применяя эту операцию конечное число раз, получить таблицу, состоящую из (+ 1)?

Решение. Ответ: нельзя. Так как число чисел в таблице нечетно, а после каждой операции число чисел (+ 1) в таблице четно. На языке инвариантов это означает: инвариантом таблицы относительно введенной операции является произведение всех чисел в таблице. В начальный момент это произведение равно ( - 1), а нам нужно получить таблицу, инвариант которой равен ( + 1).

Задача 3. На доске написаны числа 1, 2, 3, …, 1998. За один ход разрешается стереть любые два числа и вместо них записать их разность. В результате многократного выполнения таких действий на доске окажется записанным одно число. Может ли оно быть нулем?

Решение.

Не может. Так как вначале на доске 999 нечетных чисел. На каждом шаге их количество не меняется, если среди выбранных чисел не более одного нечетного числа. А если выбранные числа оба нечетны, то количество нечетных чисел уменьшается на два. Таким образом, инвариант преобразования: количество нечетных чисел нечетно. Поэтому в конце должно остаться нечетное число. А нуль – четное число.

 ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задача 1. На доске написаны 15 плюсов и 10 минусов. Разрешается стереть любые два знака и записать вместо них плюс, если они одинаковы, и минус, если они различны. Какой знак останется на доске после выполнения 2, 4 таких операций?

Задача 2. В алфавите языка племени АУ всего две буквы: А и У. В результате следующих замен сочетаний букв смысл любого слова не изменяется:

УАУАА, УАААУ, ААУУА, АААУУ

(замену можно делать в любом месте слова).

Являются ли в этом языке синонимами слова УАА и АУУ?

Задача 3. Вася разорвал листок бумаги на 10 частей, некоторые из получившихся кусков он снова разорвал на 10 частей и т.д. Мог ли он получить 2012 кусков бумаги?

Задачи на разрезание.

1уровень

Задача 1. Разрежьте фигуры, изображенные на рисунке, на две равные части по линиям сетки так, чтобы в каждой из частей был кружок. 

 

Ответ:

Задача 2. Разрежьте фигуры, изображенные на рисунке, на две равные части по линиям сетки так, чтобы в каждой из частей был кружок.

 
2 уровень

Задача 1. Разрежьте на 4 равные части

3 уровень

1.Разрежьте ракету на 3 каких-то части и сложите из них квадрат.

2.(Самостоятельно) Разрезав фигуру на 4 одинаковые части, сложите квадрат.

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

 Задачи на раскраски.

На математических олимпиадах часто встречаются задачи, решаемые методом раскраски. Ознакомимся с этим методом.

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

Решение: Раскрасим клетки доски в диагональном порядке в три цвета. При такой раскраске при любом расположении фигурки 3 * 1 она закрывает по одной клетке разного цвета, значит, если бы мы смогли разрезать прямоугольник на фигурки 3 * 1, то квадратиков каждого цвета было бы равное количество, а у нас цвета 1 – 21 клетка, цвета 2 – 22 клетки. Значит, нельзя разрезать. Ответ: нельзя.

Задача №2 Может ли Карлсон на спор с Малышом обойти шахматным конём всю шахматную доску размером 7 * 7 так, чтобы конь побывал на каждой клетке по одному разу и вернулся в начальную клетку?

Решение: Пусть конь стоит на чёрном поле. После очередного хода он окажется на белом поле, т. е. при движении коня цвет поля чередуется. Если конь обойдёт все клетки доски по одному разу, он сделает 48 ходов и окажется на клетке того же цвета, что и клетка с которой он вышел. С неё на начальную клетку, которая того же цвета, он за оставшийся ход не попадёт. Ответ: не может.

Задача №3 Можно ли разрезать квадрат 10 * 10 на прямоугольники 1 * 4?

Решение: Раскрасим клетки доски в диагональном порядке в четыре цвета. Решение аналогично решению задачи №1. Разрезать нельзя. Ответ: нельзя.

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

           Решение: В красный цвет раскрасим те клетки, на которые может перейти левая нижняя шашка. Видим, что на эти же клетки могут перейти и все оставшиеся угловые шашки. Далее, раскрасим в синий цвет те клетки, на которые может переместиться нижняя средняя шашка. Видим, что на эти же клетки перемещается верхняя средняя шашка. Аналогично закрасим в желтый цвет клетки, на которые может переместиться центральная шашка. Оставшиеся поля закрасим зеленым цветом – на эти клетки могут переместиться две оставшиеся шашки.

 Теперь сравним раскраски полей в квадратах 3×3. Все угловые квадраты раскрашены одинаково, значит, можно переместить шашки в левый и правый верхние углы. Экспериментальным путем мы сделали это. А вот в центральный квадрат переместить шашки не сможем, так как раскраска отличается от раскраски угловых квадратов.

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

а)левом верхнем;
б)правом верхнем?

Задача №6 (Самостоятельно) Доказать, что клетчатую доску 10×10 нельзя разрезать по линиям сетки на прямоугольники 1×4.
 Подсказка: может быть 9 решений.

Надеемся, что приведённые решения наглядно проиллюстрировали красоту метода раскраски, а заодно и специфические свойства каждой из раскрасок в отдельности.

Задачи на игры.

Задача №1 Имеется две кучки конфет. В первой 7 конфет, во второй – 5. За один ход разрешается взять любое количество конфет, но из одной кучки. Проигрывает тот, кому нечего брать. Кто выигрывает при правильной игре – начинающий или его партнер? И как для этого ему надо играть?

Решение: При правильной игре выигрывает начинающий игрок. Его стратегия: первым ходом он должен сравнять количеств конфет в кучках, т. е. взять из первой кучки 2 конфеты. Каждый следующий его ход должен быть «симметричен» ходу второго игрока,  т. е. если «второй» берёт n конфет из одной кучки, то «первый»  должен взять также n конфет, но из другой кучки. Таким образом, если может сделать ход «второй» игрок, то может сделать ход и «первый». Так как после каждого хода количество конфет уменьшается, то наступит момент, когда «второй» не сможет сделать ход (ни в одной из кучек конфет не останется) и проиграет.

Задача №2 (Самостоятельно) В кучке лежат 25 камней. Двое по очереди берут из неё 1, 2 или 3 камня. Проигрывает тот, кто берёт последний камень.

Задача №3 Два игрока кладут по очереди пятаки на круглый стол так, чтобы ни не накладывались друг на друга. Проигрывает тот, кто не сможет положить пятака. Кто выиграет при правильной игре и как он должен для этого играть?

Решение: При правильной игре выигрывает начинающий. Его стратегия: первым ходом он кладёт пятак в цент стола. Каждым следующим своим ходом он кладёт пятак симметрично пятаку, положенному вторым игроком относительно центра стола. Таким образом, если сможет сделать ход «второй» игрок, то может сделать ход и «первый». Так как после каждого хода «свободная» поверхность стола уменьшается, то наступит момент, когда второй не сможет сделать ход и проиграет.

Задача №4 (Самостоятельно) На окружности расставлено 88 точек. За один ход разрешается соединить любые две из этих точек отрезком, е пересекающим отрезков, проведённых раннее. Проигрывает тот, сто не сможет сделать хода.

Задача №5 Имеется полоска клетчатой бумаги длиной  n (клеток). На одной из клеток стоит фишка. Играют двое, ходят по очереди. Ход состоит в передвижении фишки на 1, 2, 3 или 4 клетки влево. Проигрывает тот, кому некуда ходить. Как играть, чтобы выиграть? При каких положениях фишки побеждает начинающий, а при каких – его партнёр?

Решение: Пронумеруем клетки числами 0,1,2,3 …, n. В каждую клетку полоски поставим плюс или минус исходя из правил, указанных выше. Клетка 0 – проигрышная, ставим в неё минус, клетки 1,2,3 и 4 – выигрышные( с них за один ход можно попасть в клетку (0)). Клетка 5 – проигрышная  (для того, кто должен из неё ходить). Клетки 6,7,8 и 9 выигрышные, ставим на них плюсы, клетка 10 – проигрышная, ставим минус и т. д. Мы видим, что плюсы и минусы образуют периодическую последовательность с периодом из 5 знаков: -,+,+,+,+, т. е. на клетках с номерами 5k (k = 0, 1, 2, …) стоят минусы, на остальных – плюсы.

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

Задача №6 (Самостоятельно) Двое пишут 2k-значное  число, употребляя только цифры 1, 2, 3, 4,5. Первую цифру пишет первый, вторую – второй, третью – первый и т. д. Может ли второй добиться того, чтобы полученное число разделилось на 9, если первый стремится этому помешать? Рассмотрите два случая: а) k = 10; б) k = 15.

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