TST 2015 - B1 - Cartoncini

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

TST 2015 - B1 - Cartoncini

Messaggioda Nadal01 » 01/04/2016, 16:58

Qualcuno mi aiuta a risolvere questo problema :?: :D :oops:

Sia [tex]m[/tex] un intero positivo. Sono dati [tex]2^m[/tex] cartoncini su ciascuni dei quali è inizialmente scritto il numero [tex]1[/tex].
Ad ogni passaggio scegliamo due cartoncini: detti [tex]a[/tex] e [tex]b[/tex] i numeri scritti su di essi, li cancelliamo entrambi e scriviamo al loro posto (su entrambi i cartoncini) il numero [tex]a + b[/tex]. Ripetiamo il procedimento [tex]m2^{m-1}[/tex] volte, scegliendo ogni volta a caso i cartoncini su cui operare.
Dimostrare che alla fine la somma dei numeri scritti su tutti i cartoncini è almeno [tex]4^m[/tex].
Nadal01
 
Messaggi: 68
Iscritto il: 16/01/2015, 17:12

Re: TST 2015 - B1 - Cartoncini

Messaggioda Giovanni98 » 01/04/2016, 18:18

Sia $P_n$ la media geometrica degli interi sui cartoncini dopo l'$n-esima$ mossa. Per $AM-GM$ vale $S_n \ge 2^mP_n$ dove $S_n:=$ la somma degli interi scritti sui cartoncini dopo l'$n-esima$ mossa. Noi quindi ora vogliamo dimostrare che $S_{m2^{m-1}} \ge 4^m$. Siano $a,b$ gli interi su cui applico una mossa. Allora notiamo che $\displaystyle P_{n+1} \ge \sqrt[2^m]{4}P_n$ poichè due fattori della media geometrica di $P_{n+1}$ sarebbero $(a+b)$ e $(a+b)$ , al posto di $a,b$ in $P_n$ ,e poichè $a+b \ge 2\sqrt{ab}$ ho quindi la disuguaglianza desiderata (cioè $(a+b)^2 \ge 4ab$). Ora quindi poichè $P_0=1$ si ha $P_n \ge (\sqrt[2^m]{4})^n$ quindi $P_{m2^{m-1}} \ge 4^\frac{m}{2}$ e per quanto detto prima $S_{m2^{m-1}} \ge 2^m4^\frac{m}{2} = 4^m$ come volevamo.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: TST 2015 - B1 - Cartoncini

Messaggioda Rho33 » 01/04/2016, 18:46

Una domanda: in questi casi è necessario mostrare come raggiungere effettivamente il minimo no? Cioè, quella di Giovanni98 è solo la parte più sostanziosa della soluzione, poi credo manchi questa:

Per raggiungere effettivamente il minimo si può creare un banalissimo algoritmo greedy ( dovrebbe chiamarsi così se non sbaglio) , in cui, per ogni passo, scelgo la migliore mossa possibile. Accoppiamo a caso i $2^m$ cartoncini ed operiamo le prime $2^{m-1}$ mosse su ciascuna coppia, ottenendo tutti $2$ alla fine ( questo è greedy perchè sto mantenendo la somma il più basso possibile). Iteriamo il procedimento $m$ volte, ottenendo come configurazione finale tutti $2^m$ . Chiaramente la loro somma è $2^m \cdot 2^m= 4^m$ , quindi il minimo è effettivamente raggiungibile.
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: TST 2015 - B1 - Cartoncini

Messaggioda Giovanni98 » 01/04/2016, 18:53

Rho33 ha scritto:Una domanda: in questi casi è necessario mostrare come raggiungere effettivamente il minimo no? Cioè, quella di Giovanni98 è solo la parte più sostanziosa della soluzione, poi credo manchi questa:

Per raggiungere effettivamente il minimo si può creare un banalissimo algoritmo greedy ( dovrebbe chiamarsi così se non sbaglio) , in cui, per ogni passo, scelgo la migliore mossa possibile. Accoppiamo a caso i $2^m$ cartoncini ed operiamo le prime $2^{m-1}$ mosse su ciascuna coppia, ottenendo tutti $2$ alla fine ( questo è greedy perchè sto mantenendo la somma il più basso possibile). Iteriamo il procedimento $m$ volte, ottenendo come configurazione finale tutti $2^m$ . Chiaramente la loro somma è $2^m \cdot 2^m= 4^m$ , quindi il minimo è effettivamente raggiungibile.


Certo, ho scritto solo quello perchè la parte difficile del problema era quella.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: TST 2015 - B1 - Cartoncini

Messaggioda Drago » 01/04/2016, 19:48

In realtà non c'è nemmeno bisogno di quest'ultima parte... Chiede di "dimostrare che è almeno..." e una volta che hai la disuguaglianza sei a posto.
Discorso diverso sarebbe stato se avesse chiesto "trova il minimo", e a quel punto occorreva trovare anche l'esempio...
Avatar utente
Drago
 
Messaggi: 1056
Iscritto il: 14/03/2013, 15:51

Re: TST 2015 - B1 - Cartoncini

Messaggioda Nadal01 » 01/04/2016, 21:38

Grazie :D
Nadal01
 
Messaggi: 68
Iscritto il: 16/01/2015, 17:12


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti