Rimpiazzi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Nemo
Messaggi: 73
Iscritto il: 03 dic 2013, 17:35

Rimpiazzi

Messaggio da Nemo » 20 apr 2014, 16:53

Su una lavagna sono scritti i numeri $1, 2, 3, \ldots, 2001$. Una mossa consiste nel cancellare due dei numeri scritti, $a$ e $b$, e rimpiazzarli con un (unico) altro numero, $\frac{ab}{a+b+1}$. Dopo $2000$ mosse, è rimasto un solo numero, $k$. Quanto vale $k$?
[math]

Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Rimpiazzi

Messaggio da Triarii » 20 apr 2014, 18:48

Si nota che l'invariante è la somma dei reciproci di tutti i prodotti possibili fra elementi dell'insieme di partenza. (Domanda: in gara lo dovrei dimostrare rigorosamente o basta farlo vedere per, che so, 4 elementi?)
Chiamiamo $I(2001)$ questa quantità. Quando mi resta solo un elemento scritto sulla lavagna (che chiameremo $N$), la somma dei reciproci di tutti i prodotti si riduce ad essere il reciproco del numero stesso. Quindi $N=\dfrac {1} {I(2001)}$.
Ora dobbiamo calcolare $I(2001)$. Come facciamo? Induzione. Voglio infatti dimostrare che I(n)=n.
Passo base: $I(1)=1$ vero per verifica diretta.
Passo induttivo: $I(n)=I(n-1)+\dfrac {I(n)} {n} +\dfrac {1} {n}=n-1+\dfrac {n-1+1} {n}=n-1+1=n$ che è ciò che volevamo mostrare.
Quindi $I(2001)=2001$, da cui $N=\dfrac {1} {2001}$
"We' Inge!"
LTE4LYF

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Rimpiazzi

Messaggio da xXStephXx » 20 apr 2014, 21:08

In caso come invariante dovrebbe andar bene pure
Testo nascosto:
Il prodotto di tutti i numeri aumentati di 1, diviso il prodotto di tutti i numeri.
In questo caso per la verifica dovrebbe bastare la prova su due soli numeri.
[edit] che in effetti a pensarci è la stessa che hai usato tu :lol:

Avatar utente
Nemo
Messaggi: 73
Iscritto il: 03 dic 2013, 17:35

Re: Rimpiazzi

Messaggio da Nemo » 20 apr 2014, 23:16

xXStephXx ha scritto:Il prodotto di tutti i numeri aumentati di 1, diviso il prodotto di tutti i numeri.
Certo! In effetti $ \left( \dfrac {1} {a}+1 \right) \left( \dfrac {1} {b}+1 \right) = \dfrac {a+b+1}{ab}+1$, per cui un'invariante è $ \prod \left( \dfrac {1}{k}+1 \right)$, per i numeri $k$ scritti sulla lavagna.
L'invariante, calcolata all'inizio, è $\left(\dfrac{1}{1}+1\right)\left(\dfrac{1}{2}+1\right)\cdots\left(\dfrac{1}{2001}+1\right) =\dfrac{2}{1} \dfrac{3}{2} \cdots \dfrac{2002}{2001} = 2002$, per cui alla fine, quando rimane solo il numero $N$, si avrà che $ \dfrac{1}{N}+1=2002$, da cui $N= \dfrac {1} {2001}$
[math]

Rispondi