26. Число знакомых

ПОдсчитывая число расположений ферзей, мы бросили МиМоходом фразу: «так как на шахматной доске только 8 горизонталей, то больше 8 ферзей поставить на доску не удастся». Если развернуть эту аргументацию подробнее, то она приняла бы такой вид: «Когда на шахматную ДосКу, имеющую 8 горизонталей, ставят 9 ферзей, то хотя бы ОдНа пара ферзей оказывается на одной и той же ГориЗонталИ, а потому будет бить друг друга». Подобные рассуждения часто встречаются в математике, они получили даже особое название Принципа Дирихле по имени немецкого математика, часто применявшего их в исследованиях по теории чисел. Этот принцип гласит:

Если в П ящиков положено более чем П предметов, то Хотя бы в одном ящике лежат два или более предметов.

Несмотря на свою простоту и очевидность, принцип Дирихле позволяет получать далеко не очевидные результаты. Докажем с его помощью, например, такое утверждение:

Если в зале находится п человек, то хотя бы двое из них имеют одинаковое число знакомых среди Присутствую-щих (мы, разумеется, считаем отношение «А знаком с B» ВЗаимным — если А знаком с B, то и B знаком с А).

В самом деле, число знакомых каждого человека моЖЕт приНИмать значения от 0 (если он не Знаком ни с кем в зале) до П-1 (если он знаком со всеми Присутствующими), т. Е. П различНЫх значений. Возможны два случая — либо хотя бы ДЛя одного значения K, в зале нет человека с K Знакомыми, либо для всех K найдется хотя бы одиН человек, имеющий ровно K Знакомых В зале. В первоМ случае число рАЗличНЫх зНАчеНИй Для K МеНЬше, чем П (хотя бы одно значение пропущеНО), а тогда по прИнЦипу Дирихле хотя бы для двух из П человек значение K одно и то же. ИНЫми словами, в первом случае есть двое людей, имеющих поровну зНАкомых.

Осталось показать, что второй случай невозможен. В этом случае в зале был бы человек с 0 знакомыМИ и Человек с П-1 знакомыми. Но ЭТо невозможно, так как если эти люди знакомы друг с другом, то первый уже ИМеЕТ хотя бы одного знакомого, а если оНИ не знакомы, то число зНАкомых второго человека МЕньше, чем П-1. УтверждеНИе доказаНО. Его можНО сформулировать геометрически так.

Если некоторые иЗ п точек плоскости соединены отРеЗками, то всегда найдутся две точки, из которых выходит поровну отрезков.

< Предыдущая		Следующая >