Соответствия, сравнения, количества

Пусть Докажем, что Рассмотрим все возможные тройки Всего их и для каждой из них То есть сумма по всем тройкам Обозначим её за С другой стороны, каждый элемент из считается в когда два или три из множеств и содержат этот элемент. Способов, когда ровно два из множеств и содержат этот элемент равно так как множества, содержащие его, определяются однозначно. И ещё есть один способ, когда все три множества и содержат этот элемент, причём в этом случае элемент считается три раза. То есть каждый элемент считается в ровно раз. То есть откуда

Осталось привести пример. Рассмотрим таблицы размера Все клетки этих таблиц будут элементами множества Пусть множество содержит все клетки строк всех таблиц и только их; множество содержит все клетки столбцов всех таблиц и только их; множество содержит все клетки диагонали, т.е. все клетки, у которых сумма координат сравнима с по модулю Нетрудно заметить, что множества образуют разбиения. Любые два множества из разных разбиений имеют общий элемент в каждой таблице. Значит любые два множества из разных разбиений имеют общих элемента, откуда для любой тройки