3536
Математика. Задачи с собеседований и олимпиад. Авторский канал выпускника мехмата, кандидата наук, чьё хобби – ходить по собеседованиям. Для связи: @clean_horizon
Год в условии задачи
Интересной традицией для авторов олимпиадных задач является использование года проведения в условии. Чаще всего год можно заменить на произвольное 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)
Школьная задача про школу
Вспомните, наверняка в ваших школах тоже на уроках английского и информатики класс делили на 2 группы. Состав групп был постоянный. Поразмышляем в задаче, как быстро могли бы перемешаться ученики, если бы можно было переходить между группами?
В общем, если вы ещё не устали от бинарности и pigeonhole, то вот вам задачка к началу учебного года!
#олимпиады
mathreshka/back2school-100-ba8cd5ec3355">О делении классов на группы (#100)
Пособие для грибников
Как выйти из леса, если вы заблудились?
В заповедных и дремучих,
Страшных Mуромских лесах
Всяка нечисть бродит тучей
И в проезжих сеет страх,
Воет воем, что твои упокойники,
Если есть там соловьи, то разбойники.
Страшно, аж жуть!
Владимир Высоцкий
#олимпиады
Грибники (#98)
Но у тебя / И значит, мы
Социальная повестка в Матрёшке. Ранее мы упоминали про проблему бездомных. Сегодня речь про эпидемию ВИЧ в стране.
Подведу вас плавно к сути. У любого медицинского теста есть два основных показателя, характеризующих его эффективность:
– чувствительность [sensitivity] = % корректно определённых положительных результатов = количество людей с положительным тестом / общее количество заболевших
– специфичность [specificity] = % корректно определённых отрицательных результатов = количество людей с отрицательным тестом / общее количество здоровых
Чем ниже чувствительность теста, тем больше будет ложноотрицательных результатов. Чем ниже специфичность, тем больше ложноположительных результатов. Современные тесты на ВИЧ обладают высокими чувствительностью и специфичностью (более 98% даже для экспресс-тестов), но надо помнить, что ни один тест не даст 100% точность.
Теперь про сегодняшнюю задачу. У неё есть много эквивалентных формулировок, но мне нравится эпидемиологический вариант – он вселяет надежду. Однако сначала предлагаю всем проверить интуицию в опросе ниже. По задумке автора (!) надо сперва отметить в опросе то, что приходит на ум без долгих размышлений, а уж потом решать задачу.
#тервер
HIV (#97)
Я интересуюсь не только математическим образованием, но в целом отраслью на глобальном и национальном уровнях. Раньше эта область у нас была далека от классического понимания успеха. Вспомните свои ассоциации с работой в образовании 5-10 лет назад...
Сейчас всё поменялось, это очень динамичная среда, есть много крутых возможностей в онлайн и оффлайн, EdTech стартапах, корпоративных центрах компетенций. Не упустить интересный вариант и быть в теме помогает канал с вакансиями в образовании @edujobs.
Автор канала — экс-лектор Высшей школы экономики. Он успешно внедрил образовательные процессы в Сбербанк, Skyeng, международные некоммерческие организации.
На канале регулярно появляются интересные вакансии по теме: от методиста в корпоративный e-learning до менеджера крупного образовательного проекта. Также важно — все вакансии с прямыми контактами.
В общем, ТЕМА!
/channel/edujobs/1726
Мы тут с вами шутки шутить собрались.
---
@fiztehjoke
Как (не)правильно постить
Сразу отмечу следующее, хотя, наверное, и так уже понятно, но всё же, чтобы полностью снять экивоки. Большинство популярных контент-платформ (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 года 🥳
спасибо
Апдейт на осень
Друзья, в этом году (а если повезёт, то и в следующем) мне предстоит непростой экзерсис – обучение в ШАДе Яндекса. Поэтому есть две новости:
плохая – количество постов придётся на первое время сократить до 2-3 в месяц
хорошая – уже за сентябрь я узнал много актуальных задачек, которыми тестируют кандидатов на интервью
Поэтому не теряемся. Впереди будет много интересных постов!
А пока простая задачка с Всероссийской #олимпиады – и пусть это вас не пугает.
mathreshka/acupuncture-101-6ca94c6586b9">Акупунктура (#101)
Русская рулетка
Забавная задачка с контринтуитивным финалом (мне так показалось). Все знают про классическую игру с револьвером и одним патроном. Если патронов два, то возникает интересный эффект.
Брейнтизер с #интервью в #Facebook. Pull the trigger.
#тервер
mathreshka/rr-99-d1fbcbf5fd11">Русская рулетка (#99)
Комментарий к опросу
Спасибо всем, кто поучаствовал в опросе!
Правильный ответ <50%. И это, как показал опыт, контринтуитивно. Казалось бы, есть всего лишь 1%, что тест покажет ложноположительный результат! Почему же тогда ответ так сильно отличается от 99%?
Дело в том, что речь идёт о разных условных вероятностях:
– Дано, что вероятность положительного теста при условии, что человек здоров, равна 1% (следует из определения специфичности).
– Надо найти наоборот вероятность того, что человек здоров (нездоров), при условии, что тест показал положительный результат.
Итак, примерно 1% = вероятность того, что человек болен (такова статистика). И также примерно 1% = вероятность того, что человек получил ложноположительный результат. Эти две группы людей примерно одинаковы по количеству, поэтому и возникает вероятность около 50% в ответе.
Другими словами, при относительно редких заболеваниях требуются более точные тесты с вероятностью ложноположительных результатов в несколько раз меньше процента заболевших.
И ещё одно важное замечание. В примере подразумевается, что у нас нет прочей информации о здоровье человека, кроме общей статистики и результата одного теста. В реальности же люди, как правило, ею обладают. Например, им скорее всего известно о событиях, которые переводят их в группу риска. Естественно, что в этом случае будет иная логика. А именно, надо брать долю инфицированных не по стране, а по определённой группе риска. А это уже совсем другая история.
Берегите себя
Равновеликость и равносоставленность
Моя бабушка из клочков разноцветной ткани шила красивые одеяла. Такая техника называется лоскутным шитьём или, как говорят у нас в России, пэчворк (patchwork).
В 1833-35 годах венгерский математик Фаркаш Бойяи и немецкий математик Пол Гервин доказали теорему (названную впоследствии Бойяи-Гервина):
Если два многоугольника имеют одинаковую площадь (равновеликость), то один из них можно разбить на такие части, из которых возможно составить второй многоугольник (равносоставленность).
Теперь попробуйте такой «танграм»: из равностороннего треугольника сложить квадрат. Получается? А ведь это простейший случай теоремы.
Но сегодняшний вопрос про другое: что будет если в условии теоремы ограничить количество частей?
#олимпиады
1000 частей (#96)
Yet another brainteaser
Логическая задачка с #интервью в #Yandex. Решение не требует специальных знаний, но если они есть, то наверное будет совсем легко.
mathreshka/wine-rabbit-95-51dfe560d4cf">Кролики и вино (#95)
Графы. Всерос
У меня зазвонил телефон.
– Кто говорит?
– Слон.
Задача актуальна и для бесконечного количества жителей. Готовимся к перенаселению.
#олимпиады
Телефонный звонок (#94)