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