Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
* QUIZ: Palline e bilance
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
GionnyBoss
Mortale devoto
Mortale devoto


Registrato: 14/02/06 19:01
Messaggi: 11

MessaggioInviato: 28 Feb 2006 06:48    Oggetto: * QUIZ: Palline e bilance Rispondi citando

Ci sono 9 palline di identico aspetto, e di queste si sa che:
- 8 hanno lo stesso peso
- una è di poco più pesante delle altre (e ovviamente... non si sa qual è!)

Si dispone di una bilancia di quelle con i due piatti. Quindi, ad ogni pesata, si può sapere se X palline pesano uguale, di più o di meno di altre Y palline.

Qual è il numero minimo di pesate per capire qual è la pallina più pesante?

(spero di averlo scritto in modo comprensibile... Razz)
Fatevi sotto con la soluzione... Ciao!
Top
Profilo Invia messaggio privato
Franto
Semidio
Semidio


Registrato: 14/06/05 15:05
Messaggi: 367
Residenza: como (provincia)

MessaggioInviato: 28 Feb 2006 10:50    Oggetto: Rispondi citando

Citazione:
si dividono le palline in gruppi di 3 palline ciascuno e si conforntano due gruppi a caso con la bilancia (prima pesata)

se i due gruppi pesano uguale la pallina più peante sarà nel terzo gruppo, altrimenti nel gruppo più pesante, ovviamente sarà presente la pallina più pesante.

ora si prende il gruppo con la pallina più pesante e si confrontano col la bilancia due palline a caso (second pesata)

se le palline sono pesanti uguali quella che rimane fuori è la pallina più pesante altrimenti la palline più pesante è quella che pesa di piu' Very Happy

risultato: sono sufficenti 2 pasate!


primo!
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 28 Feb 2006 13:23    Oggetto: Rispondi citando

Vai Gionny! Grazie per il quiz. E bravo Franto che è stato il più veloce a rispondere.

Ora però faccio il bastardo e da bravo matematico propongo una generalizzazione:

Ci sono n palline tutte dello stesso peso tranne una.
Determinare il numero minimo di pesate atte a individuare la pallina di peso differente ed esprimere tale numero in funzione del numero n di palline.
Esistono casi particolari (n pari, dispari, primo, multiplo)?

Partecipo anch'io perché non conosco ancora la risposta e mi sono inventato ora la domanda. Very Happy
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 08 Mar 2006 16:37    Oggetto: Rispondi citando

Beh... io ho trovato la risposta che mi sembra corretta:
Citazione:
Se n è il numero di palline, k il numero minimo di pesate, LOG3(x) il logaritmo in base 3 del numero x e CEIL(x) la funzione che individua il più piccolo intero maggiore o uguale a x, avremo che:
k=CEIL(LOG3(n))

Ad esempio se le palline sono 28<n<=81, essendo 28 = 3^3+1 e 81 = 3^4, il numero minimo di pesate per individuare la pallina anomala non supera 4.

Qualcuno sa spiegare il perché?
Top
Profilo Invia messaggio privato HomePage
Daviz
Eroe in grazia degli dei
Eroe in grazia degli dei


Registrato: 31/01/06 16:02
Messaggi: 133

MessaggioInviato: 17 Mar 2006 01:27    Oggetto: Rispondi citando

Scusa Ulisse, e scusate l'OT... ma quest'uomo o è un folle, o è un genio... di sicuro mi intrippa tutte le volte che fa una domanda... e mi fa sovvenire le barzellette sugli ingegneri Very Happy
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 18 Mar 2006 21:42    Oggetto: Rispondi citando

Daviz ha scritto:
Scusa Ulisse, e scusate l'OT... ma quest'uomo o è un folle, o è un genio... di sicuro mi intrippa tutte le volte che fa una domanda... e mi fa sovvenire le barzellette sugli ingegneri Very Happy


Quale uomo? Shocked se parli di me: niente genialità... forse un pizzico di follia...

Barzellette? e se aprissi un topic dedicato all'umorismo matematico?
Top
Profilo Invia messaggio privato HomePage
fauroa
Comune mortale
Comune mortale


Registrato: 14/02/06 12:52
Messaggi: 3

MessaggioInviato: 23 Mar 2006 14:01    Oggetto: Rispondi citando

io, che sono un perfido, di solito propongo :
'ci sono 80 palline, tutte uguali meno una che è più pesante...'
proponendo 81 salta subito all'occhio che è una potenza di tre, e da li si intuisce il sistema... invece per passare da 80 alla divisione in tre gruppi (viene naturale pensare di dividerle in due)
Top
Profilo Invia messaggio privato
Franto
Semidio
Semidio


Registrato: 14/06/05 15:05
Messaggi: 367
Residenza: como (provincia)

MessaggioInviato: 23 Mar 2006 14:20    Oggetto: Rispondi citando

ulisse ha scritto:
Beh... io ho trovato la risposta che mi sembra corretta:
Citazione:
Se n è il numero di palline, k .......

Qualcuno sa spiegare il perché?


non c'ho capito nulla!!!!!! Crying or Very sad Crying or Very sad Evil or Very Mad Brick wall Think
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 23 Mar 2006 18:16    Oggetto: Rispondi citando

Con un numero n di palline pari a 3^0 (leggasi con una pallina) il numero di pesate necessario a individuare la pallina anomala è 0 (notare la coincidenza tra il numero di pesate e l'esponente di 3).

Con un numero di palline compreso tra 3^0+1 e 3^1 (un modo contorto per dire tra 2 e 3) il numero di pesate è 1 (notate ancora la coincidenza).

Con un numero di palline compreso tra 3^1+1 e 3^2 (tra 4 e 9) il numero di pesate è 2 (i due numeri succitati continuano a coincidere).

Con un numero di palline compreso tra 3^2+1 e 3^3 (tra 10 e 27) il numero di pesate è 3.
Quale sarà quindi il numero k di pesate quando il numero n di palline è compreso tra un generico 3^(k-1)+1 e 3^k ?

Ovviamente k!
Come faccio a ricavare k da n ?
Basta notare che k compare sempre a esponente di una potenza in base 3 e dunque per eplicitare k serve il logaritmo in base 3.

Poiché n non è per forza una potenza di 3, il logaritmo in base 3 di n non sarà sempre intero. Ecco quindi che quando tale logaritmo non è intero bisogna prendere l'intero successivo (che è quello che fa la funzione CEIL).

Perché continua a ricorrere il 3?
Perché l'algoritmo atto a individuare la pallina anomala è ricorsivo e si basa sul principio "divide et impera" ovvero prendo le palline, le suddivido in gruppi, peso per individuare il gruppo anomalo e ripeto il procedimento limitandomi al gruppo anomalo. Poco alla volta il gruppo anomalo si riduce alla sola pallina anomala.

Perché dividere in 3 gruppi e non in 2 o 4 o altro?
Perché la bilancia ha 2 piatti ma offre 3 responsi:
la bilancia pende verso un piatto, verso l'altro, verso nessuno dei due.
Quindi con una sola pesata posso distinguere non 2 ma 3 gruppi.
Con 4 o più gruppi non mi basta una singola pesata.
Con 2 gruppi non sfrutto appieno le possibilità della bilancia.

Poiché il procedimento consiste nella ripetuta suddivisione in 3 gruppi l'algoritmo ha efficenza massima quando un gruppo contiene palline in numero uguale a una potenza di 3.
Se n non è una potenza di 3 (ad esempio 80) alla prima suddivisione formeremo due gruppi da 27 palline e il terzo gruppo con le palline residue (cioè 26).

Spero di aver chiarito!

Benvenuto fauroa! Hai ragione, sei proprio perfido! Laughing
Top
Profilo Invia messaggio privato HomePage
OXO
Dio maturo
Dio maturo


Registrato: 10/05/05 17:30
Messaggi: 1942
Residenza: Scandicci

MessaggioInviato: 27 Mar 2006 16:51    Oggetto: Rispondi citando

Citazione:
ma quest'uomo o è un folle, o è un genio...


Be', io sono alla prima apparizione in questo forum (finora mi sono limitato a seguire dall'esterno), approfitto però per convenire che Ulisse ha quanto meno una testa diversa dalla mia: questa volta il giochino delle palline era facile facile (non me ne voglia Franto, ma si consoli sapendo che l'algoritmo esula anche dalle mie delucubrazioni), ma certe volte faccio veramente fatica a seguirvi.

...e pensare che da bambino volevo fare l'ingegnere spaziale... Shocked Confused Confused Confused
Top
Profilo Invia messaggio privato
hungaricus
Mortale pio
Mortale pio


Registrato: 29/11/05 14:41
Messaggi: 27
Residenza: Trieste

MessaggioInviato: 28 Mar 2006 13:42    Oggetto: una difficoltà in più Rispondi citando

Ciao a tutti!

anch'io di solito mi limito a leggere senza intervenire, ma mi sembrava degna di nota una versione del quesito MOLTO simile a quella proposta, però con una bastardissima differenza (minima ma essenziale).

Ci sono sempre 9 palline dall'aspetto identico, e una ha un peso differente. Però non si sa se la pallina anomala pesa di più o di meno! Shocked

La domanda rimane la stessa: con una bilancia a 2 piatti, qual è il numero minimo di pesate per determinare la pallina anomala?
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 28 Mar 2006 17:53    Oggetto: Rispondi citando

Carina questa variante!

Credo che...
Citazione:
...basti una sola pesata in più necessaria a stabilire se la pallina anomala pesa di più o di meno delle altre.

Prima pesata: metto due gruppi da tre palline sui piatti.
Seconda pesata: scambio uno qualsiasi dei due gruppi col terzo rimasto da conto.
Così facendo individuo la terna anomala e, contemporaneamente, scopro se la pallina anomala pesa di più o di meno delle altre.
Con la terza pesata individuo la pallina anomala.

In dettaglio.
La prima pesata fornisce A = B quindi il gruppo anomalo è C.
Scambio B con C e peso di nuovo.
Se A > C la pallina anomala pesa di meno e con una terza pesata la individuo.
Se A < C la pallina anomala pesa di più e con una terza pesata la individuo.

La prima pesata fornisce A <> B e il gruppo anomalo è o A o B.
Scambio B con C e peso di nuovo.
Se la bilancia cambia stato il gruppo anomalo è B. Inoltre se alla prima pesata era A > B la pallina anomala pesa di meno delle altre viceversa se era A < B pesa di più e in antrambi i casi con una terza pesata la individuo.
Se la bilancia non cambia stato il gruppo anomalo è A. Inoltre se alla seconda pesata A < C la pallina anomala pesa meno delle altre e se A > C pesa di più. Anche in questo caso la terza pesata è risolutiva.


p.s.: benvenuto tra noi!
Top
Profilo Invia messaggio privato HomePage
Eureka
Mortale devoto
Mortale devoto


Registrato: 30/03/06 17:08
Messaggi: 19

MessaggioInviato: 15 Mag 2006 22:50    Oggetto: Rispondi citando

Qualche giorno fà mi hanno proposto una variante di questo problema che fortunatamente sono riuscito a risolvere Idea 8).....
ecco il problema:
12 palline, bilancia a piatti, 1 pallina anomala come trovare la pallina anomala con Twisted Evil 3 pesate Twisted Evil ?

buon divertimento Wink
Top
Profilo Invia messaggio privato
alb82
Mortale pio
Mortale pio


Registrato: 18/05/06 09:36
Messaggi: 27

MessaggioInviato: 18 Mag 2006 14:10    Oggetto: Rispondi citando

Si dividono le palline in gruppi da 3 (4 gruppi). 2 gruppi sulla bilancia. Se è sbilanciata la pallina è in uno di questi 2 gruppi, altrimenti negli altri 2.
Sostituisco su un piatto un gruppo con uno degli altri 2. Se la bilancia era sbilanciata alla prima, so che i 2 gruppi inizialmente rimasti fuori erano di peso normale, quindi se ora c'è sbilanciamento capisco che il gruppo rimasto sulla bilancia dall'inizio e quello con la pallina anomala (e capisco pure se la pallina anomala era più pesante o più leggera); se la bilancia è pari capisco che è il gruppo appena tolto quello anomalo. Se ho parità alla prima pesata e alla seconda, il gruppo anomalo è quello mai pesato. Se ho parità alla prima e disparità alla seconda...(si capisce)
Quindi rimangono tre palline che discrimino con una pesata (una pallina per braccio).
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 18 Mag 2006 16:41    Oggetto: Rispondi citando

Benvenuto Alb!
La tua risposta mi fa riflettere.
Qualche post fa avevo concluso che nel caso di 9 palline, senza conoscere il segno dell'anomalia, era sufficiente una pesata in più.
Ma avevo anche supposto (per fortuna solo tra me e me) che tale affermazione fosse valida per ogni n.

A quanto pare (e il tuo intervento lo conferma) la generalizzazione non sarebbe corretta. Infatti nel caso n=12 da te esposto servono 3 pesate sia che il segno dell'anomalia sia noto sia che sia incognito!
Top
Profilo Invia messaggio privato HomePage
Jowex
Eroe in grazia degli dei
Eroe in grazia degli dei


Registrato: 15/04/06 14:20
Messaggi: 90

MessaggioInviato: 18 Mag 2006 18:28    Oggetto: Rispondi citando

alb82 ha scritto:
Se ho parità alla prima pesata e alla seconda, il gruppo anomalo è quello mai pesato.

Quindi a questo punto sappiamo che la pallina anomala è nel gruppo di 3 palline mai pesato, ma non sappiamo se è più pesante o più leggera.
Se alla terza pesata (una pallina per braccio) la bilancia è sbilanciata, non possiamo sapere quale tra le due palline sia quella anomala!
Top
Profilo Invia messaggio privato
alb82
Mortale pio
Mortale pio


Registrato: 18/05/06 09:36
Messaggi: 27

MessaggioInviato: 18 Mag 2006 18:57    Oggetto: Rispondi citando

E vero!!
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 18 Mag 2006 19:11    Oggetto: Rispondi citando

Jowex ha scritto:
alb82 ha scritto:
Se ho parità alla prima pesata e alla seconda, il gruppo anomalo è quello mai pesato.

Quindi a questo punto sappiamo che la pallina anomala è nel gruppo di 3 palline mai pesato, ma non sappiamo se è più pesante o più leggera.
Se alla terza pesata (una pallina per braccio) la bilancia è sbilanciata, non possiamo sapere quale tra le due palline sia quella anomala!


Perché sono sempre così frettoloso?

Mi sembrava strano che con 9 palline servisse una pesata in più mentre con 12 no. Eppure non ho avuto dubbi nel concludere che l'errore fosse mio prima di completare la verifica del ragionamento di Alb.

A quanto pare nemmeno Nessuno è perfetto! Very Happy
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19480
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 18 Mag 2006 21:19    Oggetto: Rispondi citando

ulisse ha scritto:
A quanto pare nemmeno Nessuno è perfetto! Very Happy

ROTFL ROTFL ROTFL
Top
Profilo Invia messaggio privato Invia e-mail HomePage
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 18 Mag 2006 21:37    Oggetto: Rispondi

madvero ha scritto:
ulisse ha scritto:
A quanto pare nemmeno Nessuno è perfetto! Very Happy

ROTFL ROTFL ROTFL

Non ho capito perché si ride... per l'errore grammaticale, o questo Nessuno è qualcuno in particolare?
Top
Profilo Invia messaggio privato
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Vai a 1, 2, 3  Successivo
Pagina 1 di 3

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi