Olimpo Informatico

chegue17 · Eroe Registrato: 05/02/06 16:29 Messaggi: 73

Ragazzi, vi giro un quesito che mi hanno posto una settimana fa , e che ancora non sono riuscito a risolvere.
Le cose stanno più o meno così:

Abbiamo un oggetto, che per semplificare chiamerò "UnOggetto" ( Razz

) , che pesa N (appartenente agli interi) con 0<N<=240 unità di misura
(cioè per fare un esempio, il peso di "UnOggetto" può essere 1, o 7, o 13,..., o 239, o 240), ma non conosciamo con esattezza questo peso.
Abbiamo anche a disposizione una di quei vecchi bilanceri, o bilance a due braccia, quelle, per intendersi, sulle quali metti una cosa da una parte, una cosa dall'altra, e vedi se stanno in equilibrio.. insomma, quella cosa che ha la Giustizia in mano in tutte le raffigurazioni.. no, non la spada.. l'altra mano...
Comunque.. noi abbiamo questo "UnOggetto" da pesare quindi, e dobbiamo andare dal ferramenta a comprare i pesini di piombo con i quali pesare il nostro "unOggetto". Il problema è che abbiamo abbastanza soldi per poter comprare solo cinque pesini, non di più, del peso che preferiamo però. La domanda è:
di che pesi devo comprare i 5 pesini, per essere sicuro di poter stabilire con certezza il peso di "UnOggetto", una volta tornato a casa?

ulisse · Inviato: 19 Mar 2006 08:13 Oggetto: Re: 240 grammi

chegue17 · Eroe Registrato: 05/02/06 16:29 Messaggi: 73

è vero, ma io credo che il problema sta proprio lì: non importa riuscire a far stare la bilancia in equilibrio, cioè PESARE in maniera corretta quella quantità: basta determinarla..

ulisse · Inviato: 19 Mar 2006 17:04 Oggetto:

Ehm... ammetto di non averci pensato!
Ma così si passa da 40 possibili misure a 79 in quanto per determinare un peso con maggiorazioni e minorazioni, tra due misure rilevabili direttamente ce ne può essere al massimo una rievabile indirettamente (se sai che il peso è superiore a 6 e inferiore a 9 potrebbe essere tanto 7 quanto 8) ...

Per arrivare a 240 misure ne mancano ancora un bel po'!
E a me manca un bel po' per arrivare alla soluzione! Very Happy

chegue17 · Eroe Registrato: 05/02/06 16:29 Messaggi: 73

lol.. anche a me.. ci ho pensato e ripensato.. probabilmente c'è qualcosa che ci sfugge...
o semplicemente c'è una fregatura.. (tipo mi è venuta in mente che possono essere anche 2 i valori compresi tra altri due conosciuti.. basta vedere prima con un peso poi con l'altro quanto va velocemente la bilancia verso una parte o l'altra.. ma non mi sembra che così sia un vero indovinello matematico.. dopo tutto l'ha proposto un prof. universitario parigino di matematica..)
Forza, forza

ulisse · Inviato: 19 Mar 2006 18:03 Oggetto:

chegue17 · Eroe Registrato: 05/02/06 16:29 Messaggi: 73

ECCOMI!!!
dopo più di una settimana di silenzio stampa ecco la rettifica:
i pesi utilizzabili non sono quattro, ma cinque.
poi per il resto è tutto come prima. (e NB il peso può essere da 1 a 240 , non solo fino a 40..)

spero che adesso le ipotesi siano giuste..
Bene.. detto questo mi metto anche io a cercare di sciogliere il mistero.,.
a dopo Razz

BonzoGonzo · Inviato: 24 Mar 2006 15:33 Oggetto: Con 1< x < 40, si può

Leonardo · Mortale devoto Registrato: 15/11/05 11:25 Messaggi: 12

ulisse · Inviato: 24 Mar 2006 20:19 Oggetto:

