Математика помогает раскрыть преступление!

Законы комбинаторики помогают вычислить преступника! Удивительное решение головоломки. Системы счисления, размещения и сочетания
Видео снято по мотивам задачи Московской математической олимпиады: problems.ru/view_problem_deta...
Автор задачи: Косухин О.Н
СОДЕРЖАНИЕ
0:00 - Детективная история
0:35 - Первый способ
2:00 - Более сложная задача
2:40 - Важный вопрос!
3:25 - Второй способ
4:19 - Кульминация!
Мои курсы: market-135395111
VK: wildmathing
Задачник: wall-135395111_14984
Донат: www.donationalerts.ru/r/wildma...
ПОПУЛЯРНЫЙ ВОПРОС
- Почему из 12 цифры выгоднее всего выбирать 6 единичек и 6 нулей?
- Мы выбираем k цифр из 12, чтобы поставить на них единички, а на оставшиеся позиции встают нолики единственным образом. То есть в формуле сочетаний (момент 2 мин 20 сек) n=12, а k мы хотим выбрать так, чтобы результат был максимален. Он будет таковым при k=6. Полезно в этой связи вспомнить треугольник Паскаля и соответствующее разложение бинома (a+b)¹²
БОЛЬШЕ КРУТЫХ ВИДЕО О МАТЕМАТИКЕ
1. Бином Ньютона и СОЧЕТАНИЯ: • #219. БИНОМ НЬЮТОНА ДЛ...
2. Революционер в математике: • ГАЛУА. Революционер в ...
3. Самая красивая формула: • #161. САМАЯ КРАСИВАЯ Ф...
4. Величайшие проблемы XX века: • ГИЛЬБЕРТ. Величайшие п...
5. Высшая математика для детей: • Высшая математика для ...
#наука #математика #научпоп

[@WildMathing]

Если вы поняли эту задачу, то поздравляю: она была на олимпиаде I уровня. Считайте, что у вас БВИ! Не забудьте поставить лайк и написать комментарий!

[@user-nj6gb4js8u]

Блестяще!

[@Kt0-0tO]

Интересная задачка, хочется ещё таких олимпиадных!

[@user-xy3bf7wf6j]

Это было потрясающе! Осталось для БВИ сделать оценку, но за такой красивый пример половину баллов уж точно должны были дать!)

[@WildMathing]

@@user-xy3bf7wf6j, в оригинале задача была про 12 дней, так что чистый плюс у вас в кармане!

[@axelvermontov6607]

@@WildMathing как начать разбираться в математике? вообще как будто тупой

[@AT_geometr]

Решал методом Султанова. Рассмотрим четырёхмерный куб со стороной 2 и системой координат вдоль граней. Расположим подозреваемых в точках с целыми координатами на этом кубе. Осталось вызывать трёхмерные срезы этого куба, которых, как раз, 12. Так как свидетель и подозреваемый - разные люди, то хотя бы в одном срезе будет только свидетель.

[@WildMathing]

«Звонит мне как-то раз бывший ученик, Ниро Вульф... »

[@user-hh8pu9mz5z]

Вот ты выдал, братец, это классное решение

[@krover7454]

@@user-hh8pu9mz5z это то же решение, потому что в таком кубе вершины как раз в троичной системе нумеруют

[@Galaxy-111]

@@user-hh8pu9mz5z Я сначала подумал, что это прикол.

[@Alex-tx7ci]

@@Galaxy-111 я уже готов был смеяться...

[@Postupashki]

Визуализация, как всегда, выше всяких похвал, Wild!

[@WildMathing]

Спасибо, стараюсь!

[@obik7239]

Задачи интересные,но врядли детективы раскрывают преступление так). (Надо ещё сделать обратную задачу:"как преступнику избежать наказания за n дней?")

[@XxXRedSn0wXxX]

Пока его соучастники роют подкоп, чтобы его вызволить

[@wladislawortlieb8992]

Wunderbar! Впереди 5 минут подлинного удовольствия. Огромное спасибо за вашу работу!

[@user-mp5rt3hl7z]

Решение красивое. Действительно, хорошая задача. Спасибо)

[@elnurbda]

Большое спасибо за видеоролик!

[@AlexAB113]

Как всегда - восторг!

[@jonik_s526]

Вау. Спасибо за ролик!

[@amirgusulaev6044]

Один из лучших каналов про математику!

[@pavluha.official]

Замечательная работа, со вкусом) впрочем, как и всегда. Очень интересно следить за развитием мастерства автора. Я думаю, выбранный формат более продуктивен в плане развития канала. Надеюсь, количество времени, затрачиваемого на минуту ролика, с каждым разом становится меньше) Пришлось пересмотреть ещё раз, чтобы более-менее вникнуть в решение) Спасибо.

[@user-op8rp7wg9s]

Прекрасные видео!

[@AlexeyEvpalov]

Наиболее простой способ, использование троичной системы исчисления. Спасибо за интересное видео.

[@mnemoria8643]

Это вообще не моя тема, но с алгоритмами Ютуба не поспоришь. Шикарное оформление видео)

[@antshar7388]

Посмотрев до этого задачу про шахматы на 3b1b, сразу понял, что задача решается похожим образом. Спасибо за расширение кругозора с троичной системой исчисления, позволяющей сократить количество дней по сравнению с обычной двоичной, присваивая только 7-и значное число (когда выходит 14 дней).

[@supremo5645]

Спасибо за видеоролик

[@modestra178]

Мои мольбы были услышаны, комбинаторика на канале, ура!)

[@WildMathing]

Рад, что добрались до нее!

[@Tsar_Pavel]

Видео wild'a как фильм смотрю. Монтаж и озвучка на высочайшем уровне.

[@user-rk2sy8qo2f]

Посмотрел на одном дыхании! Очень крутое видео: классный математический сюжет, а название цепляет, что готов отложить все дела и узнать что же внутри. Каждое видео сильнее предыдущего и очень сильно чувствуется свой стиль в анимации!) Теперь ваши видео можно узнать просто посмотрев на анимацию, это классно!) Рука мастера видна издалека) Использовать троичную систему счисления - интересный ход!) Объяснение на высоте! Очень круто! +1 идея к тому, чем занять детишек =) С восхищением, вновь, снимаю шляпу!!! =) Большое спасибо!

[@WildMathing]

Большое спасибо за комментарий, Дмитрий! Тем более в очередной раз столь добрый!

[@janeshaman7279]

Это прекрасно...

[@MadTavernkeeper]

1 день - вызываем всех, спрашиваем кто свидетель. Свидетель называется. Просим выйти всех кроме свидетеля. Преступника в комнате нет, свидетель есть. profit

[@samattag6227]

Вспомнил задачу про отравленные пирожки и собачек из 3 модуля по подготовке к ЕГЭ по математике от Вайлда за 2020-2021 учебный год.

[@Darbeko]

Невероятно интересная задача с интересным решением. Я надеюсь что видео с такими интересными олимпиадными задачами у вас буду чаще. Удачи вам в решении других таких же интересных задач) P.S. мой словарный запас просто на высоте, кроме "интересный" ничего не придумал

[@user-ex7xd4tr5w]

Привет, самый дикий математик! А не могли бы вы снять видео на тему гипотезы Ходжа? Про нее крайне мало на ютубе, могли бы стать первым)

[@WildMathing]

Приветствую и спасибо за интерес! До задач тысячелетия мы еще обязательно доберемся! Конкретно по гипотезе Ходжа меня скорее всего опередит Макар Светлый

[@user-ex7xd4tr5w]

@@WildMathing догнать. Догнать и перегнать Макара. Но он сейчас немного другими темами занят, так что шанс есть)) . P. S. Хорошие вещи можно и на двух каналах одновременно смотреть... P. S. S. Ну Михал Абрамыч уже пилит ее доказательство в майнкрафте...

[@user-eh7gf3gt1s]

Рекс Стаут, значит… я вижу, вы человек высокой культуры

[@user-vg1qo5gi3l]

Шикарная задача

[@osmanrasulov7508]

Комментарий для распространения видео

[@user-hh8pu9mz5z]

В продвижение!

[@MadTavernkeeper]

вернусь через несколько дней чтоб досмотреть видео по ту сторону условия

[@MadTavernkeeper]

я придумал только за 13 дней((

[@platonz6582]

Классный канал по матеше.

[@user-nj6gb4js8u]

Расскажите о задаче о спасении Иосифа Флавия из колодца. Замечательная задача и для любителей истории!

[@idk-yq3hz]

Круто

[@MaratSevk]

Опять ставить лайк

[@user-lt8gu9xk2z]

Можете подсказать как называется музыка видео. Она мне понравилась, успокаивает. Подскажите пж кто знает

[@user-jx5ws9vs9t]

Прекраснейшее видео и интереснейшее решение! Но немножко не хватает музыки в конце, здесь она быстро оборвалась

[@WildMathing]

Спасибо за обратную связь! К сожалению, музыку в конце обрывают более половины зрителей, так что с этим не все просто. Но я рад, что есть истинные ценители, которые смотрят финал с удовольствием

[@sergniko]

Это просто сказка. Никогда не понимал как можно додуматься до подобных решений без примера решения.

[@jack.556]

Можно название композиции ?

[@user-vv8mz9vu6i]

Я нашёл ещё одно решение: давайте разделим всю группу людей попалам, пригласим обе группы по очереди. Если никто из каждой группы ничего не скажет, значит в 1 из половинок и свидетель и преступник. Этим шагом мы за 2 дня упростили задачу вдвое, так как теперь мы можем проделывать любые манипуляции с каждой группой одновременно. Если у нас было 80 человек, то за 8 дней мы получим 16 групп по 5 человек. Теперь остальные 4 дня будем приглашать по 2 человека из каждой группы (1и2; 2и3; 3и4; 4и5). Твким образом у нас будет день, когда будет приглашён свидетель и не приглашёнпреступник.

[@user-lb7tl4sj9z]

А если в группе из 5 человек 1-й -- свидетель, а 2-й -- преступник? Тогда свидетеля ты приглашаешь только в месте с преступником.

[@user-vv8mz9vu6i]

@@user-lb7tl4sj9z , мда... Вы правы. Новый план: опросим 1,2 и 3; затем 3,4 и 5 (это 2 дня). Если никто не сознается, то 3- точно нас не интересует, а сведетель и преступник это 1 и 2, или 4 и 5(или же преступник это 3). Теперь опашиваем 1 и 5, а затем 2 и 4 (это ещё 2 дня).

[@legocreative2142]

Прикольна

[@rockykid3785]

Но преступник в первый день оклеветал того, кого сегодня нет и все)

[@PETPO]

Признаюсь, я заплакал...

[@brushesofdarkness]

а у вас есть видео про теорему Хелли? А уравнения Пелля? Было бы очень интересно

[@WildMathing]

Пока что нет, но спасибо за интерес!

[@vittorioandoliny3]

Теорема шпернера об антицепях

[@jarvis612]

Привет из Одессы)

[@WildMathing]

Всем одесситам мой пламенный привет!

[@user-zc9ni2fp7n]

Предположение почему 6 единиц и 6 нулей. По прежнему каждый подозреваемый имеет свой двоичный номер из 12 разрядов, где n нулей и m единиц. Поэтому максимально возможное количество подозреваемых x при которых эта стратегия найдет виновного за 12 дней равна количеству двоичных чисел с n нулями и m единицами, то есть x=12!/(n! x m!). При n=6, x принимает максимальное значение поэтому в двоичном числе 6 нулей и единиц

[@user-xy3bf7wf6j]

Предположим противное и что существует способ разделить 80 человек на 8 групп и вызывать каждую в какой-то день (группа может быть пустой, тогда в какой-то день мы не вызовем никого, т.е. нам будет достаточно меньше, чем 8 дней). Тогда дадим каждой группе какой-то признак (название) : a, b, c, d... h. Тогда каждый человек определяется наличием каких-то из восьми признаков. Тогда очевидно, что если существует человек, множество признаков которого являются подмножеством (не строгим) множества признаков другого, то первым будет свидетель, а вторым преступником --> в те дни, когда мы вызываем свидетеля, приходит и преступник. Переформулируем задачу: У нас есть множество из n (n=8) элементов. Какое максимальное кол-во подмножеств этого множества (люди с набором признаков) может быть так, что ни одно из этих подмножеств не является подмножеством другого (иначе первое множество будет свидетелем, а второе преступником)?

[@simpmebaka]

Не знаю, норм или нет, но я придумал такую штуку, просто решил докрутить ту идею, что пришла первой. Идея была в том, чтобы составить матрицу, а потом (в 2-мерном случае) приглашать строки и столбцы(ну а дальше обобщить на многомерный случай не так сложно, просто я не знаю, как это обозвать нормально, разве что координатами)), так что я сразу разложил 80 на простые множители и покомбинировал по-разному суммы. Лучше, чем 13 не получилось, но потенциал идеи был виден, просто эта пятерка противная в разложении мешала так еще и двойки нельзя никак дальше трехмерного случая поделить, потому что что 2×2=4, что 2+2=4. Ну я и подумал, а почему бы не взять 81(типа, если для него 12 ходов хватит, то для 80 и подавно), как раз очень вкусное число, 3^4, и если составить четырехмерную матрицу 3×3×3×3, то все вроде получается, да? Сначала мне идейка шизовой показалась, но вроде никаких противоречий я не увидел Upd:Оо, комментатор ниже предложил схожую идею, я теперь сомневаюсь еще меньше

[@simpmebaka]

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

[@strodion2105]

Это же интерактивная задача

[@a.osethkin55]

Рассчитывал на что-то вроде сериала Числа, но нет..

[@user-ee2fd8ei9p]

А с помощью какой программы можно снимать подобные ролики, или нечто похожее?

[@WildMathing]

Все анимации сделаны с помощью Manim: github.com/3b1b/manim

[@user-ee2fd8ei9p]

@@WildMathing благодарю, хочу что то делать чтобы развить интерес детей к обучению математике

[@tooman]

4:17. Ответ: 1, в информатику переходим? True =1, False = 0?)

[@WildMathing]

Не без этого!

[@MadTavernkeeper]

попался питонист (а кто еще будет true писать с большой буквы?)

[@tooman]

@@MadTavernkeeper для решения ЕГЭ по инфе лучше реально python использовать, хотя я и плюсы и Rust знаю :/

[@MadTavernkeeper]

@@tooman если можно будет писать егэ по инфе как олимпиадки, то я буду юзать связку c++/python потому что -ни один язык не знаю на хорошем уровне- разные инструменты выгоднее в разных целях

[@user-qq4vn4xq9l]

Именно 6 единиц и 6 нулей нужно чисто потому что Макс значение перестановок с повторениями будет именно в таком случае , вообще рил прикольно что а!*б! < (а+к)!*(б-к)! В то время как а*б > (а+к)*(б-к), не мог бы кто-то доказать первое утверждение про факториалы пожалуйста 🙏

[@toran16]

Как сделать двоичный ,десатичный,троичный чисел

[@WildMathing]

sistemy-schisleniya.ru/perevody/iz-desyatichnoj-v-drugie-sistemy-schisleniya

[@evilpotato3316]

Здорово, и всë же, почему именно 6 нулей и 6 единиц?

[@WildMathing]

Это наибольший из коэффициентов в разложении (a+b)¹². Иными словами, если мы выбираем k элементов из 12, то именно при k=6 сочетаний будет больше всего

[@evilpotato3316]

@@WildMathing спасибо большое за Ваш труд, сам бы никогда не догадался!)

[@kaponsky1]

10

[@brsbrs9275]

Задача красивая, но вот вопрос: а как мы узнаем кто из наших гостей реальный свидетель? Или все остальные молчат?

[@WildMathing]

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

[@MadTavernkeeper]

мы тут не в мафию играем)))

[@brsbrs9275]

@@WildMathing перечитал условие. Да, действительно. Но спасибо за разъяснение)

[@user-uu8wy9et5m]

👌👍💞👏🇰🇿🇰🇿🇰🇿

[@dersuuzala2463]

Не понятно, что будет если преступник и свидетель одно лицо.

[@user-ei6rd7ei7x]

Пусть людей даже не 80, а 81. Закодируем их четырёхзначными числами в троичной системе счисления (в том числе, начинающихся с 0). В первый день Ниро Вульф зовёт людей с нулём в первом разряде, во второй день с единицей в первом разряде, во третий - с двойкой в первом разряде. Если первые цифры номеров свидетеля и преступника различны, то свидетель его сдаст. В следующие три дня повторим то же самое со со второй цифрой, затем ещё три дня с третьей цифрой и наконец три дня с четвёртой цифрой. Всего дней 12, номера свидетеля и преступника отличаются хотя бы в одном разряде, поэтому дело точно будет раскрыто.

[@WildMathing]

Совершенно верно!

[@user-ei6rd7ei7x]

Теперь другой алгоритм. Лемма 1. Если дело с n замешанными людьми можно раскрыть за a дней, а с m замешанными людьми можно раскрыть за b дней, то дело с nm замешанными людьми можно раскрыть за a+b дней. Доказательство: занумеруем людей парами (i,j), 1

[@user-ei6rd7ei7x]

@@WildMathing а это очень интересная идея с рассмотрением людей, закодированных двоичными n-мерными векторами с одинаковым числом нулей и единиц. При n, стремящемся к бесконечности, за n дней можно раскрыть преступление с C^{[n/2]}_n замешанными, что эквивалентно 2^n/sqrt(pi n / 2). При этом если есть более, чем 2^n замешанных, то, очевидно, за n дней дело не раскрыть. Разрыв между оценками составляет всего порядка корня из n раз!

[@user-ei6rd7ei7x]

@@WildMathing сейчас подумал, что ответом является C^{[n/2]}_n. Действительно, пусть было n дней, тогда закодируем людей n-мерными двоичными векторами. Пусть при этом у человека i-я координата его вектора равна 1, если его позвали в i-ый день, и 0, если не позвали. Тогда заметим, что не может быть такого, что у одного человека стоят единицы на тех же самых местах, что и у второго, и возможно ещё в некоторых местах, так как если он преступник, а второй - свидетель, то свидетель не сможет сдать преступника. Получаем известную задачу о максимальном числе вершин в антицепи n-мерного булева куба (порядок - частичный, вершина меньше другой вершины по этому порядку, если у другой вершины стоят единицы на всех местах, что и у первой, и возможно ещё в некоторых местах). Так как булев куб можно покрыть C^{[n/2]}_n цепями, то имеется не более такого количества вершин в антицепи. С другой стороны, взяв все вершины из слоя [n/2] (то есть с суммой координат [n/2]), получаем антицепь из такого числа вершин. Очень хорошая задача, в которой ответ можно даже дать точно, без асимптотики.

[@ball_sack6969]

похоже на матрицу 8 на 10

[@ineversayhating4148]

Можете объяснить мне пожалуйста! Кто я такой? Я не могу понять , что мне нравится, мне нравится все, я люблю изучать все что мне попадётся. Я люблю изучать математику, биологию, химию, физику, историю и не могу остановиться. Правильно ли это или надо остановиться на чем то одном?

[@WildMathing]

Это прекрасно! Причем есть вузы и направления, в которых такая универсальность востребована. Например, в МГУ есть факультет физики-химической инженерии или, скажем, факультет биоинженерии. Наверняка в МФТИ и в некоторых других вузах есть что-то похожее. Совсем не обязательно останавливаться на чем-то одном, но желательно поставить долгосрочные цели

[@user-hh5dt2de7t]

Это очень плохое кино)

[@WildMathing]

Надеюсь, все понимают, что это комплимент мне, а не укор сериалам про Ниро Вульфа!

[@illia47]

1

[@petrotkach8757]

4:45 и почему? (я тупой)

[@WildMathing]

Мы выбираем k цифр из 12, чтобы поставить на них единички. На оставшиеся позиции встают нолики единственным образом. То есть в формуле сочетаний (момент 2:20) n=12, а k мы хотим выбрать так, чтобы результат был максимален. Он будет таковым при k=6

[@DmitDmit1]

C(n,k) максимально при k=n/2

[@petrotkach8757]

@@DmitDmit1 Как доказать? (Я тупой)

[@fedoralinux8976]

Это конечно все интересно и круто, но почему детектив не может приглашать по одному человеку к себе, так что за день пройдет 7 человек? Ведь логично, что если он не знает кто свидетель при переборе, так и при хождении по одному. Или просто пригласить все 80 и по одному заводить в комнату и спрашивать, после отпускать, ведь в комнате когда то, да и появится свидетель. Может я не понял условие...

[@WildMathing]

Ниро Вульф не может «пообщаться» с каждым из приглашенных в отдельности: они словно сидят все время в одной комнате, пьют чай, прощаются - наступает новый день

[@fedoralinux8976]

Понятно, спасибо.

[@joly3122]

@@WildMathing Это решение мне напомнило такой алгоритм из уроков информатики, как поразрядная сортировка

[@AXCYKEP]

0:35 я исправил: Давайте каждому из 80 человек выдадим свой уникальный QR-код.

[@Twenti_dinamit]

Задача Король захотел оторватся по полной и устроить пир с 1000 бутылками вина, но пришёл мусульман и отравил 1 бутылку вина из 1000 бутылок в погребе, в наличии есть 12 кроликов которые тоже отравятся от этого яда но эффект проявится через день а ядовитое вино должен быть найдено на следующей день

[@WildMathing]

12 - много: хватит десяти, если занумеровать бутылки двоичными числами