Этюды об инварианте"

Х ШКОЛЬНЫЕ ХАРИТОНОВСКИЕ ЧТЕНИЯ

Тема: «Этюды об инварианте».

Секция: математика

Автор:  Медведева Мария Сергеевна,  

10б  класс, МОУ «СОШ  № 22

 с углубленным изучением отдельных предметов».

г. Электросталь, Московская область, Россия

  Руководитель: Бровкина Софья Эдуардовна,

учитель математики

МОУ «СОШ № 22 с УИОП»

ЭЛЕКТРОСТАЛЬ

2010 год

План.

       Введение.

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

Глава 2.   Поиск инварианта.

1. Пути нахождения инварианта в задачах.

Глава 3.   Классификация задач по виду инварианта.

  Этюд 1. Инвариант – четность.

  Этюд 2. Инвариант – остаток от деления

  Этюд 3. Инвариант – знак произведения.

Глава 4.    

               Этюд 4. «Свои» задачи.

                   Заключение.

                   Литература.

Введение.

Многие любят математику, и я вхожу в их число. Особенное удовольствие мне доставляет решение трудных и замысловатых головоломок. Наверное, по этой причине я увлекаюсь олимпиадными задачами. Пытаясь разобраться в секретах их решения, я натолкнулась на понятие «инвариант». Возникло множество вопросов. На чем основано решение задач с помощью инварианта? Каким образом можно его найти? Какие существуют виды инварианта? Одним словом, что же это такое – инвариант?

Для начала рассмотрим понятие инварианта.

Инвариант значит «неизменный".

Инвариантом некоторого преобразования называется величина или свойство, не изменяющееся при этом преобразовании.

Исследования литературы по данной теме, ее обобщение и систематизация, помогли мне прийти к следующим  выводам:

1. имеется целый класс задач, в которых спрашивается, можно ли в результате некоторых действий получить тот или иной результат;
2. Основным методом решения таких задач является нахождение свойства исходного объекта, которое не меняется после выполнения таких действий, - это и есть инвариант. Если конечный объект задачи не обладает найденным свойством, то он не может быть получен в результате этих действий из исходного объекта;
3. в качестве инварианта  чаще всего рассматриваются четность (нечетность), остаток от деления,  знак произведения (встречаются и другие инварианты, например, перестановки, раскраски). Причем применение четности – одна из наиболее часто встречающихся идей при решении олимпиадных задач, связанных с понятием инварианта.
4. главная трудность при решении задач на инварианты состоит в его поиске. Нахождение инварианта является самым важным шагом на пути к решению задачи.

Поэтому цель моей работы -  создание комплектов задач, классифицированных по виду инварианта: четность (нечетность), остаток от деления,  знак произведения.

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

На примере задач глава 2  показаны пути нахождения инварианта: рассмотрены различные подходы к нахождению инварианта.

 В главе 3 каждый из этюдов 1 – 3 посвящен одному из видов инварианта.

Этюд 1. «Инвариант – четность»  содержит наибольшее количество задач, так как применение четности – одна из наиболее часто встречающихся идей при решении задач, связанных с понятием инварианта. Причем эти задачи также разделены на группы, в каждой группе задачи объединены общим подходом к решению.

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

Задачи главы 4 составлены мною самостоятельно. Составление задач дает возможность глубже понять идею решения задачи, а значит, -  научиться решать  более сложные задачи.

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

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

При помощи инвариантов решаются задачи следующего типа:

даны множество М (элементы его мы будем называть «позициями») и правило, по которому разрешается переходить от одной позиции к другой.  Можно ли из данной позиции α перейти за несколько шагов в другую данную позицию β?

Очевидно, описанная ситуация обладает свойством транзитивности: если из позиции α можно перейти в позицию β и из позиции  β можно перейти в позицию γ, то из α можно перейти в γ.

В некоторых задачах, кроме свойства транзитивности, имеют место также следующие важные свойства:

1. симметричность: если из позиции α можно перейти в позицию β, то и из  позиции β можно перейти в позицию  α.
2. рефлексивность: из любой позиции α можно «перейти» в нее же. 

Будем называть  позиции α и β эквивалентными, если по заданным правилам из α можно перейти в β.

Поскольку эквивалентность позиций рефлексивна, симметрична и транзитивна, исходное множество М разбивается на непустые непересекающиеся подмножества (орбиты): М=М1UМ2UМ3… . В каждом из подмножеств Мi все позиции эквивалентны: если α Мi и   β Мi, то α  β.  Если же позиции α и β принадлежат разным подмножествам Мi и Мj (i≠j), то α и β не эквивалентны.  Таким образом, если мы находимся в позиции α, принадлежащей какой-то  орбите Мi, то мы можем, перемещаясь по этой орбите, перебраться из позиции α в любую другую позицию, принадлежащую той же орбите. Однако сойти с орбиты, то есть перебраться с позиции α в позицию β, принадлежащей любой другой орбите, мы не можем.

Назовем инвариант универсальным, если на неэквивалентных позициях он принимает различные значения. Из этого следует, что

1. универсальный инвариант на каждой орбите принимает свое значение. 
2. Универсальный инвариант для любой пары позиций позволяет установить, эквивалентны они или нет.

Чтобы проверить универсален инвариант или нет, можно воспользоваться следующей теоремой.

Теорема. Если а) существуют такие l  позиций δ1, δ 2, ..., δ t,, что каждая позиция α М эквивалентна одной из них  и

 b) инвариант f принимает, по крайней мере, l различных значений,

 то f  — универсальный инвариант и позиции δi и δj (i≠j) попарно не эквивалентны.

Рассмотрим задачу

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

Решение.

Количество секторов может быть как четным, так и нечетным. Рассмотрим два случая.

1) случай: n=2m.

Занумеруем секторы по часовой стрелке от 1 до n. Для произвольной расстановки α фишек по секторам обозначим через αk количество фишек в k-м секторе при расстановке α. Рассмотрим сумму q(α) такую, что  q(α) =1×а1+2×а2+3×а3+…+n×аn.

Проверим, будет ли эта зависимость являться инвариантом.

Произвольное допустимое перемещение затрагивает четыре слагаемых суммы:

…+i×аi+(i+1)×аi+1+…+(j-1)×аj-1+j×аj+…   (Рисунок 1)

При перемещении фишек, не переходящем через

границу между секторами 1 и n, эта сумма превратится в сумму:

…+i×(аi-1)+(i+1)×(аi+1+1)+…+(j-1)×(аj-1+1)+j×(аj-1)+…

Легко проверить, что обе суммы равны. Итак, q – инвариант.  

                                                                                                         Рисунок 1.

Но n-ый сектор граничит с первым. Значит,  есть еще три возможности. (Рисунок 2-4).

             Рисунок 2                                        Рисунок 3                                            Рисунок 4  

Путём аналогичных рассуждений можно установить, что при переходе через границу между секторами 1 и n – q  изменится на n или останется неизменным.

Итак, за одно перемещение значение числа q может измениться, но только на n. Следовательно, если позиции q(μ), когда в каждом секторе стоит по одной фишке,   и q(ν),  когда все фишки собраны в одном секторе, эквивалентны, то остаток от деления на n значения q(μ) будет совпадать с остатком от деления на n значения q(ν).                  

q(ν)=l×n, следовательно, q(ν)  делится на n без остатка.

q(μ) =1+2+3+...+n=  n•(n+1)/2.  Так как  n=2m, то q(μ) = n•m+m (m≠0, m≠n) значит остаток от деления q(μ)  на n равен m, причем m0

Получив разные остатки мы можем утверждать, что позиции q(μ) и q(ν) для четного n не эквивалентны.

2) случай: n=2m+1.

Если n=2m+1, то по доказанному в первом случае: q(μ)=n•(m+1), остаток от деления q(μ) на n равен нулю, соответственно остатки от деления q(μ) и q(ν) равны.

Докажем, что инвариант остатка от деления q на n универсален. Обозначим через δi такую расстановку фишек: одна фишка — в i-м секторе, все остальные — в п-м секторе. Под δn примем расстановку, при которой все n фишек — в n-м секторе.

Легко сообразить, что любая расстановка эквивалентна одной из позиций δ1, δ 2, ..., δn. В самом деле, пусть α — произвольная расстановка фишек. Попытаемся собрать все n фишек в n-м секторе. Для этого будем передвигать первую фишку, пока не загоним ее в  n-й сектор; одновременно, в соответствии с правилами, мы будем перемещать вторую фишку в противоположную сторону. Затем загоним в n-й сектор вторую фишку, двигая в противоположную сторону третью фишку, и так далее — вплоть до (n— 1)-й фишки. Когда мы загоним n— 1 фишек в n-й сектор, n-я фишка будет в каком-то i-м секторе (i=1, 2,…, n). Это и означает, что позиции α и δi эквивалентны.

При i≠n: q(δi)=i×1+n×(n-1), а, значит, остаток от деления на n равен i. Кроме того, q(δn)=n×n и остаток от деления на n равен 0.

По теореме инвариант остатка от деления q на n универсален, следовательно, позиции α и β эквивалентны тогда и только тогда, когда остатки от деления q(α) и q(β) на n равны.

По доказанному, при нечетном n остатки от деления q(μ) и q(ν) равны, следовательно, позиции μ и ν эквивалентны при любом нечетном n.

Глава 2. Поиск инварианта.

1. Пути нахождения инварианта в задачах.

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

На примерах конкретных задач рассмотрим различные подходы к нахождению инварианта.

Решим задачу, в которой требуется доказать, что указанная величина является инвариантом.

Задача1  Имеется квадратная таблица 10х10, в клетки которой в последовательном порядке вписаны натуральные числа от 1 до 100: в первую строку - числа от 1 до 10, во вторую - от 11 до 20 и т. д. Докажем, что сумма  любых 10 чисел таблицы, из которых никакие два не стоят в одной строке и никакие два не стоят в одном столбце, постоянна, то есть  является инвариантом.

Решение.

Обозначим сумму 10 таких чисел таблицы  S, а  слагаемые исходной суммы из первой строки через  , из второй - через 10 + , из третьей - через 20 + и т. д., наконец, из десятой - через 90 +.

Здесь каждое из натуральных чисел, ,  заключено в пределах от 1 до 10 , причем эти числа попарно различны, так как, если бы, например,  =  , то числа и 10 +  стояли бы в одном столбце таблицы. Получаем:

