by \$w4g cesare e \$w4g simone

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

by \$w4g cesare e \$w4g simone

Messaggio da Talete »

Bello Figo vuole far arrivare in Italia i suoi amici dall’Africa. Per farlo, i suoi amici in Africa hanno una barca (\$w4g barca). Ognuno dei suoi n amici ha una quantità di \$w4g distinta e ben definita, intera e compresa tra 1 ed n. La barca (\$w4g barca) riesce a sopportare una quantità di \$w4g massima pari ad n, altrimenti viene affondata dalle autorità internazionali. Gli amici hanno tutti un passaporto falso che permette loro di imbarcarsi; per il viaggio dall’Africa all’Italia non è necessario mentre per il viaggio dall’Italia all’Africa possono utilizzare il passaporto soltanto una volta a testa. La barca non può compiere viaggi se non guidata da almeno uno degli amici di Bello Figo. Per quali n gli amici di Bello Figo possono tutti raggiungerlo e rimanere con lui in Italia?
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: by \$w4g cesare e \$w4g simone

Messaggio da Sirio »

EDIT: ho sbagliato a leggere il testo, quindi questa soluzione è clamorosamente sbagliata!
Testo nascosto:
Banalmente per $n=1$ si riesce. Anche per $n=0$, ammesso che questa cosa abbia un senso.
Chiamo d'ora in poi $A_k$ l'amico di Bello Figo con $\text{\$w4g}=k$.
Per $n=2$ non funziona. Infatti, se funzionasse, avrei che $A_2$, a un certo punto, dovrebbe imbarcarsi dall'Africa per l'Italia. Tuttavia, dovrebbe essere in barca da solo, poiché se con lui ci fosse anche $A_1$ allora il totale di $\text{\$w4g}$ sulla barca sarebbe $1+2=3>2=n$, assurdo per ipotesi. Dopo essersi quindi imbarcato da solo e aver raggiunto le nostre coste, se $A_1$ non è già in Italia allora dovrebbe tornare indietro col passaporto a riprenderlo, tornando però nella situazione iniziale. Ma $A_1$ non può essere già in Italia, poiché allora ci sarebbe dovuto giungere da solo (per gli stessi motivi di prima) e però avrebbe dovuto riportare indietro la barca per far arrivare anche $A_2$, quindi avrebbe dovuto lasciare il nostro Paese.
Dimostriamo ora per induzione che per $n\geq 3$ funziona.
Passo base: $n=3$. I viaggi sono, nell'ordine:
  • $A_1$ e $A_2$ vanno in Italia;
  • $A_2$ torna in Africa col passaporto;
  • $A_3$ va in Italia;
  • $A_1$ torna in Africa col passaporto;
  • $A_1$ e $A_2$ vanno in Italia.
Si verifica facilmente che in nessun caso il totale di $\text{\$w4g}$ sulla barca supera $n=3$. Inoltre, in tutti i viaggi di ritorno è stato usato uno e un solo passaporto. Quindi funziona.
Passo induttivo: per un certo $n-1$ funziona, con $n\geq 4$. Quindi, riesco a portare tutti quanti fino ad $A_{n-1}$ in modo che il totale di $\text{\$w4g}$ sulla barca non superi $n-1$, e quindi a fortiori senza che superi $n$. Quindi, porto tutti quanti in Italia tranne $A_n$ in questo modo. Ricordando $n\geq 4$, so che in particolare $A_1$ e $A_2$ stanno in Italia. Quindi, farò così:
  • $A_2$ torna in Africa col passaporto;
  • $A_n$ va in Italia;
  • $A_1$ torna in Africa col passaporto;
  • $A_1$ e $A_2$ vanno in Italia.
Si verifica facilmente, ricordando $n\geq 4$, che in nessun caso il totale di $\text{\$w4g}$ sulla barca supera $n$. Inoltre, in tutti i viaggi di ritorno è stato usato uno e un solo passaporto. Quindi funziona. Fine.
P.S. Per Talete:
Testo nascosto:
Non avrai mica collaborato con Dormouse?
Ultima modifica di Sirio il 24 mag 2018, 16:31, modificato 1 volta in totale.
$T=\sqrt{\dfrac l g 12\pi}$
Avatar utente
Fenu
Messaggi: 77
Iscritto il: 10 set 2017, 16:34

Re: by \$w4g cesare e \$w4g simone

Messaggio da Fenu »

Ma sbaglio o
Testo nascosto:
Nella tua induzione utilizzi il fatto che $A_1$ e $A_2$ non abbiano usato il passaporto, cosa che fanno durante ogni passaggio
Provo io:
Testo nascosto:
Proviamo a dimostrare che funziona per tutti gli $n$ dispari.
Innanzitutto notiamo che denominato $A$ il numero di viaggi dall'Africa all'Italia, possiamo supporre $A-1\leq n$ dato che durante ogni viaggio di ritorno si "brucia" un passaporto, e non ha senso che torni in Africa quello con $swag=n$.
Chiaramente con $A$ andate, seguono $A-1$ ritorni. Il peso minimo trasportato dagli $A-1$ ritorni vale chiaramente $1+2+3+...+A-1$ ovvero $\frac{A(A-1)}{2}$. Il peso delle andate vale invece $1+2+3+...+n+1+2+3+...+A-1$ in quanto non solo tutte le persone swag devono partire, ma anche gli swaggoni tornati in Africa devono RIpartire. Tale somma vale $\frac{n(n+1)}{2} + \frac{A(A-1)}{2}$.
Il numero di swag che viaggia dal continente africano fino a noi e' pero' minore di $n(A)$ in quanto il valore di swag massimo trasportato dalla barca durante le $A$ andate e' proprio $n$.
Ora si ha
$$\frac{n(n+1)}{2} + \frac{A(A-1)}{2} \leq n(A)$$
$$(A-n)(A-1-n)\leq 0$$
Ma quindi $A=n$ in quanto se $A<n$ quel prodotto risulterebbe positivo..
Quindi le andate sono esattamente $n$ e le barche devono trasportare esattamente $n$ quantità di swag durante i viaggi di andata in Italia.
Puo' $n$ pari funzionare?
No, dato che nella barca contenente la persona con $swag=\frac{n}{2}$ ci dovrebbe stare un altra persona con stesso swag (cosa impossibile in quanto gli amici di Bello Figo hanno swag differente).
Per n dispari?
Si. Al primo turno facciamo partire le persone con swag $1$, $n-1$ , facciamo tornare la persona $1$ e poi facciamo partire le persone $2$, $n-2$ etc. Insomma al viaggio $i$ facciamo partire le persone con swag $i$ ed $n-i$ (per i tra $1$ ed $\frac{n-1}{2}$) e tornare la persona $i$. Una volta finito facciamo partire lo swag $n$ ed infine ripetiamo la procedura al contrario: parte lo swaggone $n-i$ e torna insieme ad $i$.
Fine
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: by \$w4g cesare e \$w4g simone

Messaggio da Sirio »

Fenu ha scritto: 24 mag 2018, 16:18 Ma sbaglio o
Testo nascosto:
Nella tua induzione utilizzi il fatto che $A_1$ e $A_2$ non abbiano usato il passaporto, cosa che fanno durante ogni passaggio
Hai ragione, ho letto male il testo.
$T=\sqrt{\dfrac l g 12\pi}$
Rispondi