Домой

Лекция 11: Ин




Скачать 133.21 Kb.
НазваниеЛекция 11: Ин
Дата11.01.2013
Размер133.21 Kb.
ТипЛекция
Содержание
Инвариант как характеристика нечисловых объектов.
Выделение отмеченной части.
Инвариант и раскраски клетчатых досок.
Идея решения.
Подобные работы:

Лекция 11: Инвариант.

Эта лекция посвящена одному, но очень важному математическому понятию - инварианту. Бывает он в задачах, где мы имеем дело с какими-то операциями, с каким-то процессом, который изменяет данный в условии объект. Вот если у объекта есть какое-то свойство или характеристика, которая не меняется при этих операциях - она и называется инвариантом. Если у объекта есть два состояния, при которых инвариант принимает разные значения, то из одного из них нельзя перейти в другое (и из второго в первое тоже). Но одинаковое значение инварианта еще не значит, что так перейти можно.
(!) Четность, рассмотренная нами в одной из предыдущих лекций - типичный пример инварианта.

Задача 1. В файле хранятся 2003 единицы и 232 нуля. Программа читает из файла два произвольных числа, стирает, и записывает на их место 0, если они были равны, и 1, если нет. Программа запускается многократно. В конце в файле остается только одно число. Чему оно равно, 0 или 1?
Решение: Несмотря на то, что вариантов действия программы очень много, мы можем установить ответ однозначно. Что может прочитать программа за каждый отдельный запуск? Либо 0 и 0 (и записать 0), либо 0 и 1 (и записать 1), либо 1 и 1 (и записать 0). В первых двух случаях сумма всех чисел в файле не меняется, в последнем - уменьшается на 2. В любом случае, четность этой суммы остается прежней. Исходно сумма была 2003*1+232*0=2003 - нечетная, значит, и в конце будет нечетная. Но в конце остается только одно число - оно и равно сумме всех - поэтому оно нечетное. А так как в файле бывают только нули и единицы, то это 1.

Задача 2. А какое число останется в файле, если программа за один запуск стирает два числа и записывает вместо них их сумму?
Решение: Если в прошлой задаче инвариантом была четность суммы всех чисел в файле, то теперь это будет сама сумма. Ясно, что при замене двух любых чисел на их сумму сумма всех не меняется. Поэтому последнее число - оно же сумма чисел в конце - равно сумме чисел в начале, т.е. 2003 (см. задачу 1).

Задача 3. Имеются три числа, которые можно заменять по следующим правилам: числа a, b и c стираются и вместо них записываются (a+b)/2, (b+c)/2 и (a+c)/2.Можно ли из чисел 101, 73, 125 получить 77, 79 и 83?
Решение: А давайте так, "на всякий случай", посмотрим, как меняется сумма чисел. Было a+b+c, а стало... вместо них записываются (a+b)/2+(b+c)/2+(a+c)/2 = (2a+2b+2c)/2 = a+b+c - не изменилась. То есть, как ни крути, а сумма трех чисел не меняется. Но 101+73+125=299, а 77+79+83=239 - суммы исходной и конечной тройки разные. Поэтому из одной нельзя получить другую.
(!) А те, кто захочет взять в качестве инварианта четность суммы или ее остаток по какому-то модулю, скорее всего, ошибутся, так как начальная и конечная суммы различаются на 60, а делителей у 60 ох как много ;-)

Задача 4. Опять имеются три числа, которые можно заменять уже по другим правилам: a, b и c - на ab/c, ac/b и bc/a. Можно ли из 5, 17/6 и 3/5 получить 16/5, 9/4 и 7/6?
Решение: Ну, о том, куда тут переходит сумма чисел, даже думать не хочется. Что еще бывает, кроме суммы? Произведение, например. Перед операцией произведение чисел - abc, а после: (ab/c)*(ac/b)*(bc/a) = a2b2c2/abc = abc - не изменилось! Значит, произведение трех чисел остается постоянным при всех операцих. Но в начале оно было равно 5*(17/6)*(3/5)=8,5, а в конце (16/5)*(9/4)*(7/6)=8,4 - не равны. Поэтому ответ "нельзя".

