В связи с одной из задач, которая сегодня была на форуме, я вспомнил о таком довольно интересном факте, доказательство которого предлагаю найти всем желающим. Способ рассуждения может быть отличным от того, который мне известен, поэтому интересно узнать, каковы могут быть здесь подходы.

Начнём с такого замечания: числа 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

Пусть $% \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? $%

(14 Дек '14 4:09) Urt

@Urt: на этот вопрос будет проще ответить, зная то, каким образом возникло это предположение, то есть какой именно многочлен $%f(x)$% возникает в соответствии с разбиением. Тогда должно стать ясно, работает ли это всё в обратную сторону.

В данном случае всё описывается словом Туэ - Морса. Это, судя по всему, исторически первая задача, где такое слово возникло (Prouhet, 1851).

(14 Дек '14 10:59) falcao

Есть похожая задача:

Даны последовательные натуральные числа от $%1$% до $%2^n-1$%. Требуется разбить их на две группы так, чтобы для любого $%k$% от $%1$% до $%n−1$% сумма $%k$%-х степеней чисел в той и другой группе была одинаковой.

(14 Дек '14 11:40) EdwardTurJ

@EdwardTurJ: мне кажется, это фактически та же самая задача, потому что с включением нуля будут числа от 0 до $%2^n-1$%, а это эквивалентно случаю чисел от 1 до $%2^n$%. Там можно брать любые последовательные в таком количестве.

(14 Дек '14 11:43) falcao

@falcao: Действительно, это фактически та же самая задача, но решение последней задачи описать проще: разбиение по чётности суммы цифр в двоичной системе.

(14 Дек '14 11:51) EdwardTurJ

@EdwardTurJ: то слово из нулей и единиц, которое здесь получается в процессе описания, в точности этим свойством и обладает, что видно из построения. Просто надо первый член последовательности считать нулевым.

(14 Дек '14 12:05) falcao

@falcao, со степенями я напутал (их взял как в проблеме Prouhet–Tarry–Escott, а множество чисел – из задачи). Формулировка утверждения для многочленов проходит из следующего соображения. Если равны суммы всех k-х степеней двух множеств чисел при k=1,...m-1, то равны и суммы всех k-наборов произведений этих чисел. Если теперь числа из этих двух множеств взять в качестве корней двух многочленов, то все их старшие коэффициенты (определенное задачей число) совпадут (при этом вместо чисел a,b в утверждении должны быть многочлены). Для решения задачи пользы, конечно, не будет, а для многочленов(?)

(14 Дек '14 13:16) Urt
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
0

Достаточно доказать, что если имеют место равенства $%\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

1

@EdwardTurJ: там можно даже не различать случай чётного и нечётного, если заметить, что новая последовательность номеров строится путём замены 0 на 01 и 1 на 10 (нули и единицы отвечают за каждое из множеств). Тогда у n-х степеней получатся разности соседних элементов, а они раскладываются по младшим степеням.

(12 Дек '14 23:23) falcao
10|600 символов нужно символов осталось
3

alt text

Для 8 чисел в одной группе будут 2, 3, 5, 8. Для 16 чисел в одной группе будут 2, 3, 5, 8, 9, 12, 14, 15. Для 32 - эти же + ещё восемь с симметричными номерами. Осталось только доказать. =)

ссылка

отвечен 13 Окт '14 1:38

изменен 14 Дек '14 16:08

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

1

Да, такая закономерность действительно имеет место, и она дальше продолжается по тому же принципу. Это можно рассматривать как верный шаг на пути к решению.

(13 Окт '14 1:43) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,288
×115

задан
13 Окт '14 0:08

показан
6821 раз

обновлен
14 Дек '14 13:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru