Caronte non guidava solo le barche?

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

Re: Caronte non guidava solo le barche?

Messaggio da AlexThirty »

Sei proprio fortunato perché questo l'ho risolto in gara.
Comunque per iniziare ti do un piccolo hint che è più un aiuto a capire il testo.
I bracci sono quattro e l'anima sta su uno dei due vicini al fulcro. Prova a fare i casi piccoli ricordandomi cosa dice la fisica sul fatto che i piatti centrali stanno a metà rispetto a quelli esterni. Dopo circa una ventina di casi dovresti capire come funziona
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: Caronte non guidava solo le barche?

Messaggio da matpro98 »

Intanto, già qui c'è un primo errore: puoi mettere uno o più pesetti anche sul piatto con l'anima
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: Caronte non guidava solo le barche?

Messaggio da matpro98 »

Sono 4 piatti, devi mettere anche $-w$
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph »

Ti dà una buona idea di cosa sta succedendo se ti fai prima (o ti "porti da casa", come dice il buon Max) la versione senza i buchi a metà dei bracci, quindi ti consiglio di partire da quella.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: Caronte non guidava solo le barche?

Messaggio da matpro98 »

E se ti dicessi che per la bilancia a 2 bracci la soluzione ottimale per i pesetti sono le potenze di 3?
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph »

Quanti pesi diversi (positivi e/o negativi) puoi fare con due pesetti?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Vinci
Messaggi: 159
Iscritto il: 30 gen 2015, 18:38

Re: Caronte non guidava solo le barche?

Messaggio da Vinci »

Il numero di modi di disporre i due pesetti sui quattro piatti, quindi $16$, ma alcuni di questi casi non permettono di bilanciare, e andrebbe considerato il fatto che deve esserci almeno un peso sul lato della bilancia che non contiene l'anima, ed andrebbe anche considerato se i due pesetti pesano uno la metà dell'altro, e se quello che pesa di più pesa più del doppio dell'altro o no, sono un bel po' di casi.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph »

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]
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph »

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: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph »

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: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph »

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: 479
Iscritto il: 22 feb 2014, 18:42

Re: Caronte non guidava solo le barche?

Messaggio da matpro98 »

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: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Caronte non guidava solo le barche?

Messaggio da fph »

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