Граф по понедельникам

61-й Уральский турнир Юных математиков. Второй тур, высшая старшая лига. (Romanian TST 2 2008, Problem 4)

#8. В связном графе с n вершинами каждое ребро содержится хотя бы в одном треугольнике. Найдите наименьшее возможное количество рёбер в этом графе.

#граф

Не знаю, почему на задачу #7 была такая реакция. Мне эта задача кажется довольно прикольной, потому что опирается на факт, который появляется обычно в младшеклассных кружках.

Дело в том, что прямоугольник 5×9 можно разрезать на уголки из трех клеток. А для того, чтобы произвести разрезание квадрата на равные шестиугольники можно взять указанное разрезание прямоугольника 5×9 и растянуть его по вертикали в 9/5 раза.

Комби числа с Венгерской олимпиады 1952-го года

#9. Из целых чисел от 1 до 3n выбрали n+2 каких-то чисел. Доказать, что при n>1 среди выбранных чисел непременно найдутся два таких, разность между которыми больше n, но меньше 2n.

При n = 60 авторы предлагают следующую переформулировку.

Библиотека открывается в 12 часов дня и закрывается в 15 часов. Входит в библиотеку разрешается с интервалом в одну минуту. Первый читатель может войти в библиотеку ровно в 12:00, последний — в 14:59. Входить в библиотеку читателям разрешается только по одному. Через час после прихода в библиотеку читатель засыпает над книгами и спит ровно час, если только закрытие библиотеки не прервет его сон. Входить в библиотеку, когда кто-нибудь из читателей спит, воспрещается. Доказать, что при столь странных правилах 62 человека не смогут побывать в библиотеке за один день.

#комбичисла

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

Задача не очень хитрая.
UPD: Не очень верное решение ниже)

Надо воспользоваться как-то связностью, которая явно в задаче по делу. Сразу приходит идея выделить остовное дерево, поскольку это дает какую-то тривиальную оценку снизу на количество ребер. В нем как минимум n-1 ребро, при этом никакие три из них не образуют треугольник. Тогда легко видеть, что есть еще как минимум [n/2] дополнительных ребер.

Для нечетного n пример приведен на рисунке. Для четного требуется легкая модификация.

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

В этой задаче более-менее сразу понятно, что все комнаты обойти нельзя (например, нельзя попасть во все угловые). Но как понять, какое наибольшее число комнат можно посетить? Доказательство таких утверждений состоит обычно из двух частей: оценка и пример. В большинстве задач такого типа пример построить довольно легко, а вот оценка требует изобретательности!

В данной задаче работает метод раскраски. Надо покрасить залы в шахматном порядке (зелёный и белый цвета на рисунке). Перемещаясь из зала в зал, мы обязательно меняем цвет. Белых залов всего 10, и цвета мы должны чередовать. Учитывая, что стартовать и финишировать мы можем в зелёных залах, можно рассчитывать на посещение максимум 10+11=21 зала. Пример с маршрутом по 21 залу — на рисунке.

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

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  почти равномерная закраска существует и что она единственна с точностью до поворотов закрашенного множества.