Фишки на клетчатой бумаге и инварианты: задание олимпиады Концевича
На бесконечной клетчатой бумаге отмечено шесть клеток (см. рисунок).
На некоторых клетках стоят фишки. Положение фишек разрешается преобразовывать по следующему правилу: если клетки соседняя сверху и соседняя справа от данной фишки обе свободны, то можно поставить в эти клетки по фишке, убрав при этом старую. Ставится цель за некоторое количество таких операций освободить все шесть отмеченных клеток. Можно ли достигнуть этой цели, если а) в исходной позиции имеются всего 6 фишек, и они стоят на отмеченных клетках; б) в исходной позиции имеется всего одна фишка, и она стоит в левой нижней отмеченной клетке.
Показать ответ
а) Нельзя; б) нельзя.
Разобрать решение
а) Присвоим каждой клетке угла "вес" (рис. 1). Вычислим сумму весов всех клеток угла:
(½ + ¼ + ⅛ + ...) + (¼ + ⅛ + ...) + (⅛ + ...) + ... = 1 + ½ + ¼ + ... = 2.
Заметим, что сумма весов клеток, на которых стоят фишки, не меняется при допустимом преобразовании. Вначале сумма весов клеток, занимаемых фишками, равна ½ + 2·¼ + 3·⅛ = 11/8. Если бы нам удалось освободить уголок от фишек, то все фишки стояли бы на клетках вне уголка, сумма весов которых равна 2 – 11/8 = ⅝ < 11/8. Противоречие.
б) Допустим, мы смогли освободить уголок от фишек. Заметим, что тогда в каждом ряду Р1 и Р2 (рис. 2) стоит ровно по одной фишке, а сумма весов занимаемых ими клеток не превосходит 1/8. Остальные фишки должны стоять в области O. Сумма весов всех клеток этой области равна ⅜. Тем самым, сумма весов клеток, занимаемых фишками, строго меньше (так как в области O располагается конечное число фишек) чем ⅜ + ⅛ = ½. Это противоречит тому, что в начале сумма весов была равна ½.
Обсуждение
0Комментариев пока нет.