О принципе Дирихле

[Sasha2]

На AoPS приведена интересная задача, звучащая так:

Даны 7 отрезков, длина каждого из которых не менее 1 и не более 10 дюймов, ну или сантиметров, что вообщем не важно.
Доказать, что из них можно выбрать 3 таких, которые являются сторонами некоего треугольника.

Вот ссылка на оригинал: https://artofproblemsolving.com/wiki/in ... d_Problems

Интересно, как образовать треугольник, если семь отрезков будут иметь вот такие длины: 1.05, 1.05, 2.15, 2.15, 4.35, 4.35, 9.95?

[Xaositect]

А что не так? 1.05, 2.15 и 2.15 образуют треугольник.

[Gagarin1968]

Sasha2 в сообщении #1463425 писал(а):

Интересно, как образовать треугольник, если семь отрезков будут иметь вот такие длины: 1.05, 1.05, 2.15, 2.15, 4.35, 4.35, 9.95?

А в чём, собственно, подвох?
Равнобедренный треугольник со сторонами $ 2.15, 4.35, 4.35$ устроит?

[gris]

Шесть штук можно подобрать для нельзя: $1,1,2,3,5,8$. А можно считать начало отсчета в см, а конец в дюймах Тогда можно восемь штук.

[Sasha2]

Да сглупил немного при организации отрезков.

А вот такая задача:
В доме живёт 123 жителя. Всем им вместе 3813 лет. Можно ли выбрать из них 100 жителей, которым всем вместе не менее 3100 лет?

Я рассуждал так. Допустим что нельзя, то есть если любым 100 жителям менее 3100 лет, то тогда любым 23 жителям более 713 лет.
Теперь расположим их в порядке возрастания их возрастов. Получаем, что средний возраст любых 23 жителей более 31 года, а значит среди любых 23 есть, как минимум один, которому больше 31 год.
В том числе и среди самых младших. Но тогда мы получим 100 человек возраст, каждого из которых более 31 года. Получаем противоречие.
Ответ: Таких 100 людей найти можно.

Вроде бы правильно, но что-то меня смущает, может все-таки мое рассуждение ошибочно?

[Gagarin1968]

Sasha2 в сообщении #1463539 писал(а):

Вроде бы правильно

По-моему, правильно, но как-то уж сумбурно.
Чётче было бы так:

Sasha2 в сообщении #1463539 писал(а):

расположим их в порядке возрастания их возрастов

и отберём $100 $ самых старших , остальных отбросим. И рассмотрим внимательно эту сотню.
А уж далее по Вашему тексту.

[Sasha2]

Кажется понял, как решать про отрезки.
Пожалуйста проверьте, правильно или нет.

Организуем три клетки по принципу:
1) В первую клетку сажаем все отрезки длины, которых находятся в диапазоне от 1 до 2 и от 9 до 10.
2) Во вторую клетку сажаем все отрезки, длины которых находятся в диапазоне от 2 до 4 и от 7 до 9.
3) И в последнюю третью клетку сажаем все отрезки, длины которых находятся от 4 до 7.

Поскольку отрезков 7, а клеток всего три, то в одной клетке будут находиться как минимум три отрезка.
Из этих трех и строим наш треугольник.

[gris]

А если в первой клетке окажутся $1,2,9$

[Руст]

Оптимально, когда не образуется треугольник, стороны образуют числа Фибоначчи. Задача состоит в том, что $F_7\ge 10$.

[Sasha2]

gris в сообщении #1464294 писал(а):

А если в первой клетке окажутся $1,2,9$

Это значит, что я неправильно решил задачу.
Что ж, буду дальше думать.

[gris]

Я просто подумал, что можно организовывать не три ящика, а больше, а ПД применять не сразу, а после некоторых рассуждений о заполняемости отдельных ящиков

[gris]

Забросили задачу
Ну вот скажу о своём видении. Ящики такие: $[1,2);[2,3);[3,5);[5,8);[8,10].$
Свойство системы такое: любые три отрезка из одного ящика годятся для треугольника; два отрезка из одного ящика и один из предыдущего годятся. Остальное не карантирует успеха.
Берём раскидываем сначала шесть отрезков. Если попадаются удачные ящики или пары соседних ящиков вида (по количеству отрезков в): $>2$ или $1,2$ или $2,2$, то седьмой отрезок можно не кидать. Рассмотрим плохие комбинации вида $2,1,1,0,2; \;2,0,2,0,2...$. Вот тут пригождается вариация Принципа Дирихле: если отрезок кинуть в систему ящиков, то ровно в одном количество отрезков увеличится на единицу. Мы видим, что всегда плохая комбинация превращается в хорошую. Ну тут можно и рассуждением, особенно при обобщении.
А обобщать можно начало и длину. Ну там несложно.

Я думаю, что есть более короткое решение и призываю ТС найти его.

[Sasha2]

Да нет не забросил.
Там достаточно понятно, если воспользоваться числами Фибоначчи.
Но хотелось бы избежать всей мути и найти красивое и короткое рассуждение.