?

Log in

ааааа - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

ааааа [окт. 8, 2013|12:14 am]
Anatoly Vorobey
Второй день не сплю, не ем, думаю только об этой задаче. Хожу как зомби. Все перепробовал. Ничего не выходит. В уме, на бумаге, на компьютере.

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

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

Update: AAAAAAAAAAAAAAAAAAAAAA!
СсылкаОтветить

Comments:
[User Picture]From: mperv
2013-10-07 10:20 pm
Да, задача хорошая и, видимо, не очень простая. Хотя решивших не так уж и мало. Самое... ммм... вдохновляющее, что есть способ сделать 6 из 10-и и при этом останется один бит информации неизрасходованным. И на бесконечности 2/3 правильных ответов таки достигается.
(Ответить) (Thread)
[User Picture]From: avva
2013-10-08 05:20 am
Я, кстати, могу сделать 7/10 на бесконечности.

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

Edited at 2013-10-08 05:49 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: alex_levit
2013-10-08 06:35 am
Я узнал об этой задаче (бесконечный случай) лет 5-6 назад. Помню, что можно сделать чуть лучше чем 4/5, но 5/6 уже не выйдет.
(Ответить) (Parent) (Thread)
[User Picture]From: m2b
2013-10-07 10:30 pm
А сама задача/её авторы/те, кто опубликовали/те, по чьим мотивам она появилась - все они или кто-то из них вас случайно ли не затроллили этой задачей всего-навсего?
(Ответить) (Thread)
[User Picture]From: mperv
2013-10-08 08:12 am
Ну раньше за этим сайтиком такого не наблюдалось.
(Ответить) (Parent) (Thread)
[User Picture]From: m2b
2013-10-08 11:36 am
Я подразумевал в более широком смысле.
Кроме сайта и текста задачи существуют, например, обстоятельства, при которых обращаешь на ту или иную вещь внимание.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-10-08 12:01 pm
Не, это невероятно.
(Ответить) (Parent) (Thread)
[User Picture]From: bortans
2013-10-07 11:14 pm
В прошлом веке я примерно так же мучался с задачей о 12 монетах (одна фальшивая, отличается по весу, неизвестно в какую сторону, надо ее найти за 3 взвешивания на весах-разновесах). И тогда было еще хуже, не было интернета и не у кого было узнать :)
(Ответить) (Thread)
[User Picture]From: southwest
2013-10-08 12:43 am
Я примерно начинаю понимать, как решать. Увы, без компьютера может не обойтись. Я понял, что надо решить задачу попроще: где они побеждают в 3-х партиях из пяти.
Это тоже далеко не тривиально, но и не сложно.
Вот моё решение задачи 3 из 5 (убрать пробелы):
pastebin . com / 0qRhk8CD
Там в конце оказывается некоторое совпадение, которое
надо обобщить на случай из 9 раундов.
(Ответить) (Thread)
From: ext_2087110
2013-10-08 01:10 am
Не читал ваше решение, но для 3 из 5 можно придумать стратегию в одну строчку. Так что не очень понял смысл в вашем решении.
Собственно первым ходом Боб говорит какой символ чаще встречается в битах с 2-го по 4-й, и далее Алиса так и играет. Если один раз Алиса ошибется, то Боб здесь кодирует ответ на 5-й вопрос.

Edited at 2013-10-08 01:13 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: southwest
2013-10-08 01:29 am
классно, у вас гораздо короче получилось )

смысл может быть лишь в том, если оно обобщаемо на 9 битов, я об этом буду думать
(Ответить) (Parent) (Thread)
[User Picture]From: dyak
2013-10-08 05:50 am
Ну да, это и есть решение для пяти из девяти: первый дает в след. шести как минимум три, плюс еще два закодированы в ошибках.

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

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

Edited at 2013-10-08 05:53 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: southwest
2013-10-08 05:58 am
это всё понятно, если разные возможности получить пять из 9
даже 5 из восьми легко

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

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

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


Edited at 2013-10-08 06:00 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: dyak
2013-10-08 06:27 am
А ну да. Щас напишу у себя.
(Ответить) (Parent) (Thread)
[User Picture]From: dyak
2013-10-08 06:35 am
Нет, не получается :(
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2013-10-08 07:00 am
Мы знаем, что Алиса первым ходом всегда говорит 0. Тогда мы имеем или 1 угадывание плюс эти самые 5 из 8, или 1 дополнительный бит информации плюс как минимум 5 из 8. Как сформулировать алгоритм, гарантирующий 6 угадываний, на ночь глядя не соображу, но судя по формулировке на сайте, он должен быть сильно условный.
(Ответить) (Parent) (Thread)
[User Picture]From: dyak
2013-10-08 03:39 pm
После прямых грубых размышлений достигается именно это понимание (у меня в голове довольно скоро именно эта формулировка возникла) и биение головой об стенку начинается именно на этом этапе.
(Ответить) (Parent) (Thread)
[User Picture]From: mz1313
2013-10-08 08:30 am
Собственно, это решение для 5 из 8. Девятый тут никак не участвует. Но не видно, как модифицировать это решение, чтобы передать доп. информацию.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: ircmaan
2013-10-08 07:18 am
тренироваться с детства на задачах со звездочкой и книгах Мартина Гарднера :)

Edited at 2013-10-08 07:19 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: mperv
2013-10-08 08:10 am
Видимо потому, что умение решать задачи - оно не врожденное, а приобретенное. И начинать лучше с чего-нибудь попроще. Например, купить какой-нибудь сборник задач с кировской ЛМШ, для не очень большого класса.
(Ответить) (Parent) (Thread)
[User Picture]From: amzin
2013-10-09 08:55 am
Анатолий, у меня тупой вопрос, извините.

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

Оно же таким образом не может победить в 100% случаев.
(Ответить) (Thread)
[User Picture]From: mperv
2013-10-09 09:22 am
Казино видит ход Алисы и Боба. Поэтому ничто не мешает говорить казино ход противоположный ходу Боба. Поскольку для победы Алисы и Боба требуется совпадение всех трех - то это будет победа казино. Таким нехитрым способом казино обеспечит себе 9 из 9и.
(Ответить) (Parent) (Thread)
From: ext_2087110
2013-10-09 01:50 pm
Судя по всему, если решение есть, оно не раскладывается на несколько частей типа
"Получить 2 из 4 оставив в запасе бит информации, и потом имея один бит получить 4 из 6"
Почему я так думаю? Потому что много думал над разными вариантами из 3,4,5,6 вопросов - что мы можем получить, сколько битов информации у нас останется, и что мы могли бы получить имея биты информации.

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

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




Edited at 2013-10-09 13:51 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2013-10-09 02:09 pm
См. новую запись :)

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