Olimpo Informatico

[Eugy]

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]

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]

[Eureka]

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]

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]

[Eureka]

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

[ulisse]

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

[ulisse]

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]

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 )
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)

[ulisse]

Eh già...
Si. Quello che dici è corretto.
Prima non avevo capito.

Diciamo che la tua è una soluzione "ibrida" nel senso che è un misto tra quella pura che consente di misurare tutti i valori da 1 a 40 senza fare misure indirette e quella che fa uso dello "stratagemma" in maniera ottimale (consentendo di raddoppiare il range dei pesi misurando esattamente i pesi pari e deducendo per minorazione e maggiorazione quelli dispari).

e...

... resta con noi!