Gara a squadre Bocconi

[polarized]

Esercizio 19:
Qual è il minor numero di confronti, a due a due, con una bilancia a due piatti, necessari per trovare i due oggetti più pesanti tra 128 assegnati, tutti di peso diverso?

[matematto]

Instintivamente direi

Testo nascosto:

[tex]133[/tex]

[polarized]

Esatto, puoi spiegami brevemente il metodo?

[matematto]

Ecco, non è molto ordinata.. Se non è chiaro qualcosa chiedi pure

Testo nascosto:

Prima di tutto effettui $64$ pesate tutte con oggetti diversi e così avrai $2$ gruppi di oggetti (i $64$ più pesanti che chiamiamo $A$ e i $64$ più leggeri)
Ora effettui altre $32$ pesate tra tutti gli oggetti in $A$ , e così via quindi poi $16$, poi $8$, poi $4$, poi $2$. Così avremo due oggetti tra cui è compreso l'oggetto più pesante, con $1$ pesata sapremo qual'è il più pesante che chiamiamo $K$, mentre non siamo sicuri che l'altro, che chiamiamo $H$, sia il secondo per peso, perché dobbiamo confrontarlo con tutti gli altri oggetti che abbiamo "eliminato" a causa di $K$. Quindi effettui $1$ pesata tra $H$ e l'oggetto che era stato pesato con $K$ all'ultimo turno e il più pesante di questi due verrà pesato con il penultimo e così via, quello che sarà il più pesante all'ultimo turno sarà il secondo più pesante. Quindi abbiamo fatto $64+32+16+8+4+2+1+1+1+1+1+1+1=133$ pesate.