Восстановление набора чисел по попарным суммам

Автор текста: Дуйсенбеков Данат

4 задачу с JBMO 2013 можно естественным образом обобщить - найти все натуральные n при которых Боб выигрывает.

Оригинальное решение можно найти в этой статье. Здесь я хочу привести решение для случая когда Алиса загадывает только натуральные числа. В таком виде задача встречается в PEN и во многих классических книжках. Собственно:

Пусть A=\{a_1, a_2, ..., a_n\} и B=\{b_1, b_2, ..., b_n\} - различные мультимножества натуральных чисел. Определим мультимножество A^{(2)}=\{a_i+a_j \mid i \neq j\}, аналогично B^{(2)}. При каких n возможно равенство A^{(2)}=B^{(2)}?

(мультимножество - это, по сути, множество в котором допускаются повторения элементов. Например \{1, 1, 2\} и \{1, 1, 1, 2\} - различные мультимножества, но \{1, 1, 2\} и \{1, 2, 1\} - одинаковые.)

Вот супер-красивое(имхо) решение с AoPS за авторством пользователей erken и freemind.

Введем многочлены f(x)=x^{a_1}+x^{a_2}+...+x^{a_n} и g(x)=x^{b_1}+x^{b_2}+...+x^{b_n}. Тогда равенство A^{(2)}=B^{(2)} означает равенство многочленов f(x)^2-f(x^2) и g(x)^2-g(x^2). Перепишем это в другом виде: (f(x)-g(x))(f(x)+g(x))=f(x^2)-g(x^2).

Обозначим многочлен f(x)-g(x) через h(x)=(x-1)^tq(x), так чтобы q(1)\neq0. Это возможно благодаря тому что мультисеты A и B различны. Значит q(x)(f(x)+g(x))=(x+1)^tq(x^2). Подставим x=1 и получим 2n=f(x)+g(x)=2^t, следовательно n=2^{t-1} - степень двойки (t>0 потому что f(1)-g(1)=0).

Но это не все. Мы показали, что если A^{(2)}=B^{(2)} то n=2^k. Для полноценного решения необходимо привести примеры таких мультимножеств A, B для всех n=2^k. Заметим, что если A^{(2)}=B^{(2)}, то и для A'=\{a_1, a_2, ..., a_n, b_1+c, b_2+c, ..., b_n+c\} и B'=\{b_1, b_2, ..., b_n, a_1+c, a_2+c, ..., a_n+c\} выполняется аналогичное равенство, где c - достаточно большое натуральное число гарантирующее A' \neq B'. Поэтому, достаточно найти подходящие мультисеты для n=2, например A=\{2,3\}, \ \ B=\{1, 4\}.

Также стоит упомянуть, что n не может равняться единице по очевидным причинам. И так, ответ: n=2^k, k>0.

Мы не зря использовали обозначение A^{(2)}, задача обобщается ещё дальше - для каких натуральных n, s существуют различные A, B, что A^{(s)}=B^{(s)} и |A|=|B|=n? Я не знаю. Советую ознакомиться с вот этой статьей, в ней собраны почти все полученные на данный момент продвижения. Некоторые результаты довольно неожиданны. В частности, A^{(3)}=B^{(3)} возможно только при n = 3, 6, 27, 486, или же A^{(4)}=B^{(4)} только при n=4, 8, 12. Вот пара примеров:

  • n=6, \ s=3: \ \ \ \ A=\{1, 5, 8, 9, 10, 15\}, \ \ B=\{3, 5, 6, 7, 11, 16\}
  • n=12, \ s=4: \ \ \ \ A=\{1, 1, 4, 6, 7, 8, 8, 9, 10, 12, 15, 15\}, \ \ B=\{0, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 16\}

Можете проверить :slight_smile:

2 симпатии
© 2021 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)