Страниц: [1]
  Печать  
Автор Тема: 100 чел  (Прочитано 4233 раз)
0 Пользователей и 1 Гость смотрят эту тему.
пачти умный
Новенький
*
Offline Offline

Сообщений: 24

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


Просмотр профиля
: Май 10, 2013, 20:13:56 �

в группе из 100 человек среди любых 10 есть трое попарно знакомых. докажите, что можно выбрать 8 чел так чтобы любой другой участник группы (92 чел) будет знать хотя бы одного из них(8 чел)
Записан
DM_
Давненько
**
Offline Offline

Сообщений: 68

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

237458
Просмотр профиля
Ответ #1 : Май 10, 2013, 20:50:33 �

Может хватит каждую задачу создавать во всех разделах? Если тебе ее надо помочь решить то пиши в этом разделе, если ты знаешь ответ на нее, то определи к какому разделу она относится и пиши в нем. Зачем создавать 10 тем? От этого скорость решения не увеличится, наоборот желание решать "таким людям" пропадает.
Записан

Карвис
Новенький
*
Offline Offline

Сообщений: 5

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


Просмотр профиля
Ответ #2 : Июль 27, 2013, 12:33:44 �

Вот самый простой метод - от противного:
Допустим мы не можем выбрать восемь людей так, чтобы выполнялось условие. Это значит, что будет как минимум один человек, который не будет знать ни одного из выбранных восьми. При его замене ни любого из выбранных восьми условие не будет выполняться тоже ( по предположению о невозможности), следовательно никто из выбранных восьми и оставшегося не знает друг друга. То есть девять человек друг с другом не знакомы, либо же кто - то из оставшихся 91 чел знает лишь одного из восьмерки. Но в таком случае при выборе в десятку этих девяти человек (или вместо человека из восьмерки тот, которыйзнает лишь этого человека из восьмерки) и еще одного любого не может образоваться круг из трех знакомых, которые друг друга знают. Изначальное условие задачи нарушено, значит предположение не верно. Что и требовалось доказать.
Записан
Страниц: [1]
  Печать  
 
Перейти в: