2007 scatolette

lpcr · Utente Non Attivo Registrato: Jan 17, 2007 Messaggi: 190

Abbiamo 2007 scatolette numerate da 1 a 2007 (con molta fantasia!)
Nella scatoletta numero uno c'è una pallina, nella scatoletta due ci sono due palline... nella scatoletta duemilasette ci sono (rullo di tamburi) 2007 palline.
Si ok, la scatoletta 2007 non può essere tanto scatoletta, sarà uno scatolone... ma fa niente.
Vogliamo adesso svuotare tutte queste scatolette, ma per un buon motivo che adesso non mi viene in mente ma sono sicuro che esista, decidiamo di dividere il processo in turni.
Ad ogni turno si può solamente scegliere un sottoinsieme delle 2007 scatolette e togliere da tali scatolette lo stesso numero di palline.
Ovviamente deve essere possibile farlo; quindi ad ogni turno, scelto un sottoinsieme di scatolette, si può togliere al massimo il numero di palline contenute nella scatoletta con il minor numero di palline (ci tengo che sia una scatoletta e non una banale scatola).
La domanda è ovviamente, amesso che il testo sia stato fin qui comprensibile: qual'è il minor numero di turni necessari per svuotare tutte le scatolette?

KitCarson · Inviato: Mar Feb 20, 2007 6:05 pm Oggetto:

Direi uno se la scatola 1 è contenuta nella due che è contenuta nella tre e così via.
Altrimenti siono 11 visto che 2^11>2007, svuotando le sole scatole opportune di 2^n palline.

Ciao

Carson

Ipazia · Inviato: Mer Feb 21, 2007 11:18 am Oggetto:

KitCarson · Inviato: Mer Feb 21, 2007 12:36 pm Oggetto:

Ipazia · Inviato: Mer Feb 21, 2007 1:51 pm Oggetto:

[quote="KitCarson"]

lpcr · Utente Non Attivo Registrato: Jan 17, 2007 Messaggi: 190

Ok per il risultato.
Per la dimostrazione... Vorrei qualche motivazione un poco più solida del fatto che la combinazione proposta al turno n è l'unica per le SCATOLETTE minori di 2^n. Così mi sembrerebbe esaurito il problema.

lpcr · Utente Non Attivo Registrato: Jan 17, 2007 Messaggi: 190

Ah già la matrioska... Beh non l'avevo prevista, ma scomporre la matrioska equivale a togliere palline da una scatoletta, per come l'ho capita io... ma magari non ho capito cosa intendi.
Potresti spiegarti meglio (insomma pistona o spiegazione invece di pistina?)

KitCarson · Inviato: Mer Feb 21, 2007 4:37 pm Oggetto:

Per la matrioska hai capito esattamente.
Partiva da una diversa distribuzione delle palline e delle scatole, ma visto che così non era....fine.

La dimostrazione che la combinazione proposta è l' unica per le scatolette minori di 2^n non l' ho dimostrato, perchè non è dimostrabile essendo falso.
Io mi fermo ad affermare che questo è vero per per un numero di scatole del tipo (2^n)-1 e peraltro senza dimostrarlo se non empiricamente.
Si può dimostrare: posto che il solo miglior modo per le prime 3 scatole è di utilizzare 1 e 2, per 7 scatole non potrà esisterne uno migliore che 1,2,4 poichè la mancanza di 1 o di 2 produrrà un sicuro peggioramento e pertanto il solo numero che con un solo altro passaggio ci permette di coprire le restanti scatole è 7-1-2=4.
Qualunque valore inferiore a 4 (2^2) richiederà un ulteriore passaggio per giungere a 7 ( (2^3)-1 ) e qualunque valore maggiore ci richiederà ugualmente un "doppio passaggio" per giungere a 4.

Analogamente avendo dimostrato che la sola miglior scomposizione per 7 è 1,2,4 dimostri che per 15 è 1,2,4,8 e così via.

Il che altro non vuol dire che il metodo "più economico" per rappresentare tutti i numeri da 1 a (2^n)-1 è il sistema binario.

Tuttavia, come avrai notato non ho detto quali siano i numeri da utilizzare per la soluzione finale.
Questo poichè seppure l' utilizzo delle potenze di 2 non sia migliorabile, non è detto che sia l' unica soluzione, anzi non la è sicuramente.
Cio che è certo è che debba contenere 1,2,4,8,16,32,64,128,256, e 512.
L' ultimo numero è a piacere in quelli che vanno da 1004 a 1024.

Ciao

Carson

lpcr · Utente Non Attivo Registrato: Jan 17, 2007 Messaggi: 190

Si ok, la fretta fa brutti scherzi, ovviamente non è l'unica possibilità.
Pe il resto, la dimostrazione è convincente, anche se in alcuni punti è un pò vaga, comunque per me è sostanzialmente corretta come idea.
Riesci a formalizzarla un pò meglio?
Comunque la mia idea era un pò diversa, magari la metto sotto in piccolo:

Supponiamo che ad un certo istante ci siano n gruppetti di scatolette con la proprietà che in ogni gruppetto le scatolette che lo compongono contengono lo stesso numero di palline.
Allora se al passo successivo scegliamo un sottoinsieme di scatolette da cui togliere palline, di queste scatolette ce ne saranno diciamo k che che contengono un numero di palline diverso.
Quindi, poichè abbiamo tolto lo stesso numero di palline a tutte le scatolette, le scatolette continuano ad appartenere ad un gruppetto diverso se e solo se appartenevano prima ad un gruppetto diverso. Degli n gruppetti iniziali con numero di palline diverse ne sono rimasti quindi almeno n/2. Poichè alla fine tutte devono avere lo stesso numero di palline (ciè 0) e all'inizio erano 2007, direbbero quelli bravi: the claim follows!