Задача 109835

Темы:    [ Задачи с ограничениями ] [ Квадратные уравнения. Теорема Виета ] [ Двоичная система счисления ]

Сложность: 5+ Классы: 9,10,11

Условие

Авторы: Агаханов Н.Х., Богданов И.И.

Сколькими способами числа 2⁰, 2¹, 2², ..., 2²⁰⁰⁵ можно разбить на два непустых множества A и B так, чтобы уравнение  x² – S(A)x + S(B) = 0,  где S(M) – сумма чисел множества M, имело целый корень?

Решение

  Если  x₁ ≤ x₂  – корни уравнения, то  x₁, x₂ N  и  x₁ + x₂ = S(A),  x₁x₂ = S(B),  поэтому   (x₁ + 1)(x₂ + 1) = S(B) + S(A) + 1 = 1 + 2 + 4 + ... + 2²⁰⁰⁵ + 1 = 2²⁰⁰⁶.   Значит,  x₁ + 1 = 2^k,  x₂ + 1 = 2^2006–k,  где k может принимать значения 1, 2, ..., 1003.
  Наоборот, пусть x₁, x₂ – числа такого вида. Тогда они являются корнями уравнения  x² – px + q = 0,  где  p = 2^k + 2^2006–k – 2,  q = 2²⁰⁰⁶ – 1 – p.
  Но число p имеет единственное разложение в сумму различных степеней двойки, и в этом разложении степени двойки не превосходят 2²⁰⁰⁵, а двоичное разложение q содержит 1 на тех местах, где у числа p – нули, так как  p + q = 2²⁰⁰⁶ – 1.  Итак, для каждого k от 1 до 2003 существует единственное разбиение  (A, B),  дающее указанные корни x₁ и x₂.

Ответ

1003 способами.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2005
Этап
Вариант	5
Класс
Класс	9
задача
Номер	05.5.9.6