Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 2 ] |
|
Автор | Сообщение | ||
---|---|---|---|
Kolyannn |
|
||
В кружок записались 2011 мальчиков и 2011 девочек, причем каждый из мальчиков знаком хотя б с 10 девочками. Докажите, что можно выбрать 100 мальчиков и 10 девочек так, чтобы каждый из выбранных мальчиков был знаком хотя б с одной выбранной девочкой. |
|||
Вернуться к началу | |||
Prokop |
|
||
Каждая девочка знакома с некоторым числом парней. Для конкретной девочки это число может оказаться нулём.
Выберем девочку, которая знает наибольшее число парней. Если таких девочек несколько, то возьмём любую. Если число этих парней больше или равно 100, то задача решена. Пусть число отобранных ребят меньше 100. Тогда из оставшихся девочек выбираем ту, которая имеет наибольшее число знакомых парней, среди оставшихся ребят после первого отбора (если таких девочек несколько, то выбираем любую). Если общее число парней после этих двух отборов будет больше или равно 100, то задача решена. Пусть это общее количество ребят будет меньше 100. Тогда повторяем процесс выбора девочки и её знакомых ребят и т.д. Отметим. Что количество вновь добавляемых мальчиков не возрастает по мере увеличения числа девочек. Предположим, что отбор 10 девочек и 100 юношей не закончился на десятом шаге. Это означает. Во-первых, что десятая девочка и все оставшиеся девочки имеют среди оставшихся мальчиков не более 9 знакомых каждая. Во-вторых, после 10 шага осталось больше 1911 ребят, каждый из которых имеет, по крайней мере, не менее 10 знакомых девушек среди 2001 оставшихся. Таким образом, этим ребятам нужно, по крайней мере, 19120 знакомств, а оставшиеся девочки могут предложить не более 2001*9 =1809 знакомств (чего явно не хватает). Как-то так получается (что-то слишком большой зазор) Проверьте. Возможно. я что-т0 упустил |
|||
Вернуться к началу | |||
[ Сообщений: 2 ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |