Разделы 
Дополнительно
Задача по математике - 1171
2018-09-15 
У каждого из жителей города $N$ знакомые составляют не менее 30% населения города. Житель идет на выборы, если баллотируется хотя бы один из его знакомых. Докажите, что можно так провести выборы мэра города $N$ из двух кандидатов, что в них примет участие не менее половины жителей.
Решение:
Первое решение основано на следующей лемме.
Лемма. Пусть $S$ - произвольное непустое множество жителей. Тогда в городе $N$ найдется житель, знакомый не менее чем с 30% жителей из $S$.
Доказательство. Обозначим через $|X|$ количество жителей в множестве $X$. Оценим общее количество (упорядоченных) пар знакомых $(t, s)$, где $t$ — произвольный человек, а $s$ — человек из $S$. Для каждого $s_{0} \in S$ количество пар вида $(t, s_{0})$ не меньше $0,31 |N|$, поэтому общее количество пар не меньше $0,3 |S||N|$. Поэтому для какого-то человека $t_{0}$ количество пар вида $(t_{0}, 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$ жителей, и так как $k \geq 0,3n$, то в выборах примет участие не менее $0,3n + 0,7 \cdot 0,3n = 0,51n$, т. е. более половины жителей $N$.
Второе решение. Обозначим через $n$ число жителей в городе $N$. Для любых двух жителей города подсчитаем число жителей, знакомых хотя бы с одним из них, и обозначим сумму всех полученных чисел через $\sigma$. Мы должны доказать, что в городе $N$ найдутся два таких жителя A и B, что число жителей, знакомых или с A, или с B, не меньше $0,5n$. Так как число пар жителем равно $\frac{n(n-1)}{2}$, то Для этого достаточно показать, что $\sigma \geq 0,5n \frac{n(n - 1)}{2} = \frac{(0,5n^{2} - 0,5n )}{2}n$.
Для каждого жителя $M$ оценим число $\sigma(M)$ пар жителей, в которых хотя бы один человек знаком с $M$. Для этого оценим количество всех остальных пар: в каждой из них оба человека не знакомы с $M$, поэтому количество таких пар не превосходит
$\frac{(n - 0,3n)(n - 0,3n - 1)}{2} \leq \frac{0,49 n^{2} - 0,7n}{2}$; поскольку общее количество пар жителем равно $\frac{n(n - 1)}{2}$, получаем, что $\sigma(M) \geq \frac{0,51n^{2} - 0,3n }{2} > \frac{0,5n^{2} - 0,5n }{2}$, поэтому $\sigma > n \frac{0,5n^{2} - 0,5n }{2}$, что и требовалось.
У каждого из жителей города $N$ знакомые составляют не менее 30% населения города. Житель идет на выборы, если баллотируется хотя бы один из его знакомых. Докажите, что можно так провести выборы мэра города $N$ из двух кандидатов, что в них примет участие не менее половины жителей.
Решение:
Первое решение основано на следующей лемме.
Лемма. Пусть $S$ - произвольное непустое множество жителей. Тогда в городе $N$ найдется житель, знакомый не менее чем с 30% жителей из $S$.
Доказательство. Обозначим через $|X|$ количество жителей в множестве $X$. Оценим общее количество (упорядоченных) пар знакомых $(t, s)$, где $t$ — произвольный человек, а $s$ — человек из $S$. Для каждого $s_{0} \in S$ количество пар вида $(t, s_{0})$ не меньше $0,31 |N|$, поэтому общее количество пар не меньше $0,3 |S||N|$. Поэтому для какого-то человека $t_{0}$ количество пар вида $(t_{0}, 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$ жителей, и так как $k \geq 0,3n$, то в выборах примет участие не менее $0,3n + 0,7 \cdot 0,3n = 0,51n$, т. е. более половины жителей $N$.
Второе решение. Обозначим через $n$ число жителей в городе $N$. Для любых двух жителей города подсчитаем число жителей, знакомых хотя бы с одним из них, и обозначим сумму всех полученных чисел через $\sigma$. Мы должны доказать, что в городе $N$ найдутся два таких жителя A и B, что число жителей, знакомых или с A, или с B, не меньше $0,5n$. Так как число пар жителем равно $\frac{n(n-1)}{2}$, то Для этого достаточно показать, что $\sigma \geq 0,5n \frac{n(n - 1)}{2} = \frac{(0,5n^{2} - 0,5n )}{2}n$.
Для каждого жителя $M$ оценим число $\sigma(M)$ пар жителей, в которых хотя бы один человек знаком с $M$. Для этого оценим количество всех остальных пар: в каждой из них оба человека не знакомы с $M$, поэтому количество таких пар не превосходит
$\frac{(n - 0,3n)(n - 0,3n - 1)}{2} \leq \frac{0,49 n^{2} - 0,7n}{2}$; поскольку общее количество пар жителем равно $\frac{n(n - 1)}{2}$, получаем, что $\sigma(M) \geq \frac{0,51n^{2} - 0,3n }{2} > \frac{0,5n^{2} - 0,5n }{2}$, поэтому $\sigma > n \frac{0,5n^{2} - 0,5n }{2}$, что и требовалось.
