La Coffee Room

[Wido]

Problemino da pausa caffe':
Abbiamo 12 palline tutte identiche tranne una che ha un peso differente dalle altre (in piu' o in meno).
Quale e' il numero minimo di pesate necessario ad individuarla con certezza e a sapere anche se pesa di piu' o di meno? Abbiamo a disposizione una classica bilancia a due piatti e possiamo mettere quante palline vogliamo sui piatti.
Perche'? (Qui sta il bello).

[Corto]

Wido ha scritto ven, 07 ottobre 2005 alle 10:16
Problemino da pausa caffe':
Abbiamo 12 palline tutte identiche tranne una che ha un peso differente dalle altre (in piu' o in meno).
Quale e' il numero minimo di pesate necessario ad individuarla con certezza e a sapere anche se pesa di piu' o di meno? Abbiamo a disposizione una classica bilancia a due piatti e possiamo mettere quante palline vogliamo sui piatti.
Perche'? (Qui sta il bello).

log in base 2 di 12 approssimato in eccesso.
Cioè 4 pesate


Dove 2 dipende da quante palline riesce a confrontare la bilancia

[Wido]

no.
e anche se fosse, perche?

[skywolf]

nn avendo voglia di pensarci tanto... 3 pesate

con la 1a ne peso 6 e 6 (6 su un piatto e 6 sull'altro) e individuo in quale gruppo dei due sta
idem con la 2a, 3 e 3
con la 3a pesata metto solo 2 palline: se hanno lo stesso peso la rimanente e' quella incriminata, altrimenti... beh lo vedo da come pende la bilancia no?

ah gia': io SO se pesa di piu' o di meno delle altre?
senno' non funziona...


cmq nn capisco il "perche'". Perche' cosa? perche' ci fai sta' domanda?

[Wido]

c'e' un baco in quello che hai scritto... DEVI determinare se pesa piu' o meno

[Corto]

Il problema è che non sappiamo se la pallina pesa di più o di meno.
La mia soluzione prevede che si sappia se la pallina è più leggera o più pesante.Inoltre la formula logaritmica è per un algoritmo senza "eccezioni", come quella di Sky sull'ultimo passaggio. Cmq

[skywolf]

Wido ha scritto ven, 07 ottobre 2005 alle 10:56
c'e' un baco in quello che hai scritto... DEVI determinare se pesa piu' o meno

quindi non lo so a priori, come sospettavo!
Beh se lo sapevo funzionava pero' pensaci bene corto!

adesso io penso al caso generale... (cazz dovrei lavorare xo'!)

[Wido]

pensavo di essere stato chiaro.

[Corto]

e io dovrei studiare!




...maledetto Wido...

[Buffalmacco]

a me non me ne frega niente... torno a giocare ad ogame

[Corto]

Una soluzione è questa:

1)fai 3 gruppi da 4 e determini quello col peso diverso --- 2 pesate
2)quindi sai la differenza di peso tra gruppi "normale" e "diverso" e sai se la pallina(chiamamola la talpa ) pesa di + o di -
3) procedi con il classico algoritmo sul gruppo della talpa (di 4 elementi) -----altre 2 pesate



Ma ci vogliono 4 pesate uguale...

Wido? Dove sbaglio?

[Wido]

il problema e' molto fisico e consiste nel massimizzare la quantita' di informazione ottenuta ad ogni passo.
Come domanda iniziale uno si puo' chiedere quale e' il limite inferiore di pesate senza le quali non potremmo assolutamente trovare un algoritmo di soluzione. Poi si cerca eventualmente l'algoritmo (se esiste).

[Corto]

Ok ho capito



Quindi il mio algoritmo sarà pure corretto ma tu sei interessato a evidenziare la dimostrazione del valore limite delle pesate, cioè del rapporto informazione/sforzo.

Appena ho un paio di giorni liberi ci penso.

[Wido]

Il tuo algoritmo per risolvere dara' anche la soluzione ma ci impiega troppe pesate. Si puo' fare con meno. Come? E con quante? La domanda e' sempre quella iniziale. A scanso di equivoci: la soluzione esiste.

[vaitrafra]

3 gruppi da 2

PESATA 1: peso 2 gruppi

CASO 1: La bilancia rimane pari;
PESATA 2: tolgo le bocce da un piatto e ci metto il terzo gruppo.
a seconda del movimento della bilancia so se la talpa pesa + o -.
PESATA 3: tolgo una palla da ogni piatto e scopro automaticamente la talpa.

3Pesate

CASO 2:
La bilancia pende;
PESATA 2: Tolgo le biglie dal piatto più leggero e ci metto il 3° gruppo.
CASO 2.1: La bilancia rimane pari, la talpa è più leggera.

PESATA 3: peso le biglie tolte in precedenza e so qual'è la talpa.

3 PESATE

CASO 2.2: La Bilancia pende verso il 3° gruppo. La talpa è + pesante

PESATA 3: peso le biglie del 3° gruppo e scopro la talpa.

3 PESATE

ecco, io farei così, con 3 pesate.

se c'è una magia fisica per cui ne bastano 2 la voglio sapere.



EDIT: ho riletto, non ci si capisce molto, ma funziona(credo)

[Wido]

le palline sono 12.

[Corto]

Wido ha scritto ven, 07 ottobre 2005 alle 16:50
le palline sono 12.

Ma cmq la cosa che interessa non è l'algoritmo.

[Wido]

La domanda e' la solita: come fareste? Quindi il COME ha la sua rilevanza.
Una volta che vi siete divertiti a trovare la soluzione vi dico perche' e' un problemino interessante (almeno secondo me).

[vaitrafra]

Wido ha scritto ven, 07 ottobre 2005 alle 16:50
le palline sono 12.

ARGH!

[rigel]

vi posto l'indirizzo di un giochetto che all'inizio lascia di stucco ma in breve tempo si scopre il trucco

simpatico

http://www.perogatt.com/lettore_mente.ht m

[Wido]

All'inizio, senza pensarci troppo, lascia veramente spiazzati ma poi in effetti il trucchetto si trova facilmente.

[Wido]

Questo penso che lo conosciate:

http://y.20q.net/

non e' altro che una variante articolata del gioco che vi ho proposto.

[Helyanwe]

Wido ha scritto ven, 07 ottobre 2005 alle 18:09
Questo penso che lo conosciate:

http://y.20q.net/

non e' altro che una variante articolata del gioco che vi ho proposto.

questo è bellissimo, mi ha anche indovinato acceleratore di particelle

[Corto]

Non mi ha indovinato la spada laser di Star Wars

[vaitrafra]

Corto ha scritto ven, 07 ottobre 2005 alle 19:17
Non mi ha indovinato la spada laser di Star Wars

se e' per questo per indovinare Quarzo ci ha messo 3 tentativi...e continua a chiedermi se si lava(cavolo, io non ho mai lavato il quarzo, nessuno lo fa ma si può! che devo risp io se non irrilevante?)