pesate
pesate
Abbiamo una certa quantità di biglie, tutte dello stesso peso tranne una, che non sappiamo se è più leggera o più pesante delle altre. Abbiamo una bilancia a piatti, che ci dice solo quale dei due piatti è più pesante. Abbiamo a disposizione n pesate. Qual è in funzione di n il massimo intero k tale che, a partire da k biglie, possiamo sicuramente scoprire in n pesate qual è quella , tra le k, di peso diverso?
E se invece sappiamo che la biglia diversa è più leggera delle altre?
Credo che tutti abbiate sentito almeno una volta questo problema in una delle sue tante versioni. Questa generalizzazione mi è sembrata interessante, anche se ho dei dubbi su alcuni aspetti... per cui attendo le vostre risposte
E se invece sappiamo che la biglia diversa è più leggera delle altre?
Credo che tutti abbiate sentito almeno una volta questo problema in una delle sue tante versioni. Questa generalizzazione mi è sembrata interessante, anche se ho dei dubbi su alcuni aspetti... per cui attendo le vostre risposte
veramente il quesito chiedeva di trovare k in funzione di n...
come hai trovato quella formula, shuzz? comunque come ha detto sisifo c'è anche il caso in cui non sai se la biglia diversa è più pesante o più leggera, ed è il caso più interessante!
cmq la mia idea di partenza è quella di identificare univocamente ogni biglia con la sua posizione ad ogni pesata (piatto destro, piatto sinistro, nessun piatto)
come hai trovato quella formula, shuzz? comunque come ha detto sisifo c'è anche il caso in cui non sai se la biglia diversa è più pesante o più leggera, ed è il caso più interessante!
cmq la mia idea di partenza è quella di identificare univocamente ogni biglia con la sua posizione ad ogni pesata (piatto destro, piatto sinistro, nessun piatto)
Nel caso non si conosca se la biglia di peso diverso è più pesante o leggera, per trovarla tra k biglie bastano la parte intera di n=log_2 (k) + 1 pesate.
P.S.
Per sapere se la biglia è più pesante o più leggera bastano 2 pesate.
Avendo per esempio 127 biglie, ne tolgo una e divido le rimanenti in due gruppi che posiziono sui due bracci della bilancia:
1. Se questi restano immobili prendo la pallina esclusa e la confronto con un'alta qualsiasi.
2. Se un braccio è più pesante dell'alto prendo uno dei due gruppi a caso, lo divido in due come sopra e peso:
a. Se i bracci restano immobili e ho preso il gruppo più leggero
la biglia è più pesante
b. Se i bracci non restano immobili e ho preso il gruppo più leggero la biglia è più leggera delle altre.
c. Se i bracci restano fermi e ho preso il gruppo più pesante la biglia è più leggera delle altre.
d. Se i bracci non restano fermi e ho preso il gruppo più pesante la biglia è più pesante.
P.S.
Per sapere se la biglia è più pesante o più leggera bastano 2 pesate.
Avendo per esempio 127 biglie, ne tolgo una e divido le rimanenti in due gruppi che posiziono sui due bracci della bilancia:
1. Se questi restano immobili prendo la pallina esclusa e la confronto con un'alta qualsiasi.
2. Se un braccio è più pesante dell'alto prendo uno dei due gruppi a caso, lo divido in due come sopra e peso:
a. Se i bracci restano immobili e ho preso il gruppo più leggero
la biglia è più pesante
b. Se i bracci non restano immobili e ho preso il gruppo più leggero la biglia è più leggera delle altre.
c. Se i bracci restano fermi e ho preso il gruppo più pesante la biglia è più leggera delle altre.
d. Se i bracci non restano fermi e ho preso il gruppo più pesante la biglia è più pesante.
ok per sapere solo se la biglia è più leggera o più pesante bastano 2 pesate... ma per identificare con certezza quale biglia è, il mio risultato è diverso... mi viene: il minimo n tale che (3^n -1)/2 >= k... se non era chiaro dal testo del quesito, non è obbligatorio che per ogni pesata ogni pallina stia per forza in uno dei due piatti, può anche non starci in nessuno
rimane il fatto che si chiedeva k in funzione di n e non n in funzione di k, ma fa lo stesso non cambia poi molto
rimane il fatto che si chiedeva k in funzione di n e non n in funzione di k, ma fa lo stesso non cambia poi molto
Datemi pure del cretino se lo ritenete, sbaglio spesso.
Ehm... una volta che tu prendi in considerazione solo un piatto da 63 (126/2) e lo "dividi" in due, te ne rimane una fuori... che non puoi ignorare seguendo il punto a. o il punto c....ti rimane da fare una pesata con la biglia rimasta fuori e una qualsiasi di quelle appena pesate, da controllare che effettivamente quella rimasta fuori abbia peso uguale alle altre.shuzz ha scritto: 2. Se un braccio è più pesante dell'alto prendo uno dei due gruppi a caso, lo divido in due come sopra e peso:
a. Se i bracci restano immobili e ho preso il gruppo più leggero
la biglia è più pesante
b. Se i bracci non restano immobili e ho preso il gruppo più leggero la biglia è più leggera delle altre.
c. Se i bracci restano fermi e ho preso il gruppo più pesante la biglia è più leggera delle altre.
d. Se i bracci non restano fermi e ho preso il gruppo più pesante la biglia è più pesante.
Questo problema è già stato posto da alefig quasi 3 anni fa, e la soluzione è quella trovata da gordio.
ECCO IL LINK.
ECCO IL LINK.
ok ero abbastanza certo di aver fatto giusto
per pirignao: hai ragione su quello non ci avevo pensato, a questo punto non c'è un minimo (valido per tutti i k) per quel problema (sapere solo se la biglia diversa è più leggera o più pesante)
andando a rivedere il quesito di alefig, lui scriveva:
per pirignao: hai ragione su quello non ci avevo pensato, a questo punto non c'è un minimo (valido per tutti i k) per quel problema (sapere solo se la biglia diversa è più leggera o più pesante)
andando a rivedere il quesito di alefig, lui scriveva:
è proprio questo il dubbio di cui parlavo all'inizio, che non son riuscito a risolvere: (3^n -1) / 2 è il max anche se togliamo il vincolo della strategia decisa per forza all'inizio? O, al contrario, concedendo la possibilità di scegliere la pesata successiva a seconda del risultato ottenuto nelle precedenti, questo max aumenta? se dovessi scommettere direi che il max resta lo stesso (ho provato per numeri bassi), ma in quanto a dimostrarlo non saprei da dove partire ...Si hanno a disposizione n pesate e la strategia da seguire nel fare le pesate deve essere decisa prima di iniziare e non si può cambiare a seconda del risultato ottenuto durante le varie pesate.