|
|
 |
Условие
Прямую палку длиной 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 + a2, A3 = a1 + a2 + a3, ..., A100 = a1 + a2 + ... + a100 найдутся два, дающие одинаковый остаток от деления на 99. Пусть это Ak и Al, k < l. Число Al – Ak больше нуля и меньше 198, при этом оно делится на 99. Значит, Al – Ak = 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.
