Тёмный

✓ Задача о том, как одна лампочка освободила 100 заключённых | Ботай со мной  

Борис Трушин
Подписаться 375 тыс.
Просмотров 60 тыс.
50% 1

clck.ru/34Witx - Регистрируйтесь на вебинар «Из каких профессий проще перейти в IT» от Яндекс Практикума
В тюрьме 100 заключённых сидят по одиночным камерам. Начальник тюрьмы решил организовать такую игру. Их по одному иногда будут приводить в комнату, где нет ничего, кроме одной лампочки, которую заключённому разрешается включить или выключить. Гарантируется, что рано или поздно каждый из заключенных побывает в комнате с лампочкой сколько угодно раз. В любой момент заключённый, приведённый в комнату с лампочкой, может объявить, что все заключенные уже побывали в комнате хотя бы по одному разу. Если он прав, то всех отпустят, если нет - казнят. Заключенных собрали вместе в этой комнате, объявили правила, разрешили договориться, придумать стратегию, и, уходя, оставить выключатель в том положении, в котором захотят. Придумайте стратегию, которая позволит им освободиться
Как поддержать канал:
Bitcoin: bc1qwzx9t9mz5h5q8sgtz74mdgedxd5wu0g9kq6q5m
Ethereum: 0xAE872DcA8B135cf62Df4B36bE576a2EE64c6066a
Регулярная помощь (Boosty): boosty.to/trushinbv
Регулярная помощь (RU-vid): / @trushinbv
Регулярная помощь (Patreon): / trushinbv
Регулярная помощь (Sponsr): sponsr.ru/trushinbv
Разовая помощь (Ю-money, бывшие Яндекс.Деньги): yoomoney.ru/to/410011017613074
Разовая помощь (PayPal): paypal.me/boristrushin
Разовая помощь (Donation Alerts): www.donationalerts.com/r/bori...
В этом учебном году я веду три курса:
✔ «Подготовка к ЕГЭ по профильной математике с 0 до 70 баллов (10-11 класс)»: trushinbv.ru/ege70
Подойдёт и десятиклассникам, которые хотят уже за год до ЕГЭ стабильно решать на 70+, и одиннадцатиклассникам, которые почти ничего не знают, но хотят за год выйти на приличные баллы. На курсе освоим как всю тестовую часть, так и многие задачи из сложной части ЕГЭ.
✔ «Подготовка к ЕГЭ по профильной математике с 60 до 100 баллов (11 класс)»: trushinbv.ru/ege100
Для тех, кто уже знает математику на базовом уровне, и хочет за год освоить её на 90+. Там, в основном, будем учиться решать задания из сложной части ЕГЭ, но залезем немного и в некоторые содержательные задания из тестовой части.
(Если у одиннадцатиклассника есть достаточная мотивация, можно параллельно учиться сразу на двух этих курсах - trushinbv.ru/egepack - их программы согласованы между собой)
✔ «Подготовка к перечневым олимпиадам по математике (10-11 класс)»: trushinbv.ru/olymp
В первую очередь этот курс для одиннадцатиклассников, которые освоили стандартную школьную программу хотя бы на «четыре», и хотят за полгода подготовиться к олимпиадам типа Физтех, Ломоносов, ОММО и ПВГ, чтобы попробовать зацепиться за диплом хотя бы в одной из них.
Кроме того, доступны мои прошлогодние курсы в записи:
✔ «Подготовка к ОГЭ»: trushinbv.ru/oge9
Это запись большого годового курса, который я провел пару лет назад. В этом году у меня не будет новых курсов для 9 класса.
✔ Мини-курсы по отдельным заданиям ЕГЭ:
- Теория вероятности с нуля и до ЕГЭ (Задания 3 и 4): trushinbv.ru/egeTV
- Уравнения и неравенства (Задания 12 и 14): trushinbv.ru/egeAL
- Стереометрия (Задание 13): trushinbv.ru/egeST
- Экономические задачи (Задание 15): trushinbv.ru/egeEC
- Планиметрия (Задание 16): trushinbv.ru/egePL
- Задачи с параметром (Задание 17): trushinbv.ru/egePR
- Теория чисел (Задание 18): trushinbv.ru/egeTC
✔ Мини-курсы по перечневым олимпиадам:
- Олимпиада Физтех: trushinbv.ru/fizteh
- Олимпиада ОММО: trushinbv.ru/ommo
- Олимпиада Ломоносов и ПВГ: trushinbv.ru/lomonosov
Другие курсы Фоксфорда: trushinbv.ru/courses
Репетиторы Фоксфорда: trushinbv.ru/coach
Магазин мерча: trushinbv.ru/shop
Книжка от Трушина: trushinbv.ru/book
вКонтакте: ege_trushin
TikTok: / trushinbv
Twitter: / trushinbv
Instagram: / trushinbv
Telegram: t.me/trushinbv
Facebook: / trushinbv
RU-vid: / trushinbv
Личный сайт: TrushinBV.ru
Реклама, АНО ДПО “Образовательные технологии Яндекса”, ИНН 7704282033, 119021, г. Москва, ул. Тимура Фрунзе, д. 11, корпус 2
LdtCKRSJq

Опубликовано:

 

27 май 2023

Поделиться:

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист
Посмотреть позже
Комментарии : 656   
@ttecnk
@ttecnk 11 месяцев назад
У меня был вариант, что раз их в этой комнате собрали, значит они уже там все побывали
@TUZZ5000
@TUZZ5000 11 месяцев назад
По моему скромному мнению это шедевральный ответ.
@Zlobny-Kotyara
@Zlobny-Kotyara 11 месяцев назад
Это как в старом анекдоте: Жена посылает программиста за хлебом и говорит: - Если будут яйца, возьми десяток. Программист пришёл с 10 батонами хлеба. На вопрос жены "зачем ты купил 10 батонов?" он ответил: "ну яйца же были, я и взял 10".
@gitarre_spielen
@gitarre_spielen 11 месяцев назад
Тоже так сразу подумал, но от ролика оставалось пять минут, потому пришлось отбросить вариант
@Animal_2444
@Animal_2444 11 месяцев назад
Товарищ, ты Гений)
@Andrey495340
@Andrey495340 11 месяцев назад
@@Zlobny-Kotyara 🤣 (самый программистский анекдот в мире)
@user-mp8om1nk4u
@user-mp8om1nk4u 11 месяцев назад
Программист. Догадался как решать после того как Борис сказал про то что мы вводим счётчика :)
@NikitaShokin2003
@NikitaShokin2003 11 месяцев назад
+
@user-is3d21e3s
@user-is3d21e3s 11 месяцев назад
да уж кто-то считает, ага...
@user-oi3zi4hf2k
@user-oi3zi4hf2k 10 месяцев назад
Чем-то напоминает тему про мьютексы с семафорами из freeRTOS.
@blackdragon7405
@blackdragon7405 5 месяцев назад
+
@BeeHPok
@BeeHPok 11 месяцев назад
Я впервые в своей жизни смог самостоятельно решить заявленно сложную логическую задачку. Причём после каких-то пяти минут размышлений ответ пришёл будто бы озарением! Спасибо за полученные эмоции!
@user-mb6qg1yt3j
@user-mb6qg1yt3j 11 месяцев назад
После озвученного условия, пришла мысль, что раз человек может побывать возможно вообще раз в 10 лет, то никто оттуда не выйдет)
@northwardcore
@northwardcore 11 месяцев назад
Ну типа это сработает в бесконечном промежутке времени, с бессмертными узниками)
@user-tw9rl7vf1g
@user-tw9rl7vf1g 11 месяцев назад
Ага. Да ещё если этот человек окажется щотчиком.
@mikezador
@mikezador 7 месяцев назад
@@northwardcoreи с бессмертной лампочкой ;)
@Pablo_de_Lexandro
@Pablo_de_Lexandro 4 месяца назад
так смысл - не лажануть и не вякнуть глупость, чтоб не попасть на казнь. а так сидишь и играешь в игры начальника, живёшь с надеждой... и Виктор Франкл улыбается с облачка)
@user-uw6lo2th4r
@user-uw6lo2th4r 11 месяцев назад
Нужно больше подобных задачек на канале.
@user-ggsebmukhaul
@user-ggsebmukhaul 11 месяцев назад
На самом деле не такая уж и сложная задачка оказалась. Решение пришло минут за 5-10, но я сильно засомневался только потому, что с условием любых по времени перерывов между посещениями шанс того, что, вероятно, каждому из заключенный придётся побывать в камере около 100 раз, а счетчику минимум 100 раз, становится абсурдным вариант, что их выпустят до того, как они, мм, умрут от старости. Тем не менее, задачка чисто математическая и к реальным условиям не имеет никого отношения.
@user-gs7pm4im2l
@user-gs7pm4im2l 11 месяцев назад
Введите элемент сколько им осталось сидеть, и допустим, тот кто выходит из тюрьмы первым, выпускайте его через эту комнату. И продолжайте игру. И тд и тп
@user-hy3vs3yj2q
@user-hy3vs3yj2q 3 месяца назад
Если взять 10 человек, то все могут выйти за год
@ypsidshi8183
@ypsidshi8183 11 месяцев назад
Ура, новое видео! Благодаря Вашим роликам стал по-настоящему понимать и интересоваться математикой. Спасибо за Ваш труд!
@MisterIncog
@MisterIncog 9 месяцев назад
Урааа, обожаю, когда получается решить такие задачки самому, прямо как по алгоритму изобретения решений. В большинстве случаев в таких задачках стоит вчитываться в условие, чтобы понять, на что там акцентируется внимание. Перечитав условие довольно быстро пришло решение на моменте со «сколько угодно раз». Классно!
@sdf0as9f0a9sda0s
@sdf0as9f0a9sda0s 11 месяцев назад
пока не сказали про счётчик, не было никакой идеи как решить..... а как только произнесли это слово, то ответ оказался на поверхности )) спасибо )) интересно ))) программист. периодически пользуюсь таким приёмом, как пример, перед оператором цикла объявляем переменную counter - cчётчик и, как вариант, выходим из цикла по достижению требуемого значения )))
@Serg4nt
@Serg4nt 11 месяцев назад
Почти догадался-не подумал про одного человека-счётчика и что только он может сказать-"здесь все побывали" а пытался решить, что бы каждый мог так сказать
@superkerilltk6020
@superkerilltk6020 11 месяцев назад
БОЖЕ МОЙ Я РЕШИЛ ЕЕ САМ, Я ТАК СЧАСТЛИВ, СПАСИБО ЗА ПОДНЯТИЕ САМООЦЕНКИ И ПРЕКРАСНУЮ ЗАДАЧУ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
@user-bj7sg1kd8i
@user-bj7sg1kd8i 11 месяцев назад
Поздравляю! Молодец
@Penobarbital
@Penobarbital 11 месяцев назад
@@user-bj7sg1kd8i красавчик. А я бы задался вопросом, что если один из заключенных забудет включить свет, либо включит его повторно, у них же бесконечное количество повторений. Да и много чего может произойти за бесконечное количество времени)) В общем, я как лирик не могу согласиться, что данное решение является истинно верным ))
@user-lu3jb8oe5y
@user-lu3jb8oe5y 11 месяцев назад
​@@Penobarbital Но стратегия-то верная. А сработает ли она это уже неважно
@Penobarbital
@Penobarbital 11 месяцев назад
@@user-lu3jb8oe5y это с точки зрения математика, где всё чётко и определенно, но, как правило, вне квантового мира это не работает )
@dexitti05
@dexitti05 11 месяцев назад
​@@Penobarbital если заключенный забудет включить, ничего не произойдет, он просто отсрочит освобождение. А если включит повторно, то с высокой вероятностью они все умрут (каждое включение - 1 человек)
@ivansaraiev7776
@ivansaraiev7776 11 месяцев назад
Задача понравилась. Сам думал долго. Думал о том как каждый может узнавать количество переключений. Но не придумал. Но нас словах о том что бы выбрать одного считающего сразу всё понял.
@ponnnnn
@ponnnnn 11 месяцев назад
Решил сам, очень доволен собой. Спасибо за видео!
@user-zo9bm2ri9k
@user-zo9bm2ri9k 11 месяцев назад
Очень круто и красиво!
@vishnyaaaaaaaaaa
@vishnyaaaaaaaaaa 7 месяцев назад
Очень понравилась задача, спасибо!
@G1uckman
@G1uckman 11 месяцев назад
Решил. Очень круто. Спасибо.
@humaniora_for_all
@humaniora_for_all 11 месяцев назад
Круто! Сразу посмотрели с детьми)
@willgoonandon3050
@willgoonandon3050 11 месяцев назад
Всё гениальное просто!
@rl55555
@rl55555 11 месяцев назад
Приходит заключённый с лампочкой в комнату, а там сидит начальник-грузин. Он спрашивает: -Все побывали в комнате? -Побывали, - отвечает заключённый. Начальник гасит лампочку...
@user-dp8kn5eh8y
@user-dp8kn5eh8y 11 месяцев назад
ААЗАЗАХАЗХ
@zloymish
@zloymish 11 месяцев назад
Вазелин, заходи...
@user-zj5jj4uf9y
@user-zj5jj4uf9y 11 месяцев назад
гачи-фанфик на логическую задачу. Воистину эпоха метаиронии
@paveld4196
@paveld4196 11 месяцев назад
Ахах Ты попу мыл? 😂 И гасит лампочку
@firsto
@firsto 4 месяца назад
я так понимаю на категорию б можно где угодно наткнуться
@vzmaxoff
@vzmaxoff 11 месяцев назад
Супер! Спасибо!
@elenabelinskaia8002
@elenabelinskaia8002 8 месяцев назад
Супер задачка! И очень красивое решение!
@user-nq6kv9tn3o
@user-nq6kv9tn3o 11 месяцев назад
Решил задачу довольно быстро, а потом долго не открывал этот ролик и думал, а какое же там "красивое" решение))))
@1917alexey
@1917alexey 11 месяцев назад
Забавно, что раньше я не понимал это решение) Спасибо
@TSM_149
@TSM_149 11 месяцев назад
Задачка огонь!! 👍
@user-me2ud7ob8p
@user-me2ud7ob8p 11 месяцев назад
Прикольная задача 👍
@MoonLight-jr5hl
@MoonLight-jr5hl 11 месяцев назад
Я лишь придумал решение с 7 лампочками при помощи двоичной системы счисления
@dan_who_exists
@dan_who_exists 11 месяцев назад
То же самое:)
@rotmerka2820
@rotmerka2820 11 месяцев назад
А как?
@MoonLight-jr5hl
@MoonLight-jr5hl 11 месяцев назад
@@rotmerka2820 пусть 0-когда лампочка не горит,а 1-когда лампочка горит,тогда у нас есть изначально число 0000000.когда человек,который еще ни разу не был в комнате, заходит, то он прибавляет к числу единичку.так можно получить 1111111(7единиц),то есть 2^7-1=128-1=127.когда человек заходит в комнату и видит число,равное 100, то говорит об окончании игры.
@dan_who_exists
@dan_who_exists 11 месяцев назад
@@MoonLight-jr5hl Надо не забыть повесить 8 выключателей
@pacific6777
@pacific6777 11 месяцев назад
огонь-задача!!!
@dexitti05
@dexitti05 11 месяцев назад
Мне удалось решить! Замечательная задача на бинарную логику, спасибо.
@koishinov
@koishinov 11 месяцев назад
Я в восторге
@konstantinsokolov5562
@konstantinsokolov5562 11 месяцев назад
спасибо, БВ. задача интересная
@bomuva
@bomuva 11 месяцев назад
Все очень просто, у нас два события возможны для передачи информации о том, был ли человек в комнате, он может либо включить, либо выключить свет. Так вот, все просто, все, кроме счетчика могут лишь раз включить свет (или выключить) свет, а счетчик приводит выключатель в обратное положение, чтобы посчитать следующего
@kusokKota
@kusokKota 11 месяцев назад
Сразу в голову пришла идея на счет единого развого включения света, но не стерпел и посмотрел решение. Эх, а я так был близок :(
@mr_bm
@mr_bm 11 месяцев назад
Идея, что надо назначить одного «избранного», который будет считать пришла прямо во время оглашения условия, дальше до полного решения думал не больше пол-минуты. Но задачка прикольная.
@user-pj8un5yx9z
@user-pj8un5yx9z 11 месяцев назад
Что так, что иначе, им освобождение не грозит.
@respectrespect546
@respectrespect546 11 месяцев назад
Поезд с вагонами в помощь😊 Версия 2.0: начальник тюрьмы бросает 10 кубиков с 11-мя гранями(от 0 до 10). Спасибо за контент, задача интересная.
@user-ec8lt5yn4h
@user-ec8lt5yn4h 11 месяцев назад
Ну да, красивое решение❤
@ANanatoliy
@ANanatoliy 11 месяцев назад
Я мыслил в верном направлении - что каждый только один раз меняет состояние, а Счетчика назвал - Избранным
@OHOTOJIE1
@OHOTOJIE1 11 месяцев назад
😂 Я назвал его Включатель. У меня все гасили а он включал лампочку.
@mrshvecov
@mrshvecov 11 месяцев назад
Прикольно 😃
@user-yy4fl8es7i
@user-yy4fl8es7i 11 месяцев назад
Получилось решить минуты за 3, но решение то же. И в правду идея очень похожа на идеи решения кучи задач по программированию, единственное, мне кажется, человек который считал ошибётся в арефметике, и они все умрут
@whatisblink
@whatisblink 11 месяцев назад
если я ничего не прослушал, то в камере никто не мешает царапать стены или вообще писать на них что то, так что счетчик может отметки ставить и нет проблем)
@wmrinchester
@wmrinchester 11 месяцев назад
@@whatisblink в видео Борис отдельно пояснил, что нельзя. Подобные задачи всегда на логику, а не попытку как-то обхитрить условия.
@whatisblink
@whatisblink 11 месяцев назад
@@wmrinchester а я и не пытался, это был ответ на предположение, что зек может затупить в арифметике, а я и сказал, как он может это посчитать, смысл решения от этого не меняется
@RedRus7689
@RedRus7689 11 месяцев назад
​@@wmrinchester нельзя для других отметки делать, для передачи информации. Делать отметки для себя, в своей камере, чтоб не сбиться со счета - не является попыткой обойти условия...
@alexandrs1159
@alexandrs1159 11 месяцев назад
Для страховки от ошибок счетчику нужно считать не до 99, а скажем до 102. Или досчитав до 99 и сомневаясь, не ошибся ли он, счетчик может еще подождать и если в течении длительного времени, так никто лампочки и не включит, то можно предположить, что он не ошибся.
@vyacheslavmarkhobrod7736
@vyacheslavmarkhobrod7736 11 месяцев назад
Спасибо. Классная задача. Жаль не догадался, хотя это чисто программная задача на массив и цикл do while. Обидно, не сообразил.
@Andrey495340
@Andrey495340 11 месяцев назад
Трушин решил в одном видео собрать всех программистов, да 🤣
@MaksStezhko
@MaksStezhko 11 месяцев назад
Тоже очень долго думал над ней )
@timurpryadilin8830
@timurpryadilin8830 8 месяцев назад
долго думал над алгоритмами, когда кто-то будет поочерёдно включать и выключать свет, но в таких решениях ничего не удавалось, всегда у надзирателя была стратегия не выпустить заключённых. в какой-то момент неожиданно придумал правильное решение, то же, что и в видео. очень обрадовался)
@niceplayer1276
@niceplayer1276 8 месяцев назад
Неделю думал над задачей, сразу решение не пришло, потом пару раз вспоминал о должке, и так, во время чистки зубов, додумался наконец-то😅
@whatisblink
@whatisblink 11 месяцев назад
сначала не догадался, решил посмотреть решение, как только услышал идею со счетчиком, я сразу понял в чем прикол)) так что процентов на 50 я сам догадался)
@jmugwel
@jmugwel 11 месяцев назад
Я наоборот дошел до счетчика, но не понял как считать. Почему то думал, что обязательно надо дать разные инструкции четным и нечетным заключенным.
@oro5421
@oro5421 8 месяцев назад
И я программист. За пару минут придумал РОВНО такое же решение. Только назвал его не счётчиком, а сторожем
@user-tv3ne2uk7f
@user-tv3ne2uk7f 11 месяцев назад
Давно знаю эту задачу, и сам решил точно также, но до сих пор уверен, что есть решение лучше.
@user-lv1pw2vi9p
@user-lv1pw2vi9p 11 месяцев назад
Жиза... по-любому задачу коммивояжёра можно решить за О(х^n) и захватить весь мир, зная что p = np😅
@ioganess
@ioganess 11 месяцев назад
Решил! Интересная задача, спасибо! "Счётчика" назвал "смотрящим" :)
@khohloma
@khohloma 11 месяцев назад
Офигенная логическая задачка
@nonamenoname274
@nonamenoname274 11 месяцев назад
У меня был вариант, что каждый из них нажмëт кнопку 10 раз и типо когда лампочка перегорит, то уже тут по любому было 100 человек. (Это первое, что мне пришло в голову, я тогда даже не подумал, что могут вообще 1 человека постоянно только звать, а потом уже второго)
@gh8499
@gh8499 11 месяцев назад
напомнило задачу про зеленые глаза и заключенных.
@chivorotsen
@chivorotsen 11 месяцев назад
Надо рассматривать задачу посложнее, когда первоначальное состояние лампочки не известно (а собирают их на совещание в другом месте). Ну и ещё круче загадывать с двумя лампочками. Вторая очень здорово вводит в заблуждение.
@balansodumar2619
@balansodumar2619 11 месяцев назад
Если первоначальное состояние лампочки не известно, то задача сложнее не становится - просто когда счетчик попадет в комнату, ему для безопастности вычислений нужно просто выключить лампочку и НЕ прибавлять 1 к счету. Другие заключенные также не должны трогать выключатель, пока лампочка будет гореть в комнате. Изменено: это работает только для включенного состояния лампочки, для выключенного механизм ломается - не следуйте моему решению)
@balansodumar2619
@balansodumar2619 11 месяцев назад
А с двумя лампочками интересно, возможно можно ускорить процесс выхода заключенных на свободу, но я пока не придумал решение.
@dragonsnyashers6309
@dragonsnyashers6309 11 месяцев назад
@@balansodumar2619 Если не известно, то твоя идея сработает только если лампочка была включена. Никто же не знает кого первым запустят в комнату. То есть, когда счётчик зашёл в комнату первый раз, а там горит лампочка, есть 2 варианта. Первый (который ты описал) лампочка была включена изначально. Второй лампочка была выключена изначально и 1 из других заключённых её уже включил.
@balansodumar2619
@balansodumar2619 11 месяцев назад
@@dragonsnyashers6309 Ну так я правильно вроде все написал, если заключенным не известно первоначальное состояние лампочки, для избежания ошибки в расчетах счетчику нужно пропустить в своем счету первую единицу, если лампочка горит в первый раз прихода счетчика. Если она не горит в первый раз прихода счетчика , то счетчик просто должен уйти и в следующий раз повторить вышеописанную мной процедуру. А когда счетчик прийдет в комнату следующий раз, то он просто должен следовать плану Трушина. Правильно обьяснил?
@wolffromnever4758
@wolffromnever4758 11 месяцев назад
@@balansodumar2619 заключённые могут включить лампочку ровно 99 раз. Суммарно. Если пропустить единицу, то "счётчик" может никогда не досчитать до 99.
@user-qb2jn9zh9i
@user-qb2jn9zh9i 11 месяцев назад
Не смог дойти до конца коментом, может все это уже было, но попробую собрать в одном месте. Задачу слышал уже давно, но там было 3 лампочки, что сбивало с толку и изрядно добавляло сложности. Хорошо бы найти предысторию задачи, было бы очень интересно. Начальное состояние лампочки не важно, достаточно договориться включать ее по два раза каждому. Что касается ускорения процесса, есть такой вариант - каждый становится счетчиком, то есть, каждый просто меняет состояние лампочки на противоположное. При этом он запоминает число своих "выключений" и действует так, что бы число его "включенний" не превышало число "выключений" на 1. Надеюсь, идея понятна, тем более, что скорее всего ее уже предлагали. Кажется, что при некоторых условиях этот подход может заметно ускорить процесс, но тут все зависит от того, по какому принципу их "вызывают". Вообще, было бы интересно обсудить и развить идею, может быть кто нибудь предложит более удобную площадку, чем комменты ютуба. Задачка того стоит, имхо )
@alexandertsimerman6280
@alexandertsimerman6280 11 месяцев назад
8
@artemcherkashin1928
@artemcherkashin1928 11 месяцев назад
Кажется ускорение не сработает, так как могут просто приводить одного и того же человека много раз подряд, в итоге у него будет равное число включений и выключений с любым их количеством
@user-qb2jn9zh9i
@user-qb2jn9zh9i 11 месяцев назад
@@artemcherkashin1928 да, в некоторых случаях эта стратегия будет хуже исходной, мне тоже так кажется, я поэтому и написал: "при некоторых условиях". Но, условие случайного вызова несколько неопределенно: тут уже писали, в других комментах, что при некоторых распределениях вероятности вызова время, за которое сходится исходная стратегия может быть устремлено к бесконечности. Так что даже численный эксперимент не поставишь. Но, если дополнительно ограничить условия, например сказать, что всех вызовут по одному разу в случайном порядке, потом по второму заходу и т.д, то мой вариант будет многократно быстрее исходного. Примитив, конечно, но я не знаю, как бороться с дурными бесконечности исходного условия. Тут могло бы матмоделирование помочь, но для него, как раз, придется алгоритм вызова сделать более определенным, можно, в принципе, предлагать варианты и пробовать )
@AndreySkakun
@AndreySkakun 11 месяцев назад
Я бы добавил к уже показанной стратегии обязанность каждого заключённого считать число переходов, 1 в 0. Т.е. если он увидел лампу уже включённой (не им самим), а потом увидел лампу уже выключенной. Это значит кто-то из обычных заходил, а потом счётчик заходил. Когда он насчитает таких переходов 97 (т.е. 97 обычных и счётчик уже заходили), то когда следующий раз будет 1 (лампа горит), значит уже 98 обычных (кроме него) и счётчик уже в комнате побывали. Можно заявлять, что уже все побывали. С небольшой вероятность, но возможно, что это событие наступит раньше последнего визита счётчика.
@user-cm9gw3hj7g
@user-cm9gw3hj7g 11 месяцев назад
Мне кажется, что это не совсем верно. Если какой-нибудь номер 2 увидел включенную лампу, вышел, зашел счетчик - выключил, зашел номер 3 - включил, зашел опять счетчик - выключил, зашел номер 4 - включил, зашел счетчик - выключил, и теперь зашел номер 2 и видит выключенную лампу. По твоей идее произошел 1 переход, хотя на самом деле было два (3-> счетчик, 4-> счетчик).
@user-cm9gw3hj7g
@user-cm9gw3hj7g 11 месяцев назад
Кажется понял, но шанс, что наступит 97 переходов крайне мал.
@AndreySkakun
@AndreySkakun 11 месяцев назад
@@user-cm9gw3hj7g В этой стратегии у всех событий вероятность маленькая, потому и время эксперимента выбрано бесконечным. Не придумал как посчитать, при каком количестве заходов вероятность успешного завершения игры, при игре по данной стратегии, достигнет 50%. Так сказать время полувыйгрыша стратегии. Любое дополнение или изменение стратегии, при котором количество заходов до полувыйгрыша уменьшится, следует считать улучшением стратегии.
@DemitryA
@DemitryA 11 месяцев назад
​@@AndreySkakun изначально собрался похвалить тебя, но нашел ошибку. Второй счетчик, увидевший 98 переходов, никогда не может быть уверен, что настоящий счетчик побывал в комнате. Поэтому стратегия не гарантированная, а рискованная.
@AndreySkakun
@AndreySkakun 11 месяцев назад
"2-й счётчик" - это любой из 99-ти обычных заключённых. А чтобы знать наверняка, что счётчик уже был, достаточно увидеть всего 1 переход (1->0).
@2tw_ant
@2tw_ant 11 месяцев назад
У меня была та же мысль, но гасить лампочку если ты там не был. Но если лампочка выключена, но ты там не был, слегка выкрутить её на четверть оборота. Для лампочки в зависимости от произволителя надо около от 5 четвертей оборотов что бы вытащить Получается 5 человек может передать что они там были
@user-fg1ce2if8m
@user-fg1ce2if8m 11 месяцев назад
Задачка на программерскую смекалочку. Лаек😼
@asadbekkhalilov9211
@asadbekkhalilov9211 8 месяцев назад
Здравствуйте хотел бы узнать что будет если счетчик не придет первым?
@irinaprokofieva2813
@irinaprokofieva2813 11 месяцев назад
❤❤❤❤❤
@1NN0V4T10N
@1NN0V4T10N 9 месяцев назад
Придумал решение минуты за 3, решил быстрее Бориса Викторовича получается😎
@armyant6187
@armyant6187 11 месяцев назад
Это прямо сюжет для какого-нибудь хоррора.
@leg0sam555
@leg0sam555 11 месяцев назад
Особенно если Счётчик в какой-то момент времени забыл, сколько человек уже побывало в комнате
@kamiloid11
@kamiloid11 11 месяцев назад
@@leg0sam555 Особенно, если среди заключённых есть предатель, и он намеренно выключил свет другого заключённого
@sergioprofessor4038
@sergioprofessor4038 11 месяцев назад
Ребят, да вам в сценаристы надо 😁👍
@gspidazrou939
@gspidazrou939 20 дней назад
О, нифига, решение пришло почти сразу же после озвучивания условия
@0vermind333
@0vermind333 11 месяцев назад
Классно
@danielvinokurov236
@danielvinokurov236 9 месяцев назад
Охрана тюрьмы пару раз включила свет сама и парам-парам-пам :) Догадался сам
@loneghost9445
@loneghost9445 7 месяцев назад
За первые 10 секунд после озвучивания условия придумал ответ. Изначально надо выключить лампочку и каждый человек если он ещё не включал лампочку и при этом лампочка не горит включает её, один человек считает количество включенных лампочек и каждый раз после себя выключает её
@user-uw1yd7kw9u
@user-uw1yd7kw9u 5 месяцев назад
элегантное решение. Нужно вводить счетчика)))))
@cnfnbcn3227
@cnfnbcn3227 11 месяцев назад
Ну не знаю, насколько она прям сложная, я пока слушал БВ, без паузы придумал решение. Хотя может годы программирования дают о себе знать 😄, но идея ввести счётчик пришла сразу
@humaniora_for_all
@humaniora_for_all 11 месяцев назад
Гений.
@paveliarmolenko9974
@paveliarmolenko9974 11 месяцев назад
Сюжет для сериала🎉
@konstantinsokolov5562
@konstantinsokolov5562 11 месяцев назад
почему я сразу до этого додумался... "да ты программист!"
@Alexey_Emelyanov
@Alexey_Emelyanov 11 месяцев назад
Реклама у Бориса Викторовича - это что-то новое
@alexostroumov7887
@alexostroumov7887 9 месяцев назад
01.08.2023. Узнал в день выпуска. Придумал сейчас. Решения по сути одинаковы. Только "Счётчик" - "Избранный", включает свет только он, а другие в свое первое посещение его выключают и подсчёт ведётся по выключенным лампочкам. Спасибо за задачу)
@pL1uXa
@pL1uXa 11 месяцев назад
Пару минут понадобилось, чтобы придумать решение. Удивительно, я походу не такой уж и тупой
@proglife3936
@proglife3936 8 месяцев назад
Надо подумать, а как лампочка помогает. Понять, что надо считать включенные (или наоборот выключенные, если сначала лампочка горит), понять, что считать в теории может только 1. А к этому моменту уже все поймут решение. Мы при заходе понимаем, что был заключенный новый или нет, а по лампочке мы понимаем горит или не горит, т.е. нужно задать соответствие между состоянием лампочки и новым побывавшим заключенным. Но раз задаем соответствие, то каждый включает 1 раз, но нам надо считать и бла бла бла и все короче.
@user-yd6gf5xl5f
@user-yd6gf5xl5f 11 месяцев назад
Странно, решение очень простое, а я к нему не пришел ни сегодня, ни годами ранее, когда впервые услышал задачку. С намека на счетчик сразу стало понятно, но блин
@oho7nik
@oho7nik 9 месяцев назад
Как только любой человек заходит в комнату он сразу же говорит что все 100 людей уже тут побывали. Всех казнят, все довольны
@user-zn6gn2oq5i
@user-zn6gn2oq5i 11 месяцев назад
Боже, какое простое решение для, казалось бы, сложной задачи
@user-lk6pg7wo1b
@user-lk6pg7wo1b 11 месяцев назад
Блин! Почти решил, совсем чуточку не докрутил. Стоило подумать на минуту дольше...
@mike0808
@mike0808 11 месяцев назад
Прическа супер!
@kasitskyi
@kasitskyi 11 месяцев назад
Когда ты сказал поставить видео на паузу и подумать, я не придумал ничего, но когда ты после паузы сказал, "уходя они выключат свет", я решил за две секунды. А возможно ли решить, если нельзя зафиксировать начальное положение?
@user-yw6nd4rq3i
@user-yw6nd4rq3i 11 месяцев назад
Да, тогда каждому придется по два раза свет включать, ну и займет вдвое больше времени
@kasitskyi
@kasitskyi 11 месяцев назад
@@user-yw6nd4rq3i ничего не понял
@user-yw6nd4rq3i
@user-yw6nd4rq3i 11 месяцев назад
@@kasitskyi в соседней ветке комментариев есть более детальный разбор.
@sergioprofessor4038
@sergioprofessor4038 11 месяцев назад
⁠@@user-yw6nd4rq3iнет. Если не известно первоначальное состояние лампочки то первый раз когда зайдет счетчик (а лампочка будет гореть он скажет 0 (не станет засчитывать а начнет с 2го посещения когда лампочка будет гореть) а если не горит значит он первый оказался в комнате). И да, это надо бы занести в условие задачи, но по умолчанию - логически если подумать то свет будет выключен на начало игры т.к. по идее после того как их соберут вместе и выведут из комнаты свет выключат и запрут комнату. Вероятно поэтому Борис и предложил так. П.с. Я бы добавил этот пункт в условие задачи, но что бы состояние лампочки было не известно на момент начала игры.
@user-yw6nd4rq3i
@user-yw6nd4rq3i 11 месяцев назад
@@sergioprofessor4038 если лампочка горит, как понять, горела ли она самого начала или ее кто-то включил?
@6ixdouble6ix64
@6ixdouble6ix64 11 месяцев назад
Главное со счета не сбиться )
@yurituev
@yurituev 11 месяцев назад
Больше логических задачек!
@migorpresents8991
@migorpresents8991 3 месяца назад
Еще не смотрел видео, вот моя идея: На митинге заключенные нумеруют себя для определенности. Начальника просят оставить свет включенным. Далее будет происходить следующее: все заключенные от 1 до n-1 выключают свет в конмнате (могут ТОЛЬКО выключать и ТОЛЬКО каждый один раз) Когда n-ный заходит в комнату, он, во-первых включает свет, во-вторых царапает черточку на руке. Когда n-ый нацарапет n-1 черточку на руке, они победили.
@danxai
@danxai 11 месяцев назад
О, задачка с Хабра! Разделяемый обший бит
@DemitryA
@DemitryA 11 месяцев назад
На практике из людей обязательно найдутся те, кто будет выключать свет вместо включения, будут включать свет много раз и т.п. И потом со словами: А што, не так надо было делать штоле? Ну тогда включите там свет после меня, сложно штоле одну кнопочку нажать.
@alexanderginger754
@alexanderginger754 11 месяцев назад
Мне кажется задача не такая сложная, т.к. я на удивление решил, хотя обычно с такими задачами у меня туго. Но я больше по программированию чем по математике, может из-за этого?
@trushinbv
@trushinbv 11 месяцев назад
Наверно )
@Andrey495340
@Andrey495340 11 месяцев назад
Попробуй ещё в шахматы поиграть, у меня есть парочка знакомых программистов, играют на 2300 Личесс ))) Сам программист, и сам играю, правда не сильно, но я самоучка
@kent1723
@kent1723 11 месяцев назад
@@Andrey495340 привет! какой ник на личесс?
@veschii_nevstrui
@veschii_nevstrui 11 месяцев назад
В этом нет ничего удивительного. В задаче из видео охранники представляют из себя процессор, а заключенные - потоки исполнения. Условие про бесконечное количество доступов до лампочки называется "гарантия прогресса". Саму же лампочку можно считать семафором, и в таких формулировках складывается несложное упражнение на многопоточное программирование, которое знающие программисты легко решат)
@alexanderginger754
@alexanderginger754 11 месяцев назад
@@veschii_nevstrui слушай, мы это проходили как раз в прошлом семестре, но это определенно не то как я думал над этой задачей))
@user-hd6gg5fn4j
@user-hd6gg5fn4j 8 месяцев назад
Вы, вроде, не говорили о Наяальном состоянии лампочки. А раз так, то она изначально может быть включена, тогда счётчик может подсчитать первого заключённого за себя и таким образом на 99 счëт комнату посетят 98 человек
@trushinbv
@trushinbv 8 месяцев назад
Было сказано, что они сами решают, каким будет начальное состояние
@dmitrypetrov8491
@dmitrypetrov8491 9 месяцев назад
Изи задача, решение придумал за минуту. Пусть первый человек всегда выключает лампочку, остальные 99 всегда включают, при чем каждый может включить ровно один раз. Когда первый человек 99-й раз выключил лампочку он говорит, что все заключенные побывали в комнате.
@alexeyfominykh8864
@alexeyfominykh8864 9 месяцев назад
Решил минут за 20. Идея со счетчиком пришла минут через 10, потом осталось только понять, что делают остальные. Опыт программирования имеется.
@brickon832
@brickon832 11 месяцев назад
сразу понял, что лампочкой будут считать. Иного варианта не дано.
@Fdo1010
@Fdo1010 11 месяцев назад
как программист (ну точнее пока учусь на втором курсе) догадался за 2 минуты
@raff_anglewood7456
@raff_anglewood7456 11 месяцев назад
Имба, сразу, как услышал условие, решил её именно так. Спасибо!
@PSpeedcuber
@PSpeedcuber 11 месяцев назад
Задача на построение фильтра)
@purity_one
@purity_one 11 месяцев назад
А что по времени жизни заключённых?
@Alpac999
@Alpac999 11 месяцев назад
считается что они живут бесконечно долго
@leonidrozenblum6880
@leonidrozenblum6880 11 месяцев назад
@@Alpac999 Не обязательно жить вечно. Достаточно жить, пока они в тюрьме. А это -- конечное время.
@Alpac999
@Alpac999 11 месяцев назад
@@leonidrozenblum6880 конечное, но не известное заранее. Поэтому нужно жить бесконечно, иначе (если известно сколько они живут) экспериментатор придумает алгоритм как сделать чтобы они все умерли в тюрьме
@leonidrozenblum6880
@leonidrozenblum6880 11 месяцев назад
@@Alpac999 У них организм может быть настроен не на бесконечное время, а только на то время, пока они находятся в тюрьме. Т.е. это все таки конечное (хоть и неизвестное) время.
@Alpac999
@Alpac999 11 месяцев назад
@@leonidrozenblum6880 тогда экспериментатор может дождаться пока они умрут, а потом начать вызывать
@felikss2065
@felikss2065 11 месяцев назад
Вот не зря говорят - Все гениальное в простоте...
@user-cm1ri1sn2u
@user-cm1ri1sn2u 11 месяцев назад
Так не говорят
@user-gn9dj7os6s
@user-gn9dj7os6s 11 месяцев назад
В условие еще надо добавить, что они бессмертные. От сидения в одиночной камере ни у кого здоровья не прибавлялось пока. Счетчика выбрали, а он через месяц загнулся, и привет.
@AndroidsReview
@AndroidsReview 11 месяцев назад
Минут 5 ушло. Сначала они оставляют свет включённым, и назначают одного который будет считать. Если заключённый заходит первый раз в комнату с включённым светом, то он выключает его. Когда назначенный заходит и видит выключенный свет, он запоминает что один уже побывал, прибавляет к сумме побывавших и включает лампу. Когда он досчитает до числа заключённых кроме себя, то он говорит что всё побывали.
@user-cy9dd1kv7d
@user-cy9dd1kv7d 11 месяцев назад
хорошая задача. можно не давать возможность выбора начального положения и задача все равно решаема, не намного сложнее.
@trushinbv
@trushinbv 11 месяцев назад
Да )
@user-is3d21e3s
@user-is3d21e3s 11 месяцев назад
все не так и трудно. горящая лампочка это "да" был один раз. негорящая я уже был. Вот и считай горящие
@dimachapaev3394
@dimachapaev3394 11 месяцев назад
у меня получилось решить, сам к такому же способу пришёл, как раз на программиста учусь :)
@DemitryA
@DemitryA 11 месяцев назад
Молодец! А я вот не решил. Отучился на программиста, но работаю не программистом. Правильные мысли были, но к итоговому решению не пришел. Видимо, отсутствие практики сказывается)
@serge6038
@serge6038 11 месяцев назад
Решил за 5 минут Аж сам того не ожидал. В размышлениях шёл от обратного. У нас есть бинарная система вкл/выкл, а нужно посчитать 100 человек. Если каждый будет проверять значение в комнате, то нереально построить какую-то комбинацию всего из 2 значений. Тогда подумал, что только часть из них будет проверять. Но поскольку они не могут друг с другом общаться, проверяющий может быть только один. Ну и последнее - все остальные включают только 1 раз - уже было легко додуматься.
@ActMedInfo
@ActMedInfo 11 месяцев назад
звучит красиво, но самого "счётчика" могут больше ни разу не повести в комнату. Или водить очень редко. А другие свет выключить не могут и ничего не делают. Все могут побывать не один раз... Т.е. когда следующий раз поведут счётчика, он выключит свет и посчитает 2. Но на самом деле все уже там побывали))
@user-ky5vy7xl2k
@user-ky5vy7xl2k 11 месяцев назад
Если свет изначально выключен , а включить каждому можно только по 1 разу и счётчик только выключить может , то "2" никак не посчитает.
@ActMedInfo
@ActMedInfo 11 месяцев назад
@@user-ky5vy7xl2k с чего бы это? 1 раз он там побывал и выключил свет. Это уже 2, если с ним считать. А если без него, то второй раз, когда его приведут, после кого-нибудь, кто был 1-й раз и включил свет - и посчитает "2"
@user-ky5vy7xl2k
@user-ky5vy7xl2k 11 месяцев назад
Изначально должен свет быть выключен а не включен быть. При этом не будет такого что ты описал. Тогда всё нормально пройдёт.
@user-yo8kt1ki3e
@user-yo8kt1ki3e 11 месяцев назад
Интересно было б доказать что нельзя решить задачу быстрее чем за O(n^2)
@mega_mango
@mega_mango 11 месяцев назад
Почему? Пронумеруем от 1 до 100, 1-ый "счётчик". Вначале заходит и включает второй, потом заходит и выключает первый. Затем также третий, потом опять первый. И того, мин время 2n, формально это вообще О(n)
@user-oq6kh2fe5m
@user-oq6kh2fe5m 11 месяцев назад
@@mega_mango По условию задачи, приводят людей рандомно. Значит, кто-то может быть ни разу, а кто-то уже 10 раз. Конечно, если по условию каждый должен попасть хотя бы 1 раз к лампочке, то рано или поздно, это случится. Но в любом случае, в подобных задачах пренебрегают человеческим фактором тех, кто принимает решение выбора.
@mega_mango
@mega_mango 11 месяцев назад
@@user-oq6kh2fe5m а. Ага. Ну, я дэбик просто, я знаю что сложность алгоритма означает его самое долгое время выполнения, просто тут затупил что-то 😶
@user-yo8kt1ki3e
@user-yo8kt1ki3e 11 месяцев назад
@@mega_mango если вероятность выбора каждого конкретного заключённого распределена равномерно -- то "счётчик" будет заходить в камеру каждый n-ый раз, и сделать это он должен n-1 раз. Вот и выходит что сложность n^2. Если попробовать смоделировать это программно то придётся использовать 2 цикла, что значит О (n^2) (если так нагляднее
@lexoid64
@lexoid64 11 месяцев назад
Главное, чтобы счетчик не сбился со счета )
@DmitryRomantsov
@DmitryRomantsov 11 месяцев назад
Я смог. Но, правда, мне кажется, я ее уже где-то читал раньше )
Далее
Редакция. News: 116-я неделя
45:38
Просмотров 2 млн
Редакция. News: 116-я неделя
45:38
Просмотров 2 млн