Problema dei pesi di Bachet
# 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

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?"

## 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 $\log _{2}N$ 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ù $\log _{3}N$ pesi, ovvero un numero minore.

