Svuotare il secchio

Messaggioda axpgn » 04/05/2020, 21:40

Avete a disposizione tre grandi secchi, ciascuno contenente un numero intero di litri d'acqua.
Ad ogni mossa, dovete raddoppiare il contenuto di uno dei secchi versandovi l'acqua contenuta in uno degli altri, il quale ovviamente ne dovrà contenere almeno altrettanta.
Ovvero potete versare acqua da un secchio che ne contiene $x$ litri in uno che ne contiene $y<=x$ litri, fino a che quest'ultimo ne contenga $2y$ (e il primo $x-y$).

Dimostrare che, qualunque sia il contenuto iniziale dei secchi, alla fine riuscirete a svuotarne uno completamente.

Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 15481 di 15856
Iscritto il: 20/11/2013, 22:03

Re: Svuotare il secchio

Messaggioda jas123 » 05/05/2020, 15:38

Ciao Alex.
Ho una mezza idea, provo a scriverla per bene, vediamo se è giusta.
Testo nascosto, fai click qui per vederlo
La terna $ (x_0,y_0,z_0) $ rappresenta il contenuto dei tre secchi e pongo (senza perdite di generalità) $ x_0ley_0lez_0 $
allora con una serie di passaggi posso arrivare alla nuova terna
$ (2^nx_0,y-x_0sum_(i =1 )^(m)2^(j_i),z_0-x_0sum_(i=1)^(h)2^(k_i)) $
con $ {j_1,\ldots ,j_m}uu {k_1,...,k_h}={1,2,...,n} $
e $ {j_1,\ldots ,j_m}nn {k_1,...,k_h}=O/ $
inoltre ogni numero intero può essere scritto come $ sum_(j) 2^j $ (sarebbe come dire che ogni numero può essere scritto in forma binaria) . In ogni caso posto la dimostrazione qui sotto.
Lo dimostro per induzione (chiamo il generico numero naturale da scrivere in binario $ n $ ):
-la tesi è vera per $ n le 2^0 $
-suppongo la tesi vera $ AA n |nle2^k $
-dimostro che la tesi è vera per $ 2^k < n le 2^(k+1) $ :
siccome $ n > 2^k $ e $ 2^(k+1)-2^k=2^k $ posso scrivere $ n= x +2^k $ con
$ x in ZZ | x le 2^k $ e per ipotesi induttiva $ x=sum_(j) 2^j $ con $ j in {1,...,k} $ quindi
$ n=sum_(j) 2^j $ con $ j in {1,...,k+1} $
CVD

Quindi scrivo
$ (2^nx_0,y-x_0sum_(i =1 )^(m)2^(j_i),z_0-x_0sum_(i=1)^(h)2^(k_i)) = (2^nx_0,y_0-sigmax_o,z_0-(2^(n+1)-1-sigma)x_0) $ con $ sigmain NN | sigma = sum_(i =1 )^(m)2^(j_i) $ .
Inoltre diciamo che $ x_1=y_0-sigmax_o $ ; $ y_1=min(2^nx_0,z_0-(2^(n+1)-1-sigma)x_0) $ ; $ z_1=max(2^nx_0,z_0-(2^(n+1)-1-sigma)x_0) $. Quindi $ x_1ley_1lez_1 $ .
Siccome posso scegliere $ sigma $ a piacimento posso fare in modo che $ x_1 $ sia il resto della divisione (con resto) di $ y_0/x_0 $ per cui $ x_1<x_0 $ per $ x_0 ne0 $ (ovviamente se $ x_0 =0 $ il problema è automaticamente risolto).
Questo processo può essere iterato fin quando $ x_n =0 $ dove $ n $ è il numero di iterazioni, ciò deve accadere per il principio del buon ordinamento di $ NN $ :
se $ x_(k+1)<x_k $ per $ x_k ne 0 $ allora si avrà una discesa infinita se $ x_kne0 AA kin NN $ il che è assurdo
Ultima modifica di jas123 il 06/05/2020, 06:53, modificato 1 volta in totale.
jas123
New Member
New Member
 
Messaggio: 20 di 55
Iscritto il: 26/06/2019, 17:37

Re: Svuotare il secchio

Messaggioda axpgn » 05/05/2020, 16:24

Confesso che non sono riuscito a starti dietro … :-D

Testo nascosto, fai click qui per vederlo
L'idea è buona (è uno dei modi che conosco) ma non sono in grado di dirti se sia stata sviluppata bene oppure no, vado in confusione dopo un po' … e non sono sicuro che non ci sia andato anche tu … :D
Per esempio, se $n$ è l'indice della dimostrazione per induzione allora devi dimostrare il passaggio induttivo per $n+1$ non per $k+1$, no?
Diciamo che ci si può arrivare in maniera un po' più soft … :-D



Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 15486 di 15856
Iscritto il: 20/11/2013, 22:03

Re: Svuotare il secchio

Messaggioda jas123 » 05/05/2020, 16:48

Grazie per la celere risposta, per l'induzione $ k $ è l'indice, $ n $ è solo un numero intero generico. L'obbiettivo è dimostrare che $ AA k in NN $ ( e quindi $ AA n in NN $) si ha che n può essere scritto in binari, non per nulla ho imposto come "punto di partenza" dell'induzione $ k=0 $. Diciamo che è una forma di induzione un po' strana, ma dovrebbe essere corretta.
Se vuoi ti posto anche un'altra dimostrazione, un po' più lunga, con l'induzione normale, che mi era venuta in mente prima di questa.
Comunque penso che la dimostrazione risulti un po' pesante perché ho cercato di essere il più formale possibile, ma il concetto di base è abbastanza semplice.
Non ci provo neanche a cercare il modo più "soft" perché mi conosco, ormai mi sono incaponito con questo procedimento.
jas123
New Member
New Member
 
Messaggio: 21 di 55
Iscritto il: 26/06/2019, 17:37

Re: Svuotare il secchio

Messaggioda axpgn » 30/05/2020, 22:03

jas123 ha scritto:Diciamo che è una forma di induzione un po' strana, ma dovrebbe essere corretta.

Mah, a me non pare proprio "induzione" .
Per esempio, dici che l'indice è $k$ ma ipotizzi che il passo induttivo valga per ogni $n$ :|
A mio parere, invece di pensare ad una dimostrazione più "lunga", prova ad "accorciare" questa, soprattutto a mettere ordine (esplicita la tesi, definisci l'indice, evidenzia separatamente il passo base e il passo induttivo, ecc.)
Questo ti sarebbe molto utile al di là del caso in questione :wink: ... IMHO

Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 15655 di 15856
Iscritto il: 20/11/2013, 22:03

Re: Svuotare il secchio

Messaggioda jas123 » 31/05/2020, 21:44

Ho visto che nelle soluzioni dell'ultima prova di ammissione alla SNS hanno usato un'induzione molto simile a quello che usai io in quest'esercizio. La posto, magari qui è più chiara.

Testo nascosto, fai click qui per vederlo
Immagine
jas123
New Member
New Member
 
Messaggio: 28 di 55
Iscritto il: 26/06/2019, 17:37

Re: Svuotare il secchio

Messaggioda axpgn » 31/05/2020, 23:28

Testo nascosto, fai click qui per vederlo
jas123 ha scritto:… hanno usato un'induzione molto simile a quello che usai io in quest'esercizio.

Loro hanno usato l'induzione non tu :wink:
Hai ripreso quella dimostrazione ma "mischiandola" un poco … :D
Peraltro quella dimostra "solo" che ogni numero intero può essere riscritto in "binario" in modo univoco che però non è sufficiente per dimostrare quanto richiesto.


Insomma, io rimango dell'idea che la tua dimostrazione sia poco chiara … IMHO …

Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 15659 di 15856
Iscritto il: 20/11/2013, 22:03

Re: Svuotare il secchio

Messaggioda jas123 » 01/06/2020, 00:20

Testo nascosto, fai click qui per vederlo
Vorrei precisare che non ho ripreso quella dimostrazione perché non ne conoscevo l'esistenza fino a qualche giorno fa. Comunque può darsi che la mia dimostrazione sia poco chiara ma mi sembra che l'induzione ci sia.
axpgn ha scritto:Peraltro quella dimostra "solo" che ogni numero intero può essere riscritto in "binario" in modo univoco che però non è sufficiente per dimostrare quanto richiesto.

L'obbiettivo di quella parte della mia dimostrazione era dimostrare che ogni numero intero può essere scritto in binario (nient'altro l'unicità è un corollario di quel tipo di dimostrazione).
Il resto della mia dimostrazione, poi è tutt'altra cosa: a partire dal fatto che ogni numero può essere scritto in binario imposto un processo iterativo che ripetuto un numero finito di volte mi porterà sicuramente a svuotare uno dei tre secchi.

in ogni caso, potresti postare la soluzione "soft"? Sono molto curioso.
jas123
New Member
New Member
 
Messaggio: 30 di 55
Iscritto il: 26/06/2019, 17:37

Re: Svuotare il secchio

Messaggioda axpgn » 01/06/2020, 10:43

Testo nascosto, fai click qui per vederlo
jas123 ha scritto:… Comunque può darsi che la mia dimostrazione sia poco chiara ma mi sembra che l'induzione ci sia. …

No, ti sbagli e secondo me è importante che te ne renda conto perché mi sembri decisamente dotato :D
E proprio confrontando le due dimostrazioni lo si nota bene: in quella della SNS è chiaramente indicato $k$ come indice dell'induzione mentre nella tua (rivedila) affermi che l'indice è $n$, provi il caso base su $n$ però quello induttivo provi a dimostrarlo su $k$.

jas123 ha scritto:L'obbiettivo di quella parte della mia dimostrazione era dimostrare che ogni numero intero può essere scritto in binario

Certamente, difatti non è un passo necessario, lo si dava per scontato :D

jas123 ha scritto:Il resto della mia dimostrazione, poi è tutt'altra cosa: a partire dal fatto che ogni numero può essere scritto in binario imposto un processo iterativo che ripetuto un numero finito di volte mi porterà sicuramente a svuotare uno dei tre secchi.

Come ho detto, l'idea è quella giusta solo che, a parer mio, è un po' contorta e non molto chiara.
Secondo il mio punto di vista, ovviamente … :D

La "mia" soluzione sostanzialmente è analoga però mi pare più "lineare" … poi la posterò, appena ho un po' più di tempo … :-D


Testo nascosto, perché contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.
A mio parere, visti anche gli altri tuoi interventi, non sei chiarissimo e questo è un punto su cui devi migliorare perché le idee sono buone :D


Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 15662 di 15856
Iscritto il: 20/11/2013, 22:03

Re: Svuotare il secchio

Messaggioda jas123 » 01/06/2020, 16:11

Innanzitutto ti ringrazio per il complimenro.
Forse hai ragione, devo lavorare sull'esposizione e l'impostazione delle dimostrazioni.
jas123
New Member
New Member
 
Messaggio: 31 di 55
Iscritto il: 26/06/2019, 17:37

Prossimo

Torna a Scervelliamoci un po'

Chi c’è in linea

Visitano il forum: Nessuno e 7 ospiti