3
1

Учащиеся одной школы часто собираются группами и ходят в кафе-мороженое. После такого посещения они ссорятся настолько, что никакие двое из них после этого вместе мороженое не едят. К концу года выяснилось, что в дальнейшем они могут ходить в кафе-мороженое только поодиночке. Докажите, что если число посещений было к этому времени больше 1 , то оно не меньше числа учащихся в школе.

задан 6 Сен '13 14:32

10|600 символов нужно символов осталось
2

Эта задача была предложена в самом первом выпуске журнала "Квант" (номер 1 за 1970 год). Решение у неё действительно сложное. С ним можно ознакомиться здесь. Оно занимает несколько страниц.

Добавление. Можно изложить сравнительно короткое решение, идея которого принадлежит известному американскому математику Джону Конвею.

Пусть $%m > 1$% -- количество посещений, $%n$% -- количество школьников. Требуется доказать, что $%m\ge n$%. Составим "таблицу непосещений", в которой будет $%m$% строк и $%n$% столбцов. На пересечении строки с номером $%i$% и столбца с номером $%j$% напишем $%0$%, если в $%i$%-м посещении кафе принимал участие школьник с номером $%j$%, а в противном случае напишем там $%1$%.

Введём обозначения: через $%k_i$% обозначим количество школьников, участвовавших в $%i$%-м посещении кафе (это не что иное как количество нулей в $%i$%-й строке), а через $%r_j$% обозначим количество посещений кафе, в которых принял участие школьник под номером $%j$% (это есть число нулей в $%j$%-м столбце).

Теперь составим две новых таблицы на основе имеющейся. Первая строится так. Сначала мы заменим все единицы, стоящие в $%i$%-й строке (для каждого $%i$% от $%1$% до $%m$%) на дробные величины $%1/(n-k_i)$%. Нули остаются на прежних местах. В итоге окажется, что сумма чисел каждой строки равна $%1$% -- ведь единиц в $%i$%-й строке было в точности $%n-k_i$%. Это значит, что сумма всех чисел получившейся таблицы равна $%m$%, то есть количеству строк. Мы хотим, чтобы сумма всех чисел таблицы стала равна $%1$%. Этого можно добиться, разделив на $%m$% каждое число таблицы.

То, что получилось, мы назовём первой таблицей: нули стоят на прежних местах, а на месте единицы у нас на пересечении $%i$%-й строки и $%j$%-го столбца возникла дробь $%\frac1{m(n-k_i)}$%. Введённые нами величины имеют естественную интерпретацию в терминах вероятностей, но эти подробности не нужны для собственно доказательства.

Теперь составим вторую таблицу аналогичным способом. Для начала мы поделим каждую единицу $%j$%-го столбца на общее количество единиц в этом столбце, что приводит к величинам $%1/(m-r_j)$%. Сумма чисел в каждом столбце равна $%1$%, откуда сумма чисел всей таблицы равна $%n$%. Поделив каждое из чисел на $%n$%, мы окончательно получим вторую таблицу. В ней нули стоят на прежних местах, а вместо единиц на пересечении $%i$%-й строки и $%j$%-го столбца теперь имеется дробь $%\frac1{n(m-r_j)}$%. Сумма всех чисел второй таблицы также равна $%1$%.

Проанализируем то, что получилось: есть две таблицы, в которых на одних и тех же местах стоят положительные числа (вообще говоря, разные), и суммирование в обоих случаях даёт одну и ту же величину (единицу). Отсюда можно извлечь такой вывод: найдётся такое место, задаваемое номером строки $%i$% и номером столбца $%j$%, на котором число первой таблицы не меньше соответствующего числа второй таблицы, то есть для некоторых $%i$%, $%j$% справедливо такое неравенство: $$\frac1{m(n-k_i)}\ge\frac1{n(m-r_j)}.$$ Это достаточно очевидно, так как в противном случае оказалось бы, что каждое слагаемое одной суммы меньше соответствующего слагаемого другой суммы, а такие суммы не могут быть одинаковыми. (Здесь можно ещё добавить, что таблица не могла состоять из одних только нулей, так как в этом случае посещение кафе было бы всего одно, и в нём присутствовали все школьники.)

Полученное неравенство преобразуется сначала в $%m(n-k_i)\le n(m-r_j)$%, а затем в $%mk_i\ge nr_j$%. При этом мы знаем, что $%j$%-й школьник не участвовал в $%i$%-м посещении кафе (так как на этом месте в таблице у нас изначально была единица). Нетрудно показать, что в этом случае справедливо неравенство $%r_j\ge k_i$% (это один из ключевых моментов рассуждения). В самом деле, в $%i$%-м посещении кафе участвовало ровно $%k_i$% школьников. Школьник под номером $%j$%, согласно условию задачи, с каждым из них когда-то поссорился, то есть участвовал в посещении кафе. Но он при этом не мог посетить кафе сразу с какими-то двумя из них, так как в этом случае те же самые два школьника приняли бы участие сразу в двух посещениях, что невозможно. Значит, $%j$%-й школьник ходил в кафе по отдельности с каждым из $%k_i$% рассматриваемых школьников, и тем самым он посетил кафе не менее $%k_i$% раз, что и означает $%r_j\ge k_i$%.

Из двух выведенных нами неравенств следует, что $%mk_i\ge nr_j\ge nk_i$%. Сокращая на положительное число $%k_i$%, приходим к выводу $%m\ge n$%, что и требовалось.

Соответствующее математическое утверждение было впервые доказано в 1948 году в совместной работе двух авторов: де Брёйна и Эрдёша.

De Bruijn, N.G. and Erdős, P. (1948): On a combinatorial problem, Indagationes Mathematicae 10, 421–423.

ссылка

отвечен 6 Сен '13 16:00

изменен 6 Сен '13 20:28

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×366

задан
6 Сен '13 14:32

показан
446 раз

обновлен
6 Сен '13 20:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru