Клеточки и разрезания по пятницам

61-й Уральский турнир Юных математиков. Финал, старшая высшая лига, бои за 1-4 места. USA TSTST 2023

#10. Дано натуральное n. Докажите, что можно закрасить некоторые клетки бесконечной клетчатой плоскости в зелёный цвет так, чтобы любой прямоугольник из n клеток содержал нечётное число зелёных клеток.

#клеточки

Разбираем задачу #9

Во-первых, не умаляя общности можно считать, что в наборе есть число 3n (иначе можно добавить ко всем числам одно и то же). Во-вторых, это означает, что чисел от n+1 до 2n-1 в наборе нет — они все образовывали бы с 3n искомую пару. Остальные числа разобьем на пары

(1, 2n), (2,2n+1), ..., (n, 3n-1)

— все эти пары удовлетворяют условию и в какой-то паре по принципу Дирихле выбраны оба числа.

Автор говорит, что вышла вот такая книжка. Думаю, хорошая...

Ссылка на инфу

Хоть сегодня и понедельник, но будет не граф, а задача про множества, но по духу похожая на граф.

61-й Уральский турник Юных математиков. Финал. Высшая старшая лига. Бои за 1-4 места.

#11. В каждом зоопарке обитает ровно 100 видов животных. Зоопарки бывают двух типов: с вайфаем и без вайфая. Для любой пары зоопарков разного типа есть вид животных, который содержится в обоих зоопарках. Докажите, что все виды животных можно разделить на три непересекающихся списка так, чтобы в каждом зоопарке обитали животные не менее чем из двух списков.

#множества

Разбираем задачу #10

Легко заметить, что если пример построен для какого-то n, то он годится для np, где p — нечетное простое число. Поэтому достаточно строить пример для степеней двойки. Поэтому пусть n=2^k. Далее считаем, что в зеленых клетках стоят единички, а в белых — нули.

Не знаю, как младшеклассники должны строить пример для степени двойки, но я знаю такой метод. Надо для каждого m<k расставить единички так, чтобы в каждом прямоугольнике 2^m×2^(k-m) стояло нечетное число единиц, а в прямоугольники любой другой формы и той же площадью — четное. А затем сложить все такие раскраски по модулю 2.

Искомая раскраска для 2^m×2^(k-m) строится так: надо поставить единичку в клетку, если координата по y делится на 2^m, а координата по x делится на 2^(k-m).

В целом, сумму таких раскрасок, наверное, можно записать явно для каждой клетки...

61-ый Уральский турнир юных математиков, третий тур

#12. Два кальмара вынуждены участвовать в игре. Перед началом игры они узнают правила и договариваются о своих действиях. Затем они будут заперты в соседних комнатах, и каждому будет выдана карточка, на которой написано натуральное число. Известно, что числа на карточках различны и не превышают 2023. Далее кальмары по очереди делают ходы. За ход можно сделать одно из двух действий:
1) Очень громко назвать любое натуральное число. Это число будет услышано другим кальмаром.
2) Сказать, у кого из кальмаров на карточке большее число.

Если во втором случае ответ верен, то кальмаров отпускают, иначе — жарят. Найдите наименьшее натуральное N, при котором кальмары могут спастись (вне зависимости от того, какие у них карточки), и при этом сумма чисел, названных кальмарами, не превысит N.

#алгоритмы

