На плоскости дано 4000 точек, никакие три из которых не лежат на одной прямой. Докажите, что существует 1000 непересекающихся четырехугольников (возможно, невыпуклых) с вершинами в этих точках.

   Решение

Темы:    [ Треугольник Паскаля и бином Ньютона ] [ Четность и нечетность ]

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

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

Условие

При каких значениях n все коэффициенты в разложении бинома Ньютона  (a + b)ⁿ  нечётны?

Решение

  Назовём строку треугольника Паскаля хорошей, если в ней все числа, кроме крайних, чётны. Пусть n-я строка хорошая. Это значит, что
(x + 1)ⁿ = xⁿ + 1 + 2f(x),  где f(x) – многочлен с целыми коэффициентами. Возведя это равенство в квадрат, убедимся, что  (x + 1)²ⁿ  имеет тот же вид, то есть 2n-я строка тоже хорошая. Отсюда следует, что хороши все строки с номерами вида 2^k.
  Пусть  n = 2^k,  то есть n-я строка хорошая. Тогда из построения треугольника Паскаля следует, что в предыдущей строке (с номером  2k – 1)  все числа одной чётности, то есть все они нечётны. Кроме того, в n-й строке стоит группа из  n – 1  чётных чисел подряд. Поэтому в (n+1)-й строке под ней образуется группа из  n – 2  чётных чисел, в (n+2)-й – группа из  n – 3  чётных чисел, …, в (2n–2)-й – одно чётное число (в середине). Таким образом, во всех строках с номерами от  2^k + 1  до  2^k – 2  чётные числа есть.

Ответ

При  n = 2^k – 1.

Замечания

См. также задачу 32881.

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