26/11/2006

Un Indovinello: Che Palline!

Posted in Creazioni, Giochi, Indovinelli, Matematica, Quiz, Riflessioni a 17:25:49 di JhacK

(INFORMAZIONE DI SERVIZIO: il nuovo blog si trova all’indirizzo http://www.jhack.it/blog, pertanto ti pregherei di visitare questo post a questo indirizzo.)

Visto questo indovinello sul blog di Pino ve lo propongo per esporre, in seguito, le mie riflessioni. Innanzittuto lo posso dividere in due indovinelli, il primo facile ed il secondo decisamente più complicato. Per entrambi si suppone di avere una bilanca a due bracci assolutamente normale, con due piatti su cui posare gli oggetti da pesare: in questo caso delle palline. Non è un indovinello di logica laterale, quindi non pensate a cose strane :D.

1) Si hanno 9 palline, di cui una è più pesante (leggera). Bisogna determinare qual è quella più pesante (leggera) con sole 2 pesate.

2) Si hanno 12 palline, di cui una diversa dalle altre. Bisogna determinare qual è quella diversa con sole 3 pesate.

Notate la differenza sostanziale, che non è il numero di palline, ma il fatto che nel primo caso si cerca una caratteristica nota a priori, cioè la pallina più leggera o più pesante, mentre nel secondo caso si chiede di determinare la pallina diversa dalle altre, senza sapere se è più pesante o meno.

La soluzione del primo quiz mi auguro di vederla presto tra i commenti, mentre quella del secondo ve la riporto di seguito, invitandovi però a scoprirla da soli :P.

Si dividono le 12 palline in tre gruppi da 4. Per capirci qualcosa numero le palline da 1 a 12:

  • G1 = 1, 2, 3 e 4;
  • G2 = 5, 6, 7 e 8;
  • G3 = 9, 10 11 e 12;

Si mettono le palline 1, 2, 3, 4 su un piatto e le palline 5, 6, 7, 8 sull’altro. Si possono presentare i casi:

  1. i piatti sono pari: la pallina diversa sarà una tra 9, 10, 11 e 12;
  2. si abbassa il piatto con le palline 1, 2, 3, 4;
  3. si abbassa il piatto con le palline 5, 6, 7, 8.

1) si mette una pallina di G1 (scelgo la 1 per comodità) e una del gruppo G3 (scelgo la 9) su un piatto della bilancia e altre due palline del gruppo G3 (scelgo 10 e 11) sull’altro piatto:

  • 1.1) i piatti sono pari: la pallina diversa è la 12. Siamo a due pesate e con la terza si può determinare se è più o meno pesante delle altre confrontandola con una qualsiasi;
  • 1.2) scende il piatto con le palline 1 e 9; la pallina diversa può essere la 9, più pesante, o una tra la 10 e la 11, più leggera. Con la terza pesata si confrontano la 10 e la 11:
    • 1.2.1) i piatti sono pari: la pallina diversa è la 9 ed è più pesante;
    • 1.2.2) i piatti non sono pari: il piatto che sale contiene la pallina diversa, che sarà più leggera.
  • 1.3) scende il piatto con le palline 10 e 11: la pallina diversa può essere la 9, più leggera, o una tra la 10 e la 11, più pesante. Con la terza pesata si confrontano la 10 e la 11:
    • 1.3.1) i piatti sono pari: la pallina diversa è la 9 ed è più leggera;
    • 1.3.2) i piatti non sono pari: il piatto che scende contiene la pallina diversa, che sarà più pesante.

2) si creano due gruppi di palline in modo tale che nel primo ce ne sia una di ciascun gruppo (scelgo 1, 5, 9) e nel secondo una di G1 e due di G2 (scelgo 2, 3, 6) e si confrontano sulla bilancia:

  • 2.1) i piatti sono pari: la pallina diversa può essere la 4, più pesante, o una tra la 7 e la 8, più leggera. Con la terza pesata si confrontano la 7 e la 8:
    • 2.1.1) i piatti sono pari: la pallina diversa è la 4, più pesante;
    • 2.1.2) i piatti non sono pari: il piatto che sale contiene la pallina diversa, più leggera.
  • 2.2) scende il piatto con le palline 1, 5, 9: la pallina diversa può essere la 1, più pesante, o la 6, più leggera. Con la terza pesata si confrontano la 1 con una di G3 (sicuramente non diversa):
    • 2.2.1) i piatti sono pari: la pallina diversa è la 6, più leggera;
    • 2.2.2) i piatti non sono pari: scende per forza il piatto con la pallina 1, più pesante.
  • 2.3) scende il piatto con le palline 2, 3, 6: la pallina diversa può essere la 5, più leggera, o una tra la 2 e la 3, più pesante. Con la terza pesata si confrontano la 2 e la 3:
    • 2.3.1) i piatti sono pari: la pallina diversa è la 5, più leggera;
    • 2.3.2) i piatti non sono pari: scende il piatto con la pallina diversa, più pesante.

3) si creano due gruppi di palline in modo tale che nel primo ce ne sia una di ciascun gruppo (scelgo 1, 5, 9) e nel secondo una di G1 e due di G2 (scelgo 2, 3, 6) e si confrontano sulla bilancia:

  • 3.1) i piatti sono pari: la pallina diversa può essere la 4, più leggera, o una tra la 7 e la 8, più pesante. Con la terza pesata si confrontano la 7 e la 8:
    • 3.1.1) i piatti sono pari: la pallina diversa è la 4, più leggera;
    • 3.1.2) i piatti non sono pari: il piatto che scende contiene la pallina diversa, più pesante.
  • 3.2) scende il piatto con le palline 1, 5, 9: la pallina diversa può essere la 5, più pesante, o una tra la 2 e la 3, più leggera. Con la terza pesata si confrontano la 2 e la 3:
    • 3.2.1) i piatti sono pari: la pallina diversa è la 5, più pesante;
    • 3.2.2) i piatti non sono pari: sale il piatto con la pallina diversa, più leggera.
  • 3.3) scende il piatto con le palline 2, 3, 6: la pallina diversa può essere la 6, più pesante o la 1, più leggera. Con la terza pesata si confrontano la 1 con una di G3(sicuramente non diversa):
    • 3.3.1) i piatti sono pari: la pallina diversa è la 6, più pesante;
    • 3.3.2) i piatti non sono pari: sale per forza il piatto con la pallina 1, più leggera.

E qui finisce la soluzione.

Nel risolvere questo quiz ho cercato di trovare una relazione tra il numero di palline e il numero di pesate per discriminarle.
Nel caso in cui si sappia cosa si sta cercando (pallina più pesante o più leggera) la bilancia può discriminare con una pesata un oggetto fra tre, quindi con k pesate si possono discriminare 3k oggetti. Quindi se “p” è il numero delle palline, “n” il numero delle pesate le due entità sono in rapporto:

n = ceil(log3p)

dove “ceil” è la funzione che restituisce l’intero superiore o uguale a quello passato per argomento e “logab” è il logaritmo in base “a” di “b“.
Da questo si può osservare che, relativamente soprendentemente, con 10 pesate è possibile scoprire la pallina che pesa di più o di meno tra 3(10-1)+1 e 310 palline, quindi fino ad un massimo di 59049.

Se però non si sa a priori quello che si sta cercando rimane una decisione binaria, leggero o pesante, che è possibile decidere con una pesata. Quindi la formula di prima diventa:

n = ceil(log3p) + 1

Applicata al problema proposto la formula dà:
n = ceil(log312) + 1 = 4

mentre si poteva risolvere in sole 3 pesate, quindi questa formula dà una soluzione sufficiente ma non necessaria, ovvero sicuramente si riesce in ceil(log3p) + 1 pesate a trovare la pallina diversa tra le “n” in gioco, ma in alcuni casi si può fare di meglio.

Per ora non ho ancora trovato la formula “necessaria“; qualcuno ha qualche idea a partire dalla mia?

Annunci

21 commenti »

  1. La cosa mi fa sorridere..
    ..qualche anno fa il miglior professore di Matematica che un Liceo abbia mai avuto ci ha fatto un pò per divertire i propri alunni, un pò perchè faceva caldo e nessuno voleva studiare questo indovinello.

    Quello con le 9 palline è di facilissima risoluzione:
    Si dividono le palline in 3 Gruppi, si pesano prima il primo e il secondo gruppo e se i piatti rimangono a livello vuol dire che la pallina + pesante è nel terzo gruppo, se invece un piatto va + in basso vuol dire che la pallina è nel gruppo che sta su quel piatto.

    Una volta capito qual’è il gruppo si fa la seconda pesata scegliendo a caso 2 delle 3 palline del gruppo. Quindi per esclusione si individua la pallina.

    Per il quiz con le palline da 12, mi fa sorridere pensare che noi alunni lo risolvemmo senza astruse formule del tipo n = ceil(log3p) +

    ..lasciatelo dire.. frequenti troppi ingegneri.

  2. JhacK said,

    Di ingegneri proprio non ne frequento, ma ho una forte passione per la matematica e per la logica :).
    Mi viene naturale cercare di generalizzare un ragionamento per tirare fuori una formula generale.
    La vostra soluzione era come quella che ho proposto?

  3. pina said,

    du maron,troppo complessi

  4. Non frequenti ingegneri?
    Allora sei più grave di me! 😛

    Scherzi a parte .la soluzione era del tutto simile a quella che hai proposto.

  5. benosa said,

    Innanzi tutto complimenti per la generalizzazione della soluzione…poi vorrei capire che cosa vi hanno fatto tanto di male gli Ingegneri? Sapete che sono anche bravissimi in CUCINA!
    Infine avete mai visto o esporato il Mondo della MateMagia
    Aspetto commenti!

  6. JhacK said,

    @benosa: grazie dei complimenti, però ora trovarmi la formula finale, eheheh. O almeno, visto che ti sei letto la soluzione e l’hai capita, spero, avrai anche una certa conoscenza di matematica che potrebbe portarti ad indovinare la soluzione dell’indovinello precedente a questo; per ora non ci è arrivato nessuno, ma uno ci è andato terribilmente vicino!
    Per quanto riguarda gli ingegnerai, a me personalmente non hanno fatto nulla, per ora, ma diciamo che nella nostra facoltà anche alcuni professori tendono a metterci in lizza con gli ingegneri :D. Immagino sia per il fatto che ci sono aree di sovrapposizione con, ad esempio, ingegneria informatica. Ma soprattutto per l’impostazione di mentalità chiusa che si dice abbiano gli ingegneri :).
    Comunque niente di personale, eh!

  7. benosa said,

    Andrò appena ho un pò di tempo a vedere questo indovinello di cui parli… ma ora pensando al primo quesito credo che non sia completa. Infatti come sottolineavi tu non bisogna solo individuare la pallina con il peso diverso ma anche se è più pesante o meno.
    Tra tutte le possibili combinazioni che fanno parte della soluzione che hai proposto esite un caso in cui riesci ad individuare la pallina con il peso diverso ma non se è più pesante o più leggera delle altre.
    Infatti delle 6 palline iniziali se con la prima pesata ottieni un pareggio e anche con la seconda ottieni il pareggio dei piatti la pallina che non è stata mai pesta sarà quella diversa ma non si sa se è più leggera o meno delle altre!

  8. JhacK said,

    @benosa: mi indichi qual è il caso? Li ho numerati apposta per possibili contestazioni :D. Comunque ripensaci mille volte facendoti anche dei disegnini: nello scrivere quei casi più volte ho dubitato di alcuni punti, ma alla fine ho capito che avevano tutti un senso; il “trucco” è non considerare le informazioni di ciascuna pesata da sole, ma ricordandosi anche quelle delle pesate precedenti.

  9. benosa said,

    io mi riferisco al primo esercizio ovvero quello delle 9 palline di cui, scusami la soluzione l’ha proposta qui Sasà Anarchia!
    In ogni caso se divido in tre grupppi di tre palline ciascuno e peso i primi due gruppi da tre e ho un pareggio vuol dire che la pallina “DIVERSA” è nel terzo Gruppo non ancora pesato!
    Se ora prendo a caso due palline di questro terzo gruppo e la sfortuna vuole che prendo propio due palline uguali, avro dalla pesata un nuovo pareggio dei piatti.
    QUINDI sono sicuro, che la pallina “diversa”, a patto che esista, sia quella non pesata. Ma non so SE è più PESANTE o PIU’ leggera delle altre!!! Cosa richiesta nell’indovonello!!!
    TU HAI LA SOLUZIONE COMPLETA?

  10. pina said,

    io mi sa che invece ho trovato errori ortografici sui commenti

    rileggere dxi pù

  11. Come nessuno?

    La prima mi pare averla risolta!

  12. JhacK said,

    @benosa: scusa, avevo letto male la tua risposta, comunque il problema nel primo quesito e’ in realta’ duplice:
    1) trovare la pallina piu’ leggera
    2) trovare la pallina piu’ pesante.
    Due problemi *indipendenti* e *svincolati*.

    La mia soluzione e’:
    ***
    Le dividi in 3 gruppi da 3 ciascuno e pesi due gruppi a caso:
    Caso 1: i due gruppi hanno lo stesso peso
    (*)Dividi le palline non pesate in 3 gruppi da 1
    ciascuno e pesi due gruppi a caso:
    Caso A: i due gruppi hanno lo stesso peso => la
    pallina non pesata è quella cercata
    Caso B: i due gruppi hanno peso diverso => la
    pallina sul piatto più in alto è quella cercata
    Caso 2: i due gruppi hanno peso diverso => come in (*) con il gruppo
    di palline sul piatto più alto
    ***

    @pina: quali errori ortografici? Se gravi, non li ho notati. O parli di cose simili al tuo “rileggere dxi pù”?

  13. benosa said,

    @JhacK credevo il quesito più complesso, ovvero che bisognava determinare non solo quale fosse la pallina con il peso diverso dalle altre ma anche se questa fosse più pesante o più leggera delle altre. Se così posto il problema, la tua soluzione va bene in tutti i casi tranne quello, C1A dove determini la pallina di diverso peso quale è ma non puoi dire se è più pesante o più leggera delle altre non avendola mai pesata!!!

  14. benosa said,

    o meglio, pensandoci bene non sono sufficienti 2 pesate se non sai a priori se la pallina è più pesante o più leggera.

  15. JhacK said,

    @benosa: quello che pensavi fosse il primo problema è in realtà il secondo, per quello mi pareva chiaro per esclusione cosa si chiedesse nel primo.
    Anche il caso 1A è correttissimo. Mi spiego per l’ultima volta, spero 🙂 : il primo problema sono in realtà due:
    1a) Si hanno 9 palline, di cui una è più pesante. Bisogna determinare qual è quella più pesante con sole 2 pesate.
    1b) Si hanno 9 palline, di cui una è più leggera. Bisogna determinare qual è quella più leggera con sole 2 pesate.
    1a-1A) Dopo aver determinato, con la prima pesata “fortunata” che quella più pesante è nell’altro gruppo da 3 effettuo la seconda pesata: sono ancora fortunato, i piatti sono pari, quindi la pallina non pesata è quella più pesante.
    1b-1A) Dopo aver determinato, con la prima pesata “fortunata” che quella più leggera è nell’altro gruppo da 3 effettuo la seconda pesata: sono ancora fortunato, i piatti sono pari, quindi la pallina non pesata è quella più leggera.

    Non vedo dove sia il problema.

  16. MaX said,

    Indovinello delle 12 palline:

    Prima pesata :
    si pongono 4 palle su un piatto della bilancia e 4 sull’altra per maggior chiarezza diro’ piatto di sinistra e piatto di destra di chi guarda.

    Si presentano subito due casi che bisogna esaminare.

    1) la bilancia e’ in equilibrio e cioe’ la palla diversa si trova tra le quattro non pesate che per maggior chiarezza diro’ che si trovano fuori a destra della bilancia.
    Il secondo caso che si potra’ verificare e’ quello della bilancia non in equilibrio.
    Riprendendo il primo caso, procedo alla seconda pesata in questo modo:
    sul piatto di sinistra metto tre palle di quelle gia’ esaminate non difettose e su quello di destra metto tre di quelle non ancora pesate.Si presenteranno tre possibilita’ :
    1) Bilancia in equilibrio ; la palla diversa e’ quella rimasta che potro’ confrontare con una bouna per determinare se piu’ leggera o piu’ pesante.
    2)Bilancia squilibrata con piatto di sinistra giu’ allora la palla diversa e’ tra le tre del piatto di destra ed e’piu’ leggera .Con la terza pesata pongo una sul piatto di sinistra e una sul piatto di destra. Il piatto della bilancia che si porta in alto mi indichera’ la palla diversa e se la bilancia resta in equilibrio non vi sara’ bisogno di alcuna pesata perche’ gia si conosce che la palla rimasta e’ piu’ leggera.
    3) Bilancia squilibrata con piatto di sinistra in alto.Si procede come nel caso precedente tranne che questa volta si conosce che la palla diversa e’ piu’ pesante.
    Il caso piu’ complicato e’ se alla prima pesata la bilancia non e’ in equilibrio
    E’ ovvio che in questo caso le quattro palle rimaste fuori della bilancia (a destra della bilancia) sono buone ..Allora si procede in questo modo: Si applica la seguente traslazione:
    Tre palle del piatto di sinistra si pongono fuori a sinistra della bilancia, contemporaneamente tre palle del piatto di destra si pongono nel piatto di sinistra e contemporaneamente tre palle buone che erano fuori a destra della bilancia si pongono sul piatto di destra.
    A questo punto la logica ci indichera’ la palla diversa qualunque caso si possa presentare.Infatti:
    a) La traslazione applicata non produca alcun effetto. Allora si sa’ che una delle due palle che non hanno subito la traslazione e’ quella diversa ed allora basta pesarne una con una buona.
    b)La traslazione produce una posizione di equilibrio ed allora una delle tre palle di sinistra e’ diversa e sappiamo anche che e’ piu’ leggera. Metteremo quindi una di queste tre su di un piatto della bilancia e un’altra sempre di queste tre sull’altro piatto. La posizione dei piatti ci indichera’ la palla diversa conoscendo ormai la pesantezza e nel caso di equilibrio, la diversa sara’ quella rimasta.
    c) La bilancia cambia equilibrio, il piatto di sinistra che era giu’ si porta in alto e quello di destra che era in alto si porta in basso.
    La logica ci dice che lo squilibrio e’ stato provocato dalle tre palle che sono passate dal piatto di destra a quello di sinistra. Le altre non possono aver causato il movimento per motivi logici facilmente individuabili.
    Poiche’ siamo anche riusciti a conoscere i motivi della diversita’ (leggerezza o pesantezza) si procede con la terza pesata come nel caso precedente .

  17. king84 said,

    Ma che problema c’era se questa pallina + pesante rimaneva ignota? Basta con le distinzioni di razza!

  18. ste said,

    Uff, l’HTML non funziona nei commenti. Ci riprovo:

    Ti suggerisco una condizione “necessaria” (o per meglio dire un lower bound sul numero di pesate). Usando la tua stessa notazione:

    n^3 >= 2p

    ovvero, tutto in un’unica formula:

    ceil(log_3(2) + log_3(p)) <= n <= ceil(log_3(p)) + 1

    A te la dimostrazione 😉

  19. joshua said,

    per il quiz delle 9 palline in due pesate:
    3 contro 3 1^pesata
    se =
    2^ delle 3 rimanenti ne contronto 2 e scelgo la meno (o piu`) pesante se il peso ovviamente e` diverso. Se invece anche di queste il peso e` uguale non rimane che la 9.
    se ><
    2^ scelgo 2 delle tre campionate se = sara` la terza diversa, se diverse scelgo la piu pesanto (o leggera).
    ciao

    e se invece le palline fossero 10?quante pesate servirebbero?

  20. raffaele said,

    ma non si può dire semplicemente tipo peso la 1 2 3 4 e dall’altra la 5 6 7 8 e poi …. io ci sto provando da 2 giorni e non ci sono ancora riuscito

  21. alessandro said,

    scusa, sia nel 2 che nel 3 c’è una cosa che non capisco, ovvero “e nel secondo una di G1 e due di G2 (scelgo 2, 3, 6)” sbaglio o in quelle che hai scelto te ce ne sono due di G1 e 1 di G2?


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: