Mathreshka – Telegram
Mathreshka
3.39K subscribers
3 photos
1 file
172 links
Математика. Задачи с собеседований и олимпиад.

Авторский канал выпускников мехмата, кандидатов наук, чьё хобби – ходить по собеседованиям.

Для связи: @clean_horizon
Download Telegram
Задача с красивым ответом

Сегодняшняя задача появлялась на собеседованиях в разных компаниях (например, #Palantir, инфо с Glassdoor) примерно с 2010 года. Недавно её предложили моему другу на #интервью в #Сбербанк. Хотя больше она подходит для Почты России.

А ещё в этой задаче красивый ответ. Я бы даже сказал, гармоничный.

50 байкеров (#105)
Кони Гугла

Говорят, что эта задачка стала известной, так как её справшивают на #интервью в #Google. На мой взгляд, очень остроумный пример задачи нахождения k-й порядковой статистики.

Кстати, в #Yandex тоже есть кони.

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

Кони (#106)
Задача о дилижансе. Облегчённая версия

Лёгкое прикосновение к разделу теории графов о кратчайших путях.

Задача кратчайшего пути – задача поиска пути между двумя вершинами на графе, минимизирующего сумму весов рёбер, его составляющих.

Сложность решения, конечно, зависит от того, что нам известно про граф. В общем случае для решения пользуются специальными алгоритмами. В нашей задаче есть изначальные сведения о графе, и требуется только доказать оценку сверху на длину кратчайшего пути.

#олимпиады #графы

На перекладных (#107)
Задача брадобрея

Это бородатая задача, но я хочу рассказать о ней здесь по двум причинам.

Во-первых, мне её предложили на #интервью в компании #Совкомфлот, а значит могут предложить и вам. В нашей компании это стало устойчивой фразой: прежде чем браться за любую задачу, проверьте, не решаете ли вы задачу брадобрея.

Во-вторых, это антиномия, то есть рассуждение, которое содержит внутреннее противоречие. Например, может ли всемогущий бог создать камень, который не сможет поднять? Всё это вариации парадокса Рассела – рассуждения, показавшего противоречивость наивной теории множеств.

Ранее мы уже говорили про классификацию феноменов, которые часто объединяют под словом #парадокс. Там же рассмотрена задача о днях рождений – парадокс другого типа.

Присылайте ваши любимые парадоксы. Самый интересный – в ленту.

Брадобрей (#108)
👍1
Международная олимпиада

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

Международная математическая олимпиада (MMO) – это Чемпионат мира по математике среди школьников старших классов, проводящийся каждый год в одной из стран. Первая MMO прошла в 1959 году в Румынии с участием семи стран. В последние годы в ММО участвуют более 100 стран с 5 континентов.

Я на международные этапы не отбирался, но если у вас есть такой опыт – отмечайтесь 👨‍🎓 внизу и делитесь впечатлениями в личку!

Чехарда (#109)
Авторские задачи

В начале «Снежной королевы» злые тролли смастерили странное зеркало, которое всё искажало. Набаловавшись на земле, они решили поглумиться и над небом. Чем выше тролли поднимались, тем сильнее зеркало кривлялось, и в какой-то момент оно выскользнуло у них из рук и разбилось на мелкие осколки. В зависимости от того, куда попадал осколок, он начинал проявлять себя по-разному. Дальше – больше, но интереснее Ганса Христиана Андерсена нам всё равно не рассказать, поэтому перечитайте сказку сами – не пожалеете!

Для нас же важно, что если абстрагироваться и принять зеркало за плоскость, осколки – за треугольники, квадраты или шестиугольники, то мы получим головоломку, которая имеет неожиданную связь с прошлым постом. На Международной олимпиаде российская сборная выступает под руководством Назара Хангельдыевича Агаханова, выпускника мехмата МГУ, ныне доцента МФТИ. Он и придумал сегодняшнюю задачу, которая предлагалась уже на Всеросе. Мы её лишь слегка дополнили.

А вообще авторов прекрасных задач великое множество. Хорошая коллекция собрана здесь.

#олимпиады

Правильные клетки (#110)
Геометрия на решётке для гриля

Рассмотрим важный класс геометрических задач, своего рода «целочисленную геометрию». Объекты на целочисленных решётках изучаются даже в теории вероятностей. Например, случайные блуждания с их разносторонними практическими применениями.

Целочисленной решёткой Z² называется множество точек декартовой плоскости с целыми координатами. Бывает удобным представлять себе целочисленную решётку как бесконечный лист клетчатой бумаги. Многоугольник считается расположенным на Z², если все его вершины являются точками (узлами) этой решётки.

Площадь S многоугольника, расположенного на решётке, считается по простой формуле S=I+E/2-1, где I – количество узлов строго внутри многоугольника, E – на его границе, включая вершины. Эта формула названа в честь австрийского математика Георга Пика, доказавшего её в 1899 году.

Для доказательства формулы Пика во всей её полноте, придётся иметь дело с так называемыми примитивными треугольниками. Будем есть слона по частям или, как сказал бы Боб Дилан: «I can’t eat all that stuff in a single bite». Примитивные треугольники сравнимы с глыбами, которые каменотёс обрабатывает лишь тремя ударами резца, создавая тем самым заготовки для более изысканных произведений искусства.

#олимпиады #геометрия

Примитивные треугольники (#111)
Ним

– Я знаю одну игру, в которой всегда выигрываю.
– Если вы не можете проиграть, это не игра.
– Я могу проиграть, но я всегда выигрываю.

В прошлом году в Мариенбаде

Логичным продолжением игр Баше, рассмотренных в постах Ёлочные игрушки (#18) и Ёлочные игрушки возвращаются (#17), является конечная игра с полной информацией ним.

Поклонникам арт-хауса рекомендуется к просмотру фильм В прошлом году в Мариенбаде, где игра занимает центральную часть сюжета. Здесь мы разбираем вариант стандартного условия выигрыша, когда победителем считается взявший последний предмет. В фильме играют в мизер, другими словами, когда взявший последнее является проигравшим. С точки зрения выигрышной стратегии мизер слегка сложнее, но имеет много общего со стандартным вариантом игры.

#игра #математикавискусстве

Игра Ним (#112)
©

Давно ли вы катались на канатных дорогах? В этом году мне выдалось путешествие по городам Поволжья. Поэтому могу отрекомендовать канатку в Нижнем Новгороде / «на Бору» (местные так поправили). Отменные виды по-над Волгой.

Короче, недавно писали про авторские задачи. Лет десять назад я тоже придумал одну. Как говорится, не судите строго.

Итак, эксклюзив для подписчиков.

Кстати, если у вас есть свои задачки – присылайте, самые крутые обязательно запостим со всеми причитающимися почестями автору.

Канатка (#113)
Леммы с красивым названием

В математике есть много утверждений с забавными названиями. Мой фаворит – это теорема о причёсывании ежа. Ещё есть такая лемма в теории графов, которая формулируется на языке рукопожатий: в любом коллективе число людей, совершивших нечётное число рукопожатий, чётно. Как ни странно, но доказательство леммы о рукопожатиях элементарно, хотя название-то какое!

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

#графы

Страна Оз. Дороги (#114)
IMO 2020

На прошлой неделе завершилась Международная Математическая Oлимпиада. Поздравляем наших ребят со вторым местом в неофициальном командном зачёте!

1. 🇨🇳 (215)
2. 🇷🇺 (185)
3. 🇺🇸 (183)

Подробная статистика.

Задачки прилагаются. Регламент: по 4,5 часа на три задачи.
👍2
Как (не)правильно постить

Сразу отмечу следующее, хотя, наверное, и так уже понятно, но всё же, чтобы полностью снять экивоки. Большинство популярных контент-платформ (youtube, instagram) имеют рекомендательную ленту. Чтобы в неё попасть и там оставаться, нужно постить регулярно (= ежедневно). В телеграме другие механизмы продвижения и доставки контента (пока), поэтому писать можно как хочется, и ничего за это не будет. Конечно, пользователь сам может отписаться в любой момент, но алгоритмической дискриминации за нерегулярность не происходит. Чем я и пользуюсь. Другими словами, я объявляю все публикации НЕРЕГУЛЯРНЫМИ (это очень удобно 🙂), чтобы корректно управлять ожиданиями своей аудитории. Но не менее торжественно уточняю, что канал ЖИВ. А всем, кто с нами, огромное СПАСИБО!

Теперь продолжим математическую повестку с геометрии на клетчатой доске. В этот раз в «диагональном» варианте.

#олимпиады

Угловые соседи (#115)
Год в условии задачи

Интересной традицией для авторов олимпиадных задач является использование года проведения в условии. Чаще всего год можно заменить на произвольное n и решать задачу в общем виде. Иногда это условно общий случай, например, если используется делимость года на некоторое число.

Сегодня предлагаем задачу Московской олимпиады 1994 года для 8 класса. Если заменить в формулировке год на текущий, то получится очень простой случай. Поэтому мы оставили оригинальное условие и дополнительно предлагаем вам решить задачу в общем случае.

#олимпиады #игра

Игра в квадраты (#116)
1
Конструктивные и неконструктивные доказательства

Доказательства существования чего-либо (например, системы наименования улиц, или раскраски, как в сегодняшней задаче) бывают конструктивными и неконструктивными.

В первом случае объект, существование которого доказывается, предъявляется в явном виде.

В последнем случае лишь доказывается, что «суслик есть», хоть мы его и не видим. Например, так работает принцип Дирихле.

В решении приводятся оба варианта доказательства. Однако понятно, что с практической точки зрения ценнее конструктивный вариант.

#олимпиады #графы

Цветочный город (#117)
Математика выборов

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

Виталий Иванов, политолог

Наиболее интересной с точки зрения статистики информацией о выборах являются распределение голосов и явка. Сегодняшняя задача касается проблемы увеличения явки, хотя с практической точки зрения, конечно, бесполезна.

Вообще, логично предположить, что чем выше явка, тем справедливее должны быть выборы, так как учитывается мнение большего количества людей (закон больших чисел). Про это ещё будет ВОПРОС.

#олимпиады #выборы

Умное голосование (#119)
ВОПРОС. Как по вашему, если в реальности статистика показывает высокую явку по определённым ТИКам (территориальным избиркомам), это скорее означает, что в этих ТИКах результаты выборов окажутся справедливее, чем в ТИКах с меньшей явкой, или наоборот?
Final Results
22%
справедливее
50%
наоборот
28%
нажми меня
Марабу

Когда я был школьником, были так называемые заочные школы, например, физтеховская ЗФТШ. Организовано было так: по почте (не электронной) участникам рассылались условия задач по физике и математике. Ученик их решал и оформлял в отдельной чистой тетрадке, которую затем отправлял обратно к определённому сроку. Учитель оставлял рецензию в той самой тетрадке и направлял почтой ученику. И так далее несколько раз.

Сейчас всё намного удобнее и эффективнее. Большая Математическая Игра от создателей «Умного лагеря Марабу» — это одновременно маткружок, онлайн-игра и коммьюнити с общим взглядом на мир и общим интересом к предмету. Где бы вы ни находились, вы (если вам от 10 до 14) или ваш ребёнок может присоединиться к игре — в неё играют дети из разных стран и школ.

https://bit.ly/39wa269

Для нового сезона организаторы сильно прокачали игру со всех сторон. Теперь БМИ — это ещё больше задач, новый дизайн, двухуровневый детализированный сюжет и расширенные возможности для командной игры. А также — индивидуальный подбор сложности задач и скорости прохождения, дорожная карта и командный чат (со второго месяца игры). Начало уже в октябре!

Пример реальной игровой задачи в сегодняшнем посте.

Первый месяц бесплатно!

#тервер

Кот и робот (#120)
👍4