ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109937
Темы:    [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
[ Процессы и операции ]
[ Перебор случаев ]
[ Инварианты ]
Сложность: 4-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Имеется таблица n×n, в  n – 1  клетках которой записаны единицы, а в остальных клетках – нули. С таблицей разрешается проделывать следующую операцию: выбрать клетку, вычесть из числа, стоящего в этой клетке, единицу, а ко всем остальным числам, стоящим в одной строке или в одном столбце с выбранной клеткой, прибавить единицу. Можно ли из этой таблицы с помощью указанных операций получить таблицу, в которой все числа равны?


Решение

  Докажем, что в исходной таблице найдётся подтаблица 2×2, в которой стоит одна единица и три нуля.
  Найдется строка, в которой стоят одни нули (так как строк n, а единиц  n – 1).  Очевидно, что в таблице найдутся две соседние строки, в одной из которых стоят все нули, а в другой по крайней мере одна единица. В этой ненулевой строке найдутся две соседние клетки, в одной из которых стоит единица, а в другой – ноль. Эти две клетки и две соседние клетки из нулевой строки образуют искомую подтаблицу.
  Выберем в нашей таблице произвольную подтаблицу 2×2: пусть в ее левом верхнем углу стоит число a, в правом верхнем – b, в левом нижнем – c и в правом нижнем – d, а после проведения операции – a1, b1, c1, d1 соответственно. Рассмотрим выражения   D = (a + d) – (b + c)  и  D1 = (a1 + d1) – (b1 + c1).   Возможны три случая.
  1) Выбранная клетка находится вне нашей подтаблицы, но лежит в строке или столбце, пересекающем нашу подтаблицу. Пусть для определенности она лежит в одной строке c a и b, тогда  a1 = a + 1,  b1 = b + 1,  c1 = cd1 = d  и  D1 = (a + 1 + d) – (b + 1 + c) = D.
  2) Выбранная клетка находится вне нашей подтаблицы, и при этом она не лежит ни в строке, ни в столбце, пересекающем нашу таблицу. Тогда, очевидно, D1 = D.
  3) Выбранная клетка находится внутри нашей подтаблицы. Пусть для определенности она – верхняя левая клетка подтаблицы, тогда  a1 = a – 1,  b1 = b + 1,  c1 = c + 1,  d1 = d  и  D1 = D – 3.  (Если правая нижняя, то опять  D1 = D – 3,  в противном случае  D1 = D + 3.)
  Таким образом, мы показали, что остаток от деления D на 3 – инвариант. Однако в исходной таблице мы нашли подтаблицу 2×2, в которой  D = ±1,  а мы должны получить таблицу, в которой все числа равны, то есть с  D = 0,  что невозможно.


Ответ

Нельзя.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1998
Этап
Вариант 4
Класс
Класс 11
задача
Номер 98.4.11.4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .