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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как знают многие подписчики нашего канала, мы занимаемся не только составлением тренировочных региональных олимпиад, но также ведём регулярные онлайн-кружки по олимпиадной математике для учеников с 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 класса занятия по геометрии ведёт автор канала «Олимпиадная геометрия» Бахарев Фёдор Львович.

Всем привет!

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

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

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


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

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

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

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

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

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

Давайте я напишу пару слов про задачу 11-6 с сегодняшней ММО:

Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты — до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну — из шести нот, …, одну — из 30 нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?

Понятно, что вместо мелодий можно говорить про слова из двух символов — например (чтобы не говорить « до » и « си »), из 0 и 1.

Для начала — а что, если Кощей начинает запрещать не с длины 5, а с длины 3? Оказывается, что тогда он может выиграть!

Действительно: пусть он сначала запретит слово 001. Тогда за двумя нулями может идти только третий — и значит, только последовательность из одних нулей. Так что пара запретов 001 + 000000000000 практически равносильна запрету просто на два нуля. (Практически — потому что если мы говорим о словах конечной длины, то там незадолго до конца написать короткий хвост из нулей будет можно, но 300 это достаточно большая длина, чтобы всё закончилось до того.)

Итак, два нуля запрещены, значит, за каждым нулём следует единица. Отлично!

Теперь Кощей запрещает 1101. Поскольку за нулём должна следовать единица — это более-менее то же самое, что запретить просто 110. И поэтому за двумя единицами будет следовать третья — так что, добавив к этому запрету 1111111111, Кощей добивается того, что и две единицы подряд запрещены.

За 0 следует 1, за 1 следует 0, теперь Кощей запрещает 01010 — и испытание становится непроходимым.
(Кстати, последовательности из 0 и 1 выше можно сократить до длин 6 и 7 соответственно — там они длинные, чтобы показать, что в этом месте можно обойтись и очень длинным запретом.)

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

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

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

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

#мтразминка

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

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

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

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

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

#мтразминка

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

Всем привет! Как вы знаете я немного связан с образовательной программой от 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!

Прочитал про теорему Дена о разрезании: если прямоугольник можно разрезать на квадраты, то отношение его сторон рационально. Интуитивно это кажется логичным, но доказать не так уж и просто. Обратное утверждение тривиально: если отношение сторон рационально и скажем равно 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", где дается много доказательство похожего, но другого по сути утверждения: что если прямоугольник разрезан на прямоугольники и у каждого внутренного прямоугольника хотя бы одна из сторон - целое число, то и у всего прямоугольника тоже хотя бы одна из сторон целая.

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