Страниц: [1] 2
  Печать  
Автор Тема: стол  (Прочитано 5205 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Черная кошка
Гений-Говорун
*
Offline Offline

Сообщений: leet

СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215


я не ангел, но ведь и жизнь- не рай.


Просмотр профиля
: Май 12, 2011, 15:38:58 �

 За круглым столом сидит компания из тридцати человек. Каждый из них либо дурак, либо умный. Всех сидящих спрашивают: «Кто ваш сосед справа — умный или дурак?» В ответ умный говорит правду, а дурак может сказать как правду, так и ложь. Известно, что количество дураков не превосходит F. При каком наибольшем значении F всегда можно, зная эти ответы, указать на умного человека в этой компании?

Эти пользователи сказали вам СПАСИБО :

Лев

За это сообщение 1 пользователь сказал спасибо!
Записан

//текст доступен после регистрации//
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #1 : Май 12, 2011, 17:03:58 �

Интересная задача. И актуальная, да.

Пятнадцать дураков заведомо много. Дальше буду решать по возвращении с пьянки)

Эти пользователи сказали вам СПАСИБО :

Черная кошка

За это сообщение 1 пользователь сказал спасибо!
Записан

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 Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #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 Offline

Сообщений: 1395

СПАСИБО
-вы поблагодарили: 157
-вас поблагодарили: 234



Просмотр профиля
Ответ #3 : Май 12, 2011, 19:03:17 �

Думаю, что должно быть 7, что бы если и дураки скажут дурак, то сумма ответов не превысила половины общей суммы ответов.

Но это пока бездоказательно.
Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #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 Offline

Сообщений: 741

СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232


Просмотр профиля Email
Ответ #5 : Май 12, 2011, 19:22:59 �

точно меньше чем 10. если дураками будет назван каждый 6-й будет неопределенность. оставшимися 4-мя может быть  любая четверка подряд между двумя которых назвали дураками. 
Записан

Зачем откладывать на завтра то, что можно отложить на послезавтра?
moonlight
Умник
****
Offline Offline

Сообщений: 741

СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232


Просмотр профиля Email
Ответ #6 : Май 12, 2011, 19:33:11 �

в случае если не более 9 умный гарантированно будет тот кто последний в самой длинной цепочке из тех кто назван умным
Записан

Зачем откладывать на завтра то, что можно отложить на послезавтра?
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #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 Offline

Сообщений: 741

СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232


Просмотр профиля Email
Ответ #8 : Май 12, 2011, 19:46:28 �

я думаю что у тебя оно уже есть в более готовом виде так что давай своё доказательство, я смогу позже.
Записан

Зачем откладывать на завтра то, что можно отложить на послезавтра?
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #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 Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #10 : Май 12, 2011, 20:06:22 �

А вот нет, кстати. Есть контрпример для девяти. Я проспорил свои любимые носки. Хотя, видимо, придумав этот контрпример, я сам их у себя и выиграл, ня.

Эти пользователи сказали вам СПАСИБО :

Илья

За это сообщение 1 пользователь сказал спасибо!
Записан

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 Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #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 Offline

Сообщений: 1737

СПАСИБО
-вы поблагодарили: 552
-вас поблагодарили: 595



Просмотр профиля
Ответ #12 : Май 12, 2011, 22:30:36 �

В ответ умный говорит правду, а дурак может сказать как правду, так и ложь.

Я один считаю, что дураков и умных в условие надо поменять местами?

Эти пользователи сказали вам СПАСИБО :

Sirion

За это сообщение 1 пользователь сказал спасибо!
Записан

Я слышу, как крабы стучат по стеклу молотками, наверное с нами случилась беда
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #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 Offline

Сообщений: 2906

СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166


Искренне Ваш...


Просмотр профиля Email
Ответ #14 : Май 13, 2011, 09:11:27 �

В ответ умный говорит правду, а дурак может сказать как правду, так и ложь.

Я один считаю, что дураков и умных в условие надо поменять местами?


Просто указанная фраза ложь - все на своих местах Smiley
Записан

В действительности все не так, как на самом деле
Страниц: [1] 2
  Печать  
 
Перейти в: