ааааа

[avva]

Второй день не сплю, не ем, думаю только об этой задаче. Хожу как зомби. Все перепробовал. Ничего не выходит. В уме, на бумаге, на компьютере.

Час назад уже совсем был уверен, что получилось (в пятый раз примерно). Но нет. "..." - привычно отозвалось эхо.

Завтра беру тайм-аут, видимо, потому что так жить нельзя. Но черт побери.

Update: AAAAAAAAAAAAAAAAAAAAAA!

Comments

[mperv.livejournal.com]

Да, задача хорошая и, видимо, не очень простая. Хотя решивших не так уж и мало. Самое... ммм... вдохновляющее, что есть способ сделать 6 из 10-и и при этом останется один бит информации неизрасходованным. И на бесконечности 2/3 правильных ответов таки достигается.

[avva.livejournal.com]

Я, кстати, могу сделать 7/10 на бесконечности.

Update: нет, неправильно посчитал, этот метод дает 7/11 на бесконечности, что немного хуже, чем простой 2/3. Лучше, чем 2/3, не получается.

[alex-levit.livejournal.com]

Я узнал об этой задаче (бесконечный случай) лет 5-6 назад. Помню, что можно сделать чуть лучше чем 4/5, но 5/6 уже не выйдет.

[m2b.livejournal.com]

А сама задача/её авторы/те, кто опубликовали/те, по чьим мотивам она появилась - все они или кто-то из них вас случайно ли не затроллили этой задачей всего-навсего?

[mperv.livejournal.com]

Ну раньше за этим сайтиком такого не наблюдалось.

[m2b.livejournal.com]

Я подразумевал в более широком смысле.
Кроме сайта и текста задачи существуют, например, обстоятельства, при которых обращаешь на ту или иную вещь внимание.

[avva.livejournal.com]

Не, это невероятно.

[bortans.livejournal.com]

В прошлом веке я примерно так же мучался с задачей о 12 монетах (одна фальшивая, отличается по весу, неизвестно в какую сторону, надо ее найти за 3 взвешивания на весах-разновесах). И тогда было еще хуже, не было интернета и не у кого было узнать :)

[southwest]

Я примерно начинаю понимать, как решать. Увы, без компьютера может не обойтись. Я понял, что надо решить задачу попроще: где они побеждают в 3-х партиях из пяти.
Это тоже далеко не тривиально, но и не сложно.
Вот моё решение задачи 3 из 5 (убрать пробелы):
pastebin . com / 0qRhk8CD
Там в конце оказывается некоторое совпадение, которое
надо обобщить на случай из 9 раундов.

[ext-2087110.livejournal.com (from livejournal.com)]

Не читал ваше решение, но для 3 из 5 можно придумать стратегию в одну строчку. Так что не очень понял смысл в вашем решении.
Собственно первым ходом Боб говорит какой символ чаще встречается в битах с 2-го по 4-й, и далее Алиса так и играет. Если один раз Алиса ошибется, то Боб здесь кодирует ответ на 5-й вопрос.

[southwest]

классно, у вас гораздо короче получилось )

смысл может быть лишь в том, если оно обобщаемо на 9 битов, я об этом буду думать

[dyak.livejournal.com]

Ну да, это и есть решение для пяти из девяти: первый дает в след. шести как минимум три, плюс еще два закодированы в ошибках.

Задача в кодировке шести из девяти.

ПС Первый дает и след. пяти как минимум три, но кодировать тогда можно только два, опять только пять, а не шесть.

[southwest]

это всё понятно, если разные возможности получить пять из 9
даже 5 из восьми легко

в моём решении есть удивительное совпадение, когда казалось бы шесть различных вариантов имеют всего лишь четыре различных окончания

и это надо использовать

дайте мне ещё пару дней )

[dyak.livejournal.com]

А ну да. Щас напишу у себя.

[dyak.livejournal.com]

Нет, не получается :(

[spamsink.livejournal.com]

Мы знаем, что Алиса первым ходом всегда говорит 0. Тогда мы имеем или 1 угадывание плюс эти самые 5 из 8, или 1 дополнительный бит информации плюс как минимум 5 из 8. Как сформулировать алгоритм, гарантирующий 6 угадываний, на ночь глядя не соображу, но судя по формулировке на сайте, он должен быть сильно условный.

[dyak.livejournal.com]

После прямых грубых размышлений достигается именно это понимание (у меня в голове довольно скоро именно эта формулировка возникла) и биение головой об стенку начинается именно на этом этапе.

[mz1313.livejournal.com]

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

[homerist.livejournal.com]

Я в жизни не решил ни одной задачи. Несколько раз действительно серьёзно пытался, но это всегда заканчивалось серьёзной депрессией (ну, не депрессией всё же, наверное, но очень острым чувством собственной неполноценности и ненависти к себе), особенно усугубленной тем, что другие люди решали ту же задачу едва не с ходу.
И в то же время мне не кажется что я совсем уж тупой. Вот почему так? (риторический вопрос)

[ircmaan.livejournal.com]

тренироваться с детства на задачах со звездочкой и книгах Мартина Гарднера :)

[mperv.livejournal.com]

Видимо потому, что умение решать задачи - оно не врожденное, а приобретенное. И начинать лучше с чего-нибудь попроще. Например, купить какой-нибудь сборник задач с кировской ЛМШ, для не очень большого класса.

[amzin.livejournal.com]

Анатолий, у меня тупой вопрос, извините.

Вот эта фраза в условии мне непонятна: "При таких условиях казино побеждает тривиальным образом (т.к. видит выборы Алисы и Боба), поэтому на самом деле казино заранее записывает все свои выборы и они хранятся в сейфе и открываются по одному. "

Оно же таким образом не может победить в 100% случаев.

[mperv.livejournal.com]

Казино видит ход Алисы и Боба. Поэтому ничто не мешает говорить казино ход противоположный ходу Боба. Поскольку для победы Алисы и Боба требуется совпадение всех трех - то это будет победа казино. Таким нехитрым способом казино обеспечит себе 9 из 9и.

[ext-2087110.livejournal.com (from livejournal.com)]

Судя по всему, если решение есть, оно не раскладывается на несколько частей типа
"Получить 2 из 4 оставив в запасе бит информации, и потом имея один бит получить 4 из 6"
Почему я так думаю? Потому что много думал над разными вариантами из 3,4,5,6 вопросов - что мы можем получить, сколько битов информации у нас останется, и что мы могли бы получить имея биты информации.

Скажем, имея два бита информации легко получить 5 из 6.
Но нельзя расширить это на "имея три бита получить 6 из 6" т.к. 6 из 6 можно получить только имея 6 битов.
Также не получается придумать "имея два бита получить 6 из 7".

Т.е. решение судя по всему цельное, и вполне возможно, неподдается человеческому объяснению ( человеческому объяснению, например, поддается программа, которая его найдет).

[avva.livejournal.com]

См. новую запись :)

(и да, я тоже склоняюсь к этой мысли)