Решение. Умное голосование (#119)

Обозначим множество жителей села через N. Пронумеруем их N = {1, …, n}. Множество N x N всех упорядоченных пар жителей села удобно организовать в виде квадрата. Количество знакомых пар, находящихся в строке и столбце пары (x, y), обозначим p(x, y). Количество знакомых пар во всём квадрате обозначим t.

Из условия следует, что в каждой строке (или столбце) количество знакомых пар не меньше, чем an. Так как всего в квадрате n столбцов, то an² ≤ t. Предположим, что утверждение задачи не выполняется, то есть для каждой пары (1, y), 1 ≤ y ≤ n, выполняется неравенство p(1, y) < bn. Тогда

Объединяя с неравенством an² ≤ t и исключая t, получаем неравенства

При подстановке числовых значений n = 301, a = 30% и b = 59,9%, получаем противоречие 301 < 300. Следовательно, для какой-то пары (1, y), 1 ≤ y ≤ n, выполняется неравенство p(1, y) ≥ bn. Её-то и следует выдвинуть в качестве кандидатов.

Условие
Telegram