Новини
Форум
Актуално
сървърЧерешката се падна на мен
1. Първите шестима палят по два пъти
2. Брояча брои до 11 12
Черешката се падна на мен
1. Първите шестима палят по два пъти
2. Брояча брои до 11 12
Задачката е интересна, една от най-коментираните във форума на William Wu от Станфорд в сайта на университета Бъркли (там е станал BS). И понеже това си е математика (затворниците и ламБата са за забавление), ако се приложат някои ограничения в условието се получават доста интерсни възможности за мисловни напъни и различни (и малко"неочаквани" стратегии).
Предложението ми е да "задължим" надзирателя да вкарва в ареста по един затворник всеки ден след анонса му. Пък да видим дали не са вкарали всички членове на Менса в затвора.
pimpirlit,
Шест пъти прочетох поста ти ... и след шестия продължавам да не разбирам за какво точно става въпрос с тая добавка към условието:
Предложението ми е да "задължим" надзирателя да вкарва в ареста по един затворник всеки ден след анонса му
Хайде да го обясниш пак, по възможност с повечко думи, please
Мисълта ми е от момента на стартиране на процеса да е задължително всеки ден в ареста да бъде вкарван по един затворник. Няма значение кой е той, но да е задължително да не се допуска ден, в който няма да бъде вкаран никой в ареста. В оригиналното ти условие такова задължение няма. Изобщо не е указано как ще влизат затворниците (по колко на ден, час или какъвто и да е интервал). Понеже това все пак си е логика/математика можем да тормозим затврниците без проблем.
Подсказка - това условие би позволило повече възможности за броене и още няколко възможности за стратегии.
Пак не разбирам с какво това променя нещата, sorry.
В оригиналното условие се търси единствено негубеща стратегия, т.е. да не се допусне грешка когато евентуално се стигне до ситуация за възможност за казване ("когато някой от вас се осмели да ми каже че всички са минали през карцера")
До такава ситуация може и да не се стигне по принцип, защото например петия може никога да не посети карцера заради кефа на началника.
Абсолютно по същия начин ми изглеждат нещата и при твоята добавка и затова се чудя какъв е нейния смисъл.
Та ако може, с още повечко думи, ... като за такива като мен бавносхващащи
Това ограничение ти позволява да измислиш по-оптимизирани стратегии. В задачката, която аз съм гледал става дума за 100 затворника и ако "броячът" трябва да преброй до 198 гасенета/паления на лампата и при математически случаен избор на затворник, то никой не би доживял излизането си. Понеже се забавлявах преди години с нея, ще се въздържа да давам решения (няма да ви е интересно), само ще ти подскажа, че единият път за оптимизация е "динамичен избор на брояч", а не предварителното му определяне. Мога да подскажа и повече ако е необходимо.
Изглежда съвсем съм го закъсал, след като продължавам да не разбирам с какво твоята добавка променя условието. Това за оптимизацията и динамичния брояч - ясно от самото начало, но не е ясно с какво двете условия се различават.
Има обаче и друг сценарий - ти предварително си се занимавал с "подобна" задача и аксиоматично приемаш, че става въпрос за нейното условие. Така да се каже, прочел си сегашното условие по диагонал и направо си мислиш за твоята задача, пък ние си мислим за тая. Чаткаш ли какво май се получава ?
Що просто не кажеш "Решението ви е калпаво, защото е много дълго по отношение на броя на влизанията в карцера. Хайде да го оптимизираме."
Или става въпрос за нещо друго ???
Не знам защо се засягаш.
Не съм казал, че решението ви не е вярно, напротив - това е най-разпространеното и универсално решение и вие стигнахте до него много по-бързо от форума на Бъркли. И също съобразихте да отработите момента с неопределеността на началното състояние на лампата. Мислех, че в чисто математически план ще ви е интересно да се развие в посока оптимизиране и намиране на други, различни стратегии. Може би съм сгрешил, съжалявам.
Все пак ако на някого му е интересно, може да хвърли едно око на студията на William Wu по повод задачката тук (.pdf!). Освен броя на затворниците и това, че става дума за столова, а не за карцер, друга разлика в условието няма (а това не променя математическата логика).
Съвсем умишлено не прочетох документа.
Първо, защото от самото начало си мислех за възможността за оптимизиране, като например че всички могат да броят, но само един да пали.
И второ, мисля че най-накрая вдянах за какво иде реч в твоята добавка и как тя променя условието - а именно, ако един затворник влезе на N-тия ден за пръв път, то той може да е сигурен, че вече е имало (поне) N-1 влизания от други затворници, съответно ако на N-тия ден влиза за M-ти път, то той може да е сигурен, че е имало вече N-M влизания от други затворници.
ПП. Нито за миг не съм се почувствал засегнат, не е имало причина
ПП2. Да, наистина при такава добавка като че ли има много сериозни възможности за оптимизиране - например да се вмъкне четно/нечетно (в случай, че в добавката става въпрос за точно един посетител на карцера дневно)
Радавам се, че се разбрахме.
Видях задачката от самото начало, но не писах в темата, за да не развалям удоволствието. Но я следях с интерес. Във форума на Бъркли се забавляват с нея вече девета година и не им омръзва. Но те са стигнали до висините на математическия висш пилотаж. Убеден съм, че когато решиш да прочетеш монографията ще ти бъде интересно.
Отговор с цитат