Newsgroup: it.hobby.enigmi
Titolo: Palline


First amendament doesn't cover burping
--------------------------------------------------------

 1 pallina ha peso diverso dalle altre...
Questo problema e' veramente inflazionato (vedei FAQ it.Dewdney),  ma
pochi forse ne conoscono l'origine. E' apparso per la prima volta in
"Scripta Mathematica vol.11 pag 360 1945.
Prendo spunto per proporvi 2 problemi poco noti risolvibili con bilancia
elettronica ad un unico piatto che restituisce il peso esatto. 
-Date 6 palline di cui una di peso differente, individuarla con 3
pesate, naturalmente non conosciamo ne' il peso delle palline regolari,
ne' il peso di quella difettosa. 
-Il passo successivo proposto da Kobon Fujimura (noto problemist
scomparso qualche anno fa) e' veramente difficile da risolvere,
praticamente e' lo stesso problema di prima, con 15 palline una delle
quali di peso differente che deve essere localizzata in 4 pesate.
Esistono molte varianti anche con bilancia a doppio piatto, alcune anche
complicate, se c'e' qualche interessato...
dario

ne' il peso di quella difettosa.
Per comodita' numero le palline da 1 a 6:
peso la 1 e la 2 isieme , e poi la 3 e la 4 insieme; ho due
possibilita' :
1) i due pesi si equivalgono: peso la 5 e se il peso e' meta' delle
rilevazioni precedenti la pallina cercata e' la 6, altrimenti e' la 5.
2) i due pesi sono differenti: peso la 1, la 3 e la 5 insieme: se il
peso e' 3/2 del primo (1+2) allora e' la 4, se e' 3/2 del secondo
(3+4) allora e' la 2, altrimenti considero la differenza tra la terza
rilevazione e la prima ((1+3+5)-(1+2)) se il risultato e' la meta'
della seconda rilevazione (3+4) allora e' la 1 altrimenti e' la 3.
 

quali di peso differente che deve essere localizzata in 4 pesate.
Allora, ci provo.
Peso insieme 1,2,3,4,5,6,7,8 e successivamente 1,2,3,4,9,10,11,12 ; ho
due possibilita' :
1) i due pesi si equivalgono: peso allora insieme 1,2,13,14 : se il
peso rilevato e' la meta' dei precedenti allora la pallina cercata e'
la 15, altrimenti peso insieme 1,3,13 : se il peso e' uguale a  3/4
quello della terza pesata (1+2+13+14) allora e' la 4, se invece e'
uguale a 3/8 quello della prima allora e' la 14, altrimenti opero come
segue: sottraggo al primo e al terzo risultato l'ultimo
((1+2+3+4+5+6+7+8) - (1+3+13)) e ((1+2+13+14) - (1+3+13)) se il numero
che ottengo dalla prima operazione e' cinque volte quella che ottengo
dalla seconda allora la pallina e' la 1, se invece il numero che
ottengo dalla seconda operazione e' 1/8 del peso ottenuto dalla prima
rilevazione (1+2+3+4+5+6+7+8) allora e' la 13, se invece il numero che
ottengo dalla prima operazione e' 5/4 del peso ottenuto dalla terza
rilevazione (1+2+13+14) allora e' la 3, altrimenti e' la 2.
2) i due pesi non si equivalgono: peso allora insieme 5,6,9,10 : se il
peso rilevato e' 1/2 quello della prima pesata (1+2+3+4+5+6+7+8)
allora peso la 11 e se il peso e' uguale 1/8 quello della prima pesata
e' la 12 altrimenti e' la 11; se il peso di 5,6,9,10 e' 1/2 quello
della  della seconda pesata (1+2+3+4+9+10+11+12) allora peso la 7 e se
il peso e' uguale 1/8 quello della seconda pesata e' la 8 altrimenti
e' la 7; se il peso di 5,6,9,10 non rientra nei due casi precedenti
peso allora insieme 5,9: se il peso e' 1/4 quello della prima pesata
allora e' la 10, se e' 1/4 quello della seconda pesata allora e' la 6
altrimenti opero come segue: sottraggo alla terza pesata la quarta
((5,6,9,10) - (5,9)) se il valore ottenuto e' 1/4 quello della prima
pesata allora e' la 9 altrimenti e' la 5.
Spero di non essere stato troppo confusionario (e soprattutto di aver
azzeccato la soluzione)
ciao!!
 

complicate, se c'e' qualche interessato...
Siamo interessati.
ciao
Paolo

Innanzi tutto mi scuso della ritardata risposta, ma ho cambiato computer cosi' sono rimasto fermo 
per qualche giorno.
Allora, bene per le risposte di Paolo e Domenico, pero' devo dirvi che volutamente ho omesso una 
clausola che rende il problema piu' complesso, questo per non farvi desistere subito e prendere un 
po' di confidenza col problema stesso.
Ecco la versione VERA:
Sempre con bilancia elettronica:
"Date 6 palline di cui una di peso differente, determinare con 3 pesate l'esatto peso sia delle 
palline regolari sia della pallina difettosa."
Stesso problema con 15 palline (una delle quali di peso differente) con 4 pesate.
Questo e' VERAMENTE difficile !!
dario

Questo e' VERAMENTE difficile !!
Anche il primo non scherzava mica.
ciao
Paolo

Questo e' VERAMENTE difficile !!
Cercando di risolvere il problema delle 15 palline e 4 pesate, credo di aver
trovato
la dimostrazione che... non esiste soluzione.
Potrei aver preso un abbaglio, quindi aspetto conferma o smentita prima di
inviare tale dimostrazione.
Se non ho capito male, i termini del problema erano:
_15 palline
_4 pesate con bilancia a un piatto
_14 palline uguali
_1 pallina differente
_non conosco i pesi delle paline regolari ne' di quella differente
_non conosco il valore ne' il segno della differenza
_devo individuare la pallina differente, il suo peso e il peso delle altre
14.
ciao
Paolo

 14.
L'enunciato e' esatto, pero' la soluzione esiste, ma come preannunciato
e' estremamente difficile da trovare.
Per non essere accusato di sadismo, do' la parte essenziale della
soluzione lasciando ai piu' volonterosi il compito di verificarne la
validita'.
Chiamiamo le 4 pesate A,B,C,D, e numeriamo le palline da 1 a 15.
Le prime due pesate devono essere:
A =(15,14,13,12,11,10,9,8)
B =(15,14,13,12,7,6,5,4)
PRIMO CASO
A=B allora la differente e' fra le palline pesate 2 volte o quelle
ancora da pesare.
Cioe' (15,14,13,12,1,2,3).
C =(15,14,3,2)
D =(15,13,3,1)
SECONDO CASO
A~B allora la differente e' fra (4,5,6,7,8,9,10,11)
C =(11,10,6,7)
D =(11,9,7,5)
Si potrebbe spingere ancora piu' avanti, qualora p (numero di pesate) e'
maggiore di 3, il numero di palline che possono entrare in gioco e' dato
da 2^p-1. Con 6 pesate ad es. si potra' trovare una pallina differente
fra 63 procedendo con questo stratagemma. Formo 15 gruppi di 4 palline
ciascuno e metto da parte momentaneamente le 3 palline in piu'. Utilizzo
ogni gruppo di 4 come fossero una sola pallina applicando la procedura
appena vista per 15. Una volta determinato il gruppo di 4 con le prime 4
pesate, utilizzo le rimanenti 2 pesate, per isolare quella diversa fra
le 4. Se, invece nelle prime 4 pesate non vi e' alcun scompenso, si
utilizzano le restanti 2 per indagare fra le 3 palline messe
precedentemente in disparte.
dario

da 2^p-1.
Ero arrivato a 2^p-2
vedi per esempio il caso 6 palline 3 pesate, o quello banale 2 palline 2
pesate.
ciao
Paolo

 peso(3)=1005
Ehi!! Mi hai fatto venire un coccolone!
Quando incontrai questo problema diversi anni fa, fui sicuro di averlo
risolto.
Riproponendolo, mi ricordavo la difficolta' incontrata, ma non trovando
piu' la vecchia soluzione, ho provato a ricostruirla. Evidentemente la
memoria mi ha tradito. Data la tua giusta osservazione, ci ho riguardato
penso che cosi' vada bene. Questo conferma la bellezza di questo
problema.
Chiamiamo le 4 pesate A,B,C,D, e numeriamo le palline da 1 a 15.
Le prime due pesate devono essere:
A =(15,14,13,12,11,10,9,8)
B =(15,14,13,12,7,6,5,4)
PRIMO CASO
A=B Allora:
C =(15,14,9,8,3,2)
D =(15,13,3,1)
SECONDO CASO
A differente da B Allora:
C =(14,11,10,7,6,3)
D =(11,9,7,5)
dario


Adesso ci siamo.
Per consolarti del coccolone ti faro' sorbire la mia PSEUDO DIMOSTRAZIONE,
con la quale credevo di aver trovato che il problema era insolubile;
opportunamente adattato il ragionamento dovrebbe invece permettere di
arrivare alla soluzione.
Cominciamo da meta' strada, vediamo cioe' di quali informazioni posso
disporre dopo due pesate, e se queste informazioni sono sufficienti per
trovare la soluzione con le rimanenti due pesate.
Le due pesate A e B dividono le palline in quattro gruppi, che chiamo (come
i gruppi sanguigni) A, B, AB, 0,
Appartengono ai gruppi rispettivamente le palline utilizzate: solo nella
prima pesata, solo nella seconda, in entrambe, in nessuna delle due.
Il gruppo 0 non puo' contenere piu' di tre palline.
Infatti se le palline fossero 4 o piu', e se la pallina diversa fosse una di
esse, e' facile vedere che con le pesate seguenti potrei individuare la
pallina diversa o il suo peso, ma non entrambi gli elementi.
I primi tre gruppi devono quindi contenere almeno 12 palline, e d'altra
parte non possono contenerne piu' di 12, ripartite in numero di quattro per
gruppo.
Se infatti uno dei gruppi ne contenesse cinque o piu', nelle pesate
successive le cinque palline si ripartirebbero tra i gruppi C, D, CD, 00, e
quindi uno dei nuovi gruppi conterra' almeno due palline. Se la pallina
diversa e' una delle due, non potro' determinare quale.
Rimane quindi l'unica possibilita' di quattro palline per ciascun gruppo A,
B, AB, cioe' la tua prima indicazione o una equivalente.
Inizialmente avevo liquidato questa ripartizione proprio pensando alla
possiilita' di ottenere due pesate uguali, ritenevo che in tal caso le
informazioni sarebbero state insufficienti; abbiamo visto infatti che in
quel caso si deve scegliere tra sette palline, senza conoscere ancora il
peso regolare ne' quello differente.
-----------------------------------------------------
A questo punto, restando nel caso A=B, possiamo decidere i criteri per le
pesate C eD:
Le palline 15,14,13,12 (ex gruppo AB) dovranno ripartirsi una per ciascun
gruppo C, D, CD, 00.
Le palline 1, 2, 3 (ex gruppo 0), dovranno ripartirsi una per ciascun gruppo
C, D, CD.
Le due pesate C e D devono interessare un numero diverso di palline.
Quindi dovrebbe andare bene la tua ripartizione:
A =(15,14,13,12,11,10,9,8)
B =(15,14,13,12,7,6,5,4)
C =(15,14,9,8,3,2)
D =(15,13,3,1)
Detto P il peso regolare e Q quello diverso, per trovare la soluzione posso
scrivere 7 sistemi ciascuno di tre equazioni, ipotizzando di volta in volta
che la pallina diversa sia una delle sette indiziate.
Per esempio, supposto che sia diversa la pallina 15:
7*P+Q=A
5*P+Q=B
3*P+Q=C
e cosi via per le altre sei possibilita'.
Tali sistemi di tre equazioni nelle incognite P e Q in genere non ammettono
soluzione.
Se trovo che la soluzione e' possibile in uno e uno solo dei casi, FATTO!
Analogamente se A e' diverso da B.
-------------------------------------------------
Spero di essere satato chiaro almeno un po'. D'altra parte il problema era
piuttosto complicato e la spegazione non puo' essere molto semplice.
Comunque complimenti per il problema, ne aspetto presto di simili (magari
appena appena piu' semplici).
ciao
Paolo

 Paolo
Bene allora proseguiamo la serie di problemi di pesate non banali.
Questa variante e' stata inventata da Dani Ferrari, lo potete incontrare
nella rubrica INTELLIGIOCHI sulla rivista MC microcomputer.
" Date 12 monete d'oro  di cui 0,1,o 2 false percio' piu' leggere,
identificarle in 4 pesate utilizzando una bilancia a doppio piatto." 
dario


Sperando di non aver commesso errori di trascrizione, do una possibile
soluzione
Credo che una breve spiegazione del metodo utilizzato sia piu' interessante
della soluzione stessa.
Inizialmente, per 0,1,2 monete false, esistono rispettivamente 1+12+66=79
possibili combinazioni, cioe' "quasi" 3^4=81.
Ciascuna pesata suddivide le combinazioni in tre gruppi, a seconda che il
peso del primo piatto sia minore, uguale o maggiore di quello del secondo.
Le quattro pesate dovranno ridurre successivamente le combinazioni in gruppi
non superiori rispettivamente a 27,9,3,1.
E' facile vedere che la prima pesata deve necessariamente essere di 4+4
monete, in quanto tutte le altre possibilita' formano almeno un gruppo
superiore a 27 combinazioni.
PRIMA PESATA: (1,2,3,4)-(5,6,7,8)
Sono possibili tre casi:
A):(1,2,3,4)<(5,6,7,8)
Possibilita' di monete false:26
una della prima quaterna(4 possibilita'), due della prima quaterna(6), una
della prima e una della terza(16)
B):(1,2,3,4)=(5,6,7,8)
Possibilita' di monete false:27
Zero(1 possibilita'), una della prima e una della seconda quaterna(16), una
della terza(4), due della terza(6)
C):(1,2,3,4)>(5,6,7,8)
Trascuro lo sviluppo in quanto simmetrico ad A, invertendo la prima e la
seconda quaterna.
.
CASO A
SECONDA PESATA: (1,5,9)-(10,11,12)
A1): (1,5,9)<(10,11,12)
Possibilita' di monete false:(1/1,2/1,3/1,4/1,9/2,9/3,9/4,9)
Terza pesata:(1.2)-(3,9)
A1.1): (1,2)<(3,9)
Possibilita' di monete false:(1/1,2/1,4)
Quarta pesata:(2)-(4)
A1.2): (1,2)=(3,9)
Possibilita' di monete false:(1,3/1,9/2,9)
Quarta pesata:(1)-(9)
A1.3): (1,2)>(3,9)
Possibilita' di monete false:(3,9/4,9)
Quarta pesata:(3)-(4)
A2): (1,5,9)=(10,11,12)
Possibilita' di monete false:(1,10/1,11/1,12/2/3/4/2,3/2,4/3,4)
Terza pesata:(3,10)-(4,11)
A2.1): (3,10)<(4,11)
Possibilita' di monete false:(1,10/2,3/3)
Quarta pesata:(1)-(2)
A2.2): (3,10)=(4,11)
Possibilita' di monete false:(1,12/2/3,4)
Quarta pesata:(1)-(2)
A2.3): (3,10)>(4,11)
Possibilita' di monete false:(1,11/2,4/4)
Quarta pesata:(1)-(2)
A3): (1,5,9)>(10,11,12)
Possibilita' di monete false:(2,10/2,11/2,12/3,10/3,11/3,12/4,10/4,11/4,12)
Terza pesata:(2)-(3)
Quarta pesata:(10)-(11)
CASO B
SECONDA PESATA: (1,3,5,9)-(2,4,6,10)
B1): (1,3,5,9)<(2,4,6,10)
Possibilita' di monete false:(1,5/1,7/1,8/3,5/3,7/3,8/9/9,11/9,12)
Terza pesata:(1)-(3)
B1.1): (1)<(3)
Possibilita' di monete false:(1,5/1,7/1,8)
Quarta pesata:(5)-(7)
B1.2): (1)=(3)
Possibilita' di monete false:(9/9,11/9,12)
Quarta pesata:(11)-(12)
B1.3): (1)>(3)
Possibilita' di monete false:(3,5/3,7/3,8)
Quarta pesata:(5)-(7)
B2): (1,3,5,9)=(2,4,6,10)
Possibilita' di monete false:(1,6/3,6/2,5/4,5/9,10/11/12/11,12/0)
Terza pesata:(6,11)-(5,12)
B2.1): (6,11)<(5,12)
Possibilita' di monete false:(1,6/3,6/11)
Quarta pesata:(1)-(3)
B2.2): (6,11)=(5,12)
Possibilita' di monete false:(9,10/11,12/0)
Quarta pesata:(9)-(11)
B2.3): (6,11)>(5,12)
Possibilita' di monete false:(2,5/4,5/12)
Quarta pesata:(2)-(4)
B3): (1,3,5,9)>( 2,4,6,10)
Trascuro lo sviluppo in quanto simmetrico a B1
ciao
Paolo

 soluzione....
Sapevo che l'avresti risolto brillantemente. Bello vero !?

Ciao,  a me l'hanno proposto con 12 palline e tre pesate, e non sono
riuscito a risolverlo...
Sapete dirmi qualcosa...
Ciao a tutti.
Paolo FERRARESI (
fp...@tin.it
).

...

 Numeriamo le palline da 1 a 12
 abbiamo 24 possibilità 1+  1-  2+  2-  3+  3-  ecc. ecc.
1a pesata  palline n.1 2 3 4 sul primo piatto 5 6 7 8 sul secondo piatto
ci sono tre possibilità
A) scende il piatto di sinistra: avremo otto possibili risultati
     1+  2+  3+  4+  5-  6-  7-  8- ( 9  10  11  12 sono regolari)
B) scende il piatto di destra  avremo: otto possibili risultati
     1-  2-   3-  4-  5+  6+  7+  8+ (9  10  11  12 sono regolari)
C) i piatti restano in equilibrio: avremo otto possibili risultati
     9+  9-  10+  10-  11+  11-  12+  12-  (1 2 3 4 5 6 7 8  sono regolari)
sviluppiamo il caso C - (il più facile)
2a pesata - 9  10 sul primo piatto 11 e  1(che sappiamo regolare) sul
secondo piatto
ci sono tre possibilità
C-A) scende il piatto di sinistra: avremo tre possibilità  9+  10+  11- (la
1 sappiamo                 regolare).
C-B) scende il piatto di destra:  avremo tre possibilità  9-  10-  11+ (la
1 sappiamo         
        regolare)
C-C) i piatti restano in equilibrio: avremo 2 possibilità  12+   12- (9  10
 11 regolari)
 
nel caso C-A e C-B  la terza pesata Sara:
primo piatto 9 - secondo piatto 10  ed a secondo dei casi avremo un unica
risposta
considerando che in caso di equilibrio sarà la 11 quella diversa e nella
maniera già 
determinata nella 2a pesata.
nel caso C-B peseremo la 12  contrapposta alla 1 (regolare) ottenendo o 12+
 o 12-
sviluppiamo il caso 1a pesata A (la prima pesata B è simmetrica)
avevamo  otto possibilità  1+  2+  3+  4+  5-  6-  7-  8- (9 10 11 12
regolari)
primo piatto 1+  2+   5-   secondo piatto 3+   6-  11reg   avremo tre
possibilità
A-A ) scende il piatto di sinistra: avremo tre possibilità. 1+  2+  6- (3 4
5 7 8 regol.)
A-B) scende il piatto di destra:    avremo due possibilità  5-  3+ (le
altre regol)
A-C) rimane in equilibrio :            avremo tre possibilità   4+  7-  8- 
(1 2 3 5 6 regol.)
in tutte e tre i casi la terza pesata e ovvia.
 
Mi rendo conto che forse non sono stato abbastanza chiaro, ma garantisco
che il 
problema è risolvibile sfruttando  i risultati di equilibrio e la
conoscenza dalle pesate
precedenti delle palline regolari.
ciao   Dario