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

Проект МЦНМО
при участии
школы 57
Задача 116547
Темы:    [ Геометрия на клетчатой бумаге ]
[ Принцип Дирихле (прочее) ]
[ Задачи с неравенствами. Разбор случаев ]
Сложность: 4
Классы: 8,9
В корзину
Прислать комментарий

Условие

Прямую палку длиной 2 метра распилили на N палочек, длина каждой из которых выражается целым числом сантиметров. При каком наименьшем N можно гарантировать, что, использовав все получившиеся палочки, можно, не ломая их, сложить контур некоторого прямоугольника?


Решение

  Пусть  N ≤ 101.  Распилим палку на  N – 1  палочку длиной 1 см и одну палочку длиной  201 – N  см. Из полученного набора невозможно сложить прямоугольник, так как каждая из сторон прямоугольника меньше полупериметра и, следовательно, палочка длины  201 – N ≥ 100  см не может быть частью никакой стороны. Таким образом,  N ≥ 102.
  Покажем, что при  N = 102  искомый прямоугольник найдётся.

  Первый способ. Заметим, что среди всех палочек найдутся две длиной по 1 см. В самом деле, если бы это было не так, то суммарная длина палочек была бы не меньше  2·101 + 1 = 203  см.
  Отложим эти две палочки. Пусть длины оставшихся палочек равны  a1, a2, ..., a100  см,  a1 + a2 + … + a100 = 198.  Среди 100 чисел  A1 = a1,
A2 = a1 + a2A3 = a1 + a2 + a3,  ...,  A100 = a1 + a2 + ... + a100  найдутся два, дающие одинаковый остаток от деления на 99. Пусть это Ak и Al,  k < l.  Число  Al – Ak  больше нуля и меньше 198, при этом оно делится на 99. Значит,  AlAk = 99 = ak+1 + ak+2 + ... + al.
  Тем самым, мы нашли несколько палочек суммарной длины 99 см. Отложим и их. Оставшиеся палочки также имеют суммарную длину 99 см. Таким образом, нам удастся сложить прямоугольник 1×99 см.

  Второй способ. Обозначим длины палочек набора через  a1, a2, ..., a102.  Рассмотрим окружность длины 200 и разобьём её 102 красными точками на дуги длины  a1, a2, ..., a102.  Эти точки являются некоторыми 102 вершинами правильного 200-угольника T, вписанного в эту окружность. Вершины T разбиваются на пары противоположных. Таких пар 100, а красных точек – 102, значит, среди красных точек найдутся две пары противоположных.
  Эти две пары точек делят окружность на две пары равных дуг. Таким образом, мы разбили все палочки на четыре группы A, B, C, D, причём суммарные длины в группах A и C, а также в группах B и D равны. Значит, можно составить прямоугольник, используя каждую группу для составления одной его стороны.

  Третий способ. Пусть  l ≥ 2  – наибольшая среди длин всех палочек, а x – количество палочек длины 1. Тогда кроме этих x палочек и палочки длины l имеется  101 – x  палочек, длина каждой из которых не меньше 2. Отсюда  l + x + 2(101 – x) ≤ 200,  то есть  x ≥ l + 2.  Итак, имеется по крайней мере
l + 2  палочки длины 1. Отложим две палочки длины 1 – из них сделаем две стороны прямоугольника, остаётся еще l палочек длины 1. Начнём выкладывать палочки в ряд в порядке убывания длин с целью выложить отрезок длины 99. Пусть на каком-то шаге ряд имел длину  L < 99,  а после добавления очередной палочки длины m стал иметь длину  L + m > 99.  Тогда уберём последнюю выложенную палочку длины m и вместо неё положим  99 – L  единичных палочек (это можно сделать, так как  99 – L < m ≤ l).  Теперь у нас выложены три стороны прямоугольника (1, 1 и 99). Выложив оставшиеся палочки в ряд, получим ещё одну сторону длины 99.


Ответ

При  N = 102.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2010-2011
Этап
Вариант 4
Класс
Класс 9
Задача
Номер 9.8
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2010-2011
Этап
Вариант 4
Класс
Класс 10
Задача
Номер 10.8

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

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