Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 66
Текст из файла (страница 66)
Таким образом построена убывающая последовательность длины п + 1. П ПРИМЕР 8.84. Предположим, что в комнате находятся шесть человек, и каждые два из них либо друзья, либо враги. Тогда есть три человека, которые дружат между собой, или есть три человека, которые враждуют между собой. Выберем одного человека, назовем его А и поставим в середине комнаты. Разместим всех его врагов вдоль южной стены, а всех друзей — вдоль северной стены. Согласно части (а) сильной формы принципа клеток либо не менее трех человек стоят вдоль южной стены, либо не менее трех человек стоят у северной стены. Если у южной стены стоит не менее трех человек, то или трое из них — взаимные друзья, что и требовалось доказать, или двое из них — враги. Тогда эти люди вместе с А— трое взаимных врагов.
Аналогично, если не менее трех человек стоят у северной стены, то или трое из них — взаимные враги, что и требовалось доказать, или двое из них — друзья. Тогда они вместе с А — трое взаимных друзей. П Рассмотренный выше пример является характерным, хотя и довольно простым примером задач из раздела комбинаторики, который носит название теория Рамсея. Можно считать, что нам повезло, поскольку в теории Рамсея очень мало простых примеров. Почти все ее проблемы по сей день не решены. Поясним теорию Рамсея на примере полного графа с раскрашенными ребрами.
Предположим, что в предыдущем примере вершины графа — аналоги людей. Образуем граф следующим образом: если двое людей — друзья, то соответствующие им вершины соединяет красное ребро. Если двое людей — враги, то соответствующие вершины соединяет синее ребро. Поскольку каждые двое — либо друзья, либо враги, то ребро существует между двумя любыми вершинами графа. Следовательно, этот граф — граф Кв, полный граф с шестью вершинами. В рассмотренном выше примере, утверждалось, что если все ребра графа Кв раскрашены либо красным, либо синим цветом, то в графе Кв имеется либо красный треугольник, либо синий треугольник, каждый из которых является подграфом графа Кв, по сути, просто графом Кз.
Граф Кз не обладает таким свойством, что если его ребра раскрашены либо красным, либо синим цветом, то он содержит красный или синий подграф Кз. Это доказывает граф, изображенный на рис. 8.!3, где пунктиром изображены красные ребра, а синей линией — синие ребра. Рис. 8.13 РАЗДЕЛ В.В. Принцип клеток 367 Теперь дадим определение свойства Рамсея для двух цветов на примере графов. Существует обобщение свойства Рамсея для произвольного числа цветов.
ОПРЕДЕЛЕНИЕ 8.85. Полный граф К„обладает (р,о) свойством Рамсел, если в случае, когда он раскрашен двумя цветами, например, красным и синим, он содержит либо подграф Кр с красными ребрами, либо подграф Кч с синими ребрами. ОПРЕДЕЛЕНИЕ 8.86. Число Рамсел, Н(р,Ч) — это наименьшее число п такое, что граф К„имеет (р,о) свойство Рамсея. Вполне очевидно, что В(р,о) = В(д,р), поскольку можно заменить красный цвет на синий, а синий — на красный. Также, если гп > В(р, о) = и, то, поскольку ʄ— подграф графа К, граф К также обладает свойством Рамсея. Относительно чисел Рамсея будут доказаны только две теоремы. Эти теоремы интересны сами по себе, но более важным является то, что они доказывают существование чисел Рамсея.
ТЕОРЕМА 8.87. Для всех р > 2 Ир, 2) = В(2, р) = р. ДОКАЗАТЕЛЬСТВО. Рассмотрим граф Кр. Если одно ребро раскрашено красным (или синим) цветом, то существует красный (или синий) граф Ка. Если нет, тогда все ребра раскрашены синим (красным ) цветом, и мы получаем синий (красный) граф Кр. ТЕОРЕМА 8.88.
(Эрдош и Шекерес) Для всех р, д > 3 Л(р,й < Л(р — 1,Ч)+Л(р,1 — 1). ДОКАЗАТЕЛЬСТВО. Предположим, что К вЂ” полный граф, имеющий Л(р — 1, о)+ Л(р, д — 1) вершин, ребра которого раскрашены в красный или синий цвет. Пусть о — выбранная вершина графа К. Пусть )У вЂ” полный подграф графа К, вершины которого Ъу связаны с вершиной о красным ребром. Пусть 5 — полный подграф графа К, вершины которого )гз связаны с вершиной о синим ребром.
Поскольку Ъ',ч О Ъ'з содержит Цр — 1, д) + В(р, о — 1) — 1 = В(р — 1, о) + Я(р, д — 1) — 2+ 1 вершин, разделенных на и = 2 множества, то либо Ъ,ч имеет )т(р — 1, д) вершин, либо Ъ~ имеет В(р,д — 1) вершин. Поэтому, либо Х вЂ” полный граф, имеющий В(р — 1, о) вершин, либо 5 — полный граф, имеющий В(р, о — 1) вершин. Если Х— полный граф, имеющий В(р — 1,о) вершин, то он содержит либо подграф Кр г со всеми красными ребрами, либо подграф Ке со всеми синими ребрами. Если он содержит граф Ке со всеми синими ребрами, то доказательство завершено. Если он содержит граф Кр 1 со всеми красными ребрами, то, добавив вершину о и все красные ребра из о в вершины подграфа Кр ы получим полный граф Кр со всеми красными ребрами, что и требовалось доказать. 368 ГлдВл 8.
комбинаторика и вероятность Аналогично, если 3 — полный граф, имеюший В(р,д — 1) вершин, то он содержит либо подграф Кр со всеми красными ребрами, либо подграф Кк 1 со всеми синими ребрами. Если он содержит граф Кр со всеми красными ребрами, то доказательство завершено. Если он содержит граф К 1 со всеми синими вершинами, то если добавить вершину и и все синие ребра из вершины и во все вершины подграфа Кк ы получим полный граф Кк с синими ребрами, что и требовалось доказать. Основываясь на результатах двух приведенных выше теорем и используя индукцию или принцип полного упорядочения для положительных целых чисел, а также технику доказательства второй теоремы, можно доказать еше один результат, сформулированный в виде следующей теоремы ТЕОРЕМА 8.89.
(Рамсей) . Если целые числа р и д больше единицы, то число Рамсея, Л(р, д), существует. ° УПРАЖНЕНИЯ 1. Сколько людей нужно выбрать из группы, включаюшей 40 человек — женшин и их мужей, чтобы наверняка выбрать супружескую пару? 2. Сколько чисел нужно выбрать из первых 210 положительных целых чисел, чтобы наверняка выбрать четное число? 3. Покажите, что в компании из 30 человек сушествуют двое, имеюшие одинаковое количество взаимных друзей. 4.
Если группа людей приехала из пяти различных стран, то насколько велика должна быть зта группа, чтобы она гарантированно включала трех человек, приехавших из одной страны? 5. Если на кухне имеется 7 банок супа с лапшой, 10 банок овошного супа, 14 банок супа с моллюсками, 18 банок лукового супа и 20 банок томатного супа, то сколько банок нужно взять, чтобы наверняка иметь 12 банок супа одного вида? 6. Сколько человек должно быть в группе людей, чтобы, по крайней мере, у двоих дни рождения были в одном месяце? 7. Сколько человек должно быть в группе людей, чтобы, по крайней мере, у троих дни рождения были в одном месяце? 8. Сколько человек должно быть в группе людей, чтобы, по крайней мере, двое родились в один день недели? 8.
Докажите, что в произвольном списке нз и положительных целых чисел всегда сушествует последовательность идущих последовательно чисел, сумма которых делится на п. 10. Сколько нужно выбрать слов, чтобы, по крайней мере, два начинались с одной и той же буквы? 11. Сколько нужно выбрать слов, чтобы, по крайней мере, два начинались с одной и той же буквы и оканчивались одной и той же буквой? 12. Анкета разослана 13 первокурсникам, 5 второкурсникам, 15 студентам предпоследнего курса и 20 выпускникам.
Сколько анкет нужно собрать, чтобы наверняка получить 9 анкет от студентов одной категории? РЯЗДЕЛ 8.9. Снова о вероятности 369 13. Сколько чисел нужно выбрать из последовательности (1,2,3,4,...,19,20), чтобы два из них давали в сумме 21? 14. Покажите, что любое подмножество, содержащее не менее и различных целых чисел, находящихся между числами 2 и 2п, всегда содержит два взаимно простых числа.
15. Пусть в ресторане 14 столов и 170 стульев, и и — наибольшее количество стульев за столом. Определите наименьшее возможное значение числа и? 16. Докажите, что десятичное разложение рационального числа имеет период. 17. Докажите, что если каждое из и+1 различных положительных целых чисел не превышает число 2п, то два из них отличаются на единицу. 18. Покажите, что если сумма 10 положительных чисел равна 151, то сумма трех из этих чисел должна быть не меньше 46. 19. Покажите, что если гп шаров положить в п коробок и п(п — 1) гп ( 2 то, по крайней мере, в двух коробках будет находиться одинаковое число шаров. 20.
Покажите, что если сумма п + 1 положительных целых чисел равна 2п, то для любого положительного целого числа Й, меньшего 2п, существует подмножество этих и+ 1 целых чисел, сумма которых равна я. 8.9. СНОВА О ВЕРОЯТНОСТИ В предыдущем рассмотрении вероятности предполагалось, что все результаты эксперимента равновозможны. Теперь мы снимем это ограничение и дадим более общее понятие вероятности, для чего наш подход должен быть более аксиоматическим; при этом некоторые теоремы станут аксиомами и определениями.
ОПРЕДЕЛЕНИЕ 8.90. Вероятностной функцией на выборочном пространстве (множестве элементарных событий) 5 называется такая функция Р из подмножеств множества о на действительную числовую ось, что 1. Р(А) > 0 для всех А С 5, 2. Р(Б) = 1. 3. Если А, В С о не имеют общих исходов, то Р(А О В) = Р(А) + Р(В). Доказательства приведенных ниже теорем аналогичны тем, которые даны в разделе 8.2. Единственное отличие состоит в том, что три сформулированных выше условия для вероятностной функции были доказаны в теореме 8.53 в предположении, что все исходы эксперимента равновозможны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
