Задача про жителей города где число знакомых как минимум 30%

[Kuga]

Источник https://problems.ru/view_problem_detail ... ?id=109539
там приведены 2 решения данной задачи

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

Вопрос. Правильно ли решение которое приведено ниже?

Решение.

Насколько я понимаю, если $X$ является знакомым $Y$, то и $Y$ является знакомым для $X$, так?

Тогда рассмотрим граф, где вершины - это жители, и между двумя вершинами проведено ребро, если соответствующие жители знакомы друг с другом. Обозначим число жителей через $n$.

Задачу будем решать от противного, и предположим, что таким образом выборы провести нельзя. Т.е. при любом выборе двух кандидатов, общее число их знакомых меньше $0.5n$.

Попытаемся оценить число ребер $R$ этого графа двумя способами. Причем оценку будем проводить в главном порядке по $n$, считая что $n>>1$ (число жителей очень велико), т.е. с точностью до линейных по $n$ членов.

Из каждой вершины исходит как минимум $0.3n$ ребер, поэтому с помощью стандартного аргумента получаем

$$ R\ge \frac{n\cdot 0.3n}{2}=0.15n^2. $$

Теперь рассмотрим какое-нибудь фиксированное разбиение жителей на $n/2$ пар. Из каждой пары исходит менее чем $0.5n$ ребер. Для каждого такого ребра, его концы принадлежат разным парам из фиксированных $n/2$ пар вершин (порядка $n$ ребер, которые могут соединять вершины внутри пар не учитываем). Значит

$$ R\le \frac{\frac{n}{2}\cdot 0.5n}{2}=0.125n^2. $$

В итоге

$$ 0.15n^2\le R\le 0.125n^2. $$

Полученное противоречие завершает доказательство. $\qed$

В частности, из этого решения можно получить, что вместо 30% в условии задачи можно взять меньшее число, например 26%. Но официальное решение не позволяет получить такого вывода, потому что оно опирается на неравенство

$$ 1-(1-0.3)^2=0.51>0.5, $$

которое не будет выполняться если 0.3 заменить на 0.26. Получается решение которое приведено тут более тонкое чем официальное решение, по крайней мере когда $n$ велико?

[Kuga]

Все еще не могу понять, есть ли в этом решении ошибка, или действительно такой простой аргумент позволяет решить задачу с более сторогим условием, где число знакомых может быть и меньше 30%?

[mihaild]

Kuga в сообщении #1641496 писал(а):

Из каждой пары исходит менее чем $0.5n$ ребер

Это неправда. Если у нас житель знаком с обоими членами пары, то он дает два ребра. Соответственно если оба человека из пары знакомы с каждым из $0.4n$ жителей, то из пары исходит $0.8n$ ребер, но пара всё равно не подходит.

Если бы Ваше рассуждение проходило, то оно доказывало бы, что можно взять вообще произвольное разбиение на пары, и какая-нибудь пара подошла бы. Но это не так. Представьте шестиугольник, в каждой вершине которого по $m$ жителей, и каждый житель знаком со всеми из соседних вершин. Тогда каждый житель знаком даже с третью города. Но если разбить на пары так, что каждая пара жителей в одной вершине, то каждая пара будет опять же знакома только с третью города.