Районная олимпиада, 2019-2020 учебный год, 11 класс

Прямоугольная таблица $16 \times 16$ заполнена числами 0 и 1. Если выбрать любые два столбца, то количество совпадений их чисел, написанных на одинаковых строках, меньше 9. Докажите, что количество 0-ей в таблице не превосходит 160.

Комментарий/решение

Всего различных способов разместить различное количество $0,1$ в клетке $4$ на $16$ равно $2^4=16$, отметим что максимум число одинаковых расположений может равняться $3$ (случаи когда два столбца одинаковы, будет следовать из ниже приведённой конструкции).

Рассмотрим случай конструкции, когда число $«0»$ будет стремится к максимуму, для этого рассмотрим клетку $12$ на $16$, а клетку $4$ на $16$ (всего $16$ на $16$) заполним одними $0$ и того $16 \cdot 4 =64$ нулей, по условию количество одинаковых чисел по строкам для любых столбцов $<9$, а так в клетке $4$ на $16$ максимум их могут быть $3$ то для клетки $16$ на $12$ получаем $\leq 3+3+3=9$ одинаковых чисел, но в $2^4$ случаев расположений количество нулей равно $32$, значит так как их меньше $9$ значит какие то числа в столбцах будет заполнятся $1$, значит максимум $0$ при таком максимальном расположении равно $64+3 \cdot 32 = 160$.