Комментарий к опросу

Спасибо всем, кто поучаствовал в опросе!

Правильный ответ <50%. И это, как показал опыт, контринтуитивно. Казалось бы, есть всего лишь 1%, что тест покажет ложноположительный результат! Почему же тогда ответ так сильно отличается от 99%?

Дело в том, что речь идёт о разных условных вероятностях:
– Дано, что вероятность положительного теста при условии, что человек здоров, равна 1% (следует из определения специфичности).
– Надо найти наоборот вероятность того, что человек здоров (нездоров), при условии, что тест показал положительный результат.

Итак, примерно 1% = вероятность того, что человек болен (такова статистика). И также примерно 1% = вероятность того, что человек получил ложноположительный результат. Эти две группы людей примерно одинаковы по количеству, поэтому и возникает вероятность около 50% в ответе.

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

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

Берегите себя

Пособие для грибников

Как выйти из леса, если вы заблудились?

В заповедных и дремучих,
Страшных Mуромских лесах
Всяка нечисть бродит тучей
И в проезжих сеет страх,
Воет воем, что твои упокойники,
Если есть там соловьи, то разбойники.
Страшно, аж жуть!

Владимир Высоцкий

#олимпиады

Грибники (#98)

Русская рулетка

Забавная задачка с контринтуитивным финалом (мне так показалось). Все знают про классическую игру с револьвером и одним патроном. Если патронов два, то возникает интересный эффект.

Брейнтизер с #интервью в #Facebook. Pull the trigger.

#тервер

Русская рулетка (#99)

Школьная задача про школу

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

В общем, если вы ещё не устали от бинарности и pigeonhole, то вот вам задачка к началу учебного года!

#олимпиады

О делении классов на группы (#100)

Апдейт на осень

Друзья, в этом году (а если повезёт, то и в следующем) мне предстоит непростой экзерсис – обучение в ШАДе Яндекса. Поэтому есть две новости:

плохая – количество постов придётся на первое время сократить до 2-3 в месяц
хорошая – уже за сентябрь я узнал много актуальных задачек, которыми тестируют кандидатов на интервью

Поэтому не теряемся. Впереди будет много интересных постов!

А пока простая задачка с Всероссийской #олимпиады – и пусть это вас не пугает.

Акупунктура (#101)

Динамическое vs статическое решение

Тема задач на взвешивание себя ещё не исчерапала. Сегодня порешаем задачу типа «найти фальшивку», когда её относительный вес неизвестен. Это #классическаязадача, впервые опубликованная в статье Goodstein R.L. (1945). Решать её можно динамически, то есть когда следующий шаг (взвешивание) решения зависит от результатов предыдущего, или статически, когда наоборот. В разборе мы покажем оба подхода.

Весы и 12 монет (#102)

++i

102 задачи
4700+ подписчиков
матрёшке 2 года 🥳
спасибо

С наступающим Новым годом!

Вы ещё с нами? 🙂

Друзья, спасибо за вашу поддержку в этом году! Последнее время вести канал непросто, но именно ваш интерес мотивирует продолжать.

С другой стороны, мне нравится, что это очень гибкая история, которая подстраивается под время. У меня нет цели публиковаться во что бы то ни стало, так как главное условие качества – всё должно быть в кайф!

Поэтому, друзья, всем отличных праздников! И, конечно, дз на каникулы прилагается.

PS Думаю, мы вас ещё потревожим в этом году с традиционным опросом, так как нам очень не хватает обратной связи...

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

Семейный альбом (#103)

🎄

Друзья, ещё раз с наступающими праздниками! По традиции – опрос. Напомню, что если у вас есть дополнительные пожелания, замечания, комментарии – welcome в личку.

Разминка

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

Изводишь единого слова ради
Тысячи тонн словесной руды

Я считаю, что год нужно начинать плавно, поэтому сегодня предлагается суперлёгкая задача. Без подвоха. Но в то же время – не без изюминки (на мой вкус). Её я услышал случайно, когда на праздниках просматривал интервью Солодникова (ещёнепознер) с Зиминым (вымпелком). Кстати, всем рекомендую посмотреть. В нём очень интересная подводка к книжке Бронштейна «Солнечное вещество». Ну и, конечно, великолепно отрекомендован (неумышленно) детский задачник Арнольда. Из него и взят сегодняшний вопрос...

В силу суперлёгкости – публикуем без решения. Но если хочется свериться – смотрите видео по ссылке выше (время выставлено).

Кирпич (#104)

Задача с красивым ответом

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

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

50 байкеров (#105)

Кони Гугла

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

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

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

Кони (#106)

Задача о дилижансе. Облегчённая версия

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

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

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

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

На перекладных (#107)

Задача брадобрея

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

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

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

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

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

Брадобрей (#108)

«Последняя задача из матрешки напомнила», —
ТОНКИЙ ТРОЛЛИНГ от подписчика.

Международная олимпиада

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

Международная математическая олимпиада (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)