problema facile da gara nazionale danese

[alunik]

Posto il problema 3, é facile, spero sia la sezione giusta.
Georg sta mettendo 250 figurine in un album. Sulla prima pagina ne mette una e su ogni pagina successiva può scegliere se metterne lo stesso numero della pagina precedente o raddoppiare. In questo modo finisce per metterne esattamente 250. Quante pagine gli servono come minimo?

[Karl Zsigmondy]

Il problema equivale al trovare il minimo della somma a+b+c+d+e+f+g+h (numeri naturali) sapendo che $ 128a+64b+32c+16d+8e+4f+2g+h=250 $. Ora ho che tutte le quantità in questione sono 0 oppure 1, dal momento che se a fosse 2 (o più) supererei 256, mentre se un altro fosse 2 (o più) potrei togliere 2 e aggiungere 1 alla quantita immediatamente precedente in ordine alfabetico, in modo da diminuire la somma a+b+c+d+e+f+g+h. Si ha che:
$ 128+64+32+16+8=248 < 250 $ da cui $ a+b+c+d+e+f+g+h > 5 $. Inoltre questa somma può essere 6 ponendo a=b=c=d=e=1, f=0, g=1, h=0, infatti in tal modo ottengo $ 128+64+32+16+8+2=250 $. Pertanto ho che servono al minimo 6 pagine.

[alunik]

Il problema in realtà prevede che tu debba comunque passare per una potenza di 2 prima di arrivare alla successiva. Del tipo puoi fare 1,1,2,4,8,8 ma non 1,2,8,...

[Karl Zsigmondy]

Si, scusami, avevo capito male il testo. Comunque, di 1 ce ne sono almeno due altrimenti la somma non sarebbe pari, ma non ce ne possono essere 4 perché altrimenti risparmierei 1 pagina mettendo 2 figurine in una. Ora ho che
$ 1+1+2+4+8+16+32+64+128=256>250 $ quindi non ci saranno 128 figurine in una pagina, ma al più 64. Ora, se non ci fossero pagine con 64 figurine, ne sarebbero necessarie almeno 15 per le 250 figurine (infatti $ 1+1+2+2+4+8+8+16+16+6 \cdot 32 = 250 $, ma come si vedrà in seguito posso farcela con meno pagine (non posso distribuire meglio le figurine nelle pagine nella somma appena trattata, perchè di ogni tipo di pagina ce ne sono 2 o meno, fatta eccezione per le pagine di 32 figurine). Dato che c'è almeno una pagine con 64 figurine, ce n'è una almeno per ogni altra potenza di due inferiore, quindi ci sono almeno $ 1+1+2+4+8+16+32+64=128 $ figurine già considerabili sistemate. Le restanti 122 possono essere sistemare in pagine rispettivamente da $ 64,32,16,8,2 $ figurine. Non posso migliorare la distribuzione perché la somma di tutte le figurine contenute in pagine con meno figurine di una fissata è minore delle figurine contenute nella pagine fissata. Sono necessarie quindi almeno 13 pagine.

EDIT: avevo aggiunto una potenza di 2 a caso, ho sistemato e ora ne vengono 13.

[fph]

Ora, se non ci fossero pagine con 64 figurine, ne sarebbero necessarie almeno 15 per le 250 figurine (infatti $ 1+1+2+2+4+8+8+16+16+6 \cdot 32 = 250 $, ma come si vedrà in seguito posso farcela con meno pagine (non posso distribuire meglio le figurine nelle pagine nella somma appena trattata, perchè di ogni tipo di pagina ce ne sono 2 o meno, fatta eccezione per le pagine di 32 figurine).

Questo punto non mi sembra chiarissimo, secondo me stai dando per scontato un ragionamento che c'è nella tua testa ma non hai scritto nero su bianco.

[stickman]

A me è venuta una combinazione da 13: $1+1+2+2+2^2+2^3+2^3+2^4+2^4+2^5+2^5+2^6+2^6$.

[Karl Zsigmondy]

Ora, se non ci fossero pagine con 64 figurine, ne sarebbero necessarie almeno 15 per le 250 figurine (infatti $ 1+1+2+2+4+8+8+16+16+6 \cdot 32 = 250 $, ma come si vedrà in seguito posso farcela con meno pagine (non posso distribuire meglio le figurine nelle pagine nella somma appena trattata, perchè di ogni tipo di pagina ce ne sono 2 o meno, fatta eccezione per le pagine di 32 figurine).

Questo punto non mi sembra chiarissimo, secondo me stai dando per scontato un ragionamento che c'è nella tua testa ma non hai scritto nero su bianco.

Faccio diversamente. Già so che non ci sono 128. Se ci fossero 3 potenze di 2 dello stesso tipo (escludo i 64) potrei migliorare la configurazione sostituendole con la potenza di 2 immediatamente successiva. Pertanto non basta arrivare a 32, infatti per quanto detto potrei sommare $ 1+1+2+2+4+4+8+8+16+16+32+32=126 $ e non arrivo a 250. Mi serve quindi il 64, ora affermo che la somma $ 1+1+2+2+4+8+8+16+16+32+32+64+64=250 $ non è migliorabile. Suppongo per assurdo di poterne sostituire m di esse con n, in cui tutte le m+n sono distinte fra loro (è chiaro che le m posso supporle distinte dalle n, altrimenti la sostituzione sarebbe inutile per i termini uguali fra loro, inoltre le m sono distinte fra loro perché se ne tolgo 2 dello stesso tipo e poi non le sostituisco si crea un "buco", così tra le n non ce ne possono essere di uguali altrimenti potrei sostituire due di esse con la potenza di due immediatamente successiva, a meno che non abbia dei 64 anche se questo caso, come si vedrà, non mi dà fastidio). Allora avrei che $ 2^{a_1} + \cdots + 2^{a_m} = 2^{b_1} + \cdots + 2^{b_n} $ con WLOG $ a_1 < \cdots < a_n \ ; \ b_1 < \cdots < b_n $. Allora $ V_2(LHS)=a_1 \neq b_1 = V_2(RHS) $ da cui segue che ho un assurdo (ecco che i 64 contano poco). Quindi non posso migliorare in quanto a numero di elementi la somma $ 1+1+2+2+4+8+8+16+16+32+32+64+64= 250 $. Comunque per far vedere che la configurazione era ottimale penso andasse bene anche l'altra dimostrazione, anche se qui completo le motivazioni per cui vale.
Spero sia chiara ora.

[fph]

Ok, mi mancava il punto che ora sta nelle tue prime tre righe!