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

Проект МЦНМО
при участии
школы 57
Задача 79283
Темы:    [ Числовые таблицы и их свойства ]
[ Теория алгоритмов ]
Сложность: 3+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

В клетках прямоугольной таблицы 8×5 расставлены натуральные числа. За один ход разрешается одновременно удвоить все числа одной строки или же вычесть единицу из всех чисел одного столбца. Доказать, что за несколько ходов можно добиться того, чтобы все числа таблицы стали равными нулю.


Решение

  Превратим в нули вначале все числа первого столбца. Если в первом столбце есть единицы, то удвоим числа в тех строках таблицы, на пересечении которых с первым столбцом стоят единицы, а затем вычтем из всех чисел первого столбца по единице. Понятно, что при этом "старые" единицы останутся на местах, а каждое отличное от единицы число первого столбца на единицу уменьшится. Если единиц в первом столбце с самого начала нет, то будем вычитать из всех его чисел по единице до тех пор, пока единицы (хотя бы одна) не появятся, а затем произведём уже описанную операцию. Эту операцию (удвоения строк, на пересечении которых с первым столбцом находятся единицы, и последующего вычитания по единице из каждого числа первого столбца) будем повторять, пока все числа первого столбца не станут единицами. Вычитая затем из каждого числа первого столбца по единице, мы превратим их все в нули.
  Итак, мы получили таблицу, в первом столбце которой стоят нули, а в остальных столбцах – натуральные числа. Превратив в нули описанным способом последовательно числа 2-го, 3-го, ..., n-го столбцов (при этом уже имеющиеся нули не будут "портиться"), мы получим таблицу, состоящую целиком из нулей.

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

журнал
Название "Квант"
год
Год 1974
выпуск
Номер 9
Задача
Номер М282
олимпиада
Название Московская математическая олимпиада
год
Номер 37
Год 1974
вариант
Класс 8
Тур 2
задача
Номер 3

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

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