Problem števila zrn na šahovnici

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Chess zhor 26.png
Chess zver 26.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.png
Chess zhor 26.png
Prazna šahovnica

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

Če moramo na šahovnico postaviti na prvo polje eno riževo zrno, na drugo dve zrni, na tretje štiri in tako naprej, tako, da za vsako polje enkrat povečamo število zrn s prejšnjega polja, koliko zrn bo na zadnjem polju šahovnice?


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 geometrično zaporedje: 20 + 21 + 22 + 23... in tako naprej do 263. 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[uredi | uredi kodo]

Običajna šahovnica[uredi | uredi kodo]

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{align} 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{align}

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[uredi | uredi kodo]

Š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; \quad n \ge 0 \!\, ,

kar da skupna števila zrn za prva števila n (OEIS A212739):

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

Zunanje povezave[uredi | uredi kodo]