Как за 14 вопросов отгадать натуральное число от 1 до 1000? Вопросы должны быть такие, что отвечать на них можно было только "Да" или "Нет". 1 раз отвечающий может соврать(может и вообще не врать, но врать не более 1 раза)

Это сообщение отредактировал denis200 - 15/07/2007, 22:14

--------------------

Двухкратный чемпион гамблера по коротким нардам.
(Весна 2007, Осень 2007)
Победитель Первого 24-х часового нардо-марафона по коротким нардам.
Победитель турнира Победителей по коротким нардам.
(Август 2013)

...

Это сообщение отредактировал grizzly - 15/07/2007, 22:43

Сплошная математика пошла) Дели пополам да и спрашивай больше половины или нет)

Пополам точно неэкономно. Я пока придумала, как узнать число за 8 вопросов - в четверичной системе счисления получается четырехзначное число с цифрами от 0 до 3, каждая цифра выясняется за два вопроса. Еще 6 вопросов остается на то, чтобы выяснить, все ли правильно, и исправить...

3333 в четверичной системе счисления это 255. Числа больше 255 четырьмя цифрами в четверичной системе счисления не запишешь. Соответственно число в диапозоне 256-1000 будет пятизначное в четверичной системе счисления.

--------------------

Двухкратный чемпион гамблера по коротким нардам.
(Весна 2007, Осень 2007)
Победитель Первого 24-х часового нардо-марафона по коротким нардам.
Победитель турнира Победителей по коротким нардам.
(Август 2013)

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

Помницца, в п/л в моем детстве был такой "фокус": загадывалось число от 1 до 63, потом "фокусник" показывал загадавшему 6 карточек, на которых надо было найти число, и сказать есть оно там, или нет. Потом называлось число.

Карточки были такие:

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

Итак, чтобы угадать число от одного до тысячи (точнее, до 1023), нам требуется 10 таких карточек. 4 вопроса в запасе для создания избыточности кодировки (контрольного разряда). Думаю, с этого места надо думать. Охота кому? Дело в том, что подобные задачки входили в мое базовое образование, не думаю, что профессиональное решение будет кому интересно, да и, возможно, кому захочется самому голову поломать. С другой стороны, больше 20 лет прошло... Так что дальше буду думать позже, чтобы никому кайф не испортить.

PS. В Сеть не лазил, даже карточки из головы извлек.

Это сообщение отредактировал SoftMetal - 16/07/2007, 13:50

Так эти карточки являются фактически таблицами перевода чисел из двоичной системы счисления в десятичную. А выясняется все в двоичном коде, 10 разрядов - 10 вопросов. Проблема в том, что проверка правильности должна производиться в той же кодировке, переводить на этом этапе в десятичную бессмысленно. Поскольку уложиться в 4 оставшихся вопроса у меня пока не получается, я и пыталась найти систему счисления, которая позволит сократить количество вопросов на первом этапе.

Да там все просто. Надо просто перестать манипулировать ЧИСЛАМИ, и начать задавать вопросы по КАРТОЧКАМ. Приблизительно так: из девяти карточек мысленно посторить "куб" 3x3, и задать три вопроса, где отвечающий соврал. Т.о. мы точно будем знать ПРАВИЛЬНЫЕ ответы на девяти карточках. Ну, а четырнадцатым вопросом (если он понадобится), спросим, не соврал ли нам отвечающий на последней, десятой карточке (если не соврал на 9 предыдущих, если соврал - мы точно уже знаем - на какой конкретно).

В таком варианте вроде бы не срастется. Тебе не обязаны соврать в течение именно 10 первых вопросов - могут правильно ответить на все 10 "основных" вопросов и соврут тогда, когда ты будешь уточнять, где соврали.