Ogled vira Problem števila zrn na šahovnici

{{Chess diagram|=
|tright
|
|=
 8 |  |  |  |  |  |  |  |  |=
 7 |  |  |  |  |  |  |  |  |=
 6 |  |  |  |  |  |  |  |  |=
 5 |  |  |  |  |  |  |  |  |=
 4 |  |  |  |  |  |  |  |  |=
 3 |  |  |  |  |  |  |  |  |=
 2 |  |  |  |  |  |  |  |  |=
 1 |  |  |  |  |  |  |  |  |=
    a  b  c  d  e  f  g  h  
| Prazna [[šahovnica]]
}}

'''Problem števila zrn na šahovnici''' je v [[razvedrilna matematika|razvedrilni matematiki]] [[problem]] v obliki [[besedni problem|besednega problema]]: {{quotation|Če moramo na [[šahovnica|š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šenica|pšenična]] zrna. Rešimo ga lahko s preprostim [[seštevanje]]m. Če se na šahovnici s [[64 (število)|64]]-imi polji število zrn podvoji na vsakem naslednjem polju, je [[vsota]] na vseh poljih enaka: 1&nbsp;+&nbsp;2&nbsp;+&nbsp;4&nbsp;+&nbsp;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 [[potenciranje|potenciranja]], hitre rasti [[eksponentna rast|eksponentnih zaporedij]] in [[geometrijsko zaporedje|geometričnih zaporedij]]. Z njim lahko pojasnimo tudi zapis vsote z veliko [[sigma|sigmo]]. Če števila zrn na posameznih poljih zapišemo s potencami, dobimo geometrijsko zaporedje: 2<sup>0</sup>&nbsp;+&nbsp;2<sup>1</sup>&nbsp;+&nbsp;2<sup>2</sup>&nbsp;+&nbsp;2<sup>3</sup>... in tako naprej do 2<sup>63</sup>. 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:

: <math> T_{64} = 1 + 2 + 4 + \cdots + 9,223,372,036,854,775,808 \!\, , </math>

kjer je <math>T_{64} \,</math> skupno število zrn.

[[geometrična vrsta|Geometrično vrsto]] lahko zapišemo s potencami:

: <math> \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} </math>

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

: <math> s = 2^{0} + 2^{1} + 2^{2} + \cdots + 2^{63} \!\, </math> 
pomnožimo z 2:

: <math> 2s = 2^{1} + 2^{2} + 2^{3} + \cdots + 2^{63} + 2^{64} \!\, </math> 

in odštejemo obe vsoti:

: <math> 2s - s = - 2^{0} + 2^{64} \!\, </math>

: <math>\therefore  s = 2^{64}- 1 \!\, . </math>

=== Kvadratne šahovnice ===

Število zrn za [[kvadrat (algebra)|kvadrat]]ne šahovnice ''n'' × ''n'' je enako:

: <math> T_{n\times n} \equiv T_{n^{2}} = \sum_{k=0}^{n^{2}-1} 2^{k} = 2^{n^{2}}-1; \quad n \ge 0 \!\, , </math>

kar da skupna števila zrn za prva števila ''n'' {{OEIS|id=A212739}}:

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

== Zunanje povezave ==

* [http://mathworld.wolfram.com/WheatandChessboardProblem.html Pšenica in problem na šahovnici] na [[MathWorld]] {{ikona en}}

{{math-stub}}

[[Kategorija:Razvedrilna matematika in uganke]]