abcdefgh
88
77
66
55
44
33
22
11
abcdefgh

Задача о зёрнах на шахматной доске — математическая задача, в которой вычисляется, сколько будет зёрен на шахматной доске, если класть на каждую следующую клетку доски вдвое больше зёрен, чем на предыдущую, начиная с одного.

Для её решения учтём, что доска имеет 64 клетки. При удвоении количества зёрен на каждой последующей клетке сумма зёрен на всех 64 клетках определяется выражением

T 64 = 1 + 2 + 4 + ⋯ + 2 63 = ∑ i = 0 63 2 i = 2 64 − 1 , <displaystyle T_<64>=1+2+4+cdots +2^<63>=sum _^<63>2^=2^<64>-1,>

Задача (и её вариации) демонстрирует высокую скорость роста экспоненциальных последовательностей.

Содержание

Истоки задачи [ править | править код ]

Хотя детали описания задачи в разных источниках отличаются, суть остаётся неизменной. По легенде [ источник не указан 637 дней ] , когда создатель шахмат (по одним данным [ источник не указан 637 дней ] — древнеиндийский математик, по другим [ источник не указан 637 дней ] — легендарный дравид велалар по имени Сесса или Сисса) показал своё изобретение правителю страны, тому так понравилась игра, что он дал изобретателю право самому выбрать награду. Мудрец попросил у короля за первую клетку шахматной доски заплатить ему одно зерно пшеницы (по другой версии [ источник не указан 637 дней ] — риса), за вторую — два, за третью — четыре и т. д., удваивая количество зёрен на каждой следующей клетке. Правитель, не разбиравшийся в математике, быстро согласился, даже несколько обидевшись на столь невысокую оценку изобретения, и приказал казначею подсчитать и выдать изобретателю нужное количество зерна. Однако, когда неделю спустя казначей всё ещё не смог подсчитать, сколько нужно зёрен, правитель спросил, в чём причина такой задержки. Казначей показал ему расчёты и сказал, что расплатиться невозможно, разве только осушить моря и океаны и засеять всё пространство пшеницей.

Количество зерна примерно в 1800 раз превышает мировой урожай пшеницы за год (в 2008-09 аграрном году урожай составил 686 млн тонн [1] ), то есть превышает весь урожай пшеницы, собранный за всю историю человечества. Количество зёрен составляет примерно 0,0031 % числа Авогадро. В единицах массы: если принять, что одно зёрнышко пшеницы имеет массу 0,065 грамма (Troy grain тройское зерно: 1 gr = 0,06479891 g [2] ), тогда общая масса пшеницы на шахматной доске составит 1200 миллиардов тонн или 1,2 триллиона тонн:

18446744073709551615 × 0,065 g ( 1000000 g / t ) ≈ 1 , 2 ⋅ 10 12 t . <displaystyle <frac <18446744073709551615 imes 0<,>065

<mathrm>.>

Варианты задачи [ править | править код ]

Есть похожая задача, в которой царь предлагает полководцу забирать каждый день монету в два раза большую предыдущей. Я. И. Перельман в своей книге «Живая математика» приводит следующий вариант задачи, сюжет которой, по его словам, позаимствован из «старинной латинской рукописи»: когда храбрый полководец вернулся в Рим из сражений, император спросил, какую плату он хочет за свою службу. Полководец запросил заоблачную сумму. Император, чтобы не прослыть скрягой или человеком, не держащим слово, предложил полководцу пойти на следующий день в казну и взять одну медную монету достоинством в один брасс (весом в пять грамм), через день — два брасса, потом четыре и т. д., пока тот сможет сам уносить полученные монеты (каждый день отливаются монеты нужного веса). Полководец, решив, что ему удастся легко разбогатеть, согласился. Однако на 18-й день он уже не смог унести монету и в результате получил только малую часть того вознаграждения, что просил у императора.

По другой версии, двое торговцев заключили соглашение о том, что в течение месяца первый будет давать второму по 10 000 долларов в день. Второй же должен возвращать первому в первый день один цент, во второй — два и т. д. Второй торговец согласился и первые три недели радовался доходам, но в конце месяца был полностью разорён, отдав всё своё состояние первому. Перельман приводит версию, согласно которой первый человек отдает не по 10 000, а по 100 000 в день (в русских денежных единицах), но результат от этого значительно не меняется.

Ещё в одной версии человек покупает коня, но недоволен ценой в 1000 рублей. Продавец ему предлагает платить не за коня, а за подковные гвозди, полушка за первый, две за второй, копейка за третий и так далее. Поскольку в каждой подкове по 6 гвоздей, покупатель вынужден заплатить более 40 000 рублей.

Вторая половина шахматной доски [ править | править код ]

В технологии стратегий «вторая часть шахматной доски» — фраза, придуманная Рэем Курцвайлем в отношении точки, в которой экспоненциальный рост фактора начинает оказывать существенное экономическое влияние на общую экономическую стратегию предприятия. В то время как количество зёрен на первой половине доски велико, количество на второй половине многократно его превышает. Количество зёрен на первой половине доски составляет 1 + 2 + 4 + … + 2 147 483 648 , всего 2 32 — 1 = 4 294 967 295 зёрен , или около 100 тонн риса при массе одного зёрнышка 25 мг [3] . Это примерно 1/1200000 от всего объёма риса, выращиваемого в Индии за год (данные за 2005 год) [4] .

Количество зерна на второй половине доски составляет 2 32 + 2 33 + 2 34 … + 2 63 = 2 64 — 2 32 зёрен риса . На одной только 64-й клетке доски будет 2 63 = 9 223 372 036 854 775 808 зёрен , более чем в 2 миллиарда раз больше, чем на всей первой половине доски. На всей доске будет 2 64 — 1 = 18 446 744 073 709 551 615 зёрен , их общая масса составит 461 168 601 842,738790375 тонн .

Когда создатель шахмат, древнеиндийский мудрец и математик Сисса бен Дахир, показал своё изобретение Правителю страны, тому так понравилась игра, что он позволил изобретателю право самому выбрать награду. Мудрец попросил у Повелителя за первую клетку шахматной доски заплатить ему одно зерно пшеницы (по другой версии — риса), за второе — два, за третье — четыре и т. д., удваивая количество зёрен на каждой следующей клетке.

Правитель, не разбиравшийся в математике, быстро согласился, даже несколько обидевшись на столь невысокую оценку изобретения, и приказал казначею подсчитать и выдать изобретателю нужное количество зерна. Однако, когда неделю спустя казначей всё ещё не смог подсчитать, сколько нужно зёрен, правитель спросил, в чём причина такой задержки. Казначей показал ему расчёты и сказал, что расплатиться невозможно, поскольку колличество зерна превышает весь урожай пшеницы, собранный за всю историю человечества.

На всей доске будет 2 в 64 степени − 1 или 18 446 744 073 709 551 616 зёрен, их общая масса составит 461 168 602 000 тонн. Для того, чтобы вместить такое колличество зерна потребуется амбар с размерами 10х10х15 км.

Правитель, чтобы взять реванш над пытавшимся его обхитрить изобретателем, велел последнему пересчитать каждое зёрнышко, чтобы не было сомнений в том, что он честно с ним расплатился.

Легенда о шахматной доске

Шахматы – одна из самых древних игр. Она существует уже многие века, и неудивительно, что с нею связаны различные предания, правдивость которых, за давностью времени, невозможно проверить.

Об одной из подобных легенд и математической составляющей ее содержания мы сегодня и поведём речь. Чтобы понять ее, не нужно вовсе уметь играть в шахматы: достаточно знать, что игра происходит на доске, разграфленной на 64 клетки. Текст легенды приводится в изложении советского учёного и популяризатора физики, математики и астрономии Якова Исидоровича Перельмана (1882–1942), взятого из его замечательной книги "Живая математика".

Давным-давно.

Шахматная игра была придумана в Индии, и когда индусский царь Шерам познакомился с нею, он был восхищен ее остроумием и разнообразием возможных в ней положений. Узнав, что она изобретена одним из его подданных, царь приказал его позвать, чтобы лично наградить за удачную выдумку.

Изобретатель, его звали Сета, явился к трону повели­теля. Это был скромно одетый ученый, получавший сред­ства к жизни от своих учеников.

Сисса бен Дахир (Сасса бен Дахир) – мифический индийский мудрец, которому приписывается изобретение шахмат. Упоминается в ряде сочинений на арабском, персидском, тюркском языках, где изложены легенды о происхождении шахмат. Попытки отождествлять Сисса бен Дахира с историческими личностями научного подтверждения не получили.

– Я желаю достойно вознаградить тебя, Сета, за прекрасную игру, которую ты придумал, – сказал царь.

– Я достаточно богат, чтобы исполнить самое смелое твое пожелание, – продолжал царь.– Назови награду, которая тебя удовлетворит, и ты получишь ее.

– Не робей, – ободрил его царь. – Выскажи свое желание. Я не пожалею ничего, чтобы исполнить его.

– Велика доброта твоя, повелитель. Но дай срок обдумать ответ. Завтра, по зрелом размышлении, я сообщу тебе мою просьбу.

Когда на другой день Сета снова явился к ступеням трона, он удивил царя беспримерной скромностью своей просьбы.

– Повелитель, – сказал Сета,– прикажи выдать мне за первую клетку шахматной доски одно пшеничное зерно.

– Простое пшеничное зерно? – изумился царь.

– Да, повелитель. За вторую клетку прикажи выдать 2 зерна, за третью 4, за четвертую – 8, за пятую – 16, за шестую – 32.

–Довольно, – с раздражением прервал его царь.– Ты получишь свои зерна за все 64 клетки доски, согласно твоему желанию: за каждую вдвое больше против предыдущей. Но знай, что просьба твоя недостойна моей щедрости. Прося такую ничтожную награду, ты непочтительно пренебрегаешь моею милостью. Поистине, как учитель, ты мог бы показать лучший пример уважения к доброте своего государя. Ступай. Слуги мои вынесут тебе твой мешок с пшеницей.

Сета улыбнулся, покинул залу и стал дожидаться у ворот дворца.

За обедом царь вспомнил об изобретателе шахмат и послал узнать, унес ли уже безрассудный Сета свою жалкую награду.

– Повелитель, – был ответ, – приказание твое исполняется. Придворные математики исчисляют число следуемых зерен.

Царь нахмурился. Он не привык, чтобы повеления его исполнялись так медлительно.

Вечером, отходя ко сну, царь еще раз осведомился, давно ли Сета со своим мешком пшеницы покинул ограду дворца.

– Повелитель, – ответили ему,– математики твои трудятся без устали и надеются еще до рассвета закончить подсчет.

– Почему медлят с этим делом? – гневно воскликнул царь. – Завтра, прежде чем я проснусь, все до последнего зерна должно быть выдано Сете. Я дважды не приказываю.

Утром царю доложили, что старшина придворных математиков просит выслушать важное донесение. Царь приказал ввести его.

– Прежде чем скажешь о твоем деле, – объявил Шерам,– я желаю услышать, выдана ли, наконец, Сете та ничтожная награда, которую он себе назначил.

– Ради этого я и осмелился явиться перед тобой в столь ранний час,– ответил старик.– Мы добросовестно исчислили все количество зерен, которое желает получить Сета. Число это так велико.

– Как бы велико оно ни было, – надменно перебил царь, житницы мои не оскудеют. Награда обещана и должна быть выдана.

– Не в твоей власти, повелитель, исполнять подобные желания. Во всех амбарах твоих нет такого числа зерен, какое потребовал Сета. Нет его и в житницах целого царства. Не найдется такого числа зерен и на всем пространстве Земли. И если желаешь непременно выдать обещанную награду, то прикажи превратить земные царства в пахотные поля, прикажи осушить моря и океаны, прикажи растопить льды и снега, покрывающие далекие северные пустыни. Пусть все пространство их сплошь будет засеяно пшеницей. И все то, что родится на этих полях, прикажи отдать Сете. Тогда он получит свою награду. С изумлением внимал царь словам старца.

– Назови же мне это чудовищное число, – сказал он в раздумье.

Восемнадцать квинтиллионов четыреста сорок шесть квадриллионов семьсот сорок четыре триллиона семьдесят три биллиона семьсот девять миллионов пятьсот пятьдесят одна тысяча шестьсот пятнадцать, о повелитель !

Арабская (X век) и персидская (XIV век) миниатюры. Обратите внимание: доска одноцветная!
Черно-белая доска – это уже более позднее изобретение европейцев.

Число-гигант

Такова легенда. Действительно ли было то, что здесь рассказано, неизвестно, – но что награда, о которой говорит предание, должна была выразиться именно таким числом, в этом вы сами можете убедиться терпеливым подсчетом.

Начав с единицы, нужно сложить числа: 1, 2, 4, 8 и т. д. Иначе эту сумму можно записать так:

1 + 2 + 4 + 8 + . . . = 2 0 + 2 1 + 2 2 + 2 3 + . . . + 2 63 .

Последнее слагаемое показывает, сколько причиталось изобретателю за 64-ю клетку доски.

Упростим полученную сумму исходя из следующих соображений. Обозначим

S = 2 0 + 2 1 + 2 2 + 2 3 + . . . + 2 63 ,

2S = 2 · (2 0 + 2 1 + 2 2 + 2 3 + . . . + 2 63 ) = 2 1 + 2 2 + 2 3 + 2 4 + . . . + 2 64

S = 2S – S = (2 1 + 2 2 + 2 3 + 2 4 + . . . + 2 64 ) – (2 0 + 2 1 + 2 2 + 2 3 + . . . + 2 63 ) =

= 2 64 – 2 0 = 2 64 – 1.

Необходимое число зёрен

Значит, подсчет сводится лишь к перемножению 64 двоек! (А уж единицу потом вычесть сумеем).

S = 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 ·

· 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 ·

· 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 ·

Для облегчения выкладок разделим 64 множителя на 6 групп по 10 двоек в каждой и одну последнюю группу из 4 двоек. Произведение 10 двоек, как легко убедиться, равно 1 024, а 4 двоек – 16. Значит, искомый результат равен

S = 1 024 · 1 024 · 1 024 · 1 024 · 1 024 · 1 024 · 16 – 1.

1024 · 1024 = 1 048 576,

S = 1 048 576 · 1 048 576 · 1 048 576 · 16 – 1.

Проявим терпение и аккуратность в подсчётах и получим:

S = 18 446 744 073 709 551 615 .

Это количество зерна примерно в 1800 раз превышает мировой урожай пшеницы за год (в 2008 – 2009 аграрном году урожай составил 686 млн тонн), то есть превышает весь урожай пшеницы, собранный за всю историю человечества.

В единицах массы: если принять, что одно зёрнышко пшеницы имеет массу 0,065 грамма, тогда общая масса пшеницы на шахматной доске составит около 1,200 триллионов тонн:

18 446 744 073 709 551 615 · 0,065 гр = 1 199 038 364 791 120 854, 975 гр =

= 1 199 038 364 791, 120 т.

Если массу пшеницы перевести в объем (1 м 3 пшеницы весит около 760 кг), то получится приблизительно 1500 км 3 , что эквивалентно амбару с размерами 10 км х 10 км х 15 км. Это больше всего объёма горы Эверест.

Индусский царь не в состоянии был выдать подобной награды. Но он легко мог бы, будь он силен в математике, освободиться от столь обременительного долга. Для этого нужно было лишь предложить Сете самому отсчитать себе зерно за зерном всю причитавшуюся ему пшеницу.

В самом деле: если бы Сета, принявшись за счет, вел его непрерывно день и ночь, отсчитывая по зерну в секунду, он в первые сутки отсчитал бы всего 86 400 зерен. Чтобы отсчитать миллион зерен, понадобилось бы не менее 10 суток неустанного счета. Один кубический метр пшеницы он отсчитал бы примерно за полгода. И осталось бы отсчитать ещё 1 499 999 999 999 м 3 . Вы видите, что, посвятив счету даже весь остаток своей жизни, Сета получил бы лишь ничтожную часть потребованной им награды.

Таблица зерен и их сумм

Для тех, кто буквам и словам предпочитает цифры и числа, приведём таблицу распределения зерен по клеткам шахматной доски и постепенного суммарного роста их количества. Зрелище, по-своему, завораживающее.