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

Друзья, на крайней встрече мы не смогли дорешать следующую задачу 😐 Дан граф. Вова хочет записать в каждую вершину целое число так, что бы для любой вершины число, записанное в ней, было равно количеству соседних с ней вершин, в которых записано четное число. Вова нашел уже 99 способов записать так числа. Обязательно ли он может найти ещё хотя бы один? То есть речь идет о количестве способов выделить множество вершин так, чтобы все внутренние степени были чётными, а от всех других вершин к выделенным шло нечётное кол-во рёбер 🤔 В нечётности числа 99 противоречия, конечно, нет, ведь количество способов может быть равно 1. Однако, кажется, что другие нечётные значения искомая величина принимать не может (не уверен). Для всяких полных графов, циклов, цепочек, звёздочек эта гипотеза подтверждается 😅 Если решите, то присылайте свое решение в комментарии в формате спойлер 😎

Математическое ожидание, заходите https://us06web.zoom.us/j/87689115427?pwd=ywIn3CCqOb23NMbUwkWS8as4aL7TwA.1

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

Друзья, у меня прошла свадьба 💒 Всем, кто приезжал в Калининград на это мероприятие, большое спасибо 🙏 Понемногу можно возвращаться к науке и прорешиванию олимпиад 🥸 Уже скоро назначу время следующей встречи

Друзья, все-таки загадка имела не совсем корректное условие 🗿 В известной задаче о 7 кёнигсбергских мостах меня смущало, что с точки зрения теории графов ни одно из 7 рёбер не являлось "мостом" (мост - это ребро, при удалении которого, в графе увеличивается кол-во компонент связности)🧐 А сегодня я увидел, что оставшийся ме(и)довый мост, действительно, является мостом, потому что соединён с висячей вершиной (островом Канта) 🥸 Однако, на самом деле, на остров Канта можно спуститься и по лестницам, то есть связность не теряется (я эти лестницы за рёбра вообще не считал) 🙏 Извиняюсь за небольшую шизню😐

Поздравляю всех с днём камня 🗿🪨

Друзья, на прошлой встрече мы решили P1 с нового IMO, она была не очень интересная, довольно простая алгебра на возню с целыми частями 🗿 Сегодня еще дорешал P5 на "слепые алгоритмы". В целом, она мне понравилась, потому что ответ не сразу очевиден 🧐 Советую её посмотреть! P4 (геометрия), ее решать не буду. А из оставшихся трёх задач есть что-то зажигательное?? 🧨

Можно заходить https://us06web.zoom.us/j/89336836595?pwd=Ra74C62XT1HPM5apQqbvDcW677JwFd.1

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

Друзья, попалась еще одна интересная задача со старого Уртюма, которую можно обсудить и я хочу поделиться с вами своими мыслями по ней 🧨. Условие ниже На вечеринку пришло 19 друзей, прочем среди любых троих из них есть двое знакомых. Докажите, что гости могут разбиться на 5 групп, в каждой из которых все попарно знакомы. 1) Если не особо париться, то можно просто попробовать выделять максимальные клики по очереди и выкидывать их из графа. Звучит это удобно, ведь можно просто на каждом шаге сравнивать число вершин с соответствующим числом Рамсея. Например, R(3,6)=18, поэтому в начале у нас точно есть клика размера 6, выкидываем её. Далее 13 > R(3,4), выкидываем 4-клику. Но нетрудно видеть, что по такому алгоритму мы сможем гарантировать себе только 6 клик (6, 4, 4, 2, 2, 1). Таким образом, приходим к идее, что можно в начале пару раз выкинуть максимальную клику, а потом уже разобраться с графом, в котором гораздо меньше вершин. Например, после двух операций у нас остаётся 9 вершин, из них нужно выделить 3 клики (это утверждение верно, его можно доказать). Но давайте взглянем чуть глубже 🤓 2) Лучше сформулировать утверждение для антиграфа: такой граф не содержит треугольников и нужно покрасить его правильным образом в 5 цветов. Тут сразу стоит заметить, что в исходной задаче дан огромный запас, его можно покрасить даже в 4 цвета. На самом деле, доказано, что граф без треугольников с хром. числом 6 имеет хотя бы 32 вершины (см. https://arxiv.org/pdf/1707.07581). На это утверждение, конечно же, мы ссылать в нашем решении не будем 🗿 Более доброе и более известное утверждение состоит в том, что минимальный по количеству вершин граф без треугольников с хром. числом 4 - это граф Грёча (можно посмотреть на вики), минимальность доказал Хватал в 1974 году. Это утверждение можно использовать в нашем первой идее после двух выкидываний (у нас 9 вершин осталось, значит трёх цветов точно хватит). Но все-таки попробуем это утверждение тоже не использовать 👌 3) При раскраске графа полезно смотреть на максимальную степень, особенно в нашем случае. Если степени в графе небольшие, то граф красится жадно или по теореме Брукса. Если же есть большая степень, то из-за отсутствия треугольников, мы имеем большую антиклику, состоящую из её соседок. Попробуем применить для нашего антиграфа. Если все степени не больше 5, то красим в 5 цветов по теореме Брукса. Если есть степень хотя бы 6, то находим антиклику мощности 6, красим её в отдельный цвет и выкидываем, продолжаем делать тоже самое. Первый шаг получился не лучше, чем в первой идее 🧐 А вот на втором шаге мы выкинем уже целых 5 вершин (а не 4, как в первой идее), то есть остаётся 8 вершин и 3 цвета. Повторяем еще раз и получаем 4 вершины и 2 цвета, граф без треугольников на 4 вершинах, очевидно, двудольный, мы победили 👍 4) Думаю, что можно еще разведать эту экстремальную задачу и собрать материала на лекцию, подумаю над этим 🤖 С другой стороны, задача то детская и должно быть совсем простое решение (раз такой огромный запас дали), какое оно (вопрос к знатокам)? 😩

Друзья, что-то я туплю, постараюсь в ближайшее время дорешать задачу с сегодняшней встречи 😅 Можете тоже попробовать, условие ниже 😐 Дан связный граф на 2009 вершинах. Докажите, что в нем можно выделить 2008 ребер и расставить на них стрелки так, чтобы для любых двух вершин, соединенных ребром в исходном графе, из одной из них в другую можно было пройти по стрелкам.

Пока начинаю решать, можно заходить в любой момент https://us06web.zoom.us/j/84553316638?pwd=x3S3rxbMCL3ZkeSuqpxY96Dpfx2ous.1

Друзья, следующая встреча будет завтра 13 июля в 12:00. Скорее всего, продолжим решать графы с уртюма, но в какой-то момент можем переключиться на APMO 🥸 Если вы придете, то поставьте реакцию: палец вверх 👍 Если хотите попозже присоединиться, то можно написать в комментариях🫡 Если вы НЕ придете, то поставьте реакцию "камень" 🗿

Хмм можно 2-3 дня отдыха от математики занять возвращением законных 6 (4) тысяч баллов рейтинга в доте 🫡