Я расскажу про несколько связанных задач, например такую: Доказать, что среди 1001 прямоугольника, стороны каждого из которых целые и отличаются не более чем на 100, найдутся 21, которые можно упаковать друг в друга (первый во второй, второй в третий и так далее). Общая идея задач - использование частично упорядоченных множеств (которые нам уже встречались). Я мотивирую и дам определения, докажу теорему Мирского и расскажу про ее применения в олимпиадных задачах. Доклад будет следовать статье Александра Спивака в «Кванте» и первым лекциям курса Алексея Балицкого. Основной материал будет доступен школьнику, но по желанию слушателей во второй части мы обсудим теорему Дилуорса и лемму Холла (тоже с приложениями). Таймкоды 00:00 начало 02:45 задача про 5 чисел 15:10 теорема Эрдеша-Секереса 20:40 разбор частного случая 44:30 общая конструкция 51:30 задача про людоедов 01:02:20 доказательство задачи про людоедов 01:12:20 доказательства теоремы Эрдеша-Секереса 01:20:15 частично упорядоченные множества 01:27:20 цепи, антицепи и теорема Мирского 01:33:20 задача про прямоугольники
