pesate

[gordio]

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

[shuzz]

Per quello che ho fatto il risultato dovrebbe essere la parte intera di n=log_2 (K)

Per esempio se ho 127 biglie bastano 6 pesate, se ne ho 128 devo usare la bilancia 7 volte

[Sisifo]

Ne ero convinto anch'io finch'è un mio compagno non mi ha mostrato un controesempio complicatissimo...

[shuzz]

Com'è quest'esempio?

[Sisifo]

Non me lo ricordo... riguardava quando non sai se pesa di più o di meno e lo devi scoprire...

[gordio]

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)

[shuzz]

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.

[gordio]

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

[pirignao]

Datemi pure del cretino se lo ritenete, sbaglio spesso.

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.

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]

Perchè non la posso ignorare?
La biglia esclusa è da tenersi in considerazione solo se sui due bracci che hanno ognuno 31 biglie (63-1)/2 restano immobili.

[MindFlyer]

Questo problema è già stato posto da alefig quasi 3 anni fa, e la soluzione è quella trovata da gordio.
ECCO IL LINK.

[gordio]

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:

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.

è 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 ...