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

Проект МЦНМО
при участии
школы 57
Задача 65759
Темы:    [ Геометрия на клетчатой бумаге ]
[ Замощения костями домино и плитками ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Автор: Храмцов Д.

На клетчатый лист бумаги размера 100×100 положили несколько попарно неперекрывающихся картонных равнобедренных прямоугольных треугольничков с катетом 1; каждый треугольничек занимает ровно половину одной из клеток. Оказалось, что каждый единичный отрезок сетки (включая граничные) накрыт ровно одним катетом треугольничка. Найдите наибольшее возможное число клеток, не содержащих ни одного треугольничка.


Решение

  Положим  n = 50.  Назовём треугольничек верхним, если он расположен сверху от прямой, содержащей его горизонтальный катет, и нижним иначе. Пронумеруем горизонтальные линии сетки снизу вверх числами от 0 до 2n.
  Оценка. Обозначим через uk (соответственно dk) число отрезочков k-й линии, участвующих в верхних (соответственно нижних) треугольничках; тогда
uk + dk = 2n  и  u0 = d2n = 2n.  Кроме того, вертикальные отрезки сетки, расположенные между k-й и (n+1)-й линиями, участвуют ровно в  uk + dk+1  треугольничках, так что  uk + dk+1 = 2n + 1.  Отсюда несложно получить, что  dk = k  и  uk = 2n – k  при всех k.
  Рассмотрим теперь клетки, расположенные между k-й и (k+1)-й линиями сетки. Хотя бы  uk = 2n – k  из этих клеток содержат по верхнему треугольнику, и хотя бы  dk+1 = k + 1  из них содержат по нижнему. Значит, свободных клеток в этом ряду не больше, чем  2n – max{uk, dk+1},  то есть не больше k при  k < n  и не больше  (2n – 1) – k  при  k ≥ n.  Итого, общее число свободных клеток не больше, чем  2(0 + 1 + … + (n – 1)) = n(n – 1).
  Пример. На рисунке показан пример для  n = 4.  Пример при  n = 50  строится аналогично: выделяется "прямоугольник" из клеток со сторонами из  n + 1  и n клеток, параллельными диагоналям доски, его клетки красятся в шахматном порядке (так, что угловые клетки прямоугольника – чёрные), и во все чёрные клетки кладётся по два треугольничка (при этом  n(n – 1)  белых клеток остаются свободными); в оставшихся же четырёх "углах" доски треугольнички кладутся так, что прямой угол треугольника "направлен" в ту же сторону, что и весь "угол".


Ответ

49·50 = 2450  клеток.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2015/2016
этап
Вариант 5
класс
Класс 11
задача
Номер 11.3

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

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