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

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

Условие

Докажите, что в таблице 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.

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

олимпиада
Название Московская математическая олимпиада
год
Год 2015
Номер 78
класс
Класс 11
задача
Номер 5

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

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