@ BonzoGonzo: Ciao e benvenuto tra noi!
Non ti scusare per non aver occultato la tua risposta: capita a tutti la prima volta che capitano qui!

@Leonardo: per ora non posso dirti nulla perché voglio prima provare a pensarci da solo. Appena ho trovato la soluzione o ho rinunciato a cercarla leggerò la tua risposta!

Ciao

Eugy · Eroe Registrato: 15/01/06 01:27 Messaggi: 65

Io invece la risposta di leonardo l'ho letta, perchè effettivamente non mi veniva in mente il TRUCCO !

Leggendo la sua risposta l'ho capito al volo:

Leonardo · Mortale devoto Registrato: 15/11/05 11:25 Messaggi: 12

Sì, non sono stato precisissimo ma mi pareva ovvio che se ho i pesi 1 e 3, (e mi fermo qui), per ottenere il 2 devo mettere il 3 da una parte e l'1 dall'altra.

Eugy · Eroe Registrato: 15/01/06 01:27 Messaggi: 65

Eureka · Mortale devoto Registrato: 30/03/06 17:08 Messaggi: 19

Buonasera a tutti
ho riflettuto al problema e ho scritto un algoritmo per calcolare la soluzione...
bhe il mio risultato anzi risultati sono i seguenti pesi (3 soluzioni):
a=1,1,1
b=3,3,3
c=9,9,9
d=26,28,27
nel caso in cui 0<N<=40
al momento non ho la soluzione completa in quanto il pc sta ancora lavorando...
cmq l'equazione che ho utilizzato è del tipo:
a*a°+b*b°+c*c°+d*d°=N che deve essere soddisfatta per N-1 volte
dove i coefficienti a°,b°,c°,d° possono assumere i valori -1,0,1

ulisse · Inviato: 30 Mar 2006 17:49 Oggetto:

Finalmente ho trovato il tempo per fare un po' di conti...

Ho dunque potuto permettermi di leggere i vari post "spoilerati".
Che casino ho combinato!
Devo mettermi in testa che essere mod non significa poter "pasticciare" i topic soprattutto se frettolosamente e che essere matematico non significa avere sempre la verità in tasca.

E' vero che nella sua formulazione originale (4 pesi ; 240 grammi)
il problema conteneva un errore ma è altrettanto vero che nella mia presunzione ho erroneamente concluso che nemmeno la coppia (5 pesi ; 240 grammi) poteva funzionare e che quindi l'unica formulazione corretta del problema era (4 pesi; 40 grammi)...

ulisse · Inviato: 30 Mar 2006 18:07 Oggetto:

Eureka · Mortale devoto Registrato: 30/03/06 17:08 Messaggi: 19

infatti avevo scritto:
l'equazione:
a*a°+b*b°+c*c°+d*d°=N deve essere soddisfatta per N-1 volte
(forse era meglio se scrivevo per almeno N-1 volte)

quando dicevo N-1 volte intendevo proprio quello perche c'è un ultreriore informazione 0<N<=40

quindi se non trovo il peso con quelle 2 quaterne la soluzione è ovvia ed è quella che non posso calcolare Wink

ulisse · Inviato: 30 Mar 2006 23:38 Oggetto:

Caro Eureka, innanzi tutto: benvenuto!
Forse c'è stato un fraintendimento.
Nel mio post precedente la parte rivolta a te era la prima:

ulisse · Inviato: 30 Mar 2006 23:49 Oggetto:

Dopo aver provocato l'ennesimo casotto, vediamo se riesco a ridare un po' di smalto alla mia immagine.

Ci provo con una dimostrazione costruttiva di esistenza e unicità della soluzione. (per i profani: dimostrazione costruttiva significa che oltre a dimostrare che la soluzione c'è ed è unica, fornisce anche un procedimento per individuarla).

Ecco cosa ho partorito.

Innanzi tutto devo dare dei nomi.
Sia n il numero di pesini.
I pesini li indico con i numeri da 1 a n.
Il peso dell'i-esimo pesino lo chiamo x_i.
Dunque x_1 sarà il peso del primo pesino e x_n quello dell'ultimo.
Senza perdere in generalità possiamo supporre x_1 < x_2 < ... < x_n.

Infine chiamo S_n = SUM(i = 1 to n)(x_i) la somma dei pesi di tutti i pesini.

E' evidente che il massimo peso che i miei n pesini saranno in grado di misurare coincide con S_n.

Costruiamo la n-pla (x_1,...,x_n) e dimostriamo che è unica ragionando per induzione.

Supponiamo di aver trovato n-1 pesini in grado di misurare tutti i pesi interi da 1 a S_(n-1).
Questo implica che un nuovo pesino dovrà pesare più della somma dei precedenti (perché altrimenti il suo peso potrebbe essere misurato in due modi differenti) cioé deve essere S_(n-1) < x_n.

Allora, aggiungendo un pesino di peso x_n, potremo certamente misurare tutti i pesi compresi tra x_n - S_(n-1) e x_n + S_(n-1).
Poiché tra S_(n-1) ed S_n non posso avere pesi non misurabili dovrà essere:
x_n - S_(n-1) = S_(n-1) + 1
e
x_n = S_n - S_(n-1)

Abbiamo quindi il seguente sistema
x_n = 2S_(n-1) + 1
x_n = S_n - S_(n-1)

dal quale si ricava l'equazione ricorsiva:
S_n = 3S_(n-1) + 1

la cui unica soluzione è:
S_n = SUM(i = 0 to n-1)(3^i)

Facendo la differenza tra due termini consecutivi essa ci fornisce anche la n-upla di pesi, infatti:
x_n = S_n - S_(n-1) = 3^(n-1)

In pratica l'unica n-upla di pesini che garantisce la possibilità di misurare tutti i pesi da 1 a S_n è (1,3,9,27,81,...,3^(n-1)) cioè è costituita da tutte le prime n potenze di 3.

Poiché per n = 5 ricaviamo S_5 = 121, sfruttando lo stratagemma suggerito da Cheque, raccolto da Leonardo e approvato da Eugy, con la 5-upla (2,6,18,54,162) ottenuta raddoppiando i pesi dei pesini riusciamo a misurare esattamente tutti i pesi pari da 2 a 242 e a determinare, con una pesata per eccesso e una per difetto, anche tutti i pesi dispari da 1 a 241.

Poiché la dimostrazione per induzione che ho ricavato mi fa gonfiare le piume come un piccione che tuba ritengo pagata la mia ammenda e mi permetto di fare lo smargiasso rilanciando:
Supponiamo che il peso di UnOggetto sia 45.
Qual è il numero minimo di pesate atte a determinarne il peso?

E se il peso di UnOggetto è x, sapete scrivere la formula che individua il numero minimo di pesate in funzione di x ? 8)

Eureka · Mortale devoto Registrato: 30/03/06 17:08 Messaggi: 19

grazie del benvenuto
allora vediamo se riesco ad essere + chiaro
Ritornando al problema sappiamo che dobbiamo pesare "un oggetto" il cui peso, appartenente all'insieme dei numeri interi, è maggiore di zero e minore di 40 ora delle 3 soluzioni che ho presentato 2 non potevano calcolare un numero in particolare come hai detto te:

Con la quaterna 1,3,9,26 non è possibile ottenere il numero 40.
Con la quaterna 1,3,9,28 non è possibile ottenere il numero 14.

bene, nel caso in cui dopo le varie pesate non riesca a determinare il peso dell'oggetto N, N dovrà pesare il peso che non posso pesare (scusate il gioco di parole Razz

)
es:
pensiamo di avere la quaterna 1,3,9,26 le soluzioni sono due o troviamo il peso di N oppure non lo troviamo e se non lo troviamo allora è 40 (questa quaterna soddisfa l'equazione sopra proposta N-1 volte)