Олимпиадная задача по комбинаторике Карасева: таблица 10×n, доказательство для n ≥ 512

Пусть R₀ – первая строка таблицы. Рассмотрим любой набор из чётного количества столбцов и пронумеруем их слева направо:  C₁, ..., C_2m.  Тогда в таблице есть строка R₁, отличающаяся от R₀ ровно в столбцах С₁ и С₂; далее, есть строка R₂, отличающаяся от R₁ ровно в столбцах С₃ и С₄; ...; наконец, есть строка R_m, отличающаяся от R_m–1 ровно в столбцах C_2m–1 и C_2m (если  m = 0,  то  R_m = R₀).  Итак, строка R_m отличается от R₀ ровно в столбцах  C₁, ..., C_2m.  Значит, строки R_m, построенные по различным наборам столбцов, различны. Поскольку количество наборов из чётного числа столбцов равно  2⁹ = 512  (см. задачу 130711), то и количество строк в таблице не меньше 512.