ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109539
Темы:    [ Объединение, пересечение и разность множеств ]
[ Разбиения на пары и группы; биекции ]
[ Подсчет двумя способами ]
[ Необычные конструкции ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Автор: Перлин А.

У каждого из жителей города N знакомые составляют не менее 30 населения города. Житель идет на выборы, если баллотируется хотя бы один из его знакомых. Докажите, что можно так провести выборы мэра города N из двух кандидатов, что в них примет участие не менее половины жителей.

Решение

Решение I основано на следующей лемме. Лемма. Пусть S – произвольное непустое множество жителей. Тогда в городе N найдется житель, знакомый не менее чем с 30% жителей из S . Обозначим через |X| количество жителей в множестве X . Оценим общее количество (упорядоченных) пар знакомых (t,s) , где t – произвольный человек, а s – человек из S . Для каждого s0 S количество пар вида (t,s0) не меньше 0,3|N| , поэтому общее количество пар не меньше 0,3|S||N| . Поэтому для какого-то человека t0 количество пар вида (t0,s) не меньше 0,3|S| , что и требовалось. Выдвинем в качестве первого кандидата произвольного жителя A . Рассмотрим множество S не знакомых с A жителей. Если множество S пусто, то в качестве второго кандидата можно взять любого жителя города N , отличного от A . Если множество S непусто, то, применив лемму, найдем жителя B , знакомого не менее чем с 30 жителей, входящих в S . Покажем, что выборы из двух кандидатов A и B удовлетворяют решению задачи. Пусть житель A имеет k знакомых, а общее число жителей в N равно n . Тогда на выборы из двух кандидатов A и B придет не менее k+0,3· (n-k)=0,3n+0,7k жителей, и так как k0,3n , то в выборах примет участие не менее 0,3n+0,7· 0,3n=0,51n , т.е. более половины жителей N .
Решение II Обозначим через n число жителей в городе N . Для любых двух жителей города подсчитаем число жителей, знакомых хотя бы с одним из них, и обозначим сумму всех полученных чисел через . Мы должны доказать, что в городе N найдутся два таких жителя A и B , что число жителей, знакомых или с A , или с B , не меньше 0,5n . Так как число пар жителей равно , то для этого достаточно показать, что 0,5=n . Для каждого жителя M оценим число (M) пар жителей, в которых хотя бы один человек знаком с M . Для этого оценим количество всех остальных пар: в каждой из них оба человека не знакомы с M , поэтому количество таких пар не превосходит ; поскольку общее количество пар жителей равно , получаем, что (M) > , поэтому >n , что и требовалось.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1993
Этап
Вариант 4
класс
Класс 10
задача
Номер 93.4.10.4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .