МАЛЫЙ МЕХМАТ МГУ

Занятие 9. ИНВАРИАНТЫ

Инвариант — это величина, которая не изменяется в результате некоторых действий. В качестве инварианта часто используют чётность, произведение или сумму данных чисел и тому подобные величины.

1.	Может ли слон за миллион ходов попасть с поля а1 на поле а8?
2.	Разменный автомат меняет одну монету на пять других. Можно ли с его помощью разменять одну монету на 26 монет?
3.	а) Волк и семеро козлят встали в один ряд и играют в чехарду: каждую секунду двое из них, стоящие через одного, могут, прыгнув, поменяться местами. Если окажется, что они стоят в обратном порядке по сравнению с исходным, игра заканчивается. Закончится ли игра? б) А если в игру играют Али-баба и сорок разбойников?
4.	По кругу расставлены числа 12, 7, 23, 45, 13, 5. За один ход можно прибавить или отнять одно и то же число (не обязательно целое) от двух стоящих рядом чисел. Можно ли за несколько ходов получить числа 7, 13, 4, 1, 5, 12?
5.	Фигура «верблюд» ходит по доске 10×10 ходом типа (1,3) (то есть она сдвигается сначала на соседнее поле, а затем ещё на три поля в перпендикулярном направлении; шахматный конь, например, ходит ходом типа (1,2)). Можно ли пройти ходом «верблюда» с какого-то исходного поля на соседнее с ним?
6.	В таблице 8×8 одна из клеток закрашена чёрным цветом, все остальные — белым. а) Докажите, что с помощью перекрашиваний строк и столбцов нельзя добиться того, чтобы все клетки стали белыми. (Под перекрашиванием строки или столбца понимаем изменение цвета всех клеток в строке или столбце.) б) А если таблица имеет размер 3×3 и закрашена в ней угловая клетка?
7.	На острове Серобуромалин обитают 13 серых, 15 бурых и 17 малиновых хамелеонов. Если встречаются два хамелеона разного цвета, то они одновременно меняют свой цвет на третий. Может ли случиться, что через некоторое время все хамелеоны будут одного цвета?
8.	В алфавите языка племени УЫУ две буквы: У и Ы, причём этот язык обладает интересным свойством: если из слова выкинуть стоящие рядом буквы УЫ или УЫУУ, то смысл слова не изменится. Смысл не меняется и при добавлении в любое место слова буквосочетаний УУ, ЫЫУУЫЫ или УЫЫУ. Можно ли утверждать, что слова УЫЫ и УЫУЫ имеют одинаковый смысл? Домашние задачи
9.	Решите шестую задачу для таблицы 3×3, если закрашены 4 угловые клетки.
10.	Вдоль забора растут 8 кустов малины. Количества ягод на соседних кустах отличаются на 1. Может ли на всех кустах вместе быть 225 ягод?
11.	Расставьте по кругу числа 14, 27, 36, 57, 178, 467, 590 и 2345 так, чтобы любые два соседних числа имели общую цифру.