Будни Джейкоба Константиновича

Можно заходить на встречу 🚀 https://meet.google.com/rbm-wsea-vqw

В целом, C2 из IMO SL23 мне понравилась, хотя это баян на принцип Дирихле и префиксные суммы 🧐 Условие ниже: Дана последовательность натуральных чисел длины m, причём все её члены не превосходят $2^2023$. Если выбрать несколько подряд идущих членов этой последовательности и поставить перед каждым из них плюс или минус, то выражение не будет равно нулю. При каком наибольшем m такое возможно? 🤖 А мы обычно используем в русских листиках такую версию (идея такая же, но без примера): Дана строчка из $25$ цифр. Всегда ли можно расставить в этой строчке знаки арифметических операций $+, -, \cdot, :$ и скобки так, чтобы образовалось числовое выражение, равное 0. Последовательно стоящие цифры можно объединять в числа, но порядок цифр изменять нельзя. 🍼 Для разнообразия можно использовать первую версию, а так по факту шило на мыло 🗿 C1 в листики не особо берётся (идея: диагональная раскраска в 3 цвета), С3 в самом варианте была, её я уже решал. Неплохо было бы еще C4 и C5 пощупать 🥸

Можно заходить на встречу https://meet.google.com/fmp-vjxj-vqo

Как-то раз я увидел в тетради у жены (будущей) задачу "Перед дождем кот всегда чихает. Сегодня он чихнул. Обязательно ли будет дождь?" 🐈 Меня это так позабавило, потому что на тот момент я совершенно забыл, что существуют такие задачи, забыл, что маленьких детей нужно учить кванторам, построению отрицаний и т.д. 🍼 После этого я все легкие задачи для младших школьников называю "кот чихнув" И вот на прошлой неделе на лиге открытий мне предоставилась возможность немного попридумывать задачи формата "кот чихнув" 🤔 Было интересно и необычно, хотя я, скорее всего, просто переизобретал классику. Тем не менее выкладываю несколько придуманных задач 1) После муниципального этапа n человек были награждены дипломами победителя. Мэр города отметил, что среди любых 5 победителей найдётся не менее 1 и не более 5 пар одноклассников. При каком наибольшем n такое возможно?🥇 2) Заяц написал в тетради k-значное натуральное число без нулей в записи. Волк пытался вычеркнуть несколько цифр так, чтобы оставшиеся цифры образовывали 5-значное число, в котором цифры идут в порядке неубывания. Волк перепробовал все способы, но так и не добился желаемого. При каком наибольшем k это возможно?🐇 3) На доске написано число 2024. Волк и Заяц по очереди приписывают несколько цифр к текущему числу справа, начинает Волк. Заяц за каждый ход может приписывать только комбинации "1", "3" или "23", а у Волка ограничений нет. Волк побеждает, если после какого-то хода Зайца на доске оказалось простое число. Может ли Заяц гарантированно не дать Волку победить? 🐇 4) Гриша расставил в клетки таблицы 15 х 15 действительные числа так, что в каждом прямоугольнике 1 х 4 сумма чисел хотя бы 4, а в каждом прямоугольнике 2 х 3 сумма чисел хотя бы 6. Обязательно ли сумма чисел во всем квадрате 15 х 15 хотя бы 225? 🗿 Кстати еще подправил немного закреплённое сообщение, чтобы для новеньких чуть понятнее была концепция канала 🧠

Друзья, следующая встреча будет в четверг 26 сентября в 20:00 мск. Я еще не решал SL IMO 23, хочу порешать, или же на месте уже выберем олимпиаду в зависимости от уровня участников встречи 😤 Если вы придете, то поставьте реакцию: палец вверх 👍 Если хотите попозже присоединиться, то можно написать в комментариях🫡 Если вы НЕ придете, то поставьте реакцию "камень" 🗿

Можно заходить https://meet.google.com/hhe-xjih-bgd

Друзья, следующая встреча будет в субботу 7 сентября в 18:00 мск. Попробуем найти Тургор, который я не решал или хотя бы частично не решал 😤 Если вы придете, то поставьте реакцию: палец вверх 👍 Если хотите попозже присоединиться, то можно написать в комментариях🫡 Если вы НЕ придете, то поставьте реакцию "камень" 🗿

Друзья, есть небольшая задачка на подумать для вас 🧐 Я только вернулся с КомбАлга и там рассказывал про задачу Эрдеша-Шош и её обобщении (см. например, https://clck.ru/3CvnvM) Райгор как раз на днях спрашивал меня про такую же задачу, только в частном случае: Какое наименьшее количество различных 6-элементных подмножеств 16-элементного множества можно выбрать так, чтобы у любых двух выбранных подмножеств пересечение не имело мощность 2 и 3? Если 16 заменить на n, то для достаточно больших n такая задача изучена, а вот для маленьких значений результатов особо нет 🫡 Сверху есть линейно-алгебраическая оценка на C_{16}^2=120, но она вряд ли достижима. Но над оценкой, мне кажется, думать не стоит, какого-то красивого способа я не вижу 🗿 Если бы все попарные пересечения имели бы мощность хотя бы 4, то ответ известен - это C_{12}^2=66 по теореме Ahlswede–Khachatrian (см. https://clck.ru/3Cvpe4) Вопрос состоял в том, есть ли пример с более 66 множествами? Я немного подумал, нашел пример на 89 множеств. Может ли кто-то найти пример лучше? 😎 На всякий случай прикладываю свой пример под "замазкой" Сначала разобьём элементы на две группы: $X_1 = \{1,2,..,6\}$ и $X_2 = \{7,8,...,16 \}$. В первую группу множеств возьмём все множества, которые имеет 5 элементов в $X_1$ и 1 элемент в $X_2$. Таких множеств $C_6^5 \cdot 10 = 60$, сюда же еще возьмём само $X_1$. Пока набрали 61 множество, между собой они имеют хотя бы 4 общих внутри $X_1$. Вторую группу множеств будем набирать только из элементов $X_2$, тогда каждое из них будет иметь максимум 1 общий элемент с любым множеством из первой группы. Поэтому нам важны только их пересечения между собой. Пока получаем $$m(16,6,\{2,3\}) \geqslant 61 + m(10,6,\{2,3\}).$$ Элементов $X_2$ уже поменьше, там по Алсведе-Хачатряну выгоднее будет выделить какие-то 8 элементов и составить все возможные шестерки из них. Это дает нам еще $C_8^6=28$ множеств, любые два из них имеют хотя бы 4 общих. У нас уже набралось $61+28=89$ множеств.

Друзья, сегодня мой последний день в Тайланде 🌴 Грустно возвращаться в Москву (Реутов) 😥 Но зато уже очень хочется работать и полноценно заниматься математикой 🥸 Я полностью заряжен и готов к новому учебному году 😎 Оставляю фото и видео беззаботного и счастливого Джейкоба 🤙🏽 🏄‍♂️

🗿 + 😎

Друзья, я балбес... 🗿 Задача из прошлого поста это просто решение системы линейных уравнений (спасибо за комментарий) За x_i мы обозначим индикатор взятия вершины в наше выбранное множество (1 - если взяли, 0 - если не берём). Если просуммировать x_i для всех смежных вершин и для самой себя, то у каждой вершины должно получиться 1 по модулю 2. Получаем СЛУ над Z/2Z, количество решений такой системы равно нулю или степени двойки (для каждой свободной переменной 2 варианта), 99 быть не может 😤 Если же матрицу смежности обозначать за A, то мы просто решаем систему уравнений (A+E)(x_i)=(1)🤓 В любом случае нужно просто показать, что количество способов соответствует количеству векторов в каком-то линейном подпространстве (Z/2Z)^n, где n - количество вершин 🧐 Ну и ну... Красиво, возьму на заметку себе✍️ Интересно, а пупсяры на Уртюме решили её?? 🍼