Partizionare potenze del due

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Partizionare potenze del due

Messaggio da rand » 07 dic 2009, 12:12

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
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 08 dic 2009, 18:16

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! :roll:
Qual è la fonte del problema?
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 09 dic 2009, 13:02

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
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 09 dic 2009, 13:51

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?
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Rispondi