На боковых сторонах AB и BC равнобедренного треугольника ABC взяты точки K и L соответственно, так что  AK + LC = KL.  Из середины M отрезка KL провели прямую, параллельную BC, и эта прямая пересекла сторону AC в точке N. Найдите величину угла KNL.

   Решение

Кресла для зрителей вдоль лыжной трассы занумерованы по порядку: 1, 2, 3, ..., 1000. Кассирша продала n билетов на все первые 100 мест, но n больше 100, так как на некоторые места она продала больше одного билета (при этом  n < 1000).  Зрители входят на трассу по одному.Каждый, подойдя к своему месту, занимает его, если оно свободно, если же занято, говорит "Ох!", идёт в сторону роста номеров до первого свободного места и занимает его. Каждый раз, обнаружив очередное место занятым, он говорит "Ох!". Докажите, что число "охов" не зависит от того, в каком порядке зрители выходят на трассу.

   Решение

Можно ли подобрать два многочлена P(x) и Q(x) с целыми коэффициентами так, что  P – Q,  P и  P + Q  – квадраты некоторых многочленов (причём Q не получается умножением P на число)?

   Решение

Одна под другой выписаны 2^n–1 различных последовательностей из нулей и единиц длины n. Известно, что для любых трёх из выписанных последовательностей найдётся такой номер p, что в p-м разряде у всех трёх стоит 1. Доказать, что в некотором разряде у всех выписанных последовательностей стоит 1 и такой разряд только один.

   Решение

Темы:    [ Числовые таблицы и их свойства ] [ Задачи с ограничениями ] [ Разбиения на пары и группы; биекции ] [ Правило произведения ] [ Объединение, пересечение и разность множеств ]

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

Прислать комментарий

Условие

Одна под другой выписаны 2^n–1 различных последовательностей из нулей и единиц длины n. Известно, что для любых трёх из выписанных последовательностей найдётся такой номер p, что в p-м разряде у всех трёх стоит 1. Доказать, что в некотором разряде у всех выписанных последовательностей стоит 1 и такой разряд только один.

Решение

  Обозначим через 0 последовательность из одних нулей, через xy – последовательность, получающуюся почленным перемножением последовательностей x и y, через x – последовательность, получающуюся из последовательности x заменой всех нулей на единицы, а единиц – на нули. В этих обозначениях условие задачи записывается следующим образом.
  Выписаны 2^n–1 различных последовательностей x_i  (i = 1,..., 2^n–1)  из нулей и единиц длины n. Известно, что  x_ix_jx_k ≠ 0  для любых i, j, k. Доказать, что в произведении  W = x₁x₂...x_2^n–1  встречается ровно одна единица.
  Заметим сначала, что  x_ix_j ≠ 0  для любых  1 ≤ i, j ≤ 2^n–1.  Следовательно, среди последовательностей x_i не могут одновременно встречаться последовательности y и y. Все последовательности длины n разбиваются на 2^n–1 пар вида  (x, x).  Так как всего последовательностей столько же, сколько и пар, а из каждой пары выписано не более одной последовательности, то из каждой пары выписана ровно одна последовательность.
  Заметим, что если последовательности y и z выписаны, то последовательность yz тоже выписана (в противном случае выписана последовательность yz;  но  yzyz = 0).  Следовательно, произведение любого количества выписанных последовательностей также выписано, а значит, выписана и последовательность W. Поэтому  W ≠ 0.
  Предположим, что в последовательности W есть не менее двух единиц. Тогда во всех выписанных последовательностях на соответствующих местах стоят единицы, а значит, всего выписанных последовательностей не более 2^n–2, что противоречит условию.

Замечания

Эта задача – перефразировка задачи 73560.

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