TST 2015 - B1 - Cartoncini

[Nadal01]

Qualcuno mi aiuta a risolvere questo problema

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

[Giovanni98]

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.

[Rho33]

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.

[Giovanni98]

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.

[Drago]

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

[Nadal01]

Grazie