3536
Математика. Задачи с собеседований и олимпиад. Авторский канал выпускника мехмата, кандидата наук, чьё хобби – ходить по собеседованиям. Для связи: @clean_horizon
Best guess
Достаточно эффективный метод решения зачастую – это угадывание / нахождение правильного ответа, а затем его обоснование. Сегодняшняя задача про свечи перекликается с популярной в своё время на собеседованиях задачей про фитили, однако имеет другую идею решения.
#олимпиады
• Игра не стоит свеч (#124)
• Решение
С Новым годом 2022 🌟
Друзья, поздравляем вас с наступающими праздниками.
Наш канал на данный момент – это хобби четырёх людей: двух математиков и двух иллюстраторов. Мы ведём Матрешку потому, что нам это нравится, и потому, что это нравится не только нам. Мы уделяем большое внимание и содержанию, и форме. А на качественное оформление нужно время. Нам бы очень хотелось постить чаще, например, раз неделю, как было бы интересно большинству подписчиков, но пока этого не получается. Поэтому вам – СПАСИБО за то, что с нами.
И пусть у вас в Новом году хорошего времени будет намного больше, чем плохого.
#олимпиады
Придворный астролог (#122)
Парадокс раздела ставки
Почувствуйте себя основателями теории вероятностей Паскалем и Ферма абсолютно БЕЗВОЗМЕЗДНО.
Экскурс. В некотором смысле теория вероятностей как наука зародилась с решения этой задачи. Сама задача впервые была опубликована Лукой Пачоли в 1494 г. (итальянский математик, который в том числе ввёл принцип двойной записи (актив / пассив) для учёта, положив основу современной бухгалтерии). Сам он дал неверное решение этой задачи. Ошибся и Николла Тарталья (открывший формулу корней кубического уравнения). Правильный ответ независимо друг от друга дали Блез Паскаль и Пьер Ферма в 1654 г. (то есть спустя 160 лет).
В добавление замечу, что современная теория вероятностей как строгая математическая дисциплина оформилась с введением аксиоматики Андреем Николаевичем Колмогоровым в 1929 г.
Парадокс здесь коннотируется как контринтуитивное утверждение. О типах парадоксов было рассказано здесь.
#тервер #парадокс
Источник: Габор Секей – Парадоксы в теории вероятностей и математической статистике (1990)
Марабу
Когда я был школьником, были так называемые заочные школы, например, физтеховская ЗФТШ. Организовано было так: по почте (не электронной) участникам рассылались условия задач по физике и математике. Ученик их решал и оформлял в отдельной чистой тетрадке, которую затем отправлял обратно к определённому сроку. Учитель оставлял рецензию в той самой тетрадке и направлял почтой ученику. И так далее несколько раз.
Сейчас всё намного удобнее и эффективнее. Большая Математическая Игра от создателей «Умного лагеря Марабу» — это одновременно маткружок, онлайн-игра и коммьюнити с общим взглядом на мир и общим интересом к предмету. Где бы вы ни находились, вы (если вам от 10 до 14) или ваш ребёнок может присоединиться к игре — в неё играют дети из разных стран и школ.
https://bit.ly/39wa269
Для нового сезона организаторы сильно прокачали игру со всех сторон. Теперь БМИ — это ещё больше задач, новый дизайн, двухуровневый детализированный сюжет и расширенные возможности для командной игры. А также — индивидуальный подбор сложности задач и скорости прохождения, дорожная карта и командный чат (со второго месяца игры). Начало уже в октябре!
Пример реальной игровой задачи в сегодняшнем посте.
Первый месяц бесплатно!
#тервер
Кот и робот (#120)
Математика выборов
Не надо математикам со своими моделями лезть в политику, анализировать выборы, придумывать какие-то свои версии. Это просто смешно, когда математик рассуждает о выборах. Давайте еще биолога спросим! Или узнаем, что по поводу результатов выборов думает физик-ядерщик!
Виталий Иванов, политолог
Наиболее интересной с точки зрения статистики информацией о выборах являются распределение голосов и явка. Сегодняшняя задача касается проблемы увеличения явки, хотя с практической точки зрения, конечно, бесполезна.
Вообще, логично предположить, что чем выше явка, тем справедливее должны быть выборы, так как учитывается мнение большего количества людей (закон больших чисел). Про это ещё будет ВОПРОС.
#олимпиады #выборы
Умное голосование (#119)
Конструктивные и неконструктивные доказательства
Доказательства существования чего-либо (например, системы наименования улиц, или раскраски, как в сегодняшней задаче) бывают конструктивными и неконструктивными.
В первом случае объект, существование которого доказывается, предъявляется в явном виде.
В последнем случае лишь доказывается, что «суслик есть», хоть мы его и не видим. Например, так работает принцип Дирихле.
В решении приводятся оба варианта доказательства. Однако понятно, что с практической точки зрения ценнее конструктивный вариант.
#олимпиады #графы
Цветочный город (#117)
Как (не)правильно постить
Сразу отмечу следующее, хотя, наверное, и так уже понятно, но всё же, чтобы полностью снять экивоки. Большинство популярных контент-платформ (youtube, instagram) имеют рекомендательную ленту. Чтобы в неё попасть и там оставаться, нужно постить регулярно (= ежедневно). В телеграме другие механизмы продвижения и доставки контента (пока), поэтому писать можно как хочется, и ничего за это не будет. Конечно, пользователь сам может отписаться в любой момент, но алгоритмической дискриминации за нерегулярность не происходит. Чем я и пользуюсь. Другими словами, я объявляю все публикации НЕРЕГУЛЯРНЫМИ (это очень удобно 🙂), чтобы корректно управлять ожиданиями своей аудитории. Но не менее торжественно уточняю, что канал ЖИВ. А всем, кто с нами, огромное СПАСИБО!
Теперь продолжим математическую повестку с геометрии на клетчатой доске. В этот раз в «диагональном» варианте.
#олимпиады
Угловые соседи (#115)
Леммы с красивым названием
В математике есть много утверждений с забавными названиями. Мой фаворит – это теорема о причёсывании ежа. Ещё есть такая лемма в теории графов, которая формулируется на языке рукопожатий: в любом коллективе число людей, совершивших нечётное число рукопожатий, чётно. Как ни странно, но доказательство леммы о рукопожатиях элементарно, хотя название-то какое!
В общем, к чему это я. Сегодняшнюю задачку можно решить и без лемм с красивым названием. На стиле. Просто к слову пришлось.
#графы
mathreshka/oz-roads-114-9a8e3bce81a7">Страна Оз. Дороги (#114)
Ним
– Я знаю одну игру, в которой всегда выигрываю.
– Если вы не можете проиграть, это не игра.
– Я могу проиграть, но я всегда выигрываю.
В прошлом году в Мариенбаде
Логичным продолжением игр Башеmathreshka/nim-112-a32d2281100">, рассмотренных в постах Ёлочные игрушки (#18) и Ёлочные игрушки возвращаются (#17), является конечная игра с полной информацией ним.
Поклонникам арт-хауса рекомендуется к просмотру фильм В прошлом году в Мариенбаде, где игра занимает центральную часть сюжета. Здесь мы разбираем вариант стандартного условия выигрыша, когда победителем считается взявший последний предмет. В фильме играют в мизер, другими словами, когда взявший последнее является проигравшим. С точки зрения выигрышной стратегии мизер слегка сложнее, но имеет много общего со стандартным вариантом игры.
#игра #математикавискусстве
mathreshka/nim-112-a32d2281100">Игра Ним (#112)
Авторские задачи
В начале «Снежной королевы» злые тролли смастерили странное зеркало, которое всё искажало. Набаловавшись на земле, они решили поглумиться и над небом. Чем выше тролли поднимались, тем сильнее зеркало кривлялось, и в какой-то момент оно выскользнуло у них из рук и разбилось на мелкие осколки. В зависимости от того, куда попадал осколок, он начинал проявлять себя по-разному. Дальше – больше, но интереснее Ганса Христиана Андерсена нам всё равно не рассказать, поэтому перечитайте сказку сами – не пожалеете!
Для нас же важно, что если абстрагироваться и принять зеркало за плоскость, осколки – за треугольники, квадраты или шестиугольники, то мы получим головоломку, которая имеет неожиданную связь с прошлым постом. На Международной олимпиаде российская сборная выступает под руководством Назара Хангельдыевича Агаханова, выпускника мехмата МГУ, ныне доцента МФТИ. Он и придумал сегодняшнюю задачу, которая предлагалась уже на Всеросе. Мы её лишь слегка дополнили.
А вообще авторов прекрасных задач великое множество. Хорошая коллекция собрана здесь.
#олимпиады
mathreshka/proper-cells-110-e7d8c55e53a8">Правильные клетки (#110)
«Последняя задача из матрешки напомнила», —
ТОНКИЙ ТРОЛЛИНГ от подписчика.
Задача о дилижансе. Облегчённая версия
Лёгкое прикосновение к разделу теории графов о кратчайших путях.
Задача кратчайшего пути – задача поиска пути между двумя вершинами на графе, минимизирующего сумму весов рёбер, его составляющих.
Сложность решения, конечно, зависит от того, что нам известно про граф. В общем случае для решения пользуются специальными алгоритмами. В нашей задаче есть изначальные сведения о графе, и требуется только доказать оценку сверху на длину кратчайшего пути.
#олимпиады #графы
mathreshka/transfers-107-dfbfedad5a06">На перекладных (#107)
Задача с красивым ответом
Сегодняшняя задача появлялась на собеседованиях в разных компаниях (напримерmathreshka/50-bikers-105-db541b0ec1d6">, #Palantir, инфо с Glassdoor) примерно с 2010 года. Недавно её предложили моему другу на #интервью в #Сбербанк. Хотя больше она подходит для Почты России.
А ещё в этой задаче красивый ответ. Я бы даже сказал, гармоничный.
mathreshka/50-bikers-105-db541b0ec1d6">50 байкеров (#105)
🎄
Друзья, ещё раз с наступающими праздниками! По традиции – опрос. Напомню, что если у вас есть дополнительные пожелания, замечания, комментарии – welcome в личку.
++i
102 задачи
4700+ подписчиков
матрёшке 2 года 🥳
спасибо
Просто, как раздватри
Матрешка на связи. Для разгона простенькая задачка на взвешивания. В отличие от классических задач весы здесь умеют не только сравнивать, но и определять массу. Мне эта задачка попалась на #интервью в #Совкомфлот в далёком 2015.
Шагать будем в ногу с веком, поэтому пробую новую фичу «скрытый текст» (или «spoiler formatting»). Всё просто, окаймляем убийца бухгалтер в двойную вертикальную черту. Не тестил обратную совместимость, поэтому, если вы сразу увидели решение, то вероятно нужно обновить клиент.
Монетный двор (#123): На монетном дворе работают 100 рабочих. Каждый день каждому рабочему выдаётся по 1 кг золота, из которого он должен изготовить 100 монет по 10 г. Стало известно, что один из рабочих делает фальшивые монеты — на 1 г легче. Как при помощи одного взвешивания точно определить прощелыгу?
Решение: Положим на весы n монет от n-го рабочего. Величина недостачи в граммах будет в точности равна номеру мошенника.
Уточнение и разбор
Приятно удивило высокое количество участвовавших в голосовании / решении задачи, за что огромное спасибо!
Не приходила в голову мысль, что условие задачи можно неверно истолковать, но понял, что можно, поэтому поясню правило начисления очков при игре в монету из предыдущей задачи:
За каждым игроком до начала игры фиксируется сторона монеты. За ход монета подбрасывается один раз. Одно очко добавляется игроку, чья сторона совпала с выпавшей стороной монеты, а другой игрок остаётся при своих.
Я считал, что это дефолтное толкование этой игры. Вспомним хотя бы арбитра футбольных матчей. Но это моё личное мнение.
Вопрос о справедливости в некотором смысле философский, так как ситуация неоконченной игры правилами априори не регламентирована. Ставку разделить необходимо, продолжить игру в будущем нельзя.
Разбор и комментарии по каждому из вариантов.
«У математиков разное понимание красоты. То, что ты считаешь красивым, и повлияет на выбор области», — уверена декан факультета математики НИУ ВШЭ Александра Скрипченко.
В спецпроекте «Ученые норм!» поговорили с современными учеными-математиками и выяснили, как проходит их обычный день и какие задачи они решают прямо сейчас. О том, как математики помогают специалистам других наук и как оптимизируют систему навигации для нас с вами, что их мотивирует и что разочаровывает, — в этом видео: https://youtu.be/nHqsBLXtk0k
Спасибо всем, кто поучаствовал в опросе! На эту тему есть интересный сюжет из лекции М. С. Гельфанда «Математика выборов».
Читать полностью…
Задачи на чётность
Большой блок олимпиадных задач составляют задачи на чётность. Иногда она завуалирована, иногда задана явно, как здесь.
#олимпиады
Две клетки в минуту (#118)
Год в условии задачи
Интересной традицией для авторов олимпиадных задач является использование года проведения в условии. Чаще всего год можно заменить на произвольное n и решать задачу в общем виде. Иногда это условно общий случай, например, если используется делимость года на некоторое число.
Сегодня предлагаем задачу Московской олимпиады 1994 года для 8 класса. Если заменить в формулировке год на текущий, то получится очень простой случай. Поэтому мы оставили оригинальное условие и дополнительно предлагаем вам решить задачу в общем случае.
#олимпиады #игра
Игра в квадраты (#116)
IMO 2020
На прошлой неделе завершилась Международная Математическая Oлимпиада. Поздравляем наших ребят со вторым местом в неофициальном командном зачёте!
1. 🇨🇳 (215)
2. 🇷🇺 (185)
3. 🇺🇸 (183)
Подробная статистика.
Задачки прилагаются. Регламент: по 4,5 часа на три задачи.
©
Давно ли вы катались на канатных дорогах? В этом году мне выдалось путешествие по городам Поволжья. Поэтому могу отрекомендовать канатку в Нижнем Новгороде / «на Бору» (местные так поправили). Отменные виды по-над Волгойmathreshka/cableway-113-ed47a4a25942">.
Короче, недавно писали про авторские задачи. Лет десять назад я тоже придумал одну. Как говорится, не судите строго.
Итак, эксклюзив для подписчиков.
Кстати, если у вас есть свои задачки – присылайте, самые крутые обязательно запостим со всеми причитающимися почестями автору.
mathreshka/cableway-113-ed47a4a25942">Канатка (#113)
Геометрия на решётке для гриля
Рассмотрим важный класс геометрических задач, своего рода «целочисленную геометрию». Объекты на целочисленных решётках изучаются даже в теории вероятностей. Например, случайные блуждания с их разносторонними практическими применениямиmathreshka/primitive-triangle-111-6fa2b79dfbc0">.
Целочисленной решёткой Z² называется множество точек декартовой плоскости с целыми координатами. Бывает удобным представлять себе целочисленную решётку как бесконечный лист клетчатой бумаги. Многоугольник считается расположенным на Z², если все его вершины являются точками (узлами) этой решётки.
Площадь S многоугольника, расположенного на решётке, считается по простой формуле S=I+E/2-1, где I – количество узлов строго внутри многоугольника, E – на его границе, включая вершины. Эта формула названа в честь австрийского математика Георга Пика, доказавшего её в 1899 году.
Для доказательства формулы Пика во всей её полноте, придётся иметь дело с так называемыми примитивными треугольниками. Будем есть слона по частям или, как сказал бы Боб Дилан: «I can’t eat all that stuff in a single bite». Примитивные треугольники сравнимы с глыбами, которые каменотёс обрабатывает лишь тремя ударами резца, создавая тем самым заготовки для более изысканных произведений искусства.
#олимпиады #геометрия
mathreshka/primitive-triangle-111-6fa2b79dfbc0">Примитивные треугольники (#111)
Международная олимпиада
Значит так, пора выходить из анабиоза. Для такого случая есть бодрящая задачка с Международной #олимпиады. Это первая задача с соревнований такого уровня в Матрёшке, поэтому если вы ни разу не решали задач с «международки», попробуйте, специальных знаний не требуется. На мой взгляд, интересная возможность оценить сложность материала, с которым работают ребята.
Международная математическая олимпиада (MMO) – это Чемпионат мира по математике среди школьников старших классов, проводящийся каждый год в одной из стран. Первая MMO прошла в 1959 году в Румынии с участием семи стран. В последние годы в ММО участвуют более 100 стран с 5 континентов.
Я на международные этапы не отбирался, но если у вас есть такой опыт – отмечайтесь 👨🎓 внизу и делитесь впечатлениями в личку!
mathreshka/leapfrog-109-cf5b8b936404">Чехарда (#109)
Задача брадобрея
Это бородатая задача, но я хочу рассказать о ней здесь по двум причинам.
Во-первых, мне её предложили на #интервью в компании #Совкомфлот, а значит могут предложить и вамmathreshka/barber-108-73072a8fc223">. В нашей компании это стало устойчивой фразой: прежде чем браться за любую задачу, проверьте, не решаете ли вы задачу брадобрея.
Во-вторых, это антиномия, то есть рассуждение, которое содержит внутреннее противоречие. Например, может ли всемогущий бог создать камень, который не сможет поднять? Всё это вариации парадокса Рассела – рассуждения, показавшего противоречивость наивной теории множеств.
Ранее мы уже говорили про классификацию феноменов, которые часто объединяют под словом #парадокс. Там же рассмотрена задача о днях рождений – парадокс другого типа.
Присылайте ваши любимые парадоксы. Самый интересный – в ленту.
mathreshka/barber-108-73072a8fc223">Брадобрей (#108)
Кони Гугла
Говорятmathreshka/hourses-106-5878b64d8347">, что эта задачка стала известной, так как её справшивают на #интервью в #Google. На мой взгляд, очень остроумный пример задачи нахождения k-й порядковой статистики.
Кстати, в #Yandex тоже есть кони.
А есть ли в ваших компаниях ̶к̶о̶н̶и̶ любимые задачи, которые почти всегда предлагаются соискателям? Добро пожаловать в личку.
mathreshka/hourses-106-5878b64d8347">Кони (#106)
Разминка
Во-первых, спасибо всем, кто проголосовал в новогоднем опросе. Очень приятно видеть, что есть интерес к нашим материалам на еженедельной основе. Мотивирует продолжать делится с вами только самыми интересными задачами, выражаясь словами поэта:
Изводишь единого слова ради
Тысячи тонн словесной руды
Я считаю, что год нужно начинать плавно, поэтому сегодня предлагается суперлёгкая задача. Без подвоха. Но в то же время – не без изюминки (на мой вкус). Её я услышал случайно, когда на праздниках просматривал интервью Солодникова (ещёнепознер) с Зиминым (вымпелком). Кстати, всем рекомендую посмотреть. В нём очень интересная подводка к книжке Бронштейна «Солнечное вещество». Ну и, конечно, великолепно отрекомендован (неумышленно) детский задачник Арнольда. Из него и взят сегодняшний вопрос...
В силу суперлёгкости – публикуем без решения. Но если хочется свериться – смотрите видео по ссылке выше (время выставлено).
mathreshka/family-album-103-8f1b87696a00">Кирпич (#104)
С наступающим Новым годом!
Вы ещё с нами? 🙂
Друзьяmathreshka/family-album-103-8f1b87696a00">, спасибо за вашу поддержку в этом году! Последнее время вести канал непросто, но именно ваш интерес мотивирует продолжать.
С другой стороны, мне нравится, что это очень гибкая история, которая подстраивается под время. У меня нет цели публиковаться во что бы то ни стало, так как главное условие качества – всё должно быть в кайф!
Поэтому, друзья, всем отличных праздников! И, конечно, дз на каникулы прилагается.
PS Думаю, мы вас ещё потревожим в этом году с традиционным опросом, так как нам очень не хватает обратной связи...
#олимпиады #графы
mathreshka/family-album-103-8f1b87696a00">Семейный альбом (#103)
Динамическое vs статическое решение
Тема задач на взвешивание себя ещё не исчерапала. Сегодня порешаем задачу типа «найти фальшивку», когда её относительный вес неизвестен. Это #классическаязадача, впервые опубликованная в статье Goodstein R.L. (1945). Решать её можно динамически, то есть когда следующий шаг (взвешивание) решения зависит от результатов предыдущего, или статически, когда наоборот. В разборе мы покажем оба подхода.
mathreshka/12-coins-102-889bd9ef7189">Весы и 12 монет (#102)
