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 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
Analisi del problema 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
Collegamenti esterni Biografia di Claude-Gaspard Bachet de Méziriac in MacTutor.
Categoria:Aritmetica