pesate

Giochini matematici elementari ma non olimpici.
Rispondi
gordio
Messaggi: 52
Iscritto il: 01 gen 1970, 01:00

pesate

Messaggio da gordio » 13 lug 2005, 22:31

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 :o

shuzz
Messaggi: 46
Iscritto il: 17 giu 2005, 14:06

Messaggio da shuzz » 16 lug 2005, 07:31

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

Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo » 17 lug 2005, 13:51

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

shuzz
Messaggi: 46
Iscritto il: 17 giu 2005, 14:06

Messaggio da shuzz » 17 lug 2005, 16:34

Com'è quest'esempio?

Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo » 18 lug 2005, 17:15

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

gordio
Messaggi: 52
Iscritto il: 01 gen 1970, 01:00

Messaggio da gordio » 18 lug 2005, 18:38

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! :wink:

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
Messaggi: 46
Iscritto il: 17 giu 2005, 14:06

Messaggio da shuzz » 20 lug 2005, 09:53

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
Messaggi: 52
Iscritto il: 01 gen 1970, 01:00

Messaggio da gordio » 21 lug 2005, 23:06

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 :wink:

pirignao
Messaggi: 83
Iscritto il: 01 gen 1970, 01:00
Località: Torino

Messaggio da pirignao » 22 lug 2005, 11:10

Datemi pure del cretino se lo ritenete, sbaglio spesso.
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.
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
Messaggi: 46
Iscritto il: 17 giu 2005, 14:06

Messaggio da shuzz » 23 lug 2005, 10:13

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

Messaggio da MindFlyer » 25 lug 2005, 03:04

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

gordio
Messaggi: 52
Iscritto il: 01 gen 1970, 01:00

Messaggio da gordio » 31 lug 2005, 16:57

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

Rispondi