?

Log in

No account? Create an account
задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [авг. 13, 2011|07:25 pm]
Anatoly Vorobey
Хорошая задачка, которую тривиально решить с помощью компьютерной программы, а без нее не так легко:

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

Comments:
[User Picture]From: e2pii1
2011-08-13 05:32 pm
1 4 6 7 10 11 13 16

(Ответить) (Thread)
[User Picture]From: saviorsorrow
2011-08-13 05:33 pm
В одной группе должны быть числа:
1-16,4-13,6-11,7-10
в другой:
2-15,3-14,5-12,8-9

(Ответить) (Thread)
[User Picture]From: os80
2011-08-13 06:18 pm
И, самое главное, это задачка имеет огромное народохозяйственное значение.
(Ответить) (Thread)
[User Picture]From: falcao
2011-08-13 07:42 pm

0110100110010110

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

Edited at 2011-08-13 19:42 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2011-08-13 07:49 pm

Re: 0110100110010110

Я не знал, но на Google+ мне уже подкинули ссылку на википедию, да. Спасибо!
(Ответить) (Parent) (Thread)
[User Picture]From: falcao
2011-08-13 08:30 pm

вглубь веков

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

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

Интересно ещё, что после работы Морса и Хедлунда пришлось внести изменения в шахматный кодекс :) Вместо "троекратного повторения ходов" (здесь можно играть бесконечно) написали о "троекратном повторении позиции" как достаточного условия требовать ничью.
(Ответить) (Parent) (Thread)
[User Picture]From: spartach
2011-08-26 12:37 pm

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

Эх, и я эту последовательность в далёком детстве "изобрёл", и думал, что должны быть крутые свойства, но такого не придумал...
(Ответить) (Parent) (Thread)
From: ztarlitz
2011-08-13 08:56 pm

Re: 0110100110010110

ух ты как круто! спасибо
(Ответить) (Parent) (Thread)
From: (Anonymous)
2011-08-14 05:12 am

Re: 0110100110010110

И от меня спасибо. Я, читая это в 4 утра на железнодорожной станции, минут пять пытался въехать, каким это образом получается, что в википедии говорится про числа 0..2^n-1, а здесь — про 1..2^n, и все равно все сходится. Из ступора вывел гудок поезда...
(Ответить) (Parent) (Thread)
From: 9000
2011-08-14 11:55 pm

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

А вот само замечание, что так разделить можно — это здорово :)
(Ответить) (Thread)
[User Picture]From: darkov
2011-08-16 10:55 pm
Переформулируем задачу.
Нужно найти коэффициенты Аi = +1 или -1, такие, что выполняются равенства.
A1 + A2 + ... = 0 (1a)
A1 1 + A2 2 + ... = 0 (2a)
A1 12 + A2 22 + ... = 0 (3a)
A1 13 + A2 23 + ... = 0 (4a)

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

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

B1 (-1 + 2) + B2 (-3 +4) + ... = 0 (2b)
B1 (-12 +22) + B2 (-32 +42) + ... = 0 (3b)
B1 (-13 +23) + B2 (-33 +43) + ... = 0 (4b)

Или пересчитав:
B1 + B2 + B3 + B4 + ... = 0 (2b)
B1 3 + B2 7 + B3 11 + B4 15 + ... = 0 (3b)
B1 7 + B2 37 + B3 91 + B4 169 + ... = 0 (4b)

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

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

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

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

C1 4 + C2 4 + ... = 0 (3c)
C1 30 + C2 78 + C3 30 + C4 78 + ... = 0 (4c)

C1 4 + C2 4 + C3 4 + C4 4 + ... = 0 (3c)
C1 30 + C2 78 + C3 126 + C4 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 чисел и с пятыми степенями было все хорошо.

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

(Ответить) (Thread)
[User Picture]From: darkov
2011-08-16 11:02 pm
Почитав другие комментарии, устыдился своей необразованности.
(Ответить) (Parent) (Thread)