2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 О принципе Дирихле
Сообщение17.05.2020, 19:38 


21/06/06
1721
На 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?

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение17.05.2020, 19:43 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение17.05.2020, 19:46 
Аватара пользователя


01/11/14
1647
Principality of Galilee
Sasha2 в сообщении #1463425 писал(а):
Интересно, как образовать треугольник, если семь отрезков будут иметь вот такие длины: 1.05, 1.05, 2.15, 2.15, 4.35, 4.35, 9.95?
А в чём, собственно, подвох?
Равнобедренный треугольник со сторонами $ 2.15, 4.35, 4.35$ устроит?

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение17.05.2020, 20:15 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение18.05.2020, 07:17 


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

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

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

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

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение18.05.2020, 07:33 
Аватара пользователя


01/11/14
1647
Principality of Galilee
Sasha2 в сообщении #1463539 писал(а):
Вроде бы правильно
По-моему, правильно, но как-то уж сумбурно.
Чётче было бы так:
Sasha2 в сообщении #1463539 писал(а):
расположим их в порядке возрастания их возрастов
и отберём $100 $ самых старших , остальных отбросим. И рассмотрим внимательно эту сотню.
А уж далее по Вашему тексту.

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение21.05.2020, 08:30 


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

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

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

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение21.05.2020, 08:51 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение21.05.2020, 09:14 
Заслуженный участник


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

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение21.05.2020, 11:07 


21/06/06
1721
gris в сообщении #1464294 писал(а):
А если в первой клетке окажутся $1,2,9$


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

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение21.05.2020, 11:29 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение22.05.2020, 19:30 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Забросили задачу :-(
Ну вот скажу о своём видении. Ящики такие: $[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...$. Вот тут пригождается вариация Принципа Дирихле: если отрезок кинуть в систему ящиков, то ровно в одном количество отрезков увеличится на единицу. Мы видим, что всегда плохая комбинация превращается в хорошую. Ну тут можно и рассуждением, особенно при обобщении.
А обобщать можно начало и длину. Ну там несложно.

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

 Профиль  
                  
 
 Re: О принципе Дирихле
Сообщение22.05.2020, 21:18 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group