|
|
 |
Условие
Одна под другой выписаны 2n–1 различных последовательностей из нулей и единиц длины n. Известно, что для любых трёх из выписанных последовательностей найдётся такой номер p, что в p-м разряде у всех трёх стоит 1. Доказать, что в некотором разряде у всех выписанных последовательностей стоит 1 и такой разряд только один.
Решение
Обозначим через 0 последовательность из одних нулей, через xy – последовательность, получающуюся почленным перемножением
последовательностей x и y, через x – последовательность, получающуюся из последовательности x заменой всех нулей на единицы, а единиц – на нули. В этих обозначениях условие задачи записывается следующим образом.
Выписаны 2n–1 различных последовательностей xi (i = 1,..., 2n–1) из нулей и единиц длины n. Известно, что xixjxk ≠ 0 для
любых i, j, k. Доказать, что в произведении W = x1x2...x2n–1 встречается ровно одна единица.
Заметим сначала, что xixj ≠ 0 для любых 1 ≤ i, j ≤ 2n–1. Следовательно, среди последовательностей xi не могут одновременно встречаться последовательности y и y. Все последовательности длины n разбиваются на 2n–1 пар вида (x, x). Так как всего последовательностей столько же, сколько и пар, а из каждой пары выписано не более одной последовательности, то из каждой пары выписана ровно одна последовательность.
Заметим, что если последовательности y и z выписаны, то последовательность yz тоже выписана (в противном случае выписана последовательность yz; но yzyz = 0). Следовательно, произведение любого количества выписанных последовательностей также выписано, а значит, выписана и последовательность W. Поэтому W ≠ 0.
Предположим, что в последовательности W есть не менее двух единиц. Тогда во всех выписанных последовательностях на соответствующих местах стоят единицы, а значит, всего выписанных последовательностей не более 2n–2, что противоречит условию.
Замечания
Эта задача – перефразировка задачи 73560.
