Problema dei pesi di Bachet
Il problema dei pesi di Bachet è un problema formulato da Claude-Gaspard Bachet de Méziriac inerente alla scomposizione dei numeri interi positivi minori di N in somme algebriche di altri numeri interi dello stesso intervallo.
Il quesito[modifica | modifica wikitesto]
Il quesito inerente può essere così sintetizzato:
- "Di quanti e quali pesi unitari distinti ha necessariamente bisogno un gioielliere per pesare sequenzialmente degli oggetti che vanno da 1 a N chilogrammi con una bilancia a due piatti?"
Origini del quesito[modifica | modifica wikitesto]
Analisi del problema[modifica | modifica wikitesto]
Per risolvere il quesito possiamo utilizzare un metodo forza-bruta o un metodo induttivo, enumerando i pesi necessari per piccoli valori di N, tentando di generalizzare il problema.
Per N = 10
| Intero | Scomposizione |
|---|---|
| 1 kg | Peso necessario |
| 2 kg | Peso necessario |
| 3 kg | Ottenibile tramite 2 kg + 1 kg |
| 4 kg | Peso necessario |
| 5 kg | Ottenibile tramite 4 kg + 1 kg |
| 6 kg | Ottenibile tramite 4 kg + 2 kg |
| 7 kg | Ottenibile tramite 4 kg + 2 kg + 1 kg |
| 8 kg | Peso necessario |
| 9 kg | Ottenibile tramite 8 kg + 1 kg |
| 10 kg | <Ottenibile tramite 8 kg + 2 kg |
Da ciò si denota come per potere pesare in una bilancia a due piatti un intero N siano al massimo necessari pesi (arrotondato all'intero superiore).
Questa tuttavia non è la soluzione ottimale. Se ipotizziamo di potere inserire pesi anche nel secondo piatto (e di conseguenza potere effettuare sottrazioni), il numero di pesi necessari nel caso peggiore diminuisce.
Per N = 10
| Intero | Scomposizione |
|---|---|
| 1 kg | Peso necessario |
| 2 kg | Ottenibile tramite 3 kg - 1 kg |
| 3 kg | Peso necessario |
| 4 kg | Ottenibile tramite 3 kg + 1 kg |
| 5 kg | Ottenibile tramite 9 kg - 3 kg - 1 kg |
| 6 kg | Ottenibile tramite 9 kg - 3 kg |
| 7 kg | Ottenibile tramite 9 kg - 3 kg + 1 kg |
| 8 kg | Ottenibile tramite 9 kg - 1 kg |
| 9 kg | Peso necessario |
| 10 kg | Ottenibile tramite 9 kg + 1 kg |
In questo caso servono al più pesi, ovvero un numero minore.
Bibliografia[modifica | modifica wikitesto]
- (EN) Edwin O'Shea, Bachet's Problem: as few weights to weigh them all, in ArXiv, ottobre 2010. URL consultato il 6 novembre 2012.
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) Biografia di Claude-Gaspard Bachet de Méziriac in MacTutor.
