Задача 97775

Темы:    [ Инварианты ] [ Шахматные доски и шахматные фигуры ] [ Процессы и операции ]

Сложность: 5 Классы: 9,10,11

Условие

Автор: Концевич М.

На бесконечной клетчатой бумаге отмечено шесть клеток (см. рисунок).

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

Решение

   а) Присвоим каждой клетке угла "вес" (рис. 1). Вычислим сумму весов всех клеток угла:
(½ + ¼ + ⅛ + ...) + (¼ + ⅛ + ...) + (⅛ + ...) + ... = 1 + ½ + ¼ + ... = 2.
  Заметим, что сумма весов клеток, на которых стоят фишки, не меняется при допустимом преобразовании. Вначале сумма весов клеток, занимаемых фишками, равна   ½ + 2·¼ + 3·⅛ = ¹¹/₈.   Если бы нам удалось освободить уголок от фишек, то все фишки стояли бы на клетках вне уголка, сумма весов которых равна   2 – ¹¹/₈ = ⅝ < ¹¹/₈.   Противоречие.

  б) Допустим, мы смогли освободить уголок от фишек. Заметим, что тогда в каждом ряду Р₁ и Р₂ (рис. 2) стоит ровно по одной фишке, а сумма весов занимаемых ими клеток не превосходит ¹/₈. Остальные фишки должны стоять в области O. Сумма весов всех клеток этой области равна ⅜. Тем самым, сумма весов клеток, занимаемых фишками, строго меньше (так как в области O располагается конечное число фишек) чем   ⅜ + ⅛ = ½.   Это противоречит тому, что в начале сумма весов была равна ½.

Ответ

а)  Нельзя;   б)  нельзя.

Замечания

1. Баллы: 8 + 8.

2. См. также статью А. Ходулева "Расселение фишек".

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Номер	2
Дата	1980/1981
вариант
Вариант	9-10 класс
Задача
Номер	5