Олимпиадная задача по математике: палка и прямоугольник, комбинаторика, 8-9 класс

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

  Покажем, что при  N = 102  искомый прямоугольник найдётся.   Первый способ. Заметим, что среди всех палочек найдутся две длиной по 1 см. В самом деле, если бы это было не так, то суммарная длина палочек была бы не меньше  2·101 + 1 = 203  см.

  Отложим эти две палочки. Пусть длины оставшихся палочек равны  a₁, a₂, ..., a₁₀₀  см,  a₁ + a₂ + … + a₁₀₀ = 198.  Среди 100 чисел  A₁ = a₁,

A₂ = a₁ + a₂,  A₃ = a₁ + a₂ + a₃,  ...,  A₁₀₀ = a₁ + a₂ + ... + a₁₀₀  найдутся два, дающие одинаковый остаток от деления на 99. Пусть это A_k и A_l,  k < l.  Число  A_l – A_k  больше нуля и меньше 198, при этом оно делится на 99. Значит,  A_l – A_k = 99 = a_k+1 + a_k+2 + ... + a_l.

  Тем самым, мы нашли несколько палочек суммарной длины 99 см. Отложим и их. Оставшиеся палочки также имеют суммарную длину 99 см. Таким образом, нам удастся сложить прямоугольник 1×99 см.   Второй способ. Обозначим длины палочек набора через  a₁, a₂, ..., a₁₀₂.  Рассмотрим окружность длины 200 и разобьём её 102 красными точками на дуги длины  a₁, a₂, ..., a₁₀₂.  Эти точки являются некоторыми 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.