Задача 116638

Темы:    [ Числовые таблицы и их свойства ] [ Задачи с ограничениями ]

Сложность: 4 Классы: 8,9,10

Условие

Автор: Карасев Р.

В каждой клетке таблицы, состоящей из 10 столбцов и n строк, записана цифра. Известно, что для каждой строки A и любых двух столбцов найдётся строка, отличающаяся от A ровно в этих двух столбцах. Докажите, что  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  (см. задачу 30711), то и количество строк в таблице не меньше 512.

Замечания

В таблице может быть ровно 512 строк – например, если в её строках записаны все 512 последовательностей из 10 нулей и единиц, среди которых чётное число нулей.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2010-2011
Этап
Вариант	5
класс
Класс	10
Задача
Номер	10.1