ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116638
Темы:    [ Числовые таблицы и их свойства ]
[ Задачи с ограничениями ]
Сложность: 4
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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

В каждой клетке таблицы, состоящей из 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 нулей и единиц, среди которых чётное число нулей.

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .