Newsgroup: it.hobby.enigmi
Titolo: Soluzione delle 12 palline IN ITALIANO

Determinare fra N monete quale ha un peso differente con W pesate
usando una bilancia a due piatti.
Il problema è risolvibile solo se N<=(3^W-3)/2.
Esempio:
Determinare fra 12 monete quale ha un peso differente con 3 pesate.
Il problema è risolvibile in quanto 12=(3^3-3)/2.
SOLUZIONE
--- Scrivere tutte le possibili stringhe di lunghezza W utilizzando i
simboli '1', '2', '3'. Le stringhe dovranno essere 3^W.
Esempio:
 000   002   112   012
 001   020   121   021
 010   022   122   102
 011   200   211   120
 100   202   212   201
 101   220   221   210
 110   222
 111
--- Eliminare le stringhe che contengono lo stesso simbolo ripetuto
W volte.
Esempio:
 XXX   002   112   012
 001   020   121   021
 010   022   122   102
 011   200   211   120
 100   202   212   201
 101   220   221   210
 110   XXX
 XXX
--- Individuare in ogni stringa,a partire da sinistra,la prima coppia
di simboli non uguali tra di loro. Se la coppia non e' 01, 12, 20
(in questo ordine) cancellare la stringa. A questo punto devono rimanere
(3^W-3)/2 stringhe. Questo numero rappresenta il numero di monete
da usare nelle W pesate. Ogni stringa rimasta rappresenta una moneta.
Esempio:
 xxx   XXX   112   012
 001   XXX   121   XXX
 010   XXX   122   XXX
 011   200   XXX   120
 XXX   202   XXX   201
 XXX   220   XXX   XXX
 XXX   xxx
 xxx
--- Eseguire le pesate come segue:
    Per la pesata K-esima mettere su un piatto le monete che hanno
    uno 0 nella K-esima posizione e sull'altro piatto le monete che
    hanno un 2 nella K-esima posizione.
    Se il piatto con le monete 0 va giu' (e' piu' pesante) scrivere
    uno 0, se va giu' l'altro piatto scrivere un 2. Altrimenti
    scrivere 1.
    Dopo W pesate ho scritto una stringa di W simboli. Se questa
    stringa compare fra quelle delle monete, allora la rispettiva
    moneta e' quella di peso differente, ed e' piu' pesante.
    Se la stringa non compare, sostituire in essa ogni 0 con un 2
    e ogni 2 con uno 0. La moneta corrispondente alla nuova stringa
    e' quella di peso differente, ed e' piu' leggera.
Esempio:
  001 moneta A
  010        B
  011        C
  012        D
  200        E
  202        F
  220        G
  201        H
  112        I
  121        L
  122        M
  120        N
  La prima pesata avviene tra le monete A,B,C,D e le monete E,F,G,H.
  Supponiamo che sia piu' pesante il primo piatto, scrivo 0.
  La seconda pesata avviene tra le monete A,E,F,H e le monete G,L,M,N.
  Supponiamo che la bilancia rimanga in equilibrio (i piatti pesano
  uguale), scrivo 1.
  La terza pesata avviene tra le monete B,E,G,N e le monete D,F,I,M.
  Supponiamo che sia piu' pesante il secondo piatto, scrivo 2.
  La stringa che ottengo e' 012, quindi la moneta di peso diverso e' la
  moneta D, che e' piu' pesante.
NOTA 1
Se bisogna identificare solo quale e' la moneta di peso differente
senza determinare se e' piu' pesante o piu' leggera, allora il problema
e' risolvibile anche considerando (3^W-3)/2+1 monete.
Chiamare la moneta aggiuntiva con una stringa di tutti '1' e usare
lo stesso metodo sopra descritto.
NOTA 2
Posso considerare (3^W-3)/2+1 monete anche se oltre a queste ne ho una
che so avere il peso corretto.
Chiamare la moneta aggiuntiva con una stringa di tutti '2' e usare
lo stesso metodo sopra descritto con un piccolo cambiamento.
Nel piatto delle monete 2 ci sara' sempre una moneta in piu'
(la moneta aggiuntiva con tutti 2), nell'altro piatto aggiungere
la moneta di peso corretto.
NOTA 3
Se dall'inizio so che la moneta e' piu' pesante (o piu' leggera) posso
condiderare 3^W monete.
In questo caso dividere le monete in tre gruppi dello stesso
numero di monete: G1, G2, G3.
Pesare il gruppo G1 con il gruppo G2. Il gruppo piu' pesante (o piu'
leggero) contiene la moneta di peso differente. Se i due gruppi pesano
uguale la moneta di peso differente e' nel gruppo G3.
Ripetere l'operazione con il gruppo rimasto fino a quando i tre gruppi
saranno formati da una sola moneta.

 condiderare 3^W monete.
...
Mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm ... trovare quella diversa conoscendo se
essa e' piu' pesante o piu' leggera delle altre non mi sembra troppo
difficile! Tuttavia mi sembra che nel quesito di partenza si fosse detto che
si sapeva solamente che una moneta aveva peso DIVERSO dalle altre! In questo
caso secondo voi e' risolvibile il problema?
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/
       Search, Read, Discuss, or Start Your Own    

...
