Indovinello delicato
12 palline, di cui una sola diversa in peso ma non in forma dalle altre 11, ma non sapete se è + leggera o + pesante.
Individuate qual'è, e se è + legg. o + pesante, avendo a disposizione 3 pesate, con una classica bilancia a 2 piatti che non fornisce risultati numerici
Individuate qual'è, e se è + legg. o + pesante, avendo a disposizione 3 pesate, con una classica bilancia a 2 piatti che non fornisce risultati numerici
Risposte
Disponiamo 6 palline in un piatto e 6 dall'altro.
Per la 2°pesata prendiamo le 6 palline ke si trovavano nel piatto + pesante e le disponiamo a 3 a 3 sui 2 piatti.
Una volta terminata la 2° pesata ci rimangono 3 palline(tra cui vi è sicuramente quella + pesante) e una sola pesata.
Da queste 3 una la leviamo e pesiamo le altre 2.
Se ragggiungono lo stesso livello allora quella eliminata è la + pesante.
Per la 2°pesata prendiamo le 6 palline ke si trovavano nel piatto + pesante e le disponiamo a 3 a 3 sui 2 piatti.
Una volta terminata la 2° pesata ci rimangono 3 palline(tra cui vi è sicuramente quella + pesante) e una sola pesata.
Da queste 3 una la leviamo e pesiamo le altre 2.
Se ragggiungono lo stesso livello allora quella eliminata è la + pesante.
quote:
Originally posted by JvloIvk
Disponiamo 6 palline in un piatto e 6 dall'altro.
Per la 2°pesata prendiamo le 6 palline ke si trovavano nel piatto + pesante...
Ma la pallina "diversa" potrebbe essere più leggera e non più pesante delle altre...
ciao
ho visto la soluzione proposta dal sito, e davvero non mi entusiasma, molto più carina quella di JvloIvk, però ora un dubbio mi viene spontaneo : 3 pesate sono sufficienti per individuare una pallina "farlocca" su 12, ora procedendo per dimezzamento come ha proposto JvloIvk, si deduce che se abbiamo n palline, bastano Inf{Log[2, n]} (parte intera inferione del logaritmo in base 2 di n), pesate per individuare la allina. ma se abbiamo k palline "farlocche" ?
Un po' di teoria dell'informazione: una bilancia a due piatti in questo caso riesce a discriminare un oggetto tra 3, ovvero mi può fornire una informazione ternaria. Se ripeto la pesata n volte riuscirò a discriminare 3^n oggetti. Quindi è se abbiamo k palline, bastano Sup{Log[3, k]} (parte intera superiore del logaritmo in base 3 di k), pesate per individuare la pallina.
Per capirci fino a k=9 bastano 2 pesate, per k=[10->27] ne serviranno 3, per k=[28->81] ne serviranno 4 e così via.
Per capirci fino a k=9 bastano 2 pesate, per k=[10->27] ne serviranno 3, per k=[28->81] ne serviranno 4 e così via.
scusa, Pachito
non vedo come ne discrimini 3 con una sola pesata
se io ho solo tre palline A,B,C (di cui una non si sa se + leggera o + pesante), con una sola pesata di A e B che informazione ottengo ?
se sono pari, deduco che C è diversa, e mi ci vuole una seconda pesata (confrontando C con A o B) per qualificarne la diversità
altrimenti, individuo che A (ad. es.) è la + pesante tra le due deducendo anche che C è "normale", e mi ci vuole una seconda pesata (confrontando A con C) per stabilire se A è veramente la "bastarda" pesante; altrimenti deduco che B è la "bastarda" leggera.
mi pare serva una pesata in più, rispetto a quel che tu dici.
dove mi sono impastato?
tony
quote:
Un po' di teoria dell'informazione: una bilancia a due piatti in questo caso riesce a discriminare un oggetto tra 3 ... [Pachito]
non vedo come ne discrimini 3 con una sola pesata
se io ho solo tre palline A,B,C (di cui una non si sa se + leggera o + pesante), con una sola pesata di A e B che informazione ottengo ?
se sono pari, deduco che C è diversa, e mi ci vuole una seconda pesata (confrontando C con A o B) per qualificarne la diversità
altrimenti, individuo che A (ad. es.) è la + pesante tra le due deducendo anche che C è "normale", e mi ci vuole una seconda pesata (confrontando A con C) per stabilire se A è veramente la "bastarda" pesante; altrimenti deduco che B è la "bastarda" leggera.
mi pare serva una pesata in più, rispetto a quel che tu dici.
dove mi sono impastato?
tony
ma, Rael,
l'obiezione di alice (11/05/2005 : 11:55:36)
"Ma la pallina "diversa" potrebbe essere più leggera e non più pesante delle altre..."
non conta ?
tony
quote:
ho visto la soluzione proposta dal sito, e davvero non mi entusiasma, molto più carina quella di JvloIvk, ... [Rael]
l'obiezione di alice (11/05/2005 : 11:55:36)
"Ma la pallina "diversa" potrebbe essere più leggera e non più pesante delle altre..."
non conta ?
tony
tony effettivamente hai ragione, se no so di partenza su che principio devo fare la discriminazione mi occorrono delle pesate in più !
quote:
tony effettivamente hai ragione, ... [Rael]
beh, aveva ragione alice, criticando la soluzione di JvloIvk
tony
quote:
Originally posted by tony
scusa, Pachito
non vedo come ne discrimini 3 con una sola pesata
Hai ragione avevo letto distrattamente il problema:
... 12 palline, di cui una sola diversa in peso ...
Non specifica se la pallina è più pesante o più leggera.
Questa nuova informazione ha una indeterminazione di tipo binario: pesante o leggero. E dunque sufficiente fare una pesata in più per ottenere questa informazione (una volta trovata una coppia diversa è sufficiente una ulteriore pesata). Citandomi...
Bastano Sup{Log[3, k]})+1 pesate per individuare la pallina.
quote:
...Bastano Sup{Log[3, k]})+1 pesate per individuare la pallina. [Pachito]
con i dati del problema avremmo
sup{log[3, 12]}+1 = sup{2,26)+1 = 3+1 = 4
ma il testo dice 3 ...
interessante dilemma:
la condizione che hai posto è più restrittiva del necessario, oppure la soluzione indicata da davi24
(confesso che non ho avuto la forza di leggerla tutta)
è errata?
tony
La soluzione indicata da davi24 è corretta. La condizione "Bastano Sup{Log[3, k]})+1 pesate per individuare la pallina" è una condizione sufficiente, ma non necessaria. Nel caso specifico del quesito si potrebbe tentare di fare un conto più preciso per dimostrare che la quantità di informazioni necessaria a risolvere il problema sia data da 3 pesate. Si può provare...
a questo punto, però, Pachito, dalla tua
potrei concludere che - poichè per discriminare un oggetto di questo tipo tra tre ci vuole una pesata + una supplementare (cioè 2 pesate) - per discriminarne 1 su nove ci vorranno 4 pesate (2 + 2) [e non 3 (1+1+ quella supplementare) come lasci intendere tu], etc.
non c'è una parvenza di logica in quello che dico io, digiuno o dimentico della teoria?
tony
quote:
Un po' di teoria dell'informazione: una bilancia a due piatti in questo caso riesce a discriminare un oggetto tra 3, ovvero mi può fornire una informazione ternaria. Se ripeto la pesata n volte riuscirò a discriminare 3^n oggetti. [Pachito]
potrei concludere che - poichè per discriminare un oggetto di questo tipo tra tre ci vuole una pesata + una supplementare (cioè 2 pesate) - per discriminarne 1 su nove ci vorranno 4 pesate (2 + 2) [e non 3 (1+1+ quella supplementare) come lasci intendere tu], etc.
non c'è una parvenza di logica in quello che dico io, digiuno o dimentico della teoria?
tony
Ragazzi sarò ripetitivo da morire ^_^ ! ma mi piace complicare le cose, supponiamo che sin da principio, le palline farlocche siano più pesanti delle normali. quante pesate occorrono con una bilancia a due piatti, per discriminare k palline farlocche su n palline totali ?
Per Rael: se ti piacciono i giochetti semplici perché non consideri 1 pallina sola, così è facile trovare quella cercata (supposto che ci sia)?
Per chi cerca di capirci qualcosa (anch’io sono “stupito” dal fatto che ne bastino 3):
Chiamo “p” il numero di palline e “n” quello delle pesate necessarie.
Condivido quello che è stato detto finora.
Infatti si capisce che sapendo che la pallina diversa è (per esempio) più pesante, si ha che n = sup{log[3, p]}, se invece non lo so ho bisogno di “informazione aggiuntiva”, per cui n non è sicuramente minore, ed anzi “sembrerebbe” strettamente maggiore.
Però se p non è una potenza naturale di 3 posso incrementarlo fino alla successiva potenza (che chiamo “n3”), senza che n aumenti, per cui ho ancora margine per le “informazioni aggiuntive” (ad esempio: posso ripesare delle palline che ho già pesato, fino a pesare l’equivalente di n3 palline).
Quindi si deduce che o n={log[3, p]} oppure n={log[3, p]}+1.
Valutare quale dei due numeri non è facile, ma sicuramente esiste un numero p1>=p e tale che con p1 palline n={log[3, p]}+1, e con (p1+1) palline n={log[3, p]}+2.
A questo punto non dimostro, ma considero che il caso del testo sia quello che “funziona meglio”, per cui se ho 3 palline mi ci vuole 1 pesata conoscendo che la diversa è più pesante, 2 pesate se non lo conosco; però con due pesate riesco anche a trovare qual è quella diversa senza conoscere se la diversa è più pesante o più leggera. In pratica riesco a discriminare con 4 palline anziché con 3.
Nulla cambia se anziché 3 palline ne ho 3 gruppi (come dire: gruppi di k palline l’uno).
In conclusione: se il numero di palline è p il numero n di pesate necessario è
n={log[3, p/4]}+2.
Per chi cerca di capirci qualcosa (anch’io sono “stupito” dal fatto che ne bastino 3):
Chiamo “p” il numero di palline e “n” quello delle pesate necessarie.
Condivido quello che è stato detto finora.
Infatti si capisce che sapendo che la pallina diversa è (per esempio) più pesante, si ha che n = sup{log[3, p]}, se invece non lo so ho bisogno di “informazione aggiuntiva”, per cui n non è sicuramente minore, ed anzi “sembrerebbe” strettamente maggiore.
Però se p non è una potenza naturale di 3 posso incrementarlo fino alla successiva potenza (che chiamo “n3”), senza che n aumenti, per cui ho ancora margine per le “informazioni aggiuntive” (ad esempio: posso ripesare delle palline che ho già pesato, fino a pesare l’equivalente di n3 palline).
Quindi si deduce che o n={log[3, p]} oppure n={log[3, p]}+1.
Valutare quale dei due numeri non è facile, ma sicuramente esiste un numero p1>=p e tale che con p1 palline n={log[3, p]}+1, e con (p1+1) palline n={log[3, p]}+2.
A questo punto non dimostro, ma considero che il caso del testo sia quello che “funziona meglio”, per cui se ho 3 palline mi ci vuole 1 pesata conoscendo che la diversa è più pesante, 2 pesate se non lo conosco; però con due pesate riesco anche a trovare qual è quella diversa senza conoscere se la diversa è più pesante o più leggera. In pratica riesco a discriminare con 4 palline anziché con 3.
Nulla cambia se anziché 3 palline ne ho 3 gruppi (come dire: gruppi di k palline l’uno).
In conclusione: se il numero di palline è p il numero n di pesate necessario è
n={log[3, p/4]}+2.
Trovata la soluzione per il problema delle k palline più pesanti ^_^ ! (si suppone di sapere si da principio che sia k, e che siano più pesanti) :
ParteInteraSuperiore[Log[2,Binomial[n, k]]]
Log[2, x] = Logaritmo in base 2 di x (se si suppone una bilancia a 2 piatti).
Ci sarebbe una versione un po' più complicata : k palline distribuite in p classi di equivalenza a seconda del peso 0 <= p <= n
(a questo sto lavorando attualmente, ma non credo ci sia una forma chiusa per la soluzione, se non definita per casi...).
Inoltre ogni problema può essere ulteriormente affermando che a priori non sono note una o più informazioni (es, numero palline, numero classi di equivalenza di peso, etc ... inoltre in questi casi ci sarebbero persino dei dubbi sulle strategie ottimali da seguire !!).
Non appena troverò qualcosa di nuovo lo posterò !
ParteInteraSuperiore[Log[2,Binomial[n, k]]]
Log[2, x] = Logaritmo in base 2 di x (se si suppone una bilancia a 2 piatti).
Ci sarebbe una versione un po' più complicata : k palline distribuite in p classi di equivalenza a seconda del peso 0 <= p <= n
(a questo sto lavorando attualmente, ma non credo ci sia una forma chiusa per la soluzione, se non definita per casi...).
Inoltre ogni problema può essere ulteriormente affermando che a priori non sono note una o più informazioni (es, numero palline, numero classi di equivalenza di peso, etc ... inoltre in questi casi ci sarebbero persino dei dubbi sulle strategie ottimali da seguire !!).
Non appena troverò qualcosa di nuovo lo posterò !
trovata (forse) le soluzione per le p classi di equivalenza :
per disribuire le pelline secondo le classi di equivalenza, per p = n, il problema di ricerca degenera in un problema di ordinamento che dovrebbe avere complessità O(n*Log[2, n]) => suppongo che il numero di pesate sia qualcosa come Sum[0 < i < p, Sup{Log[2, Binomial[n, k]]}]
dove k è il numero di palline all'interno dell' i-esima classe di equivalenza di peso.
infatti per n palline di peso diverso, il problema è effettivamente un problema di ordinamento => k = 1 per ogni i, int tal caso Binomial[n, k] = n, e dal momento che in questo caso p = n, la sommatoria = n*Log[2, n] che è l'upper-bound della complessità di un problema di ordinamento.
P.s. non sono sicuro se effettivamente funzioni, dovrebbe (spero), se trovate errori o simili vi prego correggetemi !
per disribuire le pelline secondo le classi di equivalenza, per p = n, il problema di ricerca degenera in un problema di ordinamento che dovrebbe avere complessità O(n*Log[2, n]) => suppongo che il numero di pesate sia qualcosa come Sum[0 < i < p, Sup{Log[2, Binomial[n, k]]}]
dove k è il numero di palline all'interno dell' i-esima classe di equivalenza di peso.
infatti per n palline di peso diverso, il problema è effettivamente un problema di ordinamento => k = 1 per ogni i, int tal caso Binomial[n, k] = n, e dal momento che in questo caso p = n, la sommatoria = n*Log[2, n] che è l'upper-bound della complessità di un problema di ordinamento.
P.s. non sono sicuro se effettivamente funzioni, dovrebbe (spero), se trovate errori o simili vi prego correggetemi !
eghm errata corrige :
che scemo ! la sommatoria fa (n-1)*Sup{Log[2, n]}..
se trovate altre baggianate in ciò che scrivo vi prego ditemelo ^_^ !
che scemo ! la sommatoria fa (n-1)*Sup{Log[2, n]}..
se trovate altre baggianate in ciò che scrivo vi prego ditemelo ^_^ !
Se ho ben capito quello che intendi tre post sopra confronta con quello che ha detto Pachito nel suo primo post in questo messaggio (il 6° post dall'inizio).
Eghm ... si altamente probabile che sia Log[3, ... ] dal momento che il confronto con una bilancia mi da esito ternario ^_^.
Siamo però sicuri che è sempre possibile discriminare esattamente 3 oggetti ??
Siamo però sicuri che è sempre possibile discriminare esattamente 3 oggetti ??
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo