|
В связи с одной из задач, которая сегодня была на форуме, я вспомнил о таком довольно интересном факте, доказательство которого предлагаю найти всем желающим. Способ рассуждения может быть отличным от того, который мне известен, поэтому интересно узнать, каковы могут быть здесь подходы. Начнём с такого замечания: числа 1, 2, 3, 4 можно разбить на две группы по два числа в каждой, где суммы чисел в каждой из групп одинаковы: $%1+4=2+3$%. При этом суммы квадратов получаются уже разными: $%1^2+4^2\ne2^2+3^2$%. Но для восьми чисел от 1 до 8 можно придумать разбиение на группы по 4 числа в каждой, где совпадают и суммы, и суммы квадратов. Общий факт, который требуется доказать, таков: даны последовательные натуральные числа от $%1$% до $%2^n$%. Требуется разбить их на две группы одинаковой численности так, чтобы для любого $%k$% от $%1$% до $%n-1$% сумма $%k$%-х степеней чисел в той и другой группе была одинаковой. Заметим также, что сюда можно было бы включить случай $%k=0$%, так как суммы нулевых степеней дают количество чисел в группах. задан 13 Окт '14 0:08 
falcao
показано 5 из 7
показать еще 2
|
|
Достаточно доказать, что если имеют место равенства $%\Sigma a^k_i=\Sigma b^k_i$% для всех $%k\le n-1$%, то для чётного $%n$% для всех $%k\le n$% выполняются равенства $$\Sigma a^k_i+\Sigma (c-b_i)^k=\Sigma b^k_i+\Sigma (c-a_i)^k,$$ а для нечётного $%n$% для всех $%k\le n$% выполняются равенства $$\Sigma a^k_i+\Sigma (c-a_i)^k=\Sigma b^k_i+\Sigma (c-b_i)^k.$$ Доказательство сводится просто до раскрытия скобок и группировки слагаемых. отвечен 12 Дек '14 23:19 
EdwardTurJ 1
@EdwardTurJ: там можно даже не различать случай чётного и нечётного, если заметить, что новая последовательность номеров строится путём замены 0 на 01 и 1 на 10 (нули и единицы отвечают за каждое из множеств). Тогда у n-х степеней получатся разности соседних элементов, а они раскладываются по младшим степеням.
(12 Дек '14 23:23)
falcao
|
|
Для 8 чисел в одной группе будут 2, 3, 5, 8. Для 16 чисел в одной группе будут 2, 3, 5, 8, 9, 12, 14, 15. Для 32 - эти же + ещё восемь с симметричными номерами. Осталось только доказать. =) отвечен 13 Окт '14 1:38 
Igore 1
Да, такая закономерность действительно имеет место, и она дальше продолжается по тому же принципу. Это можно рассматривать как верный шаг на пути к решению.
(13 Окт '14 1:43)
falcao
|
Пусть $% \mathcal{N}_m =\{1,2,...,m\}, \mathcal{M[\phi (x)]} $% – множество корней многочлена $% \phi (x). $% Эквивалентно ли условие задачи следующему: для любого $% m=2^n $% существуют многочлен $% f(x) $% (степени $% 2^{n-1}-1 $%) и числа $% a, b, $% для которых $% \mathcal{M[xf(x)+a]} \bigcup \mathcal{M[xf(x)+b]} = \mathcal{N}_m? $%
@Urt: на этот вопрос будет проще ответить, зная то, каким образом возникло это предположение, то есть какой именно многочлен $%f(x)$% возникает в соответствии с разбиением. Тогда должно стать ясно, работает ли это всё в обратную сторону.
В данном случае всё описывается словом Туэ - Морса. Это, судя по всему, исторически первая задача, где такое слово возникло (Prouhet, 1851).
Есть похожая задача:
Даны последовательные натуральные числа от $%1$% до $%2^n-1$%. Требуется разбить их на две группы так, чтобы для любого $%k$% от $%1$% до $%n−1$% сумма $%k$%-х степеней чисел в той и другой группе была одинаковой.
@EdwardTurJ: мне кажется, это фактически та же самая задача, потому что с включением нуля будут числа от 0 до $%2^n-1$%, а это эквивалентно случаю чисел от 1 до $%2^n$%. Там можно брать любые последовательные в таком количестве.
@falcao: Действительно, это фактически та же самая задача, но решение последней задачи описать проще: разбиение по чётности суммы цифр в двоичной системе.
@EdwardTurJ: то слово из нулей и единиц, которое здесь получается в процессе описания, в точности этим свойством и обладает, что видно из построения. Просто надо первый член последовательности считать нулевым.
@falcao, со степенями я напутал (их взял как в проблеме Prouhet–Tarry–Escott, а множество чисел – из задачи). Формулировка утверждения для многочленов проходит из следующего соображения. Если равны суммы всех k-х степеней двух множеств чисел при k=1,...m-1, то равны и суммы всех k-наборов произведений этих чисел. Если теперь числа из этих двух множеств взять в качестве корней двух многочленов, то все их старшие коэффициенты (определенное задачей число) совпадут (при этом вместо чисел a,b в утверждении должны быть многочлены). Для решения задачи пользы, конечно, не будет, а для многочленов(?)