|
Название: 100 чел Отправлено: пачти умный от Май 10, 2013, 20:13:56 в группе из 100 человек среди любых 10 есть трое попарно знакомых. докажите, что можно выбрать 8 чел так чтобы любой другой участник группы (92 чел) будет знать хотя бы одного из них(8 чел)
Название: Re: 100 чел Отправлено: DM_ от Май 10, 2013, 20:50:33 Может хватит каждую задачу создавать во всех разделах? Если тебе ее надо помочь решить то пиши в этом разделе, если ты знаешь ответ на нее, то определи к какому разделу она относится и пиши в нем. Зачем создавать 10 тем? От этого скорость решения не увеличится, наоборот желание решать "таким людям" пропадает.
Название: Re: 100 чел Отправлено: Карвис от Июль 27, 2013, 12:33:44 Вот самый простой метод - от противного:
Допустим мы не можем выбрать восемь людей так, чтобы выполнялось условие. Это значит, что будет как минимум один человек, который не будет знать ни одного из выбранных восьми. При его замене ни любого из выбранных восьми условие не будет выполняться тоже ( по предположению о невозможности), следовательно никто из выбранных восьми и оставшегося не знает друг друга. То есть девять человек друг с другом не знакомы, либо же кто - то из оставшихся 91 чел знает лишь одного из восьмерки. Но в таком случае при выборе в десятку этих девяти человек (или вместо человека из восьмерки тот, которыйзнает лишь этого человека из восьмерки) и еще одного любого не может образоваться круг из трех знакомых, которые друг друга знают. Изначальное условие задачи нарушено, значит предположение не верно. Что и требовалось доказать. |