Newsgroup: it.hobby.enigmi
Titolo: Palline e bilancie

Giochi di questo tio sono piuttosto frequenti, ma QUESTO gioco specifico
per me era una novita', fino a quando non e' stato postato sul forum di
intelligiochi.com
 da Haran. Io mi limito a proporvelo:
Allora... 10 scatole identiche, 10000 palline per scatola, una bilancia
elettronica perfetta. 4 scatole contengono solo palline da 9 grammi, le
altre 6 contengono solo palline da 10 grammi. Le palline, a parte
eventualmente il peso, sono fra loro indistinguibili. Come si possono
individuare le 4 scatole contenenti palline da 9 grammi con una sola
pesata ed usando il minor numero di palline possibile?
Da notare che il gioco e' facilmente risolvibile con il metodo della
forza bruta. Ma da voi mi aspetto una soluzione piu' elegante, sulla
base di ragionamenti.
Ciao :)
--AG

Armando Grimaldi wrote:

Non so se questa si puo' chiamare forza bruta, ma mi sembra ceh funzioni...
-
.
.
S
P
O
I
L
E
R
.
.
-
Numero le 10 scatole da 0 a 9 e prendo 2^n palline dal ciascuna scatola n.
Le metto tutte sulla bilancia e leggo il peso in grammi.
Sottraggo il peso da 10230 e scrivo il risultato in binario. Le posizioni degli 
1 indicano le scatole incriminate.
Probabilmente c'e' il modo di usare un numero di palline minore di 1023...
Dade :)


Dunque:
1. Il tuo metodo e' CERTAMENTE funzionante, cioe' la soluzione e' valida.
2. Non e' pero' la soluzione che impiega il minor numero possibile di palline.
3. Il tuo metodo, anche se applicato meglio, non consente di arrivare alla
soluzione minima
4. E' possibile, pero', ottenere utilizzando il tuo algoritmo una soluzione
migliore (anche se non LA migliore).
Ciao!
--AG

 migliore (anche se non LA migliore).
Ripensandoci, il mio metodo e' il migliore nel caso in cui non si conosca quante 
sono le scatole contenenti palline da 9 g.
Tornando al problema con 4 scatole leggere:
Per ridurre il numero di palline da 1023 a 511 basta mettere da parte una 
scatola a caso e procedere come ho gia' detto con 9 scatole. Alla fine trovero' 
o 4 scatole diverse tra le 9 scelte, oppure 3. Nel primo caso ho finito; nel 
secondo caso anche la scatola messa da parte contiene palline da 9 g.
Immagino, pero', che la tua procedura sia ancora piu' efficiente...
Dade :)

 secondo caso anche la scatola messa da parte contiene palline da 9 g.
OK, siamo riusciti ad arrivare ad uno dei punti importanti del problema. Ossia, che
se una certa sequenza che parte da 1 e' valida, allora e' valida anche la stessa
sequenza, ma partendo da zero.
Questa e' la prima intuizione del problema. Adesso vediamo di arrivare alla seconda.
Si tratta di capire che questo problema si "riduce" (si fa per dire) ad un altro
tipo di problema... Questo fatto puo' (forse) semplificare la ricerca della
soluzione; sicuramente semplifichera' l'esposizione.
Ciao.

 pesata ed usando il minor numero di palline possibile?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Il problema si riduce a trovare i più piccoli 10 numeri positivi (incluso
eventualmente lo 0) che presi in tutti i modi possibili a gruppi di 4 diano
sempre somme diverse.
Non ho usato la forza bruta, però ho usato Excel (forza semi-bruta? :-) ) e
ho trovato questi valori:
0, 1, 2, 4, 7, 13, 24, 44, 84, 161. Se non ho sbagliato i conti, queste sono
le palline che devo prelevare dalle rispettive scatole, in totale 340.
Tornando al nostro problema, prendo 0 palline dalla prima scatola, 1 dalla
seconda, ... 161 dalla decima e le metto sulla bilancia. Una volta ottenuto
il peso, lo sottraggo al numero 3400 (il peso che avrei se fossero tutte da
10 grammi). Il numero ottenuto rappresenta quante palline da 9 grammi ci
sono nella pesata. Non rimane che trovare i 4 numeri, tra quelli riportati,
che sommati insieme diano il numero ottenuto e quindi risalire alle scatole
di provenienza.
Ciao :-)
Giorgio

 Non ho usato la forza bruta, perň ho usato Excel (forza semi-bruta? :-) )
Direi di si'. Il risultato che hai dato non e' stato ottenuto da un
ragionamento, ma da una procedura automatica, per cui non lo commento... :)
Ciao
--AG

 sempre somme diverse.
Non credo ci siano modi diretti per trovare queste sequenze.
Sono una generalizzazione dei gia' trattati RCP.
Un sequenza e' detta si Sidon o B2  se tutte le somme degli
elementi presi a due a due sono differenti.
In questo caso si cerca una Sequenza B4 di 10 elementi. Ci
sono molte pubblicazioni al riguardo.
Mi sembra piu' interessante il caso in cui nessuna, alcune o
tutte le scatole possono contenere palline piu' leggere.
Martin Gardner in Science Fiction Puzzle Tales chiede al
farmacista di individuare con una sola pesata gli eventuali
flaconi fra 6, contenenti pillole difettose piu' leggere di
1g.  Dice naturalmente che sarebbe semplice prendendo da
ciascun flacone una diversa potenza di 2, ma i flaconi non
contengono piu' di 25 pillole ciascuno. Come fare?
Qui ci viene in aiuto la sequenza di Conway-Guy
0,1,2,4,7,13,24,44,84,161,309... vedi Sloane num.1075.
Come si ricavano questi numeri ? 
Scrivo prima i naturali n, che che individuano la posizione
degli elementi A_n.  
Sotto a ciascun numero metto r= [sqrt(2n)] che e' l'intero
piu' vicino alla radice quadrata di 2n. Ottenendo:
n)  0  1  2  3  4  5  6  7  8  9  10  11  12  ....
r)  0  1  2  2  3  3  3  4  4  4   4   5   5  ....
A questo punto ricavo la sequenza mettendo A_0=0,  A_1=1,
A_(n+1)=2A_n-A_(n-r). 
n)    0  1  2  3  4  5  6  7  8  9  10  11  12  ....
r)    0  1  2  2  3  3  3  4  4  4   4   5   5  ....
A_n)  0  1  2  4  7 13
In pratica per continuare faccio 2x13= 26 a cui devo
sottrarre A_(n-r)= A_2 = 2.  26-2=24.
Ancora 24x2=48.  A_(7-4)=4.  48-4=44.... ecc.
Ora per ricavare x numeri con subsomme tutte differenti, mi
basta sottrarre da A_x tutti i valori precedenti.
In questo caso sottraendo 0,1,2,4,7,13 da 24 ottengo
rispettivamente 24,23,22,20,17,11 che danno la risposta
cercata.
Questa di Conway-Guy e' solo una congettura, che e' stata
verificata da F.Lunnon per A_n <=79.   
:) dario


In realtà ho usato Excel solo come supporto per i calcoli, in modo da
limitare al minimo la possibilità di errori. Il mio metodo è stato questo:
partendo dai numeri 0, 1, 2, ho verificato che ogni nuovo numero da
aggiungere avesse la caratteristica di non formare con i numeri già presenti
somme ottenibili in altro modo per gruppi di 2 o 3 o 4. Per esempio il
numero 3 va scartato perché posso ottenere 3 sia sommando 3 e 0 che sommando
1 e 2. Andando avanti, una volta trovati i numeri 0, 1, 2, 4, 7, scarto il
12 perché 12+1+0 = 7+4+1 e così via. Considero i gruppi di 2 perché, se ad
esempio sto testando l'ottavo numero, potrei avere un'ambiguità di somma
composta dal nono, dal decimo e da due diversi gruppi di 2 scelti tra i
primi 8 numeri. Discorso simile per i gruppi di 3.
Mi rendo conto che non è facilissimo da spiegare, ma questo è il
ragionamento che ho seguito. Excel mi ha solo aiutato nelle verifiche.
Ho visto nel frattempo il post di Dario, che ancora una volta ci fa notare
che la maggior parte delle cose che faticosamente cerchiamo di ricavare sono
già state studiate e sviscerate da altri! :-)))))
Trovo molto bello il metodo per ricavare la sequenza in questione, che fa
uso di radici quadrate!!!! :-)
Ciao :-)
Giorgio

 ragionamento, ma da una procedura automatica, per cui non
lo commento... :)
Beh! A me sembra che la soluzione sia frutto di un
ragionamento. Non mi sembra rilevante che poi, per evitare un
lungo lavoro manuale, si siano utilizzate delle facilitazioni
consentite dalla moderna tecnologia.
Ciao
Gianni
--
Io voto Berlusconi perchè credo alla Befana


Il problema era che era stata data solo la soluzione, non il
ragionamento. Quindi avevo assunto che essa era stata ricavata
utilizzando le potenzialita' di calcolo di Excell, e non tramite
ragionamento.
--AG