Caronte non guidava solo le barche?

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
fph
Site Admin
Messaggi: 3304
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph » 24 mag 2017, 18:45

No no facciamo ancora l'altro problema con due piatti soli... WLOG l'anima sta a sinistra. Ogni pesetto può stare a sinistra, a destra, oppure non stare proprio. Quanti pesi di anime diversi (positivi e/o negativi) puoi bilanciare?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
lucada23
Messaggi: 45
Iscritto il: 13 set 2014, 13:20

Re: Caronte non guidava solo le barche?

Messaggio da lucada23 » 25 mag 2017, 08:22

Se ogni numero lo si può scrivere in base 2, bastano $n$ pesetti dove $2^n>p$ giusto? Ma chi mi garantisce che è ottimale?

fph
Site Admin
Messaggi: 3304
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph » 25 mag 2017, 10:03

Nessuno, e infatti non lo è. :D
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

fph
Site Admin
Messaggi: 3304
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph » 25 mag 2017, 10:31

Uff, diciamo che metto una soluzione completa del caso a due piatti, visto che nessuno sembra afferrare gli hint. :)

Abbiamo una bilancia a due bracci uguali, $k$ pesetti di peso $p_1,p_2,\dots,p_k$, e un oggetto ("anima") da pesare.

Ogni possibile "pesata" si ottiene mettendo l'anima (WLOG) a sinistra, e per ognuno di questi pesetti scegliamo se metterlo a sinistra, a destra, oppure proprio da nessuna parte. Diciamo che $t_i=-1$ se il peso $i$ è a sinistra, $t_i=0$ se manca, e $t_i=1$ se è a destra. Allora la bilancia è in pari quando il peso dell'anima è $a = t_1 p_1 + t_2 p_2 + \dots + t_k p_k$.

Quindi esistono $3^k$ modi diversi di scegliere i $t_i$, e perciò al più $3^k$ pesi di anime diverse che si possono bilanciare. Nota però che uno di questi casi è $a=0$ (quando $t_i=0$ per ogni $i$), e che gli $a$ possono essere anche negativi: in particolare se c'è una scelta che pesa $a$ allora ce n'è anche una che pesa $-a$ (scambia tutti i segni). Quindi con $k$ pesetti possiamo bilanciare al più $\frac{3^k-1}{2}$ pesi positivi diversi.

Ora, sarebbe bello se ci fosse un modo di scegliere i $p_i$ in modo che questi fossero proprio gli interi $1,2,3,\dots,\frac{3^k-1}{2}$ --- di meglio chiaramente non possiamo fare, quindi questa sarebbe la soluzione migliore. Questo si ottiene se $p_i=3^{i-1}$. Di fatti "si vede" che si riesce a bilanciare qualunque peso $-\frac{3^k-1}{2} \leq a \leq \frac{3^k-1}{2}$ in questo modo: prima si sceglie $t_1$ in modo da rendere $a-t_1p_1$ multiplo di 3; poi si sceglie $p_2$ in modo da rendere $a-t_1p_1-t_2p_2$ multiplo di 9, e così via. Detto in altro modo più elegante: prendiamo il numero $N = a+1+3+3^2+\dots+3^{k-1}$ e scriviamolo in base $3$ come $N = s_1 + 3s_2 + 3^2s_3 + \dots + 3^{k-1} s_k$ (notare che si riesce sempre a scriverlo con $k$ cifre ternarie, perché $N$ sta sempre tra $0$ e $3^k-1$, come si vede usando la formula per la somma delle progressioni geometriche). Allora da questa scrittura otteniamo $a = (s_1-1) + (s_2-1)3 + (s_3-1)3^2 + \dots + (s_k-1)3^{k-1}$, che è un modo di ottenere $a$ come somma dei pesetti a coefficienti $t_i = s_i-1 \in \{-1,0,1\}$. (Qualche volta questa scrittura si sente chiamata "sistema ternario bilanciato".)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

fph
Site Admin
Messaggi: 3304
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph » 29 mag 2017, 23:49

Qualcuno ha voglia di fare la versione a quattro piatti ora?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

matpro98
Messaggi: 395
Iscritto il: 22 feb 2014, 18:42

Re: Caronte non guidava solo le barche?

Messaggio da matpro98 » 30 mag 2017, 07:28

Non basta sostituire al tuo messaggio i vari $3$ con dei $5$ e porre $t_i \in \{-2, -1, 0, 1, 2\}$?

fph
Site Admin
Messaggi: 3304
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph » 30 mag 2017, 08:26

Eh, in effetti più o meno sì. :) Resta da giustificare perché quella è l'equazione che fa stare la bilancia in equilibrio, e fare il conto del range dei numeri scrivibili con k cifre di "quinario bilanciato". Ma sono tutte verifiche facili.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti