Черная кошка
Гений-Говорун
Offline
Сообщений: leet
СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215
я не ангел, но ведь и жизнь- не рай.
|
|
� : Май 12, 2011, 15:38:58 � |
|
За круглым столом сидит компания из тридцати человек. Каждый из них либо дурак, либо умный. Всех сидящих спрашивают: «Кто ваш сосед справа — умный или дурак?» В ответ умный говорит правду, а дурак может сказать как правду, так и ложь. Известно, что количество дураков не превосходит F. При каком наибольшем значении F всегда можно, зная эти ответы, указать на умного человека в этой компании?
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #1 : Май 12, 2011, 17:03:58 � |
|
Интересная задача. И актуальная, да.
Пятнадцать дураков заведомо много. Дальше буду решать по возвращении с пьянки)
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #2 : Май 12, 2011, 18:27:34 � |
|
Ага, десяти дураков тоже многовато. Пьянка отменилась =(
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Валерий
Гений-Говорун
Offline
Сообщений: 1395
СПАСИБО
-вы поблагодарили: 157
-вас поблагодарили: 234
|
|
� Ответ #3 : Май 12, 2011, 19:03:17 � |
|
Думаю, что должно быть 7, что бы если и дураки скажут дурак, то сумма ответов не превысила половины общей суммы ответов.
Но это пока бездоказательно.
|
|
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #4 : Май 12, 2011, 19:07:09 � |
|
Ставлю свои любимые носки, что 9. Сейчас попью чайку и формализую.
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #5 : Май 12, 2011, 19:22:59 � |
|
точно меньше чем 10. если дураками будет назван каждый 6-й будет неопределенность. оставшимися 4-мя может быть любая четверка подряд между двумя которых назвали дураками.
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #6 : Май 12, 2011, 19:33:11 � |
|
в случае если не более 9 умный гарантированно будет тот кто последний в самой длинной цепочке из тех кто назван умным
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #7 : Май 12, 2011, 19:42:47 � |
|
moonlight, да, это именно то, что я написал бы, если бы мне не было лень. А вот как строго доказать последнее утверждение?
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #8 : Май 12, 2011, 19:46:28 � |
|
я думаю что у тебя оно уже есть в более готовом виде так что давай своё доказательство, я смогу позже.
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #9 : Май 12, 2011, 19:50:27 � |
|
В том-то и проблема - пока что как собака. Всё чувствую, а сказать не могу.
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #10 : Май 12, 2011, 20:06:22 � |
|
А вот нет, кстати. Есть контрпример для девяти. Я проспорил свои любимые носки. Хотя, видимо, придумав этот контрпример, я сам их у себя и выиграл, ня.
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #11 : Май 12, 2011, 20:26:44 � |
|
Итак, доказательство.
Рассадим 8 дураков и 22 умных людей за стол. При этом образуется N<=8 серий из подряд сидящих умных (и, соответственно, подряд сидящих дураков). Мы их спрашиваем, они нам отвечают. Теперь мы хотим доказать, что последний умный человек в самой длинной серии умных людей незаменяем. Докажем от противного.
Чтобы рассадить компанию иначе, нам нужно несколько дураков поменять местами с умными людьми. Чтобы заменить дураком последнего умного человека в серии, нам нужно заменить и остальных умных людей в серии - по очевидным причинам. Откуда ж мы возьмём столько дураков? Мы не можем заменять умными людьми дураков, сидящих в начале серии - иначе умный человек перед ними изменил бы ответ. Единственное исключение - если мы этого умного человека тоже заменяем дураком. Таким образом, для подмены самой длинной серии умных людей дураками мы можем взять одного дурака из начала последующей серии дураков, а остальных - из "хвостов" дураковых серий. Нетрудно подсчитать, что всего дураков, НЕ первых в своих сериях, будет 8-N. Соответственно, самая длинная серия умных людей должна быть не длиннее 9-N. С другой стороны, по принципу Дирихле найдётся серия умных людей не короче 22/N. Получаем неравенство: 22/N<=9-N. Тупым перебором доказываем, что для N от 1 до 8 неравенство не выполняется. Контрпример для девяти: умных людей рассаживаем семью группами по 3, между этими группами - дураков произвольным образом. Всех дураков заставляем отвечать, что сосед справа умный. У нас получается два "мобильных" дурака в хвостах серий; любая серия умных может быть заменена с помощью этих двух дураков и ещё одного дурака сразу после этой серии.
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Леший
Гений-Говорун
Offline
Сообщений: 1737
СПАСИБО
-вы поблагодарили: 552
-вас поблагодарили: 595
|
|
� Ответ #12 : Май 12, 2011, 22:30:36 � |
|
В ответ умный говорит правду, а дурак может сказать как правду, так и ложь.
Я один считаю, что дураков и умных в условие надо поменять местами?
|
Я слышу, как крабы стучат по стеклу молотками, наверное с нами случилась беда
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #13 : Май 12, 2011, 22:46:59 � |
|
Таки нет)
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Лев
Из мудрейших мудрейший
Offline
Сообщений: 2906
СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166
Искренне Ваш...
|
|
� Ответ #14 : Май 13, 2011, 09:11:27 � |
|
В ответ умный говорит правду, а дурак может сказать как правду, так и ложь.
Я один считаю, что дураков и умных в условие надо поменять местами? Просто указанная фраза ложь - все на своих местах
|
|
|
Записан
|
В действительности все не так, как на самом деле
|
|
|
|