|
👍 0 👎 |
Люди добрае помогите пожалуйстаСреди 9 мушкетеров некоторые поссорились и вызвали друг друга на дуэль. Докажите, что если среди низ нет трех которые должны драться друг с другом, то среди мушкетеров найдутся четверо друзей.
иискал в нете нигде нету
математика обучение
алексеев игорь
|
|
👍 0 👎 |
Переведем задачу на язык теории графов. Надо доказать, что в любом неориентированном графе с 9 вершинами, в котором нет циклов из трех вершин, найдутся 4 вершины, среди которых никакие две не соединены ребром. Будем рассуждать от противного. Надо доказать, что если нет циклов из трех вершин и среди любых четырех вершин две соединены ребором, то такого графа не бывает.
1. Пусть максимальная степень вершины в графе больше трех. Тогда рассмотрим вершину и инцидентные ей. Их будет больше трех, не меньше 4. Берем любые 4 из них, между ними есть ребро — вот он цикл длины три. 2. Пусть максимальная степень вершин не больше 3. Покажем, что если есть вершина со степенью меньше 3 (0, 1 или 2), то найдется цикл длины три. Пусть есть вершина А степени 2. У нее есть две соседних В, С. Остается 6 вершин, не соединенных с А. Возьмем четверку, содержащую А и какие-то три вершины из тех шести. А не соединено ни с одной вершиной из тех шести, поэтому среди каждых трех вершин из тех шести найдутся две, соединенные ребром. Несложно показать, что в этом случае степени каждой из тех шести вершин равны трем, поэтому они никак не могут быть соединины с В и С. Противоречие. 3. Для вершины степени 1 и изолированной вершины получится точно такой же результат. Поэтому изначальное предположение не верно и среди всех девяти вершин найдутся четыре, между которыми не будет ребер, то есть найдутся четверо друзей. (ответ не мой, а tsupkov!) |
|
👍 0 👎 |
Квадратичная форма
|
|
👍 +1 👎 |
Помогите пожалуйста решить задачу!
|
|
👍 0 👎 |
Уравнение прямой
|
|
👍 0 👎 |
Алгебра 10 класс помогите пожалуйста спасите мое положение выручайте люди умные!!
|
|
👍 +1 👎 |
Не понимаю значения тригонометрического выражения sinx*cosx
|
|
👍 0 👎 |
Задача про 9 мушкётеров
|