Comments | janatem: (без темы)

janatem

(Untitled)

Oct 14, 2008 17:24

Набрел вот на несколько задачек: http://inkogniton.livejournal.com/34312.html

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

Казино объявляет о новой игре ( Read more... )

математика, задача

Comments 6

inkogniton October 14 2008, 15:00:44 UTC

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

biglebowsky January 8 2009, 16:00:29 UTC

С огромнейшим интересом прочитал Ваше решение. Очень понравилось!
Обязательно поставлю ссылку на Ваш post в своем блоге, но не сейчас, а чуть позже.

biglebowsky January 8 2009, 16:16:19 UTC

Я не совсем понял Вашу фразу "не смог за разумное время построить стратегию для N=7".
Стратегия же у Вас изложена. Или следует понимать буквально - Вы не уложились в 1 час, упомянутый inkogniton ?

janatem January 9 2009, 12:32:36 UTC

Из 2б (которое доказано) явно никак не следует 2а (существование нужной стратегии). А "построение стратегии для N=7", изложенное в самом конце, не содержит доказательства. И нужно изрядно повозиться, чтобы аккуратно всё выписать; я этого не делал. ;)

biglebowsky January 9 2009, 13:17:19 UTC

Я являюсь среднестатистическим читателем. Когда я смотрел Ваше доказательство, у меня сложилось впечатление, что все объяснено (для N=7). Дело в том, что не указанные в явной форме логические ходы домысливаются автоматически:

1)Набор индексов "черных вершин" - действительно правильный. Они ведь все отстоят друг от друга не менее, чем на 3 бита.

2) Алгоритм действия игроков тоже ясен:
- Распечатать 7 копий набора "черных вершин".
- Игрок пытается понять, мысленно варьируя цвет собственной шляпы, не может ли наблюдаемая ситуация являться "черной вершиной".
- Если да, то называет цвет, противоположный "черной вершине".
- Если нет, воздерживается от хода.

biglebowsky March 2 2009, 03:06:42 UTC

У меня в журнале toroboan привел еще один алгоритм решения http://biglebowsky.livejournal.com/23346.html