title: Problema dei pesi di Bachet
text: # 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.
  
  