Задание олимпиады: неравенство для пар функций f(x) и g(x), 9

Задача

Функции f(x) и g(x) определены на множестве целых чисел, не превосходящих по модулю 1000. Обозначим через m число пар (x, y), для которых

f(x) = g(y), через n – число пар, для которых f(x) = f(y), а через k – число пар, для которых g(x) = g(y). Докажите, что 2m ≤ n + k.

Решение

Пусть a – одно из значений, принимаемых функцией f(x), а n_a и k_a – количество тех x, для которых f(x) = a и g(x) = a соответственно (возможно, что k_a = 0). Тогда n_ak_a пар чисел (x, y) будут удовлетворять равенствам f(x) = g(y) = a, пар – равенствам f(x) = f(y) = a и пар – равенствам