Partizionare potenze del due

[rand]

Dimostrare che:
Per ogni k si possono partizionare gli interi da 1 a $ 2^k $ in due insiemi A e B tali che, per ogni $ 1 \leq i \leq k-1 $, le sommatorie delle potenze i-esime degli interi in A e in B sono uguali. Enjoy!

P.S.: l'ho postato qui perchè la soluzione mi sembra essenzialmente combinatoria

[Tibor Gallai]

E' molto bellino. Io lo dimostro in modo algebrico, ma sono curioso di sapere la tua soluzione combinatoria. Se nessuno la trova, ricordati di postarla!
Qual è la fonte del problema?

[rand]

Beh, in effetti forse sono io che confondo Algebra e Combinatoria .
Al di là di questo la soluzione dovrebbe essere quella. Se volete leggerla ecco la partizione che risolve il problema:

In A tutti gli interi che hanno un numero pari di 1 nella rappresentazione binaria e in B tutti gli altri

[Tibor Gallai]

Tenderei anche a congetturare che quegli A e B che dici (che per come è posto il problema andrebbero traslati in avanti di 1...) siano gli unici con quella proprietà. Sai se è vero questo?

Da dove esce il problema? Ha qualche applicazione?