* По-трудна от най-трудната задача
Публикувано на 09 януари 2009 в раздел Математика.
Вече публикувах задача вариант на най-трудната логическа задача на всички времена. Намерих задача на Том Елис, която твърди, че е по-трудна от най-трудната задача на всички времена. Мисля, че е прав.
Оригиналната задача е следната:
Трима богове A, B и C, в някакъв ред казват истина, лъжа или произволен отговор. Трябва да разпознаете кой кой е питайки три въпроса, на които се отговаря с да и не. Те разбират български език, но отговарят на техен собствен, който вие не разбирате. Какви въпроси ще зададете?
Том Елис развива задачата, като добавя следните условия:
1. Нека боговете са 2N+1;
2. Единственото, което знаете за тях е, че точно N на брой са тези, които дават произволен отговор.
Задайте 2N въпроса, за да познаете кой бог какъв е.
Признавам си – провалих се в опита да намеря решението сам, въпреки, че знаех решението на оригиналната задача. Оказа се не чак толкова сложно. Ще публикувам връзка към решението скоро :)
pyrwo mi kavi dali otkriwam prawilno hybrid-a tuzemec. ako re[enieto na `astniq slu`aj, koeto publikuwah e prawilno ]e stane i w abstract-niq.
Първо ще трябва да се постарая да разгадая решението, което си дал, защото е трудно четимо… На общ план всичко му е наред. Днес вечерта ще пусна моят вариант подробно.
wypros kym uslowieto – prawilno li razbiram, `e move da ima N hybrid-da i N+1 lyvci? t.e. ne e kazano, `e zadylvitelno ima takyw, kojto kazwa istinata, no pyk move da ima (0 – N+1)?
o]e 1 wypros – tyj kato ne move da se zadade po 1 wypros na bog (2N+1 bogowe, no samo 2N wyprosi), kakto be[e pri kanibalite, pozwoleno li e da se pita 1 bog nqkolko wyprosa? taka i taka ]e ostane nqkoj bez wypros, move li da ostanat i nqkolko bez wypros?
http://www.srcf.ucam.org/~te233/maths/puzzles/evenharder.html