Svuotare il secchio

[axpgn]

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

[jas1231]

Ciao Alex.
Ho una mezza idea, provo a scriverla per bene, vediamo se è giusta.

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

Cita

Segnala

[axpgn]

Confesso che non sono riuscito a starti dietro …

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

Cordialmente, Alex

[jas1231]

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.

[axpgn]

"jas123":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 ... IMHO

Cordialmente, Alex

[jas1231]

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.

[axpgn]

"jas123":… hanno usato un'induzione molto simile a quello che usai io in quest'esercizio.

Loro hanno usato l'induzione non tu
Hai ripreso quella dimostrazione ma "mischiandola" un poco …
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

[jas1231]

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

[axpgn]

"jas123":… 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
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":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

"jas123":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 …

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

[ot]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 [/ot]

Cordialmente, Alex

[jas1231]

Innanzitutto ti ringrazio per il complimenro.
Forse hai ragione, devo lavorare sull'esposizione e l'impostazione delle dimostrazioni.

[axpgn]

Ecco la soluzione a cui mi riferivo …

Siano $A, B, C$ i tre secchi e $0
Sia $b=qa+r$ dove $0<=r=1$ sono interi.
Scrivo $q$ in binario così $q=q_0+2q_1+...+2^nq_n$ dove ogni $q_i$ vale $0$ o $1$ e $q_n=1$.

La procedura consiste in $n+1$ "mosse", numerate da $0$ a $n$, eseguite come segue:
Alla mossa $i$-esima verso da $B$ in $A$ se $q_i=1$ altrimenti verso da $C$ in $A$ se $q_i=0$.
Compiute le $n+1$ mosse, avrò versato una quantità $qa$ da $B$ in $A$ ed in $B$ saranno rimasti $b-qa=r Ripetendo questa procedura un numero finito di volte finirò con l'ottenere un secchio vuoto.
Si può notare che da $C$ al massimo avrò versato $sum_(i=0)^(n-1) 2^ia<2^na<=qa<=b<=c$, quindi in $C$ c'è sempre acqua a sufficienza.

Conosco un'altra soluzione che va al contrario ma non l'ho capita bene …

Cordialmente, Alex