Олимпиадная задача по комбинаторике Карасева: таблица 10×n, доказательство для n ≥ 512
Задача
В каждой клетке таблицы, состоящей из 10 столбцов и n строк, записана цифра. Известно, что для каждой строки A и любых двух столбцов найдётся строка, отличающаяся от A ровно в этих двух столбцах. Докажите, что n ≥ 512.
Решение
Пусть R0 – первая строка таблицы. Рассмотрим любой набор из чётного количества столбцов и пронумеруем их слева направо: C1, ..., C2m. Тогда в таблице есть строка R1, отличающаяся от R0 ровно в столбцах С1 и С2; далее, есть строка R2, отличающаяся от R1 ровно в столбцах С3 и С4; ...; наконец, есть строка Rm, отличающаяся от Rm–1 ровно в столбцах C2m–1 и C2m (если m = 0, то Rm = R0). Итак, строка Rm отличается от R0 ровно в столбцах C1, ..., C2m. Значит, строки Rm, построенные по различным наборам столбцов, различны. Поскольку количество наборов из чётного числа столбцов равно 29 = 512 (см. задачу 130711), то и количество строк в таблице не меньше 512.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь