Problem števila zrn na šahovnici

Problem števila zrn na šahovnici je v razvedrilni matematiki problem v obliki besednega problema: Predloga:Quotation

V problemu se poleg riževih pojavljajo lahko tudi pšenična zrna. Rešimo ga lahko s preprostim seštevanjem. Če se na šahovnici s 64-imi polji število zrn podvoji na vsakem naslednjem polju, je vsota na vseh poljih enaka: 1 + 2 + 4 + 8... in tako naprej za vseh 64 polj. Celotno število zrn je enako 18.446.744.073.709.551.615, kar je precej večje število, ki bi ga intuitivno pričakovali.

Obravnavo problema lahko uporabimo za pojasnitev in prikaz potenciranja, hitre rasti eksponentnih zaporedij in geometričnih zaporedij. Z njim lahko pojasnimo tudi zapis vsote z veliko sigmo. Če števila zrn na posameznih poljih zapišemo s potencami, dobimo geometrijsko zaporedje: 2⁰ + 2¹ + 2² + 2³... in tako naprej do 2⁶³. Osnova vsake potence, »2«, nakazuje podvojitev števila na vsakem polju, potenca pa predstavlja lego vsakega polja (0 za prvo polje, 1 za drugo itd.).

Rešitve

Običajna šahovnica

Za običajno šahovnico je preprosta rešitev z grobo silo ročna podvojitev in seštevanje v vsakem koraku zaporedja:

$T_{64}=1+2+4+\cdots +9,223,372,036,854,775,808,$

kjer je $T_{64}$ skupno število zrn.

Geometrično vrsto lahko zapišemo s potencami:

$\begin{array}{cc}{T}_{8\times 8}\equiv T_{64}& =2^0+2^1+2^2+\cdots +2^{63}=\sum _{k=0}^{63}{2}^k=2^{64}-1=18446744073709551615\\ & =3\cdot 5\cdot 17\cdot 257\cdot 641\cdot 65537\cdot 6700417.\end{array}$

Da vsota velja, pokažemo, če obe strani vsote:

$s=2^0+2^1+2^2+\cdots +2^{63}$

pomnožimo z 2:

$2s=2^1+2^2+2^3+\cdots +2^{63}+2^{64}$

in odštejemo obe vsoti:

$2s-s=-2^0+2^{64}$

$\therefore s=2^{64}-1.$

Kvadratne šahovnice

Število zrn za kvadratne šahovnice n × n je enako:

$T_{n\times n}\equiv T_{n^2}=\sum _{k=0}^{n^2-1}{2}^k=2^{n^2}-1;n\ge 0,$

kar da skupna števila zrn za prva števila n Predloga:OEIS:

0, 1, 15, 511, 65535, 33554431, 68719476735, 562949953421311, 18446744073709551615, 2417851639229258349412351, 1267650600228229401496703205375, ...

Zunanje povezave

• Pšenica in problem na šahovnici na MathWorld Predloga:Ikona en