(!) Если у нас есть какой-то набор чисел, над которым совершаются операции, то всегда стоит проверить, как изменяются при этих операциях сумма и произведение всех чисел. Очень часто они сами или их остатки по какому-то модулю являются инвариантом, с помощью которого решается задача.

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

^ Инвариант как характеристика нечисловых объектов. Во всех предыдущих примерах в задаче фигурировали числа, от которых мы в качестве инварианта брали какую-то функцию. Но, конечно, в исходной формулировке может ни быть никаких чисел! Что тогда делать? Конечно, эти числа придумать.

Задача 5. В стране серобуромалинии 27 серых, 32 бурых и 45 малиновых хамелеонов. Когда встречаются два хамелеона разных цветов, они оба перекрашиваются в третий цвет. Могут ли когда-нибудь все хамелеоны стать одного и того же цвета?
Решение: Ну где же тут у нас числа? Наверное, количества хамелеонов серого, бурого и малинового цвета. Как же они изменяются? Либо (A, B, C) переходит в (A-1, B-1, C+2) - встречаются серый и бурый хамелеоны и перекрашиваются в малиновый цвет, либо в (A-1, B+2, C-1) - серый и малиновый в бурый, либо, наконец, в (A+2, B-1, C-1) - бурый и малиновый в серый. Сумма всех трех, конечно, сохраняется, но это нам не поможет. А что поможет установить, могут ли два количества из трех стать нулями? Скорее, разности - кстати, еще один из базовых видов инвариантов. Между теми двумя числами, которые уменьшились на 1, разность не поменяется, зато разность между ними и третьим изменится ровно на 3. То есть по модулю 3, все попарные разности неизменны (сравните, как в задаче 1, из того, что сумма может уменьшаться на 2, мы находили, что ее четность неизменна). Значит, инвариант - значения попарных разностей по mod 3. Если какая-то разность в конце стала нулем (а так будет, если два количества станут нулями!), то исходно она делилась на 3. Но разности между исходными количествами на 3 не делится! Значит, не могут...

Задача 6. В языке программирования MustDie всего две команды, для краткости называемых M и D. Из-за глюка в компиляторе, действие программы не изменится, если из нее выкинуть кусок кода MDDM, а также если в любое ее место вставить кусок кода DMMDMD или MDMD. Могут ли программы MMDMD и DMMDD выполняться одинаково?
Решение: Иначе говоря: существует ли такое равнозначное преобразование кода, которое переводит одну программу в другую? Нет, конечно, и вы уже догадались...инвариант только надо придумать. В одном куске 2 команды M 2 команды D, во втором тех и других по 3, в третьем - опять по 2. Кажется, ясно: в любом вставляемом или убираемом куске команд M и D поровну. Значит не меняется... правильно, разность между числом тех и других команд. Она будет нашим инвариантом - и очень хорошо, так как в одной программе на одну больше команд M, а в другой на одну больше команд D (значение разности поменялось в 1 на -1).

Задача 7. По кругу стоят 232 елки, на каждой из которых сидит по белке. Если какая-то белка перепрыгивает с одной елки на соседнюю, то какая-то другая перепрыгивает на соседнюю елку в обратом направлении. Докажите, что все белки не могут собраться на одной елке.
Решение: Обратите внимание на прием, который мы здесь применим! (Начинающим такое обычно в голову не приходит ;-) Давайте занумеруем елки по кругу от 1 до 232. Тогда каждой белке можно сопоставить число: номер елки, на которой она сидит. И все эти прыжки представятся, как преобразования набора чисел. Обычно одна белка, перепрыгивая в одну сторону, уменьшает свой номер на 1, а другая, прыгая в другую сторону, увеличивает на 1. Конечно сумма номеров не меняется. А как еще бывает? Либо одна белка прыгает с 1-й елки на 232-ю, а другая, наоборот, с 232-й на 1-ю (сумма опять не меняется). Либо одна белка прыгает с 1-й елки на 232-ю, а другая - где-то еще, увеличивая свой номер на 1 - сумма растет на 232. Последний слуяай: одна белка прыгает с 232-й елки на 1-ю, а другая - в другом месте, уменьшая номер на 1. Тогда сумма номеров уменьшается на 232. В любом случае значение суммы номеров по модулю 232 - неизменно (то есть инвариант). Если бы все белки собрались на одной елке, то их номера были бы 232-мя одинаковыми числами, и их сумма на 232 делилась бы. Но тогда и исходная сумма номеров делилась бы на 232, а этого не наблюдается (эта сумма - см. лекцию "Индукция" о сложении чисел от 1 до N - равна 232*233/2), ч.т.д.
Упражнение. Докажите, что все белки могут собраться на одной елки тогда и только тогда, когда их нечетное число. (То есть, для четных чисел обобщить данное выше решение, для нечетных - придумать пример.)

(!) Разность каких-то количеств и набор попарных разностей - тоже типичные инварианты. После суммы и произведения следующим делом надо проверять именно разности.

Задача 8. Есть три программы. Одна по файлу с числами X и Y создает файл с числами X+1 и Y+1, вторая по файлу с четными числами X и Y создает файл с числами X/2 и Y/2, третья по двум файлам с числами X, Y и Y, Z создает файл с числами X, Z. Все старые файлы сохраняются. Исходно есть 1 файл с числами (5, 19). Можно ли с помощью этих программ получить файл с числами (1, 2004)?
Решение: Где же искать инвариант? С суммой чисел в файле как-то сложно, потому что третья программа изменяет ее черт знает как. С том смысле, что зная суммы чисел в двух входных файлах мы не можем определить сумму чисел в выходном файле. С разностью чисел в файле все лучше: первая программа не меняет разность ((X+1)-(Y+1)=X-Y), вторая - делит ее на 2 (X/2-Y/2=(X-Y)/2), а третья - складывает разности (X-Z=(X-Y)+(Y-Z)). Что же не меняется при всех этих преобразованиях - так сразу и не сообразишь...
Поставим эскперимент (да, математика - наука экспериментальная!).
Исходный файл (5, 19) можно пропустить только через первую программу и получить файл (6, 20). Из него можно дальше делать последовательность (7, 21), (8, 22) и т.д., а можно запустить вторую программу и получить файл (3, 10). Из него можно сделать последовательность (4, 11), (5, 12)... (19, 26). Потом можно запустить третью программу на (5, 19) и (19, 26) и получить файл (5, 26)...
Посчитаем разности: 5-19 = -14 = 6-20 = 7-21 = 8-22 = ...; 3-10 = -7 = 4-11 = 5-12 = ... = 19-26; 5-26 = -21. Что же общего у чисел -14, -7, -21? Конечно, они все на 7 делятся. Вот пусть эта делимость и будет инвариантом.
Действительно, когда разность не меняется, то и делимость сохранится; когда разность делится на 2, то делимость на 7 не исчезнет (2 и 7 взаимно просты); а когда разности, делящиеся на 7, складываются, то сумма тоже делится на 7. Понятно, что, имея в начале файл с разность чисел, делящейся на 7, мы только такие разности и будем получать. Но разность 1-2004 = -2003 на 7 не делится, и такой файл мы получить не сможем.
Упражнение. Докажите, что здесь можно получить все те и только те файлы, где первое число меньше второго, а их разность делится на 7.

Глубокий смысл тут в чем: инвариант может зависеть не только от правил, по которым производятся преобразования, но и от начальных данных. Как здесь: значение разности по модулю 7, вообще говоря - не инвариант при производимых преобразованиях. Но при конкретных начальных условиях, когда это значение с самого начала равно 0 - тогда оно становится инвариантом.
Безусловно, если типичные инварианты (сумма, произведение, разности и их значения по какому-то сразу заметному модулю) не подходят, то полезно поставить эксперимент: проделать несколько преобразований и поискать некоторые закономерности в том, что при этом будет получаться.

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

Задача 9. На доске 3x5 все клетки белые, а один угол черный. За ход можно поменять цвет всех клеток в одной строке или столбце. Можно ли все клетки сделать белыми?
Решение: Четность числа черных клеток на всей доске, увы, меняется очень часто, а потому нам не поможет. Где бы найти такую часть доски, на которой эта четность неизменна? У нас тут в условии нерегулярность в углу - так возьмем 4 угла. При операции перекрашивания меняет цвет ровно два угла, либо ни один - т.е. четность числа черных углов - инвариант. Но в начале такой угол один, а в конце хочется ноль - нельзя.

Задача 10. На окружности стоит 12 точек, в одной написано -1, в остальных +1. Можно изменить знак у трех единиц подряд. Можно ли сдвинуть единственную -1 в соседнюю вершину?
Решение: Пусть, для определенности, мы сдвинули -1 в соседнюю против часовой стрелки вершину (иначе можно всю картинку зеркально отразить и получить именно такую). Давайте занумеруем вершины, начиная с исходной -1, уже по часовой стрелке (тогда то, куда сдвинулось -1 - это вершина 12). Давайте выделим такую часть (множество вершин), где есть первая вершина, нет 12-й, а четность кол-ва -1 - инвариант (тогда это кол-во в данной части надо будет изменить с 1 до 0, а это невозможно из-за четности).
Правильное такое множество - вершины с номерами 1, 2, 4, 5, 7, 8, 10 и 11 (проверьте самостоятельно!).
Упражнение. Придумать такие множества, если мы меняем знак не у трех, а у 4 или 6 единиц подряд.

^ Инвариант и раскраски клетчатых досок. Очень важный и стоящий несколько особняком класс задач на инвариант - какие-то преобразования на клетчатых досках. Либо мы ходит чем-нибудь по доске, либо замощаем доску фигурами. В любом случае, очень полезной может быть раскраска доски в два или более цветов, обладающая какими-то особыми свойствами. Наиболее распространенные раскраски:
- шахматная (два цвета чередуются так, что любые две соседние по стороне клетки - разных цветов);
- "матрас" (чередование строк, выкрашенных в два цвета - или столбцов);
- укрупненная шахматная (в шахматном порядке красятся не отдельные клетки, а целые блоки 2x2, 3x3 и т.д.);
- укрупненный "матрас" (чередуются не строки, а одинаковые по толщине блоки из строк);
- "матрас" в N цветов: чередуются строки, выкрашенные в цвета, 1-й, 2-й, ... N-й, 1-й, 2-й и т.д.
- шахматная в N цветов - легче показать, чем написать; см. на рис. пример для 3-х цветов; можно и по-другому, чтобы одноцветные диагонали были наклонены в другую сторону.



Обычный инвариант - цвет клеток, по которым мы ходим (или какое-то чередование цветов, или какие-то цвета, на которые мы никогда не попадаем...), либо количества клеток тех и других цветов на всей доске и в фигурах замощения (если не совпадают, то замостить нельзя). Смотрите приведенные ниже примеры.

Задача 11. Фигура "крокодил" ходит по клетчатой доске на 3 клетки в одном направлении и одну в перпендикулярном (почти как шахматный конь, только конь ходит не на 3, а на 2 клетки). Докажите, что нельзя пройти крокодилом с какого-то поля на соседнее (по стороне) с данным.
Решение: Раскрасим доску в шахматном порядке. Тогда (нетрудно убедиться) крокодил при своем ходе не меняет цвет клетки, на которой стоит. А соседняя клетка, увы, другого цвета, ч.т.д.

Задача 12. Докажите, что шахматную доску нельзя замостить 15-ю прямоугольничками 1x4 и одной фигуркой вида .
Решение: Шахматная раскраска тут не поможет. Она, так скажем, не отличает особую фигурку от прямоугольничка: и в ней и в них ровно 2 белых и 2 черных клетки. И ничто не противоречит тому, что доску можно замостить 16-ю фигурами с таким свойством. Попробуем другую раскраску, скажем, "матрас". Тогда в прямоугольничке 1x4 то ли 0, то ли 2, то ли 4 черные клетки (смотря как он лежит). А в особой фигурке - то ли 1, то ли 3. Короче, там - четное, здесь - нечетное. А сумма 15 четных чисел и одного нечетного нечетна и не может поэтому быть равна 32 (числу черных клеток на шахматной доске), ч.т.д.
Собственно, инвариантом тут можно назвать четность количества черных клеток. Только мы тут не преобразуем объект или набор объектов, а составляем один объект (доску) из других.

Задача 13. Фишка ходит по доске NxN, сдвигаясь на 1 клетку вверх, вправо или вниз-влево по диагонали. Может ли фишка обойти все клетки доски по разу и закончить путь сверху от начальной клетки.
Решение: Подберем раскраску, при которой фишка будет одинаково менять цвет при любом ходе. Просто шахматная и "матрас" не подойдут. А зато шахматная раскраска в 3 цвета - просто замечательно (см. рис. выше). Наша фишка будет ходить с красного на желтый, с желтого на зеленый, с зеленого на красный и т.д. Пусть, скажем, начальная клетка красная - тогда конечная будет желтая. Цвета чередуются по циклу длины 3, поэтому число ходов: 3k+1 (т.е. =1 по mod 3). Но то же число ходов на доске NxN равно N2-1. Отсюда N2=2 (mod 3), чего, по соображениям теории чисел (см. лекцию "Теория чисел-2") не бывает. Ответ "нельзя".

(!) Инвариант инвариантом, но и про другие области математики по ходу дела не надо забывать. Часто решение может придти именно оттуда.

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

Инварианты


 

Инвариант – величина, которая не изменяется в результате некоторых операций (например, разрезание и перестановка частей фигур не меняет суммарной площади). Если инвариант различает два положения, то от одного нельзя перейти к другому. В качестве инварианта может использоваться чётность или раскраска. В задачах про сумму цифр используют остатки от деления на 3 или 9. Полуинвариант – величина, изменяющаяся только в одну сторону (т.е. которая может только увеличиваться или только уменьшаться). Понятие полуинварианта часто используется при доказательствах остановки процессов.

 

Пример 1. На чудо-яблоне растут бананы и ананасы. За один раз разрешается сорвать с неё два плода. Если сорвать два банана или два ананаса, то вырастет ещё один ананас, а если сорвать один банан и один ананас, то вырастет один банан. В итоге остался один плод. Какой это плод, если известно, сколько бананов и ананасов росло вначале.

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

 

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

Решение. Заменим знак плюс на число 1 и знак минус на число –1. Заметим, что произведение всех чисел в таблице не меняется при смене знака у всех чисел столбца или строки, так как одновременно меняется знак у четырёх чисел. В начальном положении это произведение равно –1, а в таблице из одних плюсов +1, чем и доказана невозможность перехода.

 

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

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

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

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

 

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

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

 

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

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

 

Задачи

 

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

        2. 2.     Можно ли круг разрезать на несколько частей и сложить квадрат? (Разрезы – это прямые и дуги окружностей).

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

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

        5. 5.     (сизифов труд). На горе 1001 ступенька, на некоторых лежат камни, по одному на ступеньке. Сизиф берёт любой камень и переносит его вверх на ближайшую свободную ступеньку (т.е. если ближайшая ступенька свободна, то на неё, а если она занята, то на несколько ступенек вверх до первой свободной). После этого Аид скатывает на одну ступеньку вниз один из камней, у которых предыдущая ступенька свободна. Камней 500 и первоначально они лежали на нижних 500 ступеньках. Сизиф и Аид действуют по очереди, начинает Сизиф. Цель Сизифа положить камень на верхнюю ступеньку. Может ли Аид ему помешать?

        6. 6.     Столица страны соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединён авиалиниями ровно с 10 городами (если А соединён с В, то В соединён с А). Известно, что из любого города можно попасть в любой другой (может быть, с пересадками). Докажите, что можно закрыть половину авиалиний, идущих из столицы, так что возможность попасть из любого города в любой другой сохранится.

        7. 7.     Во время перемирия за круглым столом разместились рыцари из двух враждующих станов. Оказалось, что число рыцарей, справа от которых сидит враг, равно числу рыцарей, справа от которых сидит друг. Докажите, что число рыцарей делится на







Скачать 133.21 Kb.
Поиск по сайту:



База данных защищена авторским правом ©dogend.ru 2014
При копировании материала укажите ссылку
обратиться к администрации
Уроки, справочники, рефераты