Задача о зёрнах на шахматной доске

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Chess zhor 26.svg
Chess zver 26.svg
Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg
Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg
Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg
Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg
Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg
Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg
Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg
Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg
Chess zver 26.svg
Chess zhor 26.svg

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

T_{64} = 1 + 2 + 4 + \cdots + 2^{63} = \sum_{i=0}^{63} 2^i  = 2^{64}-1,

что составляет 18 446 744 073 709 551 615.

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

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

Lahur Sessa

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

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

\frac{18446744073709551615 \times 0{,}065 ~ {\mathrm {g}}}{(1000000 ~ {\mathrm {g}}/{\mathrm {t}})} = 1199038364791,120854 ~ {\mathrm {t}}.

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

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

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

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

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

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

Иллюстрация сути задачи

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

Количество зерна на второй половине доски составляет 232 + 233 + 234 … + 263, всего 264 − 232 зёрен риса. На одной только 64-й клетке доски будет 263 = 9 223 372 036 854 775 808 зёрен, более чем в 2 миллиарда раз больше, чем на всей первой половине доски. На всей доске будет 264 − 1 = 18 446 744 073 709 551 615 зёрен, их общая масса составит 461 168 602 000 тонн.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

Внешние ссылки[править | править вики-текст]