S =  + (10 + ) +( 20 +) + …+ ( 90 + ) == (10 + 20 +…+ 90) + (+ +) =

= 450 + (+ +)

Поскольку числа, , попарно различны и принимают все целые значения от 1 до 10 , то каждое из натуральных чисел от 1 до 10 входит в сумму+ + в качестве слагаемого ровно один раз. Следовательно,

+ += 1 + 2 +3 +… + 10 = 55, S = 450 + 55 = 505.

Если в сумме  S одни слагаемые заменить другими, но так, чтобы все слагаемые новой суммы стояли в таблице в разных строках и в разных столбцах, сумма примет, то же самое значение. Следовательно, сумма S  является инвариантом.

На примере задачи 2  рассмотрим различные подходы к нахождению инварианта.

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

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

Проведем рассуждения иначе, используя следующий прием:

Решение 2.  Заменим все плюсы нулями, а минусы – единицами, и заметим, что сумма двух стираемых чисел имеет ту же четность, что и число, записываемое вместо них. Так как сначала сумма всех чисел была нечетной (она равнялась 15), то и последнее,  оставшееся на доске число будет нечётным, то есть единицей, и, значит, на доске останется минус.

Используя идею замены, можно найти еще одно решение:

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

Проанализируем все три решения.

1. Первое решение основывалось на неизменяемости четности числа минусов.
2. Второе решение   - на неизменяемости четности их суммы.
3. Третье – на неизменности знака произведения написанных чисел;

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

Проанализируем решение еще одной задачи.

Задача 3. В таблице 4x4 знаки «+»  и «—» расставлены так, как показано на рисунке. Разрешается изменить знак на противоположный одновременно во всех клетках, расположенных в одной строке, в одном столбце или  вдоль прямой, параллельной какой-нибудь  из диагоналей,  |в частности, в любой угловой клетке. Можно ли с помощью этих преобразований получить таблицу, не содержащую ни одного  минуса?

Решение.  Заменим плюсы и минусы числами 1 и —1. Тогда произведение всех чисел таблицы в первоначальной позиции будет отрицательным.

                       Рисунок 1                                                           Рисунок 2                            

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

1. в каждом столбце;
2. в каждой строке;
3. в клетках, расположенных вдоль прямой,  параллельно любой диагонали квадрата.

Очевидно, что для  угловых клеток третье условие не выполняется. Поэтому в качестве инварианта можно взять произведение чисел, находящихся в закрашенных клетках на рисунке 2. Это произведение равно  -1.

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

Следующая задача интересна тем, что  для нахождения инварианта, в ней используется метод координат.

Задача 4. Три кузнечика играют в чехарду: если кузнечик из точки А прыгает через кузнечика, находящегося в точке В, то он окажется в точке С, симметричной точке А относительно точки В. В исходном положении кузнечики занимают три вершины квадрата. Могут ли они, играя в чехарду, попасть в четвертую его вершину?

Решение.   Введем на плоскости систему координат так, чтобы три вершины квадрата, в которых находятся кузнечики, имели координаты (0; 0), (0; 1) и (1; 0). Заметим, что абсциссы и ординаты у каждой пары кузнечиков отличаются на 0 или 1, значит, при переходе одного кузнечика в точку симметричную его положению относительно другого кузнечика абсциссы и ординаты соответственно изменятся на 0 или 2.  Следовательно, при указанных прыжках каждая из координат кузнечиков или остается неизменной, или изменяется в ту или иную сторону на четное число. Так как в начальном положении, по меньшей мере, одна из координат каждой из трех точек четна, то она при прыжках останется четной, поэтому попасть в М ни один из кузнечиков не может.

Инвариантом в этой задаче является сохранение четности или нечетности координат положения кузнечика.

Анализ решения следующей  задачи  поможет при решении подобных задач с конкретными данными.

Задача5.  Над строкой из n чисел проделаем следующую операцию: между каждыми двумя соседними числами впишем число, которое получится в результате вычитания левого числа из правого. Над новой строкой проделаем ту же операцию и т.д. Найдите сумму чисел строки, которая получится после р таких операций.

Решение.   Пусть, ,  — строка, к которой применяется преобразование. Обозначим за S сумму n исходных чисел. Посмотрим, как изменяется сумма чисел строки после одного преобразования.

Новая строка имеет вид, ,, .

Сумма чисел новой строки равна:

 ,+(+ =++ 

+ (-) =  S+(-).

Заметим теперь, что для любой строки, полученной из строки , ,  описанным в условии задачи преобразованием, первое и последнее числа не изменяются, следовательно, разность- – постоянна, то есть является инвариантом. Таким образом, после каждого преобразования сумма чисел изменяется на -. Следовательно, сумма чисел строки, которая получится после р таких преобразований, равна

 S + р(-).

Составим  подобную задачу и воспользуемся для ее решения выводами задачи 3.

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

Решение   Сумма чисел данной строки равна 17. За одну операцию сумма чисел изменяется на (3-1), то есть увеличивается на 2. Следовательно, сумма чисел строки, которая получится после ста таких операций, равна 17 + 2 · 100 = 217.

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

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

Решение   Сумма всех хамелеонов острова равна 13 + 15 + 17 = 45. Заметим, что для решения задачи необходимо определить, можно ли из позиции(13, 15, 17), выполняя данное преобразование, перейти к позиции: (45, 0, 0), (0, 45, 0) или (0, 0, 45).Обозначим буквами С, Б, М – количество серых, бурых и малиновых хамелеонов соответственно.  

Проанализируем, как при смене окраски хамелеонов могут измениться  числа С и Б. Могут замениться:

1) на  С – 1 и  Б – 1,

2) на  С + 2 и  Б – 1,

3)  на  С – 1 и Б + 2.

Заметим, что в первом случае разность Б – 1 – (С – 1) = Б – С, во втором разность  Б – 1 – ( С+ 2) = Б – С – 3, а в третьем -  Б + 2 – (С – 1) = Б – С + 3.  В первом случае  получаем Б – С,  в двух других эта разность изменяется на 3, следовательно,  во всех трех случаях остаток  от деления на 3 не изменяется. Инвариантом здесь является остаток от деления на 3 разности Б - С.

 Остаётся заметить, что для исходной тройки (13, 15, 17) он равен 2, а для любой из троек (45, 0, 0), (0, 45, 0) , (0, 0, 45) остаток от деления на 3 равен 0. Следовательно, мы не сможем получить только серых или только бурых хамелеонов. Аналогично рассуждая, приходим к выводу, что нельзя получить только малиновых хамелеонов. При делении на 3 числа М – Б всегда будем получать остаток 1, а для любой из последних трех позиций остаток от деления на 3 равен 0.

Глава 3. Классификация задач по виду инварианта.

Этюд 1. Инвариант - четность.

Сформулируем наиболее важное утверждение, на котором основано применение идеи четности и нечетности.

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

 Это утверждение используется при решении задач, где инвариантом является четность суммы.

1. Важно понимать, число х+2 имеет ту  же четность, что и число х (эти числа или оба четные, или оба нечетные), а числа а и а+1 имеют разную четность (если а – четное число, то  а + 1 – нечетное, а если а – нечетно, то а + 1 – четно).

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

Задача 1. На столе стоят 7 стаканов - все вверх дном. Разрешается за один раз перевернуть любые 4 стакана. Можно ли за несколько раз добиться того, чтобы все стаканы стояли правильно, то есть вниз дном?

Решение.

На столе вверх дном стоит нечетное число стаканов. Для того чтобы все стаканы стояли правильно нужно, чтобы число, стоящих вверх дном стаканов, равнялось нулю,

т. е. четному числу. Перевернуть 4 стакана можно несколькими способами. Рассмотрим их.

1. Если перевернуть 4 стакана, то на столе останется нечетное число стаканов, стоящих вверх дном.

2. Перевернув 3 стакана, а затем 1 разными способами, мы, по сути, перевернем 2 стакана. 2 – четное число, значит, на столе стоящих вверх дном стаканов останется нечетное количество.

3. И, наконец, перевернув 2 и 2 стакана разными способами, мы снова получим нечетное число, стоящих вверх дном стаканов, так как, по сути, мы не изменили ситуацию. Следовательно, невозможно добиться того, чтобы все стаканы стояли правильно, то есть вниз дном.

Таким образом, в задаче остается неизменным то, что количество перевернутых вверх дном стаканов – нечетное число. Значит, инвариантом является нечетность количества неправильно стоящих стаканов.

 Задача 2. 101 лошадь разместили в 15 конюшнях. Почему хотя бы в одной конюшне будет обязательно нечетное число лошадей?

Решение:

        Докажем задачу методом от противного. Пусть в каждой конюшне находится четное число лошадей, тогда сумма четных чисел – число четное. А по условию всего лошадей 101 – число нечетное. Таким образом, получили противоречие. Значит, хотя бы в одной конюшне будет нечетное число лошадей.

        Инвариантом в данной задаче будет четность суммы нескольких четных чисел.

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

Решение:

        Если число арбузов в соседних корзинах отличается на 1, то характер четности числа арбузов в этих корзинах будет разным. Тогда четность числа арбузов в корзинах будет чередоваться, поэтому в половине корзин будет четное число арбузов, а  в половине нечетное. Тогда общее число арбузов в 8 корзинах с четным числом арбузов и в 8 корзинах с нечетным числом арбузов будет четным. По условию же всего арбузов – 55, а это нечетное число. Значит, разложить нельзя.

        Инвариантом в данной задаче будет то, что сумма четного количества чисел – четное число.

Задача 4. Три кузнечика играют в чехарду: если кузнечик из точки А прыгает через кузнечика, находящегося в точке В, то он окажется в точке С, симметричной точке А относительно точки В. В исходном положении кузнечики занимают три вершины квадрата. Могут ли они, играя в чехарду, попасть в четвертую его вершину?

Решение:

Введем на плоскости систему координат так, чтобы три вершины квадрата, в которых находятся кузнечики, имели координаты (0; 0), (0; 1) и (1; 0). При указанных прыжках каждая из координат кузнечиков или остается неизменной, или изменяется в ту или иную сторону на четное число. Так как в начальном положении, по меньшей мере, одна из координат каждой из трех точек четна, то она при прыжках останется четной, поэтому попасть в М ни один из кузнечиков не может.

Инвариантом в этой задаче является сохранение четности или нечетности координат положения кузнечика.

Задача 5. На чудо - дереве садовник вырастил 45 груш и 50 яблок. Каждый день он срывает 2 плода и тут же на дереве вырастает новый. Причем, если он срывает 2 одинаковых плода, то вырастает яблоко, а если – 2 разных, то вырастает груша. Каким окажется последний плод на дереве?

Решение:

Рассмотрим возможные случаи:

1) Садовник сорвал 2 яблока, тогда вырастает 1 яблоко и на дереве будет 45 груш и 49 яблок.

2) Садовник сорвал 2 груши, в этом случае вырастает 1 яблоко и на дереве будет 43 груши и 51 яблоко.

3) Если же садовник срывает 2 разных плода: яблоко и грушу, то на дереве вырастает груша и всего плодов будет: 45 груш и 49 яблок.

Итак, можно заметить, что в каждом из трех случаев неизменным остается одно, а именно: количество груш – нечетное число. Значит, инвариантом будет нечетность числа груш на дереве, а поэтому последним плодом окажется груша.

Задача 6. Можно ли разменять купюру достоинством 50 рублей с помощью 15 монет достоинством 1 и 5 рублей?

Решение:

        Числа 1 и 5 – нечетные. Так как сумма 15 нечетных чисел является числом нечетным, а 50 – число четное, то разменять 50 рублей на 15 монет по 1 и 5 рублей нельзя.

        Инвариантом в данной задаче будет нечетность суммы 15 (нечетного количества)  нечетных чисел.

Задача 7. На доске написаны в строку 2009 целых чисел. Докажите, что из них можно стереть одно число так, что сумма оставшихся чисел будет четной. Верно ли это для  2010 чисел?

Решение:

        Рассмотрим 3 случая.

а) Среди 2009 целых чисел есть четные и нечетные числа. Если количество нечетных чисел нечетно, то стираем любое из них. Если количество нечетных чисел четно, то из 2009 целых чисел хотя бы одно четное. Его и стираем.

б) Пусть все 2009 чисел – нечетные. Тогда стираем любое из них.

в) Пусть все 2009 чисел – четные. В этом случае стираем любое из них.

        В случае, когда чисел 2010 и все они нечетные, оставшаяся сумма не может быть четной. Поэтому для 2010 целых чисел это неверно.

     Инвариантом в этой задаче является нечетность суммы нечетного количества нечетных чисел.

Задача 8. Страницы книги пронумерованы подряд с первой до последней страницы. Хулиган Вася вырвал из разных мест книги 17 листов и сложил номера всех 34 вырванных страниц. У него получилось число 2010. Правильно ли Вася сосчитал?

Решение:

        На каждом из 17 листов сумма номеров двух страниц число нечетное, так как на одной странице номер четный, а на другой – нечетный. Тогда сумма 17 нечетных чисел будет нечетной. Так как 2010 – число четное, то Вася ошибся при подсчете.

        Инвариант – сумма 17 нечетных чисел – нечетное число.

Задача 9. В древней рукописи приведено описание города, расположенного на 8 островах. Острова соединены между собой и с материком мостами. На материк выходят 5 мостов; на 4 островах берут начало 4 моста, на 3 островах берут начало 3 моста и на один остров можно пройти только по одному мосту. Может ли быть такое расположение мостов?

Решение:

        Найдем число концов у всех мостов: 5+4×4+3×3+1=31.

Число 31 является нечетным. Так как число концов у всех мостов должно быть четным, то такого расположения мостов быть не может.

        Инвариант – четность числа концов моста.

Рассмотрим задачи, в которых полезно определять четность  суммы всех данных чисел.

 Задача10.  На доске написаны числа 1, 2, 3, ..., 2008, 2009. Разрешается стереть с доски любые два числа и вместо них записать модуль их разности. В конце концов, на доске останется одно число. Может ли оно равняться нулю?

Решение:

Сумма всех записанных на доске чисел будет нечетной, так как количество нечетных чисел – нечетно. При стирании двух чисел возможны 3 варианта:

а) стираются 2 четные числа, тогда модуль разности будет четным числом, а новая сумма будет числом нечетным;

б) стираются 2 нечетные числа, тогда модуль разности будет четным числом, а новая сумма будет числом нечетным;

в) стираются 1 четное и 1 нечетное число, тогда модуль разности будет нечетным числом, а новая сумма будет снова числом нечетным;

Таким образом, в любом случае, на доске останется нечетное число. Так как нуль  – число четное, то оставшееся число нулем быть не может.

В этой задаче инвариант – это нечетность суммы всех чисел, записанных на доске.

Задача 11. Круг разбит на 10 секторов, в каждом из которых стоит по одной фишке. Одним ходом разрешается любые 2 фишки передвинуть в соседние секторы. Удастся ли через несколько ходов все фишки собрать в одном секторе?

Решение:

Пронумеруем сектора последовательно числами 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 и присвоим каждой фишке номер сектора, в котором она находится. При передвижении какой-либо фишки в соседний сектор номер фишки меняется на нечетное число: на 9, если фишка переходит из десятого в первый сектор или наоборот и на 1 в других случаях. Сумма двух нечетных чисел – четная, поэтому четность суммы номеров всех фишек при любых передвижениях двух фишек не меняется. В первоначальном положении сумма всех номеров фишек была равна 1+2+…+10=55 (нечетное число). Если бы все фишки удалось собрать в одном секторе, то сумма номеров была бы четной, так как сумма десяти одинаковых чисел – четное число. Значит, собрать фишки в одном

секторе не удастся.

В этой задаче инвариантом будет нечетность суммы номеров секторов.

        Задача 12. Числа 0, 1, 2, … , 9 записаны по кругу. За один ход разрешается прибавить к двум соседним числам одно и то же целое число. Можно ли за несколько ходов получить десять нулей?

Решение:

Найдем сумму всех данных чисел. Найдем сумму чисел, записанных по кругу, она равна 45. Прибавляя 2 одинаковых целых числа к соседним числам, мы к нечетному числу прибавляем четное: сумму двух одинаковых целых чисел, следовательно, получим нечетное число. Таким образом, характер четности суммы не меняется: она по-прежнему остается нечетной. Так как сумма 10 нулей – нуль – число четное, то указанными преобразованиями получить 10 нулей нельзя.

Инвариантом в этой задаче является нечетность суммы чисел.

Решим подобную задачу.

Задача 13. В вершинах куба записаны числа 2, 0, 0, 3, 1, 9, 5, 7. За один ход разрешается прибавить к числам, стоящим на концах одного ребра, одно и то же целое число. Можно ли за несколько ходов получить нули во всех вершинах?

Решение:

Так как сумма данных чисел: число 27 – нечетное, а при прибавлении двух одинаковых целых чисел четность суммы не меняется, то получить все нули во всех вершинах невозможно, так как сумма восьми нулей – число четное.

В этой задаче инвариант – нечетность суммы чисел, записанных в вершинах куба.

Рассмотрим ряд задач, в которых важно найти чередующиеся объекты.

Задача 14. Учитель написал на листке бумаге число 10. 25 учеников передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу – как хочет. Можно ли в результате получить число 0?

Решение:

        От прибавления или вычитания единицы меняется характер четности числа: после первого ученика число становится нечетным; после второго четным; после третьего – нечетным. Следовательно, если 25 раз менять характер четности числа 10, в результате получится нечетное число. Значит, число 0 получиться не может.

        В этой задаче инвариантом будет чередование четности и нечетности числа после совершения над ним предложенной операции.

Задача 15. Конь вышел с поля а1 шахматной доски и через несколько ходов вернулся на него. Докажите, что он сделал четное число ходов.

Решение:

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

     Инвариантом в данной задаче будет чередование цвета клетки.

Задача 16. На плоскости расположено 13 шестеренок, соединенных по цепочке. Могут ли все шестеренки вращаться одновременно? А если шестеренок 14?

Решение:

        Пусть первая шестеренка вращается по часовой стрелке, тогда вторая – против часовой стрелки, третья – по часовой стрелке и т. д. Получим, что двенадцатая будет вращаться против часовой стрелки, а тринадцатая – по часовой стрелке. Значит, первая должна вращаться против часовой стрелки, что противоречит тому, что она вращается по часовой стрелке. Поэтому, все 13 шестеренок вращаться одновременно не могут. А вот 14 уже могут.

        В задаче неизменно то, что каждая четная шестеренка вращается против часовой стрелки, а каждая нечетная – по часовой стрелке, поэтому инвариантом в этой задаче является чередование четности и нечетности места шестеренки.

Задача 17. 2010 человек выстроились в шеренгу. Всегда ли можно их расставить по росту, если за один ход разрешается переставлять только двух человек, стоящих через одного?

Решение:

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

        Здесь число 2010 роли не играет.

        Инвариантом в этой задаче является сохранение четности места человека.

Задача 18. 100 фишек стоят в ряд. Любые две фишки, расположенные через одну, можно менять местами. Удастся ли расположить фишки в обратном порядке?

Решение:

        Так как при перестановке фишек четность места фишки сохраняется, то первую фишку никогда не сделать последней (1 – число нечетное, а 100 – число четное).

        В этой задаче не изменяется четность или нечетность места той или иной фишки, а значит, инвариантом будет чередование четных мест.

При решении задач 19, 20, 21 необходимо научиться объекты разбивать на пары.

Задача 19. Все костяшки домино выложены в цепь. На одном конце цепи оказалось 3 очка. Сколько очков на другом конце?

Решение:

        Всего костяшек с тройкой на конце 7: 0-3, 1-3, 2-3, 3-3, 4-3, 5-3, 6-3. Костяшка 3-3 имеет «тройку» на обоих концах. Без нее остается 6 костяшек. Так как при игре в домино в цепи они должны располагаться парами, то на другом конце цепи будет 3 очка.

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

Задача 20. При дворе короля Артура собрались 30 рыцарей, причем каждый из них имеет среди присутствующих не более 14 врагов. Докажите, что Мерлин, советник Артура, может так рассадить рыцарей за Круглым Столом, что ни один из них не будет сидеть рядом со своим врагом.

Решение:

        Рассадим рыцарей за Круглым Столом произвольным образом. Если при этом получится, что никакие два врага не сидят рядом, то требование задачи выполнено. В противном случае рассмотрим рыцаря А, сидящего слева от своего врага В. Среди друзей рыцаря А обязательно найдется такой рыцарь С, что его правый сосед D – друг рыцаря В (иначе у рыцаря В врагов более 14). Поменяем рыцарей В и С местами. При этом рыцарь В станет соседом рыцаря D, рыцарь С – соседом рыцаря А. Остальные пары соседей не изменятся. Поступая аналогично с рыцарями, сидящими со своими врагами, мы придем к  искомому расположению рыцарей за Круглым Столом.

                              В       А                                В    А                                     С     А

        D                                        D

                                                                C                                        В

Задача 21. Можно ли по правилам игры в домино выложить все 28 костяшек в одну цепочку так, чтобы сумма на ее концах была нечетной? (Дубли кладем вдоль цепи, конечной считаем вторую половину костяшки).

Решение:

        В наборе домино клеток-половинок кости с одинаковым количеством очков 8 штук, а в цепи они стоят подряд по 2 или 4. Значит, на концах может оказаться только разорванная пара. Поэтому сумма очков на концах будет четной. Значит, выложить цепь так, что сумма очков на концах была нечетной, нельзя.

        Здесь инвариантом является то, что каждая половинка костяшки имеет пару.

Этюд 2. Инвариант – остаток от деления.

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

Задача 22. Мише учитель математики поставил в дневник отметку «2». Миша, желая скрыть от мамы данный факт, порвал свой дневник на 4 части. Этого ему показалось мало, поэтому некоторые из этих частей (может быть и не все)  он порвал на 4 части и так далее. Мама нашла 20 «кусочков» дневника. Все ли куски нашла мама?

Решение:

Для того, чтобы решить задачу, необходимо ответить на вопрос: «Какое число обрывков могло получиться?» Сначала Миша порвал дневник на 4 части. Если он порвал на 4 части  один из четырех кусочков, то их станет 4+ 3 = 7. Если Миша и дальше будет рвать кусочки на 4 части, то их будет получаться 4 +6 = 10, 4 + 9 = 13, 4 + 12 = 16, 4 + 15 =19,     4 +18 =22 и так далее. Таким образом, кусочков может быть 4, 7, 10, 13, 16, 19, 22, …  Значит, мама нашла не все кусочки. Можно заметить, что при делении каждого из этих чисел  на 3 получается остаток 1.

 В данной задаче в качестве инварианта выступил остаток от деления на 3.

Решим еще несколько подобных задач.

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

Решение:

        Рассмотрим, какое количество обрывков могло получиться. За одно действие Васи, количество обрывков всегда будет увеличиваться на 4. За одно действие Пети, количество обрывков всегда будет увеличиваться на 8, то есть на 2×4. То есть, число кусков может равняться только 1, 5, 9, 13, 17, 21 и т. д. Можно заметить, что общее число кусков можно записать как 4n+1. Так как 1999=499×4+3, то ученики собрали не все обрывки стенгазеты.

В данной задаче в качестве инварианта выступил остаток от деления на 4.

Задача 24. В некотором государстве первоначально было 10 банков. С момента перестройки общества все захотели быть банкирами. Но, по закону, открыть банк можно только путем деления уже существующего банка на 4 новых банка. Через 2 года министр финансов сообщил президенту, что в стране действует уже 2010 банков, после чего был немедленно уволен за некомпетентность. Что не понравилось президенту?

Решение:

        В результате превращения одного старого банка в четыре новых общее число банков увеличивается на 3, тогда количество банков может быть равным 10 + 3 =13, 10 +6 = 16, 10 +9 = 19, и так далее. Таким образом, в любой момент времени число банков будет равно 10+3n. Остаток от деления 10 (первоначальное количество банков) на 3 равен 1, а 2010 делится на 3  без  остатка.  Значит, образоваться ровно 2010 банков в стране не могло.

        Здесь инвариантом является остаток от деления на 3.

Задача 25. Каждое натуральное число от 1 до 50000 записанных по порядку заменяют числом равным сумме его цифр. С получившимися цифрами проделывают ту же операцию, и так поступают до тех пор, пока все числа не станут однозначными. Затем, в строку выписывают по порядку остатки от деления на 9, каждого получившегося однозначного числа. Сколько раз среди этих однозначных чисел встретится каждое из целых чисел от 0 до 8?

Решение:

Заменив натуральные числа суммой его цифр – получим следующий ряд чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, ... . Остатки этих чисел при делении на 9 в последовательном порядке таковы: 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2,3, 4, 5, 6, 7, 8, 0,… . Эта закономерность сохраняется и дальше. В самом деле, при замене натурального числа суммой его цифр остаток от деления числа на 9 остается неизменным, поэтому при переходе от каждого натурального числа к следующему остаток от деления числа на 9 увеличивается на 1 или перескакивает от 8 к 0. Для того чтобы узнать, сколько таких групп цифр по 9 цифр в каждой, разделим 50000 на 9 с остатком : 50000 = 9 * 5555 + 5. Следовательно, таких групп 5555 . Еще одну, неполную группу образуют последние 5 цифр : 1, 2, 3, 4, 5. Получаем: 1, 2, 3, 4, 5 - по 5556 раз , 6, 7, 8, 0 - 5555 раз .

Этюд 3. Инвариант – знак произведения.

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

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

        Приведем примеры:

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

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

     Применяя это утверждение, решим следующие задачи.

    Вернемся к задаче1. Рассмотрим другой подход к ее решению.

 Задача 26. На столе стоят 7 стаканов - все вверх дном. Разрешается за один раз перевернуть любые 4 стакана. Можно ли за несколько раз добиться того, чтобы все стаканы стояли правильно, то есть вниз дном?

Решение:

Поставим в соответствии стакану, стоящему нормально, +1, а стоящему вверх дном, - 1. Инвариантом здесь будет знак  произведение чисел, соответствующих всем 7 стаканам, так как при изменении знака у 4 множителей произведение не меняется. Но в начальном положении это произведение равно -1, а значит, стать +1 оно никогда не сможет. Поэтому невозможно добиться того, чтобы все стаканы стояли правильно.

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

Решение:

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

        Инвариантом в этой задаче является знак произведения всех чисел в квадрате – оно отрицательное.

Задача 28. В каждую клетку квадратной таблицы размером 25×25 вписано произвольно одно из чисел: +1 или -1. Под каждым из столбцов записывается произведение всех чисел данного столбца, а справа от каждой строки – произведение всех чисел данной строки. Может ли сумма всех 50 произведений быть равной нулю?

Решение:

        Перемножая все 50 произведений, мы получим 1, так как в каждое произведение любое из чисел, вписанных в клетки таблицы, войдет 2 раза - один раз в произведение по строкам, один раз – по столбцам. Тогда в число пятидесяти  множителей будет входить четное число произведений, с «-1». Поэтому сумма четного числа произведений, с  «1»,  и четного числа произведений, с «-1», не может быть равна 0. (Одинакового числа слагаемых не будет, так как  50 : 2 = 25 – число нечетное.)  

        Инвариантом в этой задаче будет знак произведения 50 множителей.

.

Глава 3.

Этюд 5. «Свои» задачи.

Составление задач  - непростое, но увлекательное занятие, которое дает возможность глубже понять идею решения задачи, а значит, -  научиться решать  более сложные задачи.

Задача 1. В магазин привезли несколько коробок с конфетами. Продавец раскладывал конфеты из каждой маленькой коробки в 18 пакетов, а из каждой большой – в 27 пакетов. Разложив все конфеты, продавец насчитал 352 пакета с конфетами. Докажите, что он ошибся.

Решение:

        Числа 18 и 27 делятся на 3 без остатка, значит сумма нескольких таких чисел, тоже будет нацело делиться на 3. Но 352:3=117∙3+1, значит, продавец ошибся.

Задача 2. По кругу записаны числа 1, 2, 3, … , 99, 100. Разрешается прибавить или отнять от числа модуль разности соседних чисел и записать вместо него полученный результат. Можно ли после нескольких таких операций получить одинаковые числа?

Решение:

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

Задача 3.

        Сумма 507 чисел - четное число. Каким, четным или нечетным будет произведение этих чисел?

Решение:

        Сумма 507 нечетных чисел – нечетная, значит, среди них есть хотя бы одно четное число. А произведение четного и нечетных – четное число. Значит, произведение этих чисел четное.

Задача 4.

          В строку, в произвольном порядке, записаны 33 буквы русского алфавита. Разрешается переставлять две стоящие через одну буквы. Всегда ли их можно расставить по алфавиту?

Решение:

          Не всегда, так как при выполнении данной операции сохраняется четность места буквы. Поэтому, например, если буква «А» стоит на втором месте, то она никогда не станет первой.

Задача 5.

Новогодняя гирлянда состоит из 125 лампочек. При первом включении все лампочки гирлянды загораются. Через каждую секунду какие-нибудь 38 лампочек меняют своё состояние (из включенного в выключенное или из выключенного во включенное). Может ли оказаться, что через некоторый промежуток времени гирлянда полностью погаснет?

Решение:

Обозначим каждую включенную лампочку числом -1, а каждую выключенную числом 1. Знак произведения чисел, соответствующих 125 лампочкам не будет изменяться, так как при изменении знака у 38 чисел – произведение не меняется. При включении это произведение равно   -1, а значит, никогда не станет равным 1. Поэтому все лампочки гирлянды никогда не погаснут.

Заключение.

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

IV. Литература

1. Математические кружки в школе. 5-8 классы / А. В. Фарков. – 3-е изд. – М.: Айрис-пресс, 2007. – 144 с. – (Школьные олимпиады). 2005
2. Готовимся к олимпиадам по математике: учеб.-метод. пособие / А. В. Фарков – М.: Издательство «Экзамен», 2006.
3. Математика. Занятие школьного кружка. 5-6 кл. – М.: Изд-во НЦ ЭНАС, 2002. – 208 с. – (Портфель учителя).
4. Московские математические олимпиады: Кн. Для учащихся / Под ред. А. Н. Колмогорова. – М.: Просвещение, 1986. – 303 с., ил.
5. Математический винегрет: 2-е изд., испр. и доп. – М.: Мир, 2002. – 221 с., ил. – (Математическая мозаика).
6. Научно-популярный физико-математический журнал «Квант». 1989. Изд-во «Наука».
7. Агаханов Н. Х., Подлипский О. К. Математические олимпиады Московской области. – М.: Изд-во МФТИ, 2003. – 224 с.
8. Научно-популярный физико-математический журнал «Квант». 1976. Изд-во «Наука».

j-1

i+1 11=+=

i-1 11=+=

i+1 11=+=

j

i

i

i

1

n

1

n

n

1

М (1;1)

0

1

1

x

y

М (1;1)

0

1

1

x

y