ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 116638
УсловиеВ каждой клетке таблицы, состоящей из 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 (см. задачу 30711), то и количество строк в таблице не меньше 512. ЗамечанияВ таблице может быть ровно 512 строк – например, если в её строках записаны все 512 последовательностей из 10 нулей и единиц, среди которых чётное число нулей. Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|