Всем привет! Сегодня мы поговорим с вами о задача, которая известна как "лемма о бензоколонках" (или Raney's lemma). Лемму эту опубликовал George Raney в 1960 году в журнале Transactions of the American Mathematical Society.

В России это утверждение больше известно благодаря публикации в задачнике журнала "Квант" в 1971 году под номером М82. Автором задачи указан читатель С. Охитин из Оренбурга.

Формулировка задачи такая

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

Ее несложно переформулировать с следующем более математическом виде (упражнение)

Даны числа x_1, x_2, ..., x_n с нулевой суммой. Тогда существует циклическая перестановка, для которой все частичные суммы неотрицательны. То есть существует такое k, что x_k⩾0, x_k+x_{k+1}⩾0, x_k+x_{k+1}+x_{k+2}⩾0,... x_k+x_{k+1}+...x_{k-1}⩾0.

Одно из наиболее классических и простых доказательств этого утверждение проводится при помощи индукции. Если машина одна, то в ней достаточно бензина на полный круг. Пусть у нас есть n машин, то можно найти 2 соседние, такие, что из первой можно доехать до второй по часовой стрелке. Уберем вторую и отдадим весь ее бензин первой. По предположению индукции, среди оставшихся n-1 существует одна, из которой можно проехать полный круг по часовой стрелке — она же подойдет и для n в исходной конфигурации.

Однако совсем недавно благодаря каналу Феди П я узнал прекрасное доказательство (которое он в свою очередь узнал от Таи Коротченко) с выпукло-геометрическими мотивами.

Рассмотрим n векторов, полученных из (1,-1,0,0,..,0) циклическими перестановками. Они все лежат в (n-1)-мерной гиперплоскости (сумма координат равна нулю) и являются вершинами симплекса, содержащего начало координат (центр его масс). Луч из начала координат в точку (x_1,...,x_n) пересекает некоторую грань этого симплекса. Сделаем циклическую перестановку так, чтобы эта грань не содержала вершину (-1,0,0,...,0,1). Но все точки (y_1,...,y_n) в этой грани имеют неотрицательные частичные суммы координат, поскольку этим свойством обладают все вершины этой грани, а значит и все выпуклые комбинации.

классическое применение леммы Рени — формула для чисел Каталана:

пути Дика можно отождествить с последовательностями из n+1 числа +1 и n чисел -1, все частичные суммы которых положительны — а по лемме Рени последнее условие выделяет 1/(2n+1) часть от всех \binom{2n+1}{n+1} последовательностей (для каждой последовательности подойдет ровно один циклический сдвиг)

про последовательности ±1, частичные суммы и циклические перестановки есть также статья Эрдеша и Капланского 1946 года — https://old.renyi.hu/~p_erdos/1946-09.pdf — но там немного другое утверждение и уж совсем другое доказательство (но тоже, кстати, поучительное)

Ссылка на канал Феди П, так что-то не очень работала

К. Кноп меня тут научил, что треугольник Серпинского связан с ханойской башней. А именно, возможные конфигурации n колец можно сопоставить маленьким треугольникам на салфетке "порядка n" (после n раундов выкидывания).

При этом конфигурациям, отличающимся на один разрешённый ход, соответствуют соседние треугольники. Полностью собранным на одном из стержней кольцам — маленькие треугольники в самых вершинах исходного. А знание положений k самых больших колец определяет, в каком треугольнике ранга k (получающегося после k раундов выкидывания) содержится отвечающий данной позиции самый маленький.

Построить можно по индукции — построив для (n-1) кольца и состыковав [правильно повернув] три таких (отвечающих возможным положениям последнего кольца) нужным образом: треугольники "последнее кольцо на вершине А" и "последнее кольцо на вершине B" должны стыковаться по тем вершинам, где все кольца, кроме последнего, собраны в вершине C.

Задача от лауреата филдсовской премии Максима Концевича. Задача когда-то очень давно предлагалась на сложном туре Турнира городов. Как вы думаете сколько баллов она стоила?

#15. k вершин правильного n-угольника закрашены. Закраска называется почти равномерной, если для любого натурального m верно следующее условие: если M₁ – множество m расположенных подряд вершин и M₂ – другое такое множество, то количество закрашенных вершин в M₁ отличается от количества закрашенных вершин в M₂ не больше чем на 1. Доказать, что для любых натуральных n и  k ≤ n  почти равномерная закраска существует и что она единственна с точностью до поворотов закрашенного множества.

Задача с прошедшей только что Китайской национальной олимпиады 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. Условия и разбор первого тренировочного варианта можно посмотреть тут, второго — тут, а третьего — тут.