Dal BST dello scorso WC

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Dal BST dello scorso WC

Messaggioda cip999 » 04/01/2016, 18:12

Abbiamo $2^n$ numeri che all'inizio sono tutti $1$. Per $n2^{n - 1}$ volte facciamo la seguente cosa: scegliamo due numeri e li sostituiamo con la loro somma (ripetuta due volte, una per ogni numero rimosso).
Sia $S$ la somma dei numeri alla fine. Quanto vale come minimo $S$?
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: Dal BST dello scorso WC

Messaggioda Ale99 » 04/01/2016, 21:01

Senza essere troppo formali

Testo nascosto:
Bon dimostriamo che la somma minima è $ 4^n $ . Per farlo procediamo in maniera greedy ovvero ogni volta scegliamo i due numeri da operare in maniera che la somma sia minima ; ovviamente dunque ad ogni passo sommeremo i due più piccoli quindi ad esempio dopo $2^{n-1}$ mosse avremo la configurazione $ 2-2 \cdots 2-2$ .
Dunque dividendo idealmente per $ 2 $ ogni numero torniamo alla situazione iniziale e dunque applicheremo l'algoritmo greedy nello stesso modo .
Reiterando il procedimento per $n$ volte otteniamo $ S_i = 2^n $ , ed ora dovremo andare a moltiplicare qusta somma fittizia per $ 2 ^ {i} $ dove $ i $ è il numero delle volte che abbiamo reiterato il procedimento ovvero $ n $ . Dunque $ S_{min} = 2^n \cdot 2^n = 4^n $
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Avatar utente
Ale99
 
Messaggi: 482
Iscritto il: 24/08/2014, 11:51

Re: Dal BST dello scorso WC

Messaggioda Lasker » 04/01/2016, 21:21

@Ale99: non è che non sei stato formale, manca proprio tutta la dimostrazione! Cioè, hai solo trovato un buon candidato ad essere il valore $S$, ma nessuno ti assicura (per il momento) che sia davvero il minimo.
Cur enim scribere tre numeri quando se ne abbisogna di due? Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani.

PRIMA FILA TUTTI SBIRRI!

#FREELEPORI
Lasker
 
Messaggi: 834
Iscritto il: 17/03/2013, 16:00

Re: Dal BST dello scorso WC

Messaggioda Ale99 » 04/01/2016, 22:23

Capisco , quindi non basta dire che abbiamo la somma minima quando scegliamo ogni volta i due numeri più piccoli ? Oppure è un'affermazione che va dimostrata in qualche modo ?
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Avatar utente
Ale99
 
Messaggi: 482
Iscritto il: 24/08/2014, 11:51

Re: Dal BST dello scorso WC

Messaggioda Ale99 » 04/01/2016, 22:36

Comunque ho trovato anche un'altra soluzione che credo sia una vera soluzione

Testo nascosto:
Sia [tex]P_k[/tex] il prodotto dei nuemeri scritti sui fogli all'$k$-esima mossa . Supponiamo dunque che alla $ k+1 $-esima mossa i numeri $ x,y $ vengono sostituiti da $ (x+y) $ e dunque nel prodotto avremo $ ( x+y) ^ 2 $ invece che $ xy $ , per il resto non cambia . Ma per ovvie disuguaglianze $ (a+b) ^ 2 \ge 4ab $ dunque avremo $ P_{k+1} \ge 4 P_k $ ed in particolare ( partendo da $ P_0 = 1 $ ) otteniamo che [tex]P_{2^{n-1}\cdot n} \ge (2^n)^{2^n}[/tex] .
ora abbiamo che per AM-GM $ S \ge 2^n \cdot \sqrt[n^2] {P_{2^{n-1}\cdot n}} = 4^ n $
Dobbiamo ora dimostrare che possiamo effettivamente ottenere questo minimo e questo lo facciamo come nel post di sopra ...
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Avatar utente
Ale99
 
Messaggi: 482
Iscritto il: 24/08/2014, 11:51

Re: Dal BST dello scorso WC

Messaggioda Lasker » 04/01/2016, 23:02

Ale99 ha scritto:è un'affermazione che va dimostrata in qualche modo ?

Esatto, nella soluzione lo davi per scontato, e non è proprio ovvio... o almeno io non sono riuscito a dimostrarlo durante il BST provando con tecniche banali (tipo varianti dell'induzione) e ho preso giustamente zero :roll: .
La seconda soluzione invece dovrebbe andare bene (a memoria è uguale a quella "ufficiale"), bravo!
Cur enim scribere tre numeri quando se ne abbisogna di due? Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani.

PRIMA FILA TUTTI SBIRRI!

#FREELEPORI
Lasker
 
Messaggi: 834
Iscritto il: 17/03/2013, 16:00

Re: Dal BST dello scorso WC

Messaggioda Ale99 » 04/01/2016, 23:11

Perchè esistono le soluzioni ufficiali dei bst ??? Sarebbe una gran cosa , almeno per me ...
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Avatar utente
Ale99
 
Messaggi: 482
Iscritto il: 24/08/2014, 11:51

Re: Dal BST dello scorso WC

Messaggioda Lasker » 04/01/2016, 23:13

Beh, la maggior parte sono IMO SL medio/bassi dell'anno del BST (che viene resa pubblica solo 5 mesi dopo con le IMO), e questo non fa eccezione! Tipo al prossimo WC nel BST appariranno quasi sicuramente dei problemi tratti dalla misteriosa SL delle IMO 2015 (moltissimi stati costruiscono così alcuni dei loro test di selezione). Anche alcuni problemi delle sessioni fanno parte di questa grande famiglia, quindi se andrai al WC (non so se hai provato oppure no :? ) ti verrà detto di non divulgarli a chicchessia.
Ultima modifica di Lasker il 04/01/2016, 23:16, modificato 2 volte in totale.
Cur enim scribere tre numeri quando se ne abbisogna di due? Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani.

PRIMA FILA TUTTI SBIRRI!

#FREELEPORI
Lasker
 
Messaggi: 834
Iscritto il: 17/03/2013, 16:00

Re: Dal BST dello scorso WC

Messaggioda Ale99 » 04/01/2016, 23:15

Ah non lo sapevo , grazie mille Lasker . Ecco perchè vengono pubblicate solo dopo un anno ...
Comunque si ho provato per il WC , speriamo bene ..
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Avatar utente
Ale99
 
Messaggi: 482
Iscritto il: 24/08/2014, 11:51


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti