Un problema matematico
Vi propongo un problema matematico molto interessante anche perchè è molto pratico e attinente alla vita reale. Il problema in origine riguardava 8 monete, ma ho pensato di estenderlo a un numero n qualsiasi di monete.
Quindi supponiamo di avere un certo numero n di monete che in apparenza sono tutte identiche, ma una di loro è difettosa perchè fatta di un altro materiale e pesa meno di tutte le altre uguali fra loro per peso. Avendo una disposizione una BILANCIA A 2 PIATTI, qual’è il numero minimo di pesate che si devono effettuare per individuare la moneta diffettosa? Trovate una formula riferita a tale numero n di monete. POI comunque vi diro’ la FORMULA CHE HO SCOPERTO.
Lettere che potrebbero interessarti
Categorie: - Attualità
23 commenti
Lascia un commento
Max 2 commenti per lettera alla volta. Max 3 links per commento.
Se non vedi i tuoi ultimi commenti leggi qui.
▸ Mostra regolamento
Leggi l'informativa sulla privacy. Usa toni moderati e non inserire testi offensivi, futili, di propaganda (religiosa, politica ...) o eccessivamente ripetitivi nel contenuto. Non riportare articoli presi da altri siti e testi di canzoni o poesie. Usa un solo nome e non andare "Fuori Tema", per temi non specifici utilizza la Chat.
Puoi inserire fino a 2 commenti "in attesa di pubblicazione" per lettera.
La modifica di un commento è possibile solo prima della pubblicazione e solo dallo stesso browser (da qualsiasi browser e dispositivo se hai fatto il Login).
Visto che parli di “n” monete, il numero minimo di pesate dovrebbe prescindere dal loro numero. In questi quesiti, talvolta la soluzione dipende da come essi sono formulati. Se per “pesata” intendi mettere n/2 monete su ogni piatto e poterne sottrarrne ed aggiungerne a piacimento, allora credo possa bastare una sola pesata. Basta mettere la metà esatta delle monete su ciascuno dei piatti (se in numero pari), che teoricamente non dovrebbero essere perfettamente bilanciati e toglierne una e una dai due piatti, finchè gli stessi non torneranno in perfetto equilibrio e la moneta diversa sarà quella tolta dal piatto che pesava meno. Se il numero delle monete fosse dispari, ci sono due possibilità: accantonarne una e mettere un numero pari di monete su cascun piatto e seguire la procedura illustrata poc’anzi. Se, ipoteticamente, i piatti si equivalessero già dalla prima pesata, la moneta diversa sarebbe quella accantonata. Ti piace l’idea ? Fabio.
Ma togliendo le monete mano a mano, si fà ogni volta una pesata perchè il peso cambia e sposti anche monete quindi è come se tu ripesassi i 2 gruppi di monete diminuiti di 1 ogni volta. NON è una sola PESATA!!!!!! A fare come dici tu se da 2 gruppi di 25 tolgo una moneta da ciascuno , ho altri pesi in gioco dop aver tolto le 2 monete e è come se avessi tolto i 2 gruppi da 25, avessi sottratto ad ognuno di essi una moneta e li avessi rimessi sulla bilancia. CAPISCI? INOLTRE NON cambia nulla se il numero è pario dispari, la FORMULA è sempre la stessa che mi dice con n monete quale è il minimo numero di pesate.Inoltre nessuno ti obbliga a dividere a metà il totale delle monete, anche se è ovvio che i mucchi su ogni piatto devono essere uguali per numero.
….. manco aggiungerne mano mano, si può ?
ogni volta che aggiungi o togli è una pesata in piu’. Poi con questo metodo non arrivi da nessuna parte, sei ben lontano
Premesso che non vedo cosa ci sia di “molto pratico e attinente alla vita reale” credo che la soluzione possa essere nel dividere in gruppi e andare per comparazione.
Esempio: 9 monete -> 2 pesate
dividi in 3 gruppi da 3 monete
pesi 2 gruppi ad esempio 1-2-3 in un piatto e 4-5-6 nell’altro
se stanno in equilibrio la moneta è nel gruppo 7-8-9
se no è nel gruppo più leggero
poi pesi 2 delle 3 monete del gruppo incriminato (una in un piatto e una nell’altro) e se stanno in equilibrio è quella non pesata altrimenti e la più leggera delle due.
Giusto?
Ma la formula non la riesci a trovare per n monete? Ad esempio con mille monete come procedi? Con 10000 ? Quante pesate devi fare con 1000 monete? con n monete? Capisci che voglio dire? Questo si sapeva già con 9 monete e con 8 perchè è un problema conosciuto oramai, ma difficile diventa estenderlo a un numero qualsivoglia n di monete
Non so con 1000 credo farei prima due gruppi da 500 poi con il più leggero due da 250 poi due da 125.
A questo punto farei 5 gruppi da 25 e ne peserei 4 due su un piatto e due sull’altro.
In caso di equilibrio sarebbe tra le 25 fuori se no dividendo i due gruppi più leggeri troverei il gruppo da 25 che la contiene.
A questo punto dividerei 5 gruppi da 5 e farei lo stesso procedimento.
Identificato il gruppo da 5 che la contiene ne toglierei una e peserei 2 e 2.
E se non sono in equilibrio è facile trovare con una ulteriore pesata quella incriminata.
Quindi totale… 3 per arrivare a 125 + max 2 per arrivare a 25 + max 2 per arrivare a 5 + max altre 2 per individuarla… quindi al massimo 9 pesate.
Non so se esista poi una formula valida perchè credo che ci siano troppe combinazioni possibili per racchiuderle in una sola formula.
E INVECE bastano 7 pesate per essere sicuri di trovare fra 1000 la moneta difettosa. LA FORMULA ESISTE e è precisissima, vale per ogni numero n di monete anche un numero enorme.La ho scoperta e verificata.
Ha qualcosa a che fare con i multipli di sette ?
NON centra nulla coi multipli di 7.ma prova a usare carta e penna per risolverlo.
Ok la sparo li… il concetto è lo stesso del problema che ho risolto delle 9 monete… e consiste nel dividere a gruppi.
Per ottenere il numero minimo di pesate quale è la soluzione? Quella di formare tanti gruppi e confrontarli… però avendo solo 2 piatti sulla bilancia i gruppi che posso formare sono 3… due li confronto e la moneta o è in uno dei due gruppi (il più leggero) oppure è in quello non pesato.
Ora in matematica non sono molto pratico e non so come riportare questo concetto in una formula… ma il numero di pesate necessario è dato dal numero di volte che è divisibile per 3 il numero di monete che voglio pesare + 1.
Nel caso delle 1000 monete:
(i valori tra parentesi sono riferiti al caso del gruppo più numeroso)
1) 333 – 333 – 334
peso i 2 da 333 e può essere o in uno dei 2 gruppi o nel gruppo 334
2) 111 – 111 – 111(112)
peso 2 gruppi da 111 e ne lascio fuori 111(o 112 se era nel gruppo 334)
3) 37 – 37 – 37(38)
stessa cosa di sopra
4) 12(13) – 12(13) – 13(12)
sempre stesso concetto
5) 4 – 4 – 4(5)
idem come sopra
6) 2 – 2 – (1)
a questo punto invece non essendo più divisibili con una ulteriore pesata si ha la soluzione
7) 1 – 1
Come ho scritto sopra però non ho le conoscenze matematiche per scrivere una formula che indichi questo procedimento… anche se credo sia questa la soluzione.
Questo è un inizio di ragionamento, ma non è rigoroso, e non porta lontano se non hai un metodo.La formula non richiede nessuna conoscenza matematica ma solo raagionamento.
Anch’io avevo pensato a qualcosa di molto simile a Topodiddl ….
gello e ponale sono la stessa persona?
Comunque mi spiace contraddirti ma per scrivere una formula servono conoscenze matematiche e io ammetto di non averne.
Il concetto te l’ho espresso a parole di più non riesco… provo a dirtelo così forse ti piace di più.
Dato un numero n di monete si divide per 3 facendo attenzione ad avere almeno 2 mucchi con lo stesso numero di monete; si pesano i due mucchi uguali lasciando fuori quello che un numero diverso di monete.
Si individua il gruppo che contiene la moneta falsa tra i 3 (se sono in equilibrio è quello non pesato se no è il più leggero) e si ripete fin tanto che si possono fare 3 mucchi dei quali 2 uguali.
Una volta che non si possono fare più gruppi o abbiamo trovato la moneta o vuol dire che abbiamo 4 monete.
In quel caso con altre 2 pesate si trova come indicato nel commento n.11 qua sopra.
Ora come ti ho già detto non sono capace di scrivere questo su una formula.
Ok, bisogna dividere in 3 mucchi di cui almeno 2 uguali, dici bene. Ma alla fine non necessariamente rimangono 4 monete. Comunque la formula richiede conoscenze di aritmetica che possiede già un ragazzo alla fine delle scuole MEDIE!!! Serve solo un gran ragionamento.
ciao, a tutti
la soluzione è p=p(n) il numero di pesate è uguale a
p=[ln(n)/ln(3)];
dove [ * ] indica l’arrotondamento all’intero superiore.
bella li ragazzi sentite questa generalizzazione?
se la “bilancia ideale” avesse r piatti e non due.
non è una complicazione …
Esatto , la hai trovata su google? Per un numero di piatti si ha ln(n) / ln (x+1) il tutto arrotondato all’intero successivo. E le ho scoperte da solo, non in rete.
beh se scrivi la soluzione come ln(n)/ln3 significa che hai trovato la soluzione in rete, almeno a mio avviso, comunque e facilissimo trovare che la soluzione e logaritmo in base 3 di n, che attraverso il teorema del cambiamento di base da la formula di prima
In generale se ho X possibili casi da differenziare (in questo caso ne ho n perche ho n possibilita diverse, ognuna per ogni moneta che potebbe essere quella falsa ) e ad ogni scelta (pesata nel nostro caso) posso dividire in ‘a’ sottocasi, allora ho bisogno di logaritmo in base a di X decisioni, o ln(X)/ln(a)
Ad esempio se io ho mille monete e la moneta può essere sia piu pesante sia piu leggera e io avendo la bilancia a 2 piatti posso dividire in 3 casi (equilibrio e si alza il primo o si alza il secondo) avrò 2000 casi possibili (1000 possibilita di scegliere la falsa e due modi di scegliere se pesa di piu o di meno), e avrò bisogno di almeno ln2000/ln3 pesate.Questo però e il limite minimo, se provate anche solo con una ventina di monete tocca usare pesante aggiuntive.
Per chi conosce i concetti matematici (o piu che altro informatici) di albero a più vie basta pensare ai possibili casi come foglie di un albero ad ‘a’ vie e il numero minimo pesate e l’altezza minima che deve avere un albero di tale tipo per avere almeno X foglie, ogni foglia rappresenta un ‘caso’ e ogni nodo una pesata.
Vedere anche alberi decisionali
ma visto che si cercava una semplice ragionamento ecco qui quello che mi sembra piu facile da capire:
immaginate di poter elencare tutti i possibili casi: saranno el tipo la moneta falsa e la prima, la seconda, la terza, etc.. fino alla ennesima, ora ad ogni pesata come è evidente si potranno scartare al massimo due terzi dei casi
infatti io posso dividere in tre i casi e abbinarli ognuno ad un risultato della pesata (esempio bilancia piatta->moneta falsa sul gruppo non pesato etc..)
Ora per eliminare piu monete possibili gli insiemi devono essere equilibrati, quindi contenenti ognuno un terzo dei casi possibili.
Quindi ad ogni pesata divido per tre i casi possibili, perciò per arrivare ad un solo caso devo dividere per 3 tante volte quante sono le volte che devo dividere per 3 n per ottenere 1, ovvero il logaritmo in base 3 di n.
Piccola nota: i logaritmi da quel che so io alle medie non si fanno, quindi un minimo di matematica “avanzata” serve.
per generalizzare a n piatti basta aumentare il quoziente per cui dividere ad ogni pesata.
Io pensavo tre pesate.. la prima di quattro contro quattro, la seconda prendendo quella che pesa meno dividendo in una pesata da due e due, la terza prendendo la pesata inferiore divisa in uno e uno…
La formula però non la so..nel senso che non mi sto prendendo la briga di dedurla
Se n è il numero di palline bisogna guardare il primo numero minore o uguale a n del tipo 2 elevato alla x n tale che n>=2^x
es: se ho 14 palline, il primo numero minore o uguale a 14 di quel tipo è 2^3 (8)
le pesate minime necessarie sono l’esponente x
quindi in questo caso le pesate sono 3….infatti se ho una sola moneta non ho bisogno di pesate, poiché 2 elevato alla 0 da 1.
Non che avessi molta voglia di leggere le varie risposte ma credo che la soluzione sia statsa gia trovata…
Comunque:
Non so scrivere in matematichese e quindi esporrò solo un algoritmo che comunque sarà RIGOROSO.
Analisi:
I piatti della bilancia sono 2.
le monete sono Pari oppure Dispari.
UNA SOLA di esse ha un peso MINORE.
TUTTE le altre hanno IDENTICO peso.
0 – START
1 – Prendi il gruppo di monete a disposizione
2 – se il numero di monete è pari vai alla riga 4
3 – togli una moneta e mettila da parte
4 – dividi equamente il gruppo di monete sui due piatti
4a – Se i piatti sono equipesanti vai alla riga 10
5 – scarta il gruppo di monete più pesante
6 – Se il gruppo di monete rimasto è pari a uno vai alla riga 8
7 – vai alla riga 1
8 – Hai in mano la moneta più leggera
9 – Vai alla riga 11
10 – la moneta che hai messo da parte è quella più leggera
11 – END
il numero massimo delle pesate è dato dalla seguente disequazione:
2^x < Numero di monete < 2^x+1 con x = numero di pesate
il numero minimo di pesate è dato da DUE condizioni:
1 – Ho un numero dispari di monete
2 – Ho la fortuna di mettere da parte quella più leggera