Problema greutăților lui Bachet

Problema greutăților lui Bachet este o problemă formulată de Claude-Gaspard Bachet de Méziriac referitoare la descompunerea numerelor întregi pozitive mai mici de N în sume algebrice ale altor numere întregi din același interval.

Intrebarea

Întrebarea inerentă poate fi rezumată după cum urmează:

"De câte și ce greutăți distincte are nevoie un bijutier pentru a cântări în mod secvențial obiecte cuprinse între 1 și N kilograme cu o cântare cu două panuri?"

Originea întrebării

Analiza problemelor

Pentru a rezolva întrebarea putem folosi o metodă cu forță brută sau o metodă inductivă, enumerând greutățile necesare pentru valorile mici ale lui N , încercând să generalizăm problema.

Pentru N = 10

Întreg	Dărâma
1 kg	Greutatea necesară
2 kg	Greutatea necesară
3 kg	Se poate obține prin 2 kg + 1 kg
4 kg	Greutatea necesară
5 kg	Se poate obține cu 4 kg + 1 kg
6 kg	Se poate obține cu 4 kg + 2 kg
7 kg	Se poate obține prin 4 kg + 2 kg + 1 kg
8 kg	Greutatea necesară
9 kg	Se poate obține prin 8 kg + 1 kg
10 kg	<Se poate obține cu 8 kg + 2 kg

Din aceasta se indică modul în care se poate cântări un număr întreg N într-o scală cu două panuri este cel mult necesar $\log _{2}N$ ${\ displaystyle \ log _ {2} N}$ ${\ displaystyle \ log _ {2} N}$ greutăți (rotunjite la cel mai apropiat număr întreg).

Cu toate acestea, aceasta nu este soluția optimă. Dacă presupunem că putem introduce și greutăți în a doua placă (și, prin urmare, putem să scădem), numărul greutăților necesare în cel mai rău caz scade.

Pentru N = 10

Întreg	Dărâma
1 kg	Greutatea necesară
2 kg	Se poate obține prin 3 kg - 1 kg
3 kg	Greutatea necesară
4 kg	Se poate obține prin 3 kg + 1 kg
5 kg	Se poate obține prin 9 kg - 3 kg - 1 kg
6 kg	Se poate obține prin 9 kg - 3 kg
7 kg	Se poate obține prin 9 kg - 3 kg + 1 kg
8 kg	Se poate obține prin 9 kg - 1 kg
9 kg	Greutatea necesară
10 kg	Se poate obține prin 9 kg + 1 kg

În acest caz servesc cel mai mult $\log _{3}N$ ${\ displaystyle \ log _ {3} N}$ ${\ displaystyle \ log _ {3} N}$ greutăți, care este un număr mai mic.

Bibliografie

(EN) Edwin O'Shea, Problema lui Bachet: cât mai puține greutăți pentru a le cântări pe toate în arXiv , octombrie 2010. Adus la 6 noiembrie 2012.

linkuri externe

( EN ) Biografia lui Claude-Gaspard Bachet de Méziriac în MacTutor .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică