В выпуклом многоугольнике на плоскости содержится не меньше  m² + 1  точек с целыми координатами.
Докажите, что в нём найдутся  m + 1  точек с целыми координатами, которые лежат на одной прямой.

   Решение

Обозначим через S(m) сумму цифр натурального числа m. Докажите, что существует бесконечно много таких натуральных n, что  S(3ⁿ) ≥ S(3ⁿ⁺¹).

   Решение

Можно ли доску размером 5×5 заполнить доминошками размером 1×2?

   Решение

M_a, M_b, M_c – середины сторон, H_a, H_b, H_c – основания высот треугольника ABC площади S.
Доказать, что из отрезков M_aH_b, M_bH_c, M_cH_a можно составить треугольник, найти его площадь.

   Решение

Имеются два набора из чисел 1 и –1, в каждом по 1958 чисел. Доказать, что за некоторое число шагов можно превратить первый набор во второй, если на каждом шагу разрешается одновременно изменить знак у любых 11 чисел первого набора. (Два набора считаются одинаковыми, если у них на одинаковых местах стоят одинаковые числа.)

   Решение

Темы:    [ Теория алгоритмов (прочее) ] [ Четность и нечетность ]

Сложность: 3+ Классы: 8,9

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

Условие

Имеются два набора из чисел 1 и –1, в каждом по 1958 чисел. Доказать, что за некоторое число шагов можно превратить первый набор во второй, если на каждом шагу разрешается одновременно изменить знак у любых 11 чисел первого набора. (Два набора считаются одинаковыми, если у них на одинаковых местах стоят одинаковые числа.)

Решение

  Сначала заметим, что у любой пары чисел  (a_i, a_j)  (i ≠ j)  в наборе можно сменить знак. Для этого возьмём произвольные десять чисел, отличных от a_i и a_j. Тогда, изменив знаки сначала у десятки, дополненной a_i, а потом у той же десятки, дополненной a_j, получим, что знаки изменились только у a_i и a_j.
 Теперь покажем, как сменить знак у любого числа a_k из набора. Рассмотрим произвольные десять чисел b₁, b₂, ..., b₁₀, отличных от a_i, сначала изменим знаки у b₁, b₂, ..., b₁₀, a_i, а затем у пар  (b₁, b₂),  (b₃, b₄),  ...,  (b₉, b₁₀).  Тем самым в итоге знак изменится только у a_i.
  Сменив таким образом знаки у всех несовпадающих чисел, из любого набора можно получить любой другой набор за конечное число шагов.

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