棋盤(pán)上的麥粒
? 國(guó)際象棋起源于古代印度,據(jù)說(shuō)當(dāng)時(shí)的國(guó)王要獎(jiǎng)賞國(guó)際象棋的發(fā)明者。國(guó)王問(wèn)發(fā)明者想要什么獎(jiǎng)勵(lì),發(fā)明者說(shuō)請(qǐng)您在棋盤(pán)的第一個(gè)格子里放一粒麥子,第二個(gè)格子里放兩粒麥子,第三個(gè)格子里放四粒麥子......以此類(lèi)推,每個(gè)格子里的麥子數(shù)量都要是前一個(gè)格子里的兩倍,直到把64個(gè)格子全部放完,把這些麥粒全部獎(jiǎng)賞給我就行了。
? 國(guó)王覺(jué)得這個(gè)要求不高,就欣然同意了。但是當(dāng)他往棋盤(pán)上一格一格的放麥粒的時(shí)候才發(fā)現(xiàn),全國(guó)的麥子竟然都不夠放滿(mǎn)整個(gè)棋盤(pán)。其實(shí)在高中我們就應(yīng)該學(xué)到過(guò)這個(gè)故事,這其實(shí)就是一個(gè)以1為首項(xiàng),2為公比的等比數(shù)列,我們要求的就是這個(gè)數(shù)列的前64項(xiàng)之和。根據(jù)等比數(shù)列前n項(xiàng)和的公式,我們可以輕易計(jì)算得到一共需要()-1粒麥子,而這足足是全世界差不多2000年的小麥產(chǎn)量!
? 但是我覺(jué)得這些小麥還是不夠多,畢竟最后得到的數(shù)字可以用指數(shù)的形式輕易表達(dá)出來(lái)。如果換我向國(guó)王提要求,我會(huì)這樣提:請(qǐng)不斷向第一個(gè)格子里一粒一粒的放麥子,當(dāng)?shù)谝粋€(gè)格子里第一次有10粒麥子時(shí)將第一格清空,同時(shí)在第二個(gè)格子里放一粒麥子。要注意,當(dāng)?shù)谝桓竦诙斡?0粒麥子時(shí)就不能直接“進(jìn)位”到第二格了,此時(shí)我們需要10×2^10粒麥子才能把第一格清空,并在第二個(gè)格子里放下第二粒麥子。規(guī)則是這樣的:每在第一個(gè)格子里放下一粒麥子,就視為走了“一步”,步數(shù)記為m。所有的格子第一次向下一個(gè)格子“進(jìn)位”時(shí),都只需要在本格子里出現(xiàn)10粒麥子。步數(shù)每走一步,下下次的進(jìn)位“匯率”就會(huì)在原有基礎(chǔ)上翻倍?;氐缴厦娴睦樱谝粋€(gè)格子里第一次有了10粒麥子時(shí)第一次向第二個(gè)格子里進(jìn)位,而此時(shí)我們已經(jīng)走了10步。而每走一步,下下次進(jìn)位的“匯率”就會(huì)翻倍,所以當(dāng)?shù)谝粋€(gè)格子里出現(xiàn)10×2^10粒麥子時(shí)才能第二次向第二個(gè)格子里進(jìn)位。同樣的,第一個(gè)格子第三次向第二個(gè)格子里進(jìn)位就需要10×2^10×2^(10×2^10)粒麥子。
? ?當(dāng)?shù)诙€(gè)格子也第一次有了10粒麥子后,同樣需要向第三個(gè)格子里面進(jìn)位。但是要注意,第二個(gè)格子里的麥子第二次向第三個(gè)格子里進(jìn)位時(shí)可不是簡(jiǎn)單的10×2^10粒,因?yàn)榇藭r(shí)已經(jīng)走過(guò)的步數(shù)遠(yuǎn)不止10步!記每個(gè)格子之間進(jìn)位的匯率為a,第一次進(jìn)位時(shí)a?=10,第二次進(jìn)位時(shí)a?=a?×2^m?,其中m?是該格子第一次向下個(gè)格子進(jìn)位時(shí)走過(guò)的步數(shù)。第三次進(jìn)位時(shí)a?=a?×2^(m?-m?),其中m?是該格子第二次向下個(gè)格子進(jìn)位時(shí)走過(guò)的步數(shù)。a?n=a?(n-1)×2^(m?n-m?(n-1))。請(qǐng)問(wèn)按照這個(gè)規(guī)則,當(dāng)?shù)?4個(gè)格子上出現(xiàn)第一粒麥子時(shí),需要走過(guò)多少步,或者說(shuō)一共需要在第一個(gè)格子里放多少粒麥子才能讓第64格出現(xiàn)一粒麥子?