problema facile da gara nazionale danese

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
alunik
Messaggi: 69
Iscritto il: 05 dic 2009, 12:07

problema facile da gara nazionale danese

Messaggio da alunik » 10 gen 2012, 13:39

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?
[tex]\equiv mergency[/tex]

Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Re: problema facile da gara nazionale danese

Messaggio da Karl Zsigmondy » 10 gen 2012, 14:51

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.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"

Avatar utente
alunik
Messaggi: 69
Iscritto il: 05 dic 2009, 12:07

Re: problema facile da gara nazionale danese

Messaggio da alunik » 10 gen 2012, 14:55

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,...
[tex]\equiv mergency[/tex]

Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Re: problema facile da gara nazionale danese

Messaggio da Karl Zsigmondy » 10 gen 2012, 15:20

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.
Ultima modifica di Karl Zsigmondy il 10 gen 2012, 17:38, modificato 1 volta in totale.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"

fph
Site Admin
Messaggi: 3835
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: problema facile da gara nazionale danese

Messaggio da fph » 10 gen 2012, 15:40

Karl Zsigmondy ha scritto: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.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
stickman
Messaggi: 7
Iscritto il: 24 dic 2011, 13:17

Re: problema facile da gara nazionale danese

Messaggio da stickman » 10 gen 2012, 15:49

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$.

Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Re: problema facile da gara nazionale danese

Messaggio da Karl Zsigmondy » 10 gen 2012, 17:59

fph ha scritto:
Karl Zsigmondy ha scritto: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.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"

fph
Site Admin
Messaggi: 3835
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: problema facile da gara nazionale danese

Messaggio da fph » 10 gen 2012, 19:26

Ok, mi mancava il punto che ora sta nelle tue prime tre righe! :D
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Rispondi