Shakkipelin keksijän palkkio

Shakkipelin keksijän palkkio on vanhaan tarinaan perustuva matemaattinen probleema. Kirjallisuudessa tarinan mainitsi tiettävästi ensimmäisenä arabialainen Abu l’Abbas Ahmad ibn Khallikanin vuonna 1256.

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Shakkilauta

Eri ruutuja vastaavien jyvien lukumäärät.

Sopimus palkkiosta

Tarinan mukaan intialainen kuningas Shiram pyysi myös matemaatikkona tunnettua suurvisiiri Sissa ben Dahiria kehittämään uuden strategisen lautapelin ja lupasi tälle pelin keksimisestä suuren palkkion. Sissa ben Dahir keksi shakin. Ruhtinas ihastui peliin ja kysyi keksijältä, mitä tämä halusi palkkioksi. Keksijä pyysi palkkioksi ”ainoastaan” niin monta vehnän (tai tarinan eräiden versioiden mukaan riisin) jyvää kuin saadaan koko shakki­laudalta, jos niitä asetetaan sen ensimmäiselle ruudulle yksi, toiselle ruudulle kaksi, kolmannelle neljä, neljännelle kahdeksan ja edelleen jokaiselle ruudulle kaksi kertaa niin monta kuin edelliselle ruudulle. Ruhtinas ensin arveli tällaisen palkkion olevan niin vähäinen, että hän jopa ihmetteli, miksi keksijä ei pyytänyt suurempaa palkkiota. Todellisuudessa se kuitenkin osoittautui niin suureksi, että tällaisen vilja­määrän toimittaminen pelin keksijälle oli mahdotonta.

Jyvien lukumäärä

Shakkilaudalla on 64 ruutua. Näin ollen tämä jyvien lukumäärä voidaan laskea geometrisen sarjan osasummana:

$T_{64}=1+2+4+8+\cdots +2^{63}=\sum _{i=0}^{63}2^{i}=2^{64}-1\,$

Tämä summa eli jyvien kokonais­luku­määrä on yli 18 triljoonaa – täsmälleen laskettuna 18 446 744 073 709 551 615. Sama luku saadaan myös siirtojen luku­määräksi Hanoin torniprobleemassa 64 renkaalla.

Tarinaa käytetään usein kuvaamaan sitä, kuinka suuriin lukuihin eksponentiaalinen kasvu piankin johtaa.

Sekä vehnän että riisin jyvän massa on tyypillisesti noin 50 milligrammaa. Näin ollen palkkio vastaisi noin 18,4·10¹⁸ · 50 mg = 9,2·10²⁰ mg = 9,2·10¹¹ t eli noin 920 miljardia tonnia vehnää tai riisiä. Vertailun vuoksi voidaan todeta, että koko maailman vuotuinen vehnäsato 1990-luvulla oli noin 540 miljoonaa tonnia ja riisisato hieman pienempi.. Näin ollen palkkio vastaisi noin 1700-kertaisesti koko maailman vuotuista vehnä- tai riisisatoa.