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

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

Условие

Клетки шахматной доски занумерованы числами от 1 до 64 так, что соседние номера стоят в соседних (по стороне) клетках.
Какова наименьшая возможная сумма номеров на диагонали?


Решение

  Оценка. Рассмотрим числа  a1 < a2 < ... < a8,  стоящие на чёрной диагонали (конечно, на диагонали они могут стоять не по порядку). Тогда  a1 ≥ 1,  a2 ≥ 3,  a3 ≥ 5,  ...,  a7 ≥ 13.  Докажем, что  a8 ≥ 39.
  Предположим, что мы вписывали числа в клетки доски в порядке их возрастания. Тогда в тот момент, когда мы вписывали на диагональ восьмое число, покидаемая нами половина доски была заполнена (ибо мы в неё уже не вернулись). Эта половина (включая диагональ) содержит 36 клеток: 16 белых и 20 чёрных. Но при заполнении доски белые и чёрные клетки чередуются. Поэтому к этому моменту были заполнены ещё как минимум три белые клетки в другой половине доски, то есть всего заполнено не меньше 39 клеток.
  1 + 3 + 5 + ... + 13 + 39 = 88.
  Пример изображён на рисунке.


Ответ

88.

Замечания

6 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 2001/2002
Номер 23
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 3

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

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