Олимпиадная комбинаторика

Пост благодарности! Я бы хотел поблагодарить всех участников олимпиады за то, что они не поленились потратить свое воскресное время на решение задач, борьбу с лингвистическими и, порой, техническими трудностями, и это при том, что олимпиада эта не дает практически никаких бенефитов — без вас эта олимпиада была бы неполноценной.

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

Я бы очень хотел поблагодарить авторов задач, которые не пожалели потратить свои творения на в общем-то никому пока неизвестную олимпиаду. В этом году, на мой взгляд, вариант получился значительно более интересным именно благодаря вам. Спасибо и тем, кто прислал свои задачи, но задачи нам почему-то не подошли. Я очень надеюсь, что вы не перестанете придумывать задачи и будете столь же отзывчивы на наши просьбы о помощи!

Я бы, конечно, хотел поблагодарить организаторов, потому что без их инициативы это мероприятие уж точно не состоялось бы. Организаторам всегда приходится не сладко, а работу их почти никто не видит.

Ну и конечно, я хотел бы поблагодарить своих коллег по методической комиссии!

Надеюсь олимпиада будет расти! И мы проведем ее еще лучше в следующем году. Пока что все задачи можно найти на аопсе. Но очень скоро мы доделаем и официальный файлик с условиями и решениями.

Опубликуем одну из задач нашей сегодняшней олимпиады «JetBrains Youth Challenge», автор — Д. В. Афризонов.

В лиге старших классов она была 4-й из 8, и её решили 8 команд из 50. А вы сможете?

#мт_задача

Пользуясь случаем, напомню следующую задачу.

У Белочки есть бесконечно много орехов: по одному ореху каждой из
масс 1 г, 2 г, 3 г, \dots. Она взяла n мешков, положила в каждый по
конечному числу орехов, после чего написала на каждом мешке суммарную
массу лежащих в нем орехов.

а) Докажите, что можно было собрать мешки с
такими же массами, использовав не более 4n-3 орехов.

б*) Какова точная оценка на число орехов, которого заведомо достаточно?

Пункт б) я решать не умею.

Так-так-так... Разыскиваются сильные команды, способные решить все задачи на JetBrains Math Challenge! Мне кажется, что в этот раз это будет не так просто... До окончания регистрации осталась всего неделя! А до самой олимпиады всего две недели (чуть меньше)!

(Кстати, это хороший способ потренироваться перед Колмом...)

А вот и обещанная задача

Есть гирьки массами 2⁰, 2¹, …, 2ⁿ грамм и чашечные весы, изначально находящиеся в равновесии. Нужно последовательно выставлять по одной гирьке на весы в некотором порядке так, чтобы в каждый момент времени правая чаша весов не перевешивала. Сколькими способами это можно сделать?

А вот кстати, завтра закроется регистрация на математический курс от Jet Brains. За три недели мы там поговорили про многочлены в целом, про разностный многочлен и вычисление разных сумм, про интерполяцию. Сейчас у нас первая неделя комбинаторного (дискретно-вероятностного) блока. И в нем мы дали одну, кажется, довольно трудную задачу. На вчерашний день ее правильно решил только один человек... из 400 зарегистрировавшихся на курсе (ну ладно, кого я обманываю, из 80-ти активно решающих). В конце недели опубликую эту задачу тут

Прочитал про теорему Дена о разрезании: если прямоугольник можно разрезать на квадраты, то отношение его сторон рационально. Интуитивно это кажется логичным, но доказать не так уж и просто. Обратное утверждение тривиально: если отношение сторон рационально и скажем равно p/q, то увеличив масштаб в q раз, получим прямоугольник с целыми сторонами, который можно разрезать на квадраты 1x1.

Линейная алгебра помогает построить простые и красивые доказательства:

Отношение длин сторон прямоугольника W,H иррационально - это то же, что "W,H линейно независимы как векторы в пространстве R над Q". Это в свою очередь значит, что существует Q-линейная функция f:R->R, так, что f(W) и f(H) - любые удобные нам значения.

Для любой Q-линейной функции f определим f-площадь прямоугольника со сторонами A,B как f(A)*f(B). Тогда легко увидеть, что при разрезании прямоугольника на другие прямоугольники f-площадь целого равна сумме f-площади частей (это очевидно при разрезании одного прямоугольника на два, и к повторению этого можно свести любое разрезание, если сделать из него "сетку", продлив все внутренние линии до краев).

Как ни странно, доказательство почти закончено. f-площадь любого квадрата равна f(A)*f(A), то есть неотрицательна. Отсюда f-площадь любого прямоугольника размером W:H, разрезанного на квадраты, неотрицательна. Но если W/H не рационально, то мы можем выбрать такую f, что f(W)=1, f(H)=-1, и его f-площадь равна -1, это противоречие.

Другое доказательство с помощью линейной алгебры вместо f-площади пользуется тензорным произведением R@R. Если стороны прямоугольника w,h линейно независимы, то {w,h} можно продлить до базиса, и поэтому ясно, что в R@R линейно независимы также векторы w@w, w@h, h@w, h@h. С другой стороны, если прямоугольник разбит на квадраты, то w@h является суммой членов вида a@a (доказательство аналогично примеру с площадью). Это значит, что изоморфизм в R@R, который меняет координаты местами, одновременно переводит w@h в h@w и оставляет неизменным, т.е. w@h = h@w, а это противоречит их независимости.

Еще есть красивое доказательство с помощью гармонических функций на конечных графах (второе в этой заметке). А в древней книжке Яглома "Как разрезать квадрат?" (1968) есть элементарное доказательство через систему уравнений, связывающих длины сторон.

P.S. Вспоминается также замечательная статья "Fourteen proofs of a result about tiling a rectangle", где дается много доказательство похожего, но другого по сути утверждения: что если прямоугольник разрезан на прямоугольники и у каждого внутренного прямоугольника хотя бы одна из сторон - целое число, то и у всего прямоугольника тоже хотя бы одна из сторон целая.

Всем привет! Как вы знаете я немного связан с образовательной программой от JetBrains в университете Неаполиса на Кипре. Один из преподавателей этой программы и мой хороший приятель Саша Авдюшенко на грядущей неделе проведет стрим на тему, как эффективно учиться (и учить!) с чатом ЖПТ. Ожидаю, что это будет очень классно! Регистируйтесь по ссылке и приходите!

Livestream Alert: How to Study Effectively With ChatGPT 📚

Are you interesed in transforming your study habits with AI?

Join our livestream on May 22 at 4:00 pm UTC as we explore the potential of AI in education, including ChatGPT and other cutting-edge tools.

What we'll cover:
🚀 The latest AI tools: Explore the latest advancements, such as GPT-4, Google Gemini, and Anthropic Claude 3, and learn how they can boost your learning.
🎓 AI's impact on education: Discover how AI is changing how we study, from solving complex geometry problems to enhancing exam prep and coding skills.
💫 Balancing AI and learning: Learn to integrate AI effectively while fostering critical thinking and independent learning.

See you there!

1 и 2 день, решения

Сегодня в Нижнем Новгороде прошёл первый тур Всероссийской олимпиады

Повысим сложность! Третья задачная разминка — от нашего преподавателя Афризонова Дениса Владимировича. Он прокомментировал её так:

В качестве новой разминки предложу задачи на тему «Подсчёт количества информации». В основном в задачах такого типа при помощи доступных операций/вопросов необходимо что-то выяснить за минимальное количество таких действий. Как правило, привести конкретный алгоритм и проверить его — не очень сложно. А вот доказательство его оптимальности вызывает определённые трудности, и без подсчёта количества информации зачастую просто не обойтись.

Такие задачи начинают встречаться в 5-6 классах, и зачастую это задачи про взвешивания (задача №1). Также без подсчёта количества информации не обойтись в более серьёзных задачах про фокусы (задача №2). А про задачу №3 скажу только, что задачу своего авторства не вставить в такую подборку я просто не мог 😀

Пишите ваши решения в комментариях, выделяя их скрытым шрифтом. Всем ответим!

Разбор задач будет проводиться Денисом Владимировичем в субботу 13 апреля в 16:00 мск по ссылке https://us02web.zoom.us/j/88455100213?pwd=NkkwMDdzbjdqZ0xsOGljQ2hLQjdUdz09
Присоединяйтесь!

#мтразминка

А вот и вторая задачная разминка — от нашего преподавателя Попова Леонида Андреевича. Он прокомментировал её так:

Задачи о подсчёте числа способов встречаются в кружках 5-8 классов довольно часто. Однако иногда кажется, что эта тема не так уж сильно раскрыта в старших классах. Тем не менее в серьёзных олимпиадах периодически встречаются интересные задачи, связанные с этой областью математики.

В этой разминке приведены 3 задачи, которые меня заинтересовали и которые я с удовольствием решал. Первая задача может быть решена даже учеником 5 класса, вторая требует более тщательного рассмотрения, а третья представляет собой более сложную задачу, над которой точно придётся какое-то время подумать.

Разбор задач будет проводиться Леонидом Андреевичем в субботу 6 апреля в 16:00 мск по ссылке https://us02web.zoom.us/j/83680022032?pwd=WXVvL2J0MEsvL25QajdkTVBFUzVOZz09
Присоединяйтесь!

#мтразминка

Всем привет! На прошедшей сегодня олимпиадке JB была очень классная задача.

#18. Дано дерево с n вершинами, на ребрах которого написаны числа (длины ребер). Известно, что среди длин кратчайших маршрутов между вершинами встречаются все натуральные числа от 1 до n(n-1)/2. Требуется доказать, что либо n либо n-2 является точным квадратом.

Такое дерево называется деревом Лича.

Всем привет!

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

Короче, мы тут с коллегами замутили олимпиадку по просьбе JetBrains. Итак, важная информация такая:

◆ Олимпиада устная
◆ Олимпиада онлайн в Дискорде
◆ Олимпиада международная (насколько это получится)
◆ Олимпиада командная (в команде 1-3 человека)
◆ Язык олимпиады английский (это означает, что условия вы получите на английском языке, но довольно много членов жюри говорит по-русски)
◆ В олимпиаде 12 задач (4 довывод - в зачет не идут, 8 вывод - идут в зачет)
◆ Уровень сложности последных задач - уровень последних задач всероссийской олимпиады
◆ Две лиги: Юниоры (13-16) и Сеньоры (17-18), не обучающиеся в высших учебных заведениях
◆ Финальный раунд состоится 25-го февраля в 10:00 CET (12:00 мск)
◆ До этого будет предложен демо-вариант, во время которого можно будет познакомиться с Дискордом и чуть меньшим количеством чуть менее неизвестных задач.


Зарегистрироваться на олимпиадку можно по ссылке:

https://lp.jetbrains.com/youth-challenge/

А если вы еще и программировать умеете, то можете поучастовать и в олимпиадке по проге, но там в одиночку.

Объявляем стипендию на обучение в наших кружках для учеников региональных школ!

Как знают многие подписчики нашего канала, мы занимаемся не только составлением тренировочных региональных олимпиад, но также ведём регулярные онлайн-кружки по олимпиадной математике для учеников с 5 по 11 класс (больше подробностей можно найти тут).

Сейчас у нас обучается довольно много ребят из Москвы и Санкт-Петербурга. Но при этом более половины наших преподавателей начали свой олимпиадный путь не в столичных регионах. Поэтому мы решили взять в наши кружки 10 учеников из российских регионов со скидкой более 80%! С учётом стипендии стоимость составит 350 рублей за каждое двухчасовое занятие в течение нескольких месяцев.

Мы сформулировали следующие критерии отбора:
— вы учитесь в школе не из Москвы, Мособласти, Санкт-Петербурга и Татарстана (именно эти регионы показали самые высокие результаты на прошлогоднем финале ВсОШ по математике);
— вы учитесь не в 11 классе, то есть готовиться к будущим олимпиадам вам ещё не поздно;
— на региональной олимпиаде ВсОШ или олимпиаде Эйлера (прошедшей пару дней назад) вы набрали хотя бы 42 балла;

Если всё написанное выше — про вас, смело заполняйте следующую анкету https://forms.gle/9CzHAFz8YYStgGJe8.
Анкета будет закрыта либо через 2 недели, либо ранее, если стипендиальные места закончатся.

Со всеми, кто своевременно заполнит анкету, мы проведём индивидуальные собеседования, по итогам которых будут выданы приглашения в наши кружки.

PS. Все кружки проходят в онлайн-формате (по московскому времени).
— Кружок 7-8 класса под руководством Смирнова Александра Викторовича проходит по вторникам и четвергам с 18:00 до 20:00.
— Кружок 9 класса под руководством Меньщикова Андрея Борисовича проходит по вторникам и пятницам с 18:00 до 20:00.
— Кружок 10 класса под руководством Афризонова Дениса Владимировича проходит по вторникам и пятницам с 18:00 до 20:00.
— В кружках 9 и 10 класса занятия по геометрии ведёт автор канала «Олимпиадная геометрия» Бахарев Фёдор Львович.

Книжка с авторскими решения региональной олимпиады для 9-11 класса (2 день)

Последний (четвёртый) тренировочный вариант региональной олимпиады

По ссылкам ниже находятся тренировочные варианты региональной олимпиады ВсОШ для каждой из параллелей (9, 10, 11 класс) и олимпиады Эйлера, разработанные командой преподавателей МТ кружков:
— Эйлер
— 9 класс
— 10 класс
— 11 класс

Если у вас есть такая возможность, то лучше всего прорешать вариант, соблюдая все правила написания реальной олимпиады:
— решать задачи надо в течение 4 часов подряд;
— в течение этого времени надо не только решать задачи, но ещё и записать их подробные решения;
— пользоваться можно только канцелярскими принадлежностями.

В конце этой недели к каждому варианту мы проведём стрим с подробным разбором. Ссылки на стримы будут опубликованы в нашем канале отдельным сообщением. Всем удачи🙂

PS. Условия и разбор первого тренировочного варианта можно посмотреть тут, второго — тут, а третьего — тут.

Клетчатая классика!

#18. Докажите, что число разбиений прямоугольника n×(n+1) на доминошки нечетно.

Всем привет! Сегодня у нас традиционна рубрика "Пятничные клеточки".

На этой неделе на курсе "ВсОШ" Дабромата как раз проходят клетчатые задачи. Лично мне очень нравится последняя задача и игрушка. Я в свое время получил огромное удовольствие от решения этих задач.

PS. Просьба не обсуждать задачи до завтрашнего вечера, когда случится их разбор в Дабромате

Для любителей комбинаторики с числовыми мотивами прекрасная задача с американского отбора на международную олимпиаду.

#17. Пусть даны натуральные числа n>k и простое число p. Предположим, что p делит количество k-элементных подмножеств множества {1, 2, ..., n}. Докажите, что тогда все эти k-элементные подмножества можно разделить на p групп одинакового размера так, чтобы любые два подмножества с одинаковой суммой оказались в одной группе.

Приближается к концу мой первый совместный триместр с Даброматом. Это было огого! Целых три программы по геометрии! Но теперь все немного переформатируется и будет еще круче. Во втором триместре Дабромат запускает несколько полноценных курсов-кружков.

Курс “Эйлер”
Этот курс рассчитан на условных восьмиклассников, которые готовятся к региону/финалу олимпиады Эйлера этого или следующего года. Содержит в себе занятия по всем важным разделам. Занятия будут вести просто супер-преподаватели Александр Кузнецов и Давид Бродский.

Курс “ВсОШ”
Этот курс рассчитан на условных 9-10 классников, готовящихся к региональной олимпиаде или финалу в этом году или в будущем. Каждую неделю участникам будут предложены листочки по Алгебре&ТЧ, Комбинаторике и Геометрии. Будет теоретический материал, отслушка и три разбора. Занятия ведем мы с Давидом Бродским. Он отвечает за алгебру, а я буду заниматься комбинаторикой и геометрией.

Тренировки по геометрии
Из предыдущего курса можно отдельно выделить геометрию — каждую неделю вы решаете, хотите ли порешать листик по геометрии. Получаете задачи, доступ к лекции, проверку ваших письменных решений и доступ к стриму с разбором, который провожу я в субботу. Расписание тренировок и кое-какие материалы я буду постить на канале, чтобы вы уже решали, нужно оно вам или нет. Приблизительную программу тренировок можно найти в программе Курса “ВсОШ”.

Курс “Современная геометрия”
Тут все по прежнему. Геометрическая жесть как она есть от Давида Бродского и немного от меня (я сглаживаю экстремизм коллеги). Тут программа начнется с подготовки к региону и финалу, а потом перейдет в прокач проективной геометрии.

Курс “Перечни”
Подготовка к перечневым олимпиадам. Ее ведет Мирослав Краснов.

По ссылкам вы можете найти программы курсов. Присоединяйтесь! Кажется, у нас получается довольно круто!

Задача с прошедшей только что Китайской национальной олимпиады 2024. Задача предлагалась под номером 6 (самая сложная задача в варианте).

#16. В вершинах правильного 99-угольника расставляются натуральные числа от 1 до 99 (расстановки, отличающиеся поворотом, считаются одинаковыми). За одну операцию разрешается поменять местами два числа, стоящие в соседних вершинах. Найдите наименьшее n такое, что из любой расстановки можно получить любую другую, совершив не более чем n операций.