100 собак в хорошие руки

Почитал, с чего тема начиналась - едва не уронил скупую мужскую слезу. Думаю, пора мне задуматься о повышении качества задачек... Или эти тоже ничего?

Тут ведь вот какое дело... Качество - очень уж субъективный фактор. На мой взгляд, критерием качества является количество участников решения задачи. Пока, мягко скажем, не густо

Но, с другой стороны, уходить в глухую алгебру - тоже не дело... Так что ищем золотую середину, так сказать...

2 AmberSoler
Я про то, что за 5 нельзя и доказал: 3 операции - различные вопросы, 4тая - называние ответа. Почитайте внимательней ЭТОИ И ПРЕДЫДУЩИЙ(где перебор) пост. Не поленитесь, попробуйте понять.

Сэр hister, 4.10.2006 05:25
Почитал, с чего тема начиналась - едва не уронил скупую мужскую слезу. Думаю, пора мне задуматься о повышении качества задачек... Или эти тоже ничего?

Это мне вполне нравится
PS если вам(вместе с AmberSoler'oм) всё ещё непонятно моё решение, прошу - за Барную стойку! Практика показала, это многое решает.

Сэр St-RauS, 4.10.2006 19:22
Не поленитесь, попробуйте понять.

Не поленился:
1) *То есть, три единицы. Скажем, что совпадений нет.* А остальные варианты кто за Вас рассматривать будет. Эдак рассуждая, давайте тогда уж скажем, что совпадений 3 - вуаля, с первого хода угадал. Вай, какой я малацца!
Короче, уже на первом шаге Вы полностью убиваете общность рассуждений: во-первых, вы отталкиваетесь от того, что первый ход - непременно 111, ответ  - непременно 0, и от этого строите свое доказательство. По-моему, бред. Если уж идти от переборного доказательства, то на первом шаге как минимум нужно рассматривать 3 варианта: три x; два x и y; один x, один y, один z (тут порядок действительно несущественный). И, соотвественно, все возможные ответы: 0, 1 или 2.
2) Дальнейшие рассуждения аналогичны по своей *строгости*...

В общем, барная стойка тут ни при чем: Вас никто не просит отрисовывать на борде криволинейные интегралы, от Вас ждут просто, понятного и логичного решения. Просто покажите, что нет стратегии для гарантированного угадывания числа с 4х попыток. Как вариант можете, например, доказать, что есть такая стратегия ответов на вопросы, что после 3 ответов множество оставшихся вариантов все ще не сокращается до 1го. Или как-то по-другому. Главное, чтобы правильно было!

Сэр hister, 5.10.2006 17:31

Сэр St-RauS, 4.10.2006 19:22
Не поленитесь, попробуйте понять.

Не поленился:
1) *То есть, три единицы. Скажем, что совпадений нет.* А остальные варианты кто за Вас рассматривать будет. Эдак рассуждая, давайте тогда уж скажем, что совпадений 3 - вуаля, с первого хода угадал. Вай, какой я малацца!
Короче, уже на первом шаге Вы полностью убиваете общность рассуждений: во-первых, вы отталкиваетесь от того, что первый ход - непременно 111, ответ  - непременно 0, и от этого строите свое доказательство. По-моему, бред. Если уж идти от переборного доказательства, то на первом шаге как минимум нужно рассматривать 3 варианта: три x; два x и y; один x, один y, один z (тут порядок действительно несущественный). И, соотвественно, все возможные ответы: 0, 1 или 2.
2) Дальнейшие рассуждения аналогичны по своей *строгости*...

В общем, барная стойка тут ни при чем: Вас никто не просит отрисовывать на борде криволинейные интегралы, от Вас ждут просто, понятного и логичного решения. Просто покажите, что нет стратегии для гарантированного угадывания числа с 4х попыток. Как вариант можете, например, доказать, что есть такая стратегия ответов на вопросы, что после 3 ответов множество оставшихся вариантов все ще не сокращается до 1го. Или как-то по-другому. Главное, чтобы правильно было!

Верю, не поленились, но не поняли.
1) То, что число 111 - неважно. В предыдущем посте я написал: 1*1**1***. То есть, также, как 1*1**1*** - единицы могут обозначать разные цвета. Вот, например, давайте выкладывать карточки по разрядам: есть 3 кучи карточек. Из каждой берём по одной и получается упорядоченный набор. Теперь, если нам сначала выложили карточки произвольных цветов, напишем на них единичку. Потом, некоторые карточки убрали - заменили на новые. На замененные поставим цифры 2. Так и вырисовываются 3 случая(222 122 и 112).
2) То, что вы спрашиваете, почему 0 совпадений, значиит, сто вы не поняли основной идеи. Повторю: Игра в условии - мы выкладываем карточки, нам говорят совпадения. Мы же доказываем обратное: за 4 нельзя. Значит, игра реально такая: НАМ(то есть, ведущие мы) показывают комбинацию - мы показывают комбинацию - мы говорим кол-во совпадений. Теперь перед нами задача: Докажите, что при "перемене ролей" мы при любых действиях сопернико избирать такие количества совпадений, что после трех вопросов останется 2 числа, удовлетворяющих всему, что мы сказали до этого. Союственно, мы и говорим 0 с самого начала.

Сэр St-RauS, приношу Вам свои самые искренние извинения! Грешен, что не разобрался с самого начала в Ваших рассуждениях (:
Немного подумав, перечитав 2 последние страницы, все же понял, что Вы на самом деле предложили абсолютно точное доказательство. Поздравляю! Браво! Вы не только дали идеально правильное решение, так еще и нашли в себе достаточно здравого упорства отстоять свою идею!! Награду можете видеть в своей анкете (:

2 St-RauS

Сэр, примите также мои искренние поздравления за завершенный Вами процесс, и особенно - за Ваше "Здравое Упорство". Однако, прошу Вас все же быть аккуратнее с применением этого полезного "вторичного навыка" , а то иногда с этим бывает явный перебор - никаких хитпоинтов не хватит выдержать Ваши атаки на всех фронтах...

2 hister

Признаюсь, что ниАсилил разбор полетов, предложенный уважаемым оппонентом, а потому прошу Вас изложить краткий конспект идеи "иным языком"...

Речь идет примерно о следующем. Сэр St-RauS предложил нам некую универсальную стратегию для ведущего, согласно которой он может на наши вопросы отвечать таким образом, что трех гаданий не хватит, чтобы с четвертой попытки точно назвать число.
1 ход: всегда говорим 0.
2 ход: все зависит от количества изменившихся в числе разрядов!
- изменились все 3 разряда - отвечаем 2, тогда игрок за оставшийся 1 ход никак не определяет тройку всю тройку (т.е., фактически, произошел переход к случаю, когда у вас 3 разряда, в каждом по 2 возможных варианта, просто исключая первый названный - при ответе 2 за один ход вы не угадаете числа и их порядок).
- изменились 2 разряда - отвечаем 1, тогда игроку за одно гадание надо определить, какое из изменившихся чисел на своем месте, какое должно быть на месте второго, и какое должно быть на месте нетронутого (т.е. надо угадать (2 из двух) + (1 из двух) - несвязанные друг с другом первым ответом, попытавшись на третий ход "дернуть" первое число и двойку, получите ответ 2, и не будете знать, то ли вы в первом разряде угадали, то ли в двойке, а если не "дернуть" - тем более заведомо что-то останется неразгаданным).
- изменился 1 разряд - отвечаем 0, тогда игрок знает только значение в этом передернутом разряде (оставшееся из 3х возможных значений для этого разряда - как в Вашем алгоритме) и то, что в оставшихся по одному варианту не годятся - т.е. за 1 гадание ему предстоит полностью разгадать 2 из 2х - этого не сделать (для случая 2 из 2х ответ "1" ставит игрока в тупик: числа + порядок).

Вот, примерно, так. Боюсь, манера объяснения сэра St-RauS'a оказалась заразительной ((: Просто попробуйте "поиграться" так против себя же по этой стратегии - сразу поймете все, что неудачно выражено словами (: Т.е. сэр St-RauS придумал стратегию антиигры за ведущего и показал, что 3 хода не дают игроку полной картины, чтобы с 4го точно угадать число.

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

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

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

Так что всем - по бокалу!  

Спасибо за понимание! hister выше всё верно изложил. Все эти штучки с 111 122 112 и 222 были лишь для удобности перебора. Рекомендую использовать и не только здесь - помогает.
PS. К вечеру напишу сюда задачу, увы только на 50. Нало ещё в турниры играть.
PPS. Поздравим тогда уж, и обделённого некогда поздравлениями упорного сэра Kulti. Он превзошёл то, что было сеёчас.

Простите за опоздание. Я заказал атрибуты, денег нет пока. Потом, когда появятся, дам 50@ победителю.
ЗАДАЧА:
На 100 мужиков одевают колпаки двух цветов. Каждый видит все колпаки, кроме своего. Каждый, не сговариваясь, пишет цвет, какой он думает на нем. Какое максимальное количество совпадений можно получить гарантировано(У меня есть свой пример. Ответы меньше него не считаются. Выигрывает предложивший стратегию для наибольшего кол-ва. В случае равенства кол-ва, но разных стратегий приз отдается тому, кто докажет минимальность, хотя я этого сам не знаю. Если не будет такого - как-нибудь разберемся).
Приз будет потом - денег сейчас нет.

Может я чего не понял... Но какая тут может быть "гарантированность", если участники не общаются между собой?.. Нет обмена информацией, значит нет связи между событиями. Какая может быть здесь стратегия?

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

За исключением одного единственного случая: 99+1 (распределение по цветам).

Тогда тот, кто видит все колпаки одного цвета и, заранее зная, что цветов должно быть два, уверенно назовет свой цвет... Но и то не факт!

Поправьте, если я не уловил идею...

Сэр AmberSoler, 7.10.2006 21:52
Может я чего не понял... Но какая тут может быть "гарантированность", если участники не общаются между собой?.. Нет обмена информацией, значит нет связи между событиями. Какая может быть здесь стратегия?

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

За исключением одного единственного случая: 99+1 (распределение по цветам).

Тогда тот, кто видит все колпаки одного цвета и, заранее зная, что цветов должно быть два, уверенно назовет свой цвет... Но и то не факт!

Поправьте, если я не уловил идею...

Они могут ИЗНАЧАЛЬНО договорится, кто в зависимости от чего, что он видит что пишет. Сратегия есть.

На 100 мужиков одевают колпаки двух цветов.

Сразу вопрос, колпаки делятся поровну (50+50) или произвольно (х+у)?

Если поровну и :

Они могут ИЗНАЧАЛЬНО договорится

то самая простая стратегия - они все договорятся писать одинаковый цвет, тогда совпадений будет ровно половина

А вообще желательно чётче формулировать условие.

Сэр St-RauS, 7.10.2006 21:41
...Каждый, не сговариваясь, пишет цвет, какой он думает на нем.

Сэр St-RauS, 7.10.2006 22:32
Они могут ИЗНАЧАЛЬНО договорится, кто в зависимости от чего, что он видит что пишет. Сратегия есть.

Начинается старая песня... Думаем одно, пишем другое, потом не понимаем кто чего недопонял, да? Термин "не сговариваясь" эквивалентен понятию "не сговариваясь ЗАРАНЕЕ", потому что "сговариваться в процессе игры" нельзя по определению значения слова. Хорошо, будем считать - уточнили...

Сэр Zin, 7.10.2006 23:03
Сразу вопрос, колпаки делятся поровну (50+50) или произвольно (х+у)?

Думаю, решать нужно в общем виде - (х+у). А 50/50 будет частным случаем общего решения...

Сэр AmberSoler, 7.10.2006 23:22

Сэр St-RauS, 7.10.2006 21:41
...Каждый, не сговариваясь, пишет цвет, какой он думает на нем.

Сэр St-RauS, 7.10.2006 22:32
Они могут ИЗНАЧАЛЬНО договорится, кто в зависимости от чего, что он видит что пишет. Сратегия есть.

Начинается старая песня... Думаем одно, пишем другое, потом не понимаем кто чего недопонял, да? Пока условие задачи некорректно, я опасаюсь, что Вы не все обозначили в условии...

Сэр Zin, 7.10.2006 23:03
Сразу вопрос, колпаки делятся поровну (50+50) или произвольно (х+у)?

Думаю, решать нужно в общем виде - (х+у). А 50/50 будет частным случаем общего решения...

1) Я имел ввиду, что они могут договорится, по какому алгоритму пишут(Например: Вот ты пишешь тот же цвет, что у него)
Но ничего после друг другу не говорят(наприме, нет такого: Вот на тебе красный колпак(я вижу), а на тебе синий)
2) Естественно, для х+у.

