Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/free-books/prasolov/planim/gl23.htm
Дата изменения: Wed Aug 4 15:18:54 2004
Дата индексирования: Sat Dec 22 17:15:23 2007
Кодировка: Windows-1251
Прасолов В. В. Задачи по планиметрии. (4-е изд. — Осторожно! В этом издании немало опечаток!)МЦНМО, 2002

Глава 22. Решения | Оглавление | Глава 23. § 1

инварианты, раскраски Глава 23. § 0 Делимость,

Глава 23.
Делимость, инварианты, раскраски



Основные сведения

1. В ряде задач встречается следующая ситуация. Некоторая система последовательно изменяет свое состояние, и требуется выяснить нечто о ее конечном состоянии. Полностью проследить за всеми переходами может оказаться делом сложным, но иногда ответить на требуемый вопрос помогает вычисление некоторой величины, характеризующей состояние системы и сохраняющейся при всех переходах (такую величину называют инвариантом для рассматриваемой системы). Ясно, что тогда в конечном состоянии значение инварианта будет то же самое, что и в начальном, т. е. система не может оказаться в состоянии с другим значением инварианта.

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

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

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


Глава 22. Решения | Оглавление | Глава 23. § 1

Copyright © 2002 МЦНМО Внимание! Данное издание содержит опечатки!
Исправленные исходные файлы книги и файлы нового издания доступны со страницы автора.
Заказ книги: biblio@mccme.ru.
Rambler's Top100