Математикадан аудандық олимпиада, 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$.