PS 2hister
Я приятно удивлен ангелочком, но не встречал более сложной задачи, чем расшифровать подпись. Вы не можете дать авторский ответ? Или может как задачу сюда дать: кто придумает наиболее правдоподобно

Сэр St-RauS, 7.10.2006 23:31
Я приятно удивлен ангелочком, но не встречал более сложной задачи, чем расшифровать подпись.

Поздравляю с первым заслуженным боевым знаком отличия!

Сэр St-RauS, 7.10.2006 23:31
Вы не можете дать авторский ответ? Или может как задачу сюда дать: кто придумает наиболее правдоподобно

Один из наиболее правдоподобных ответов:

Уважаемого Галилео Галилея инквизиторы жгли заживо на костре. И делали они это только за то, что он доказывал неприемлемый в те времена факт вращения Земли. Он, конечно же, на всякий случай отрекся от своих заявлений и признал, что ошибся...

Но когда уходил из офиса Святой Инквизиции - (до чего же упорный монстр был! ) - заявил:
"И все-таки она вертится!"

Ну как, неплохо придумал?...

2 hister: Браво!

2Kulti
Можно использовать лишь то, что видишь, то есть, цвета других(не написанные, а реальные).

Сэр St-RauS, 8.10.2006 00:35
2Kulti
Можно использовать лишь то, что видишь, то есть, цвета других(не написанные, а реальные).

Праально! Так ему! А то в яндексе нашел ответ - и улыбается (:
А вообще не вижу никакого подвоха, все предельно просто...
Короче, вот что с ходу пришло в голову:
1. Мы имеем набор из совершенно отдельно взятых мужиков, которые вообще не имеют ничего кроме своей заранее придуманной стратегии и знания чужих цветов. Т.е. они не имеют доступа ни к информации об ответах других мужиков, и вообще ни о чем кроме выше описанного.
2. В такой ситуации вижу единственным целесообразным подходом тупо писать тот цвет, который преобладает вокруг (больше белого - писать белый, больше черного - черный). Очевидно, так мы гарантированно получим как минимум 50 совпадений. Причем, если я правильно понял условие задачи, то это будет максимальное гарантированное число совпадений.
Доказательство максимальности:
- рассмотрим случай, когда им надели по 50 колпаков каждого цвета
- каждый мужик тогда видит 49 колпаков одного цвета, и 50 другого
- не ограничивая общности рассуждений, можно считать, что мужики пишут цвета поочереди
- очевидно, если есть стратегия антиигры, позволяющая 50 раз отвергнуть ответ, то это и есть доказательство
- а она есть - просто первым 50-и мужикам сказать нет - мы это можем сделать, посколько на первые 50 ходов нам гарантировано хватает каждого цвета!

PS: Вообще все абсолютно очевидно, но я старался писать предельно *математично* ((:

Сэр hister, 8.10.2006 01:38
...вижу единственным целесообразным подходом тупо писать тот цвет, который преобладает вокруг (больше белого - писать белый, больше черного - черный)...

Хотел написать примерно тоже самое, но показалось, что это слишком просто. Кстати пара замечаний:

Очевидно, так мы гарантированно получим как минимум 50 совпадений.

На самом деле минимум 51 совпадение (в случае 50+50, не угадает никто), а максимум 99 (если будет 99+1 колпаков)

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

Сэр Zin, 8.10.2006 02:42
Они заранее договариваются, что, после того, как им оденут колпаки, они соберуться в одну группу. Затем из группы выходит один колпак, к нему выходит другой, третий смотрит на них и если колпаки одинакового цвета то тоже подходит к ним, и так до тех пор пока к первой группе не подойдет колпак другого цвета...

Это уже обмен информацией: "Я к Вам подошел потому, что у вас колпаки одинакового цвета. Посмотри на колпак соседа, если я к вам подошел, значит у тебя цвет такой же..." Нарушение условия...

Про сэра Zin'a справедливо сказал сэр AmberSoler.
2hister. Zin сказал уже, что если одето 50-50, то по вашей стратегии не угадает никто. Хотя у меня есть стратегия такая, что угадает 50 человек.

Сэр St-RauS, 8.10.2006 09:58
Про сэра Zin'a справедливо сказал сэр AmberSoler.
2hister. Zin сказал уже, что если одето 50-50, то по вашей стратегии не угадает никто. Хотя у меня есть стратегия такая, что угадает 50 человек.

Ок. Оставляем все как было, только дополнительная договоренность: если видим 49+50 (т.е. есть опасность 50/50 ситуации), то все называем цвет как у вон того парня, а он сам называет цвет, который видит в меньшинстве.
После этого дополнения алгоритм дает гарантированных 50 колпаков без проблем ((:

Видите ли, тогда непонятно, кто есть тот парень. Если 50-50, то все видят 49-50, и тогда все ОК. Но если 49-51, то 1 види 49-50. Непонятно, что тогда будет.

Согласен - ошибся. Надо думать...

Сэр AmberSoler, 8.10.2006 07:07
Это уже обмен информацией: "Я к Вам подошел потому, что у вас колпаки одинакового цвета. Посмотри на колпак соседа, если я к вам подошел, значит у тебя цвет такой же..." Нарушение условия...

Ну так это понятно , я ж поэтому и написал "если допустить..."

И всё таки, Сэр St-Raus, могут ли колпаки собираться в группы, или они сидят на стульях в хаотичном порядке и перемещаться не могут?

Если могут (при этом соблюдая условие, что никак вообще не будут даже намекать другим ни на что), то у меня, кажется, есть стратегия дающая гарантированно минимум 50 угаданных колпаков.

В том и дело, что обмен информацией после того как надели колпаки невозможен...

Сэр hister, 9.10.2006 03:55
В том и дело, что обмен информацией после того как надели колпаки невозможен...

В моей стратегии никакого обмена информацией не будет. Она основана на предварительной договорённости и на подсчете количества колпаков в заранее(до того как колпаки надели) составленных группах.

Напишите мне решение по личке. А вообще, можете считать, что они с компьютерами сидят в разных камерах и компьютер показывает им цвета остальных. Так вам проще понять?