|
|
 |
Условие
Докажите, что в таблице 8×8 нельзя расставить натуральные числа от 1 до 64 (каждое по одному разу) так, чтобы в ней для любого квадрата 2×2 вида
было выполнено равенство |ad – bc| = 1.
Решение
Предположим, что расставить числа удалось. Рассмотрим произвольный
квадрат 2×2. Так как |ad – bc| = 1, то числа ad и bc имеют разную чётность. Следовательно, среди чисел a, b, c и d есть по крайней мере одно чётное и два нечётных числа, причём если в этом квадрате два чётных числа, то они стоят по диагонали. Значит, чётные числа не могут стоять в соседних по вертикали или горизонтали
ячейках таблицы.
Таблица 8×8 состоит из 16 квадратов такого вида. Так как среди чисел от 1 до 64 ровно 32 чётных и 32 нечётных, то в каждом из этих 16
квадратов должны быть записаны ровно два чётных числа. Занумеруем эти 16
квадратов в произвольном порядке от 1 до 16. Определим для каждого из них свое
число, равное дроби ad/bc, если чётными являются числа a и d, и дроби bc/ad, если чётными являются числа b и c. Обозначим через Pj число, которое получилось для квадрата под номером j. Пусть для определенности в квадрате под номером j
чётными являются числа a и d. Тогда из
|ad – bc| = 1 следует, что . Значит, Pj < Qj, где Qj равно дроби, в знаменателе которой
написано произведение двух нечётных чисел из квадрата j, а в числителе – произведение больших их на единицу чётных чисел.
С одной стороны, , так как в числителях дробей
P1, P2, ..., P16
встретятся по одному разу все чётные числа от 2 до 64, а в знаменателях – все нечётные числа от 1 до 63. С другой стороны,
, так как в знаменателях дробей
Q1, Q2, ..., Q16
встретятся по одному разу все нечётные числа от 1 до 63, а в числителях – все чётные числа от 2 до 64. Получаем противоречие, ведь по доказанному
P1P2...P16 < Q1Q2...Q16.
