Разработка занятия на тему Олимпиадная математика. Инварианты

Инварианты

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

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

Вспомним определения четного и нечетного числа. Особое внимание надо уделить абстрактному понятию четности, объяснить, что такое "разная четность". Например, число х + 2 имеет ту же четность, что и число х (или оба четные, или оба нечетные), а при прибавлении единицы четность меняется. Применение идеи четности и нечетности основано на двух важных утверждениях (леммах):

Лемма 1. Четность суммы нескольких целых чисел совпадает с четностью количества нечетных слагаемых.

Пример1. Число 1 +2 + 3 + … + 10 - нечетное, так как в сумме 5 нечетных слагаемых.

Пример 2. Число 5 + 7 + 9 + 11 +13 + 15 - четное, так как в сумме 6 нечетных слагаемых.

Лемма 2. Знак произведения нескольких (отличных от 0) чисел определяется четностью количества отрицательных сомножителей.

Пример 3. Число (-1) *(-2) *(-3) *(-4) положительно, так как в произведении четное число отрицательных сомножителей.
Пример 4. Число (-1) *2 * (-3) * (-4) отрицательно, так как в произведении нечетное число отрицательных сомножителей.

Задача 1. На листе бумаги написано число 11. Шестнадцать учеников передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу - как хочет. Может ли в результате получиться число 0?

Нужно предложить выполнить эту операцию учащимся (результат каждого хода записывается на доске), заметить закономерность: после каждого хода характер четности меняется: после первого ученика число становится четным, после второго нечетным; после третьего - четным; после четвертого - нечетным. Тогда после шестнадцатого число будет нечетным. Поэтому нуль в конце получиться не может.

Задача 2. На доске написано 15 чисел: 8 нулей и 7 единиц. Вам предлагается 14 раз подряд выполнить такую операцию: зачеркиваем любые два числа, и если они одинаковые, то дописываем к оставшимся числам нуль, а если разные, то единицу. Какое число останется на доске?

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1

1)Если вычеркиваем два нуля, то дописываем нуль, тогда «0»-7,

«1»-7.Осталось 14 чисел. Сумма -нечетное.

2)Если вычеркиваем две единицы, то дописываем нуль, тогда «0»-9, «1»-5. Сумма -нечетное.

3)Если нуль и единицу, то дописываем единицу, тогда «0»-7,

«1»-7.Сумма-нечетное число.

После выполнения данной операции на доске получается на одно число меньше.

---сумма оставшихся чисел все время число нечетное.

Значит, после 14 раз указанной операции на доске останется одно и нечетное число, а это-1!

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

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

Задача 4. Квадрат 5х5 заполнен числами так, что произведение чисел в каждой строке отрицательно. Доказать, что найдется

столбец, в котором произведение чисел также отрицательно.

Найдем произведение всех чисел. Оно отрицательно.

Произведение всех чисел равно произведению чисел в столбцах.

А так как произведение всех чисел отрицательно, то оно должно быть отрицательно в пяти, трех или хотя бы в одном столбце.

Что и требовалось доказать!

Задача 5. 16 корзин расположили по кругу. Можно ли в них разложить 55 арбузов так, чтобы количество арбузов в любых двух соседних корзинах отличалось на 1?

Т.к количество арбузов в любых двух соседних корзинах отличается на 1, то рассмотрим сумму: ч + н + ч +…+ н =55

Или н + ч + н +…+ ч = 55.

И т.к. это будет сумма 16 слагаемых и нечетных слагаемых в ней - 8(четное),то сумма должна быть четным числом!

Значит, разложить 55 арбузов нельзя!

Задачи для самостоятельного решения(6-7 классы):

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

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

2. Разменный автомат меняет одну монету на пять других. Можно ли с его помощью разменять металлический рубль на 26 монет?

Решение: Нельзя. Проследите за остатками по модулю 4.

3. На столе 6 стаканов, Из них 5 стоят правильно, а один перевернут вверх дном. Разрешается переворачивать одновременно 4 любых стакана. Можно ли все стаканы поставить правильно?

Решение. Нет, так как в любом случае перевернутых вверх дном стаканов будет числом нечетным.

4. В марсианском алфавите есть две буквы - У и Ы, причем если из любого слова выкинуть стоящие рядом буквы УЫ, то смысл слова не изменится. Точно также смысл не изменится при добавлении в любое место слова буквосочетания ЫУ или УУЫЫ. Верно ли, что слова ЫУЫУЫ и УЫУЫУ имеют одинаковый смысл?

Решение: Обратите внимание, что при любой разрешенной нам операции добавления или выкидывания куска слова количества букв У и Ы в этом куске равны. Это означает, что разность между числом букв У и букв Ы в слове не изменяется. Проследите это на примере

Ы -> ЫЫУ -> ЫУУЫЫЫУ -> ЫУЫЫУ

Во всех этих словах букв Ы на одну больше, чем букв У. Вернемся к решению. В слове ЫУЫУЫ разность равна (-1), а в слове УЫУЫУ равна 1. Значит, из слова ЫУЫУЫ нельзя разрешенными операциями получить слово УЫУЫУ, и следовательно, нельзя утверждать, что эти слова обязательно имеют одинаковый смысл.

5. 100 фишек выставлены в ряд. Разрешено менять местами две фишки, стоящие через одну фишку. Можно ли с помощью таких операций переставить все фишки в обратном порядке?

Решение: нельзя.

Решение. Пронумеруем места, на которых стоят фишки.

В итоге же картинка должна стать такой:

Итак, если изначально фишка стояла на четном месте, то должна оказаться на нечетном месте, но это невозможно, так как разрешено менять местами две фишки, стоящие через одну фишку (если фишка лежала на четном месте, то ее можно переложить только на четное место). То есть четность места фишки является инвариантом.

6. Круг разделен на 6 секторов, в каждом из которых стоит фишка-рыбка. Разрешается за один ход сдвинуть любые две фишки в соседние с ними сектора. Можно ли с помощью 20 таких операций собрать все фишки в одном секторе?

Решение:

Ответ: нельзя.

Решение. Занумеруем сектора по часовой стрелке числами от 1 до 6. Для любого расположения фишек рассмотрим величину S - сумму номеров секторов, в которых лежат данные нам 6 фишек (при этом если в каком-то секторе лежит две фишки, то его номер учитывается дважды, если три фишки - трижды и т.д. Например, для ситуации, приведенной на рис. эта величина равна 1+2+3+3+5+6=20). Тогда, если мы перекладываем фишку на соседний сектор, S меняется или на 1 или на 5 (если мы перекладываем с 1 на 6 или наоборот). В любом случае четность S меняется. Следовательно, после 20 ходов четность S будет такая же, как в начале. В начале S=1+2+3+4+5+6=21. А если бы все фишки лежали в одном секторе с номером n, то S равнялось бы 6n - четное число. Значит, собрать все фишки в одном секторе за 20 ходов не получится.

7. На доске написаны десять чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. За один ход разрешается к любым двум из них одновременно добавлять по единице. Можно ли за несколько ходов все числа сделать равными?

Решение: нельзя.

Проследим за суммой всех чисел. При операции из условия эта сумма увеличивается на 2. Значит, четность суммы всех чисел не меняется, она инвариант. В начале сумма всех чисел равна 1+2+…+9+10=45. То есть сумма была нечетной. А если все числа сделать равными какому-то числу n, то их сумма станет равно 10n - четное число. Следовательно, сделать все числа равными невозможно.

Замечание. Сумму чисел от 1 до 10 можно подсчитать аналогично Замечанию 1. А можно не считать, а заметить что она нечетная так как в ней участвует 5 нечетных слагаемых - 1,3,5,7,9.

8. На доске написаны шесть чисел: 1, 2, 3, 4, 5, 6. За один ход разрешается к любым двум из них одновременно добавлять по единице. Можно ли за несколько ходов все числа сделать равными? (задача, аналогичная предыдущей).

9. На квадратном поле 10*10 девять клеток 1*1 поросли бурьяном. После этого бурьян может распространиться на клетку, у которой не менее двух соседних клеток уже поросли бурьяном. Докажите, что тем не менее бурьян не сможет распространиться на все клетки.

Подсказка

Как изменяется периметр области, поросшей бурьяном?

Решение

Рассмотрим границу области, поросшей бурьяном (т.е. все отрезки длиной 1 между узлами, по одну сторону от которых бурьян, а по другую - нет). Вначале длина границы была не более 9*4=36, поскольку бурьян рос только в девяти клетках. Нетрудно заметить, что в процессе распространения бурьяна длина границы не может увеличиваться. Но если бы все поле 10*10 в некоторый момент оказалось поросшим бурьяном, то длина границы стала бы равной 10*4=40, что противоречит соображениям, приведенным выше.

Для построения инвариантов иногда бывают полезны вспомогательные раскраски, т.е. разбиения рассматриваемых объектов на несколько групп (каждая группа состоит из объектов одного цвета).

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

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

Задача 2. Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки какой-либо горизонтали или вертикали. Может ли при этом получиться доска, у которой ровно одна черная клетка?

Решение. При перекрашивании горизонтали или вертикали, содержащей k черных и 8k белых клеток, получится 8k черных клеток, и k белых клеток. Поэтому число черных клеток изменится на (8k)k=82k, т.е. на четное число. Т.к. четность числа черных клеток сохраняется, из исходных 32 черных клеток мы не можем получить одну черную клетку.

Задача 3. В каждой клетке доски 5х5 клеток сидит жук. В некоторый момент все жуки переползают на соседние по горизонтали или по вертикали клетки. Обязательно ли при этом останется пустая клетка?(есть в презентации)

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

Задача 4. На шести елках сидят шесть чижей, на каждой елке  по чижу. Елки растут в ряд с интервалами 10м. Если какой-то чиж перелетает с одной елки на другую, то какой-то другой чиж обязательно перелетает на столько же метров, но в обратном направлении. Могут ли все чижи собраться на одной елке? А если чижей и ёлок  семь?

Решение

а) Пронумеруем деревья с 1 по 6 и пусть первоначально на каждой елке сидит по чижу и каждый чиж имеет тот же номер, что и ель. Т. к. чижи перелетают на елки в разных направлениях, то сумма номеров чижей не меняется - инвариант.

Первоначально сумма была (1+6):2*6 = 21. Если предположить, что все чижи собрались на одной елке, то сумма номеров будет 6*n (т. к. все чижи получили номер елки, на которую прилетели), зн 6*n=21, n=3,5 - не натуральное. Значит предположение неверно и такого не может быть.

б) (1+7):2*7=28, 28=7n? N=4, значит все чижи могут собраться на ели № 4

Ответ: да

Задача 5 Дно прямоугольной коробки вымощено плитками 1х4 и 2х2. Плитки высыпали из коробки, и одна плитка 2х2 потерялась. Её заменили на плитку 1х4. Докажите, что теперь дно коробки вымостить не удастся.

Доказательство

Рассмотрим раскраску в четыре цвета, указанную на рисунке:

Тогда каждая плитка 2 х 2 содержит ровно одну клетку цвета1, а каждая плитка 1 х 4 - или ни одной или две клетки цвета 1. Следовательно, характер чётности числа плиток 2 х 2 должен совпадать с характером чётности числа клеток цвета 1. Но после замены плиток характер чётности числа плиток 2 х 2 изменится. Это и доказывает то, что замостить дно коробки не удастся.

Задача 6. В таблице 6х6 закрашена одна клетка. Можно ли, перекрашивая строки и столбцы (как в задаче 2), сделать всю таблицу одноцветной?

Решение: В процессе перекрашивания в какой-то момент выберем, н-р, строчку, пусть в ней к- закрашенных клеток, 6-к -чистых.

Перекрасим 6-к -закрашенных, к-чистых. Посмотрим на разность между окрашенными и неокрашенными клетками на 1 и на 2 этапах: к-(6-к)=2к-6 -четное;

6-к-к= 6-2к -четное, т.е. количество окрашенных клеток изменилось на четное число, тогда четность закрашенных клеток не меняется при этом процессе, а первоначально закрашена была одна клетка, зн сколько бы мы не перекрашивали закрашенных клеток будет нечетное число, а таблице 36 клеток -четное, зн все закрашенными оказаться не могут.

Ответ: нет

Задача 7. В таблице 3х3 закрашена одна клетка. Можно ли, перекрашивая строки и столбцы (как в задаче 2), сделать всю таблицу одноцветной?

Будем перекрашивать клетки и столбцы, обращая внимание на часть таблицы 2х2, где первоначально была закрашена одна клетка. В этой части таблицы: если первоначально было закрашено k клеток, то после перекрашивания стало 2- k окрашенных клеток, т.е. изменилось на число (2- k)- k=2-2k - четное, а значит если первоначально закрашена 1 клетка - нечетное, зн после перекрашивания будет нечетное число, а у нас их 4 клетки - четное, зн все эти 4 клетки мы не закрасим, след-но, не закрасим всю таблицу 3х3.

Ответ: нет

Задача 8. В угловой клетке таблицы 5 х 5 стоит плюс, а в остальных клетках стоят минусы. Разрешается в любой строке или любом столбце поменять все знаки на противоположные. Можно ли за несколько таких операций сделать все знаки плюсами?

Решение. Возьмём квадрат поменьше, 2 х 2 (один плюс и три минуса). Можно ли сделать все знаки плюсами? Нельзя.

Воспользуемся этим результатом: выделим в квадрате 5 х 5 квадратик 2 х 2, содержащий один плюс. Про него уже известно, что сделать все знаки плюсами нельзя. Значит, в квадрате 5 х 5 и подавно.

Задача 9. У марсиан бывает произвольное число рук. Однажды все марсиане взялись за руки так, что свободных рук не осталось. Докажите, что число марсиан, у которых нечётное число рук, чётно.

Решение. Назовём марсиан с чётным числом рук - чётными, а с нечётным - нечётными. Поскольку руки образуют пары, то общее число рук чётно. Общее число рук у чётных марсиан чётно, поэтому общее число рук у нечётных марсиан тоже чётно. Следовательно, число нечётных марсиан чётно.

Задача 10. Лист бумаги разрезали на 4 части. Некоторые из полученных частей режут еще на 4 части, любой из имеющихся кусков - еще на 4 и т.д. Можно ли таким образом получить 62 куска?

Решение: Если лист разорвать на 4 части, то кусков станет на 3 больше. Т.к. в начале был всего один лист, то после n разрывов будет 3n+1 кусков, а значит 3n+1=62, натур решения нет, значит нельзя.

Ответ: нет.

Работу подготовила - учитель высшей категории Старикова Ирина Николаевна