Это достаточно красивая и интересная, на мой взгляд, задача.
На столе лежат 16 монет, составляющих квадрат 
. Часть из этих монет лежит вверх орлом, а часть — решкой. Монеты можно переворачивать по следующим правилам: можно перевернуть все монеты, находящиеся в одном горизонтальном ряду, в одном вертикальном ряду или на одной диагонали (если монета лежит в углу, она образует диагональ из одной монеты). Целью игры является перевернуть все монеты вверх либо орлом, либо решкой. Всегда ли возможно это сделать или существуют некоторые расположения монет, для которых это невозможно?
Показать решение
Это задача на инвариант.
Мы будем рассматривать конечное расположение монет, при котором все монеты лежат вверх орлом. Ясно, что из этого расположения можно получить второй вариант — когда все монеты лежат вверх решкой — довольно легко: например, можно перевернуть все горизонтальные ряды.
Разделим монеты на три группы: в первую группу отнесем все угловые монеты — их 
. Во вторую группу отнесем четыре внутренние монеты. В третью группу отнесем оставшиеся монеты, т.е. четыре пары монет, стоящих по сторонам квадрата, но не угловых.
На рисунке ниже монеты первой группы синие, второй — зеленые, третьей — красные.
Очевидно, что можно перевернуть любую угловую монету, не трогая ни одной из оставшихся монет.
Покажем теперь, как можно перевернуть одну из внутренних монет так, что все остальные монеты останутся в исходном состоянии:
Здесь монеты, лежащие вверх орлом, изобраены синими точками, а монеты, лежащие вверх решкой — красными точками.
Ясно, что точно так же, произведя симметричные операции, можно перевернуть и любую из трех других внутренних монет.
Теперь рассмотрим одну из монет, относящихся к третьей группе. Эта монета лежит в одном горизонтальном ряду, в одном вертикальном и на двух диагоналях. Как видно из рисунка, при перевороте любого ряда, содержащего данную монету, перевернутой останется одна и только одна монета той же группы. Тем самым, мы не сможем перевернуть все монеты вверх орлом, если у нас в начале игры перевернуто нечетное число монет третьей группы. При этом любые две монеты из третьей группы, как легко видеть, можно одновременно перевернуть.
Итак, инвариантом в этой задаче является четность числа перевернутых решкой монет третьей группы.
Источник: http://ima.org.uk/viewitem.cfm?cit_id=383601
1 disputant:
Дык… Если это + и – единицы в матрице, вот и имеем инвариант – произведение всех элементов матрицы
[Ответить]
16 Май 2012, 6:062 disputant:
Виноват, упустил “если монета лежит в углу, она образует диагональ из одной монеты” – тогда, понятно, что инвариант другой. Но что это такое – диагональ из одной монеты?
Тогда инвариант, по сути, произведение во внутреннем квадрате 2×2…
[Ответить]
16 Май 2012, 6:103 disputant:
Да, а можно решения давать не сразу, а через пару дней? а то неинтересно…
[Ответить]
16 Май 2012, 6:114 Корнеев В.Ф.:
Что такое диагональ из одной монеты? Да то же, что и диагональ из двух монет. Это рядом.
[Ответить]
16 Май 2012, 9:325 Елизавета Александровна Калинина:
2disputant О решениях, давать ли их сразу или чуть позже, было голосование. Большинство высказавшихся было за то, чтобы решения были сразу. Я их закрываю
Вы просто не читайте их сразу 
[Ответить]
16 Май 2012, 12:56