задачка

[avva]

Хорошая задачка, которую тривиально решить с помощью компьютерной программы, а без нее не так легко:

Разделить числа от 1 до 16 на две группы одинакового размера, так что выполняются
следующие три условия:
- суммы чисел в двух группах равны
- а также суммы квадратов чисел равны
- а также суммы кубов чисел равны

Comments

[e2pii1.livejournal.com]

1 4 6 7 10 11 13 16

[saviorsorrow.livejournal.com]

В одной группе должны быть числа:
1-16,4-13,6-11,7-10
в другой:
2-15,3-14,5-12,8-9

[os80.livejournal.com]

И, самое главное, это задачка имеет огромное народохозяйственное значение.

0110100110010110

[falcao.livejournal.com]

А Вы в курсе общего решения этой задачи? То есть для чисел от 1 до 2ⁿ, и чтобы в каждой из двух групп совпадали суммы k-х степеней при всех 0<=k<n. Это результат примерно 1850 года, и это "исторически первый" пример появления замечательной последовательности, которую позже стали именовать в честь Туэ и Морса. Принцип разбиения довольно простой: число m относим к первой или второй группе в зависимости от чётности или нечётности количества единиц в двоичной записи числа m-1.

Re: 0110100110010110

[avva.livejournal.com]

Я не знал, но на Google+ мне уже подкинули ссылку на википедию, да. Спасибо!

вглубь веков

[falcao.livejournal.com]

С этой последовательностью вообще замечательная история была. Её "переоткрывали" чуть ли не десяток раз, не зная о "предшественниках". У нас говорили о "последовательности Аршона" (работа 1937 года), у Морса и Хедлунда была работа в 40-х годах, потом французы какие-то в 60-е годы заново это всё получали. В конце 70-х нашли старые работы Туэ (1906 года), про которые все забыли. Это считалось самым первым упоминанием, а потом обнаружили работу Prouhet середины XIX века как раз с задачей о суммах степеней.

Один мой коллега "не выдержал", и в обзоре написал, что скоро найдут эту же последовательность в каких-нибудь наскальных рисунках первобытного человека :)

Интересно ещё, что после работы Морса и Хедлунда пришлось внести изменения в шахматный кодекс :) Вместо "троекратного повторения ходов" (здесь можно играть бесконечно) написали о "троекратном повторении позиции" как достаточного условия требовать ничью.

Re: 0110100110010110

[ztarlitz.livejournal.com]

ух ты как круто! спасибо

Re: 0110100110010110

[(Anonymous)]

И от меня спасибо. Я, читая это в 4 утра на железнодорожной станции, минут пять пытался въехать, каким это образом получается, что в википедии говорится про числа 0..2^n-1, а здесь — про 1..2^n, и все равно все сходится. Из ступора вывел гудок поезда...

[nine_k]

"Don't send a human do a computer's work" (ц)
Интереснее написать самую короткую / выразительную / эффективную программу для этого.

А вот само замечание, что так разделить можно — это здорово :)

[darkov.livejournal.com]

Переформулируем задачу.
Нужно найти коэффициенты А_i = +1 или -1, такие, что выполняются равенства.
A₁ + A₂ + ... = 0 (1a)
A₁ 1 + A₂ 2 + ... = 0 (2a)
A₁ 1² + A₂ 2² + ... = 0 (3a)
A₁ 1³ + A₂ 2³ + ... = 0 (4a)

Заметим, что (без учета знаков) имеем четыре последовательности, первая константа, вторая линейная, третья квадратичная, четвертая кубичная. Все дальнейшие действия будут связаны с манипуляциями парами соседних членов.

Положим, что A_2n-1 = - A_2n.
Первое равенство при этом выполнится. Перепишем все остальные в следующем виде

B₁ (-1 + 2) + B₂ (-3 +4) + ... = 0 (2b)
B₁ (-1² +2²) + B₂ (-3² +4²) + ... = 0 (3b)
B₁ (-1³ +2³) + B₂ (-3³ +4³) + ... = 0 (4b)

Или пересчитав:
B₁ + B₂ + B₃ + B₄ + ... = 0 (2b)
B₁ 3 + B₂ 7 + B₃ 11 + B₄ 15 + ... = 0 (3b)
B₁ 7 + B₂ 37 + B₃ 91 + B₄ 169 + ... = 0 (4b)

Снова же заметим, что (без учета знаков) последовательность слагаемых в (2b) - константа, в (3b) - линейная, в (4b) - квадратичная.

Положив B_2n-1 = - B_2n, получим выполнение равенства (2b).

На данном этапе мы получили следующее,
если разбить всю последовательность А_i на четверки и внутри каждой четверки положить
(А_4m+1,А_4m+2,А_4m+3,А_4m+4) = +- (-1, +1, +1, -1)
то мы получим выполнение равенств (1) и (2).

Еще раз перепишем равенства (3b) и (4b)
C₁ (-3 + 7) + C₂ (-11 +15) + ... = 0 (3c)
C₁ (-7 + 37) + C₂ (-91 +169) + ... = 0 (4c)

C₁ 4 + C₂ 4 + ... = 0 (3c)
C₁ 30 + C₂ 78 + C₃ 30 + C₄ 78 + ... = 0 (4c)

C₁ 4 + C₂ 4 + C₃ 4 + C₄ 4 + ... = 0 (3c)
C₁ 30 + C₂ 78 + C₃ 126 + C₄ 174 + ... = 0 (4c)

Положив С_2n-1 = - С_2n, получим выполнение равенства (3с).

Итогом этого этапа является тот факт, что если разбить всю последовательность А_i на восмерки
с значениями внутри каждой с точностью до знака равными (-1,+1,+1,-1,+1,-1,-1,+1),
то мы получим выполнение равенств (1), (2) и (3)


Надеюсь, понятно как получить, что последовательность A = (-1,+1,+1,-1,+1,-1,-1,+1, +1,-1,-1,+1,-1,+1,+1,-1) удовлетворяет всем равенствам
(1)-(4)

Заодно, должно быть ясно как разбить на две группы числа от 1 до 32, так чтобы и суммы четвертых степеней совпадали. А для 64 чисел и с пятыми степенями было все хорошо.

Уф. Индексы набивать на ночь глядя очень утомительно. Так что, я тут больше основную мысль обозначал, чем строго доказывал.

[darkov.livejournal.com]

Почитав другие комментарии, устыдился своей необразованности.

Re: вглубь веков

[spartach.livejournal.com]

Эх, и я эту последовательность в далёком детстве "изобрёл", и думал, что должны быть крутые свойства, но такого не придумал...