Задача о пшенице и шахматной доске

К тому времени, когда на шахматной доске будет достигнута пятая клетка, на доске будет в общей сложности 31 клетка, или ${\textstyle 2^{5}-1}$, зерна пшеницы.

Задача о пшенице и шахматной доске (иногда выражаемая в виде рисовых зерен) — это математическая задача, выраженная в текстовой форме следующим образом:

Если бы на шахматной доске на каждой клетке была размещена пшеница так, что одно зерно было помещено на первую клетку, два — на вторую, четыре — на третью и так далее (удваивая количество зерен на каждой последующей клетке), сколько зерен пшеницы окажется на шахматной доске в конце?

Задачу можно решить простым сложением . Если на шахматной доске 64 клетки, то если количество зерен на последующих клетках удваивается, то сумма зерен на всех 64 клетках равна: 1 + 2 + 4 + 8 + ... и так далее для 64 клеток. Можно показать, что общее количество зерен равно 2. ⁶⁴ −1 или 18 446 744 073 709 551 615 (восемнадцать квинтиллионов , четыреста сорок шесть квадриллионов, семьсот сорок четыре триллиона, семьдесят три миллиарда, семьсот девять миллионов, пятьсот пятьдесят одна тысяча, шестьсот пятнадцать, более 1,4 триллиона метрических тонн) , что более чем в 2000 раз превышает годовое мировое производство пшеницы.

Это упражнение можно использовать для демонстрации того, как быстро растут экспоненциальные последовательности, а также для введения показателей степени, нулевой степени, обозначения сигмы с заглавной буквы и геометрических рядов . Формула, обновленная для современного времени с использованием пенсов и гипотетического вопроса, такого как «Что бы вы предпочли: миллион долларов или пенни в первый день, удваиваемый каждый день до 30-го дня?», Формула использовалась для объяснения сложных процентов . (Удвоение даст более одного миллиарда семидесяти трех миллионов пенни, или более 10 миллионов долларов: 2 ³⁰ −1=1,073,741,823).

Происхождение

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

Макдоннелл также исследует более раннее развитие этой темы.

[Согласно ранней истории Индии аль-Масуди], шатрандж, или шахматы, были изобретены при индийском короле, который выразил свое предпочтение этой игре перед нардами . [...] Индийцы, добавляет он, также вычисляли арифметическую прогрессию с квадратами шахматной доски. [...] Ранняя любовь индийцев к огромным вычислениям хорошо известна изучающим их математику и проиллюстрирована в трудах великого астронома Арьябатхи (родившегося в 476 году нашей эры). [...] Дополнительным аргументом в пользу индийского происхождения этого расчета служит арабское название квадрата шахматной доски (بيت, «бейт»), «дом». [...] Ибо это, несомненно, имеет историческую связь с его индийским названием коштхагара, «склад», «житница» [...].

Решения

Сумма степеней двойки от нуля до заданной положительной целой степени на 1 меньше следующей степени двойки (т. е. следующего числа Мерсенна )

Простое решение методом грубой силы — просто вручную удвоить и добавить каждый шаг последовательности:

$T_{64}$ = 1 + 2 + 4 + ..... + 9,223,372,036,854,775,808 = 18,446,744,073,709,551,615

где $T_{64}$ это общее количество зерен.

Ряд можно выразить с помощью показателей:

$T_{64}=2^{0}+2^{1}+2^{2}+\cdots +2^{63}$

и представлено обозначением с заглавной сигмой как:

$\sum _{k=0}^{63}2^{k}.\,$

Эту проблему также можно решить гораздо проще, используя:

$T_{64}=2^{64}-1.\,$

Доказательством тому является:

$s=2^{0}+2^{1}+2^{2}+\cdots +2^{63}.$

Умножаем каждую сторону на 2:

$2s=2^{1}+2^{2}+2^{3}+\cdots +2^{63}+2^{64}.$

Вычтите исходный ряд с каждой стороны:

${\begin{aligned}2s-s&=\qquad \quad {\cancel {2^{1}}}+{\cancel {2^{2}}}+\cdots +{\cancel {2^{63}}}+2^{64}\\&\quad -2^{0}-{\cancel {2^{1}}}-{\cancel {2^{2}}}-\cdots -{\cancel {2^{63}}}\\&=2^{64}-2^{0}\\\therefore s&=2^{64}-1.\end{aligned}}$

Приведенное выше решение является частным случаем суммы геометрической прогрессии, заданной формулой

$a+ar+ar^{2}+ar^{3}+\cdots +ar^{n-1}=\sum _{k=0}^{n-1}ar^{k}=a\,{\frac {1-r^{n}}{1-r}},$

где $a$ это первый член ряда, $r$ это общее соотношение и $n$ это количество терминов.

В этой проблеме $a=1$, $r=2$ и $n=64$.

Таким образом,

${\begin{aligned}\sum _{k=0}^{n-1}2^{k}&=2^{0}+2^{1}+2^{2}+\cdots +2^{n-1}\\&=2^{n}-1\end{aligned}}$

для $n$ любое положительное целое число.

Упражнение по решению этой задачи можно использовать для объяснения и демонстрации показателей степени и быстрого роста экспоненциальных и геометрических последовательностей. Его также можно использовать для иллюстрации сигма-нотации . , выраженная в показателях, Геометрическая прогрессия имеет вид: 2 ⁰  + 2 ¹  + 2 ²  + 2 ³ + ... и так далее, до 2 ⁶³ . Основание каждого возведения в степень, «2», выражает удвоение каждого квадрата, а показатели степени представляют положение каждого квадрата (0 для первого квадрата, 1 для второго и т. д.).

Число зерен — 64-е число Мерсенна .

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

Иллюстрация Рэя Курцвейла второй половины принципа шахматной доски . Буквы представляют собой сокращения префиксов метрики SI .

В технологической стратегии «вторая половина шахматной доски» — это фраза, придуманная Рэем Курцвейлом . в отношении точки, где экспоненциально растущий фактор начинает оказывать значительное экономическое влияние на общую бизнес-стратегию организации. В то время как количество зерен на первой половине шахматной доски велико, их количество на второй половине значительно (2 ³² > в 4 миллиарда раз) больше.

Число зерен пшеницы на первой половине шахматной доски равно 1+2+4+8+...+2 147 483 648 , всего 4 294 967 295 (2 ³² − 1) зерна, или около 279 тонн пшеницы (при массе одного зерна пшеницы 65 мг).

Число зерен пшеницы на второй половине шахматной доски равно 2. ³² + 2 ³³ + 2 ³⁴ + ... + 2 ⁶³ , всего 2 ⁶⁴  − 2 ³² зерна. Оно равно квадрату количества зерен на первой половине доски плюс она сама. Только первый квадрат второй половины содержит на одно зерно больше, чем вся первая половина. Только на 64-м поле шахматной доски было бы 2 ⁶³ = 9 223 372 036 854 775 808 зерен, что более чем в два миллиарда раз больше, чем на первой половине шахматной доски.

На всей шахматной доске было бы 2 ⁶⁴ − 1 = 18 446 744 073 709 551 615 зерен пшеницы весом около 1 199 000 000 000 метрических тонн . Это более чем в 1600 раз превышает мировое производство пшеницы (729 миллионов тонн в 2014 году и 780,8 миллиона тонн в 2019 году).

Использовать

Карл Саган назвал вторую главу своей последней книги «Персидская шахматная доска» и написал, имея в виду бактерии, что «Экспоненты не могут продолжаться вечно, потому что они сожрут все». Точно так же в «Пределах роста» эта история используется для представления предполагаемых последствий экспоненциального роста : «Экспоненциальный рост никогда не может продолжаться очень долго в ограниченном пространстве с ограниченными ресурсами».

См. также

• Легенда об Амбалаппуже Паал Пайасам
• Мальтузианская модель роста
• Закон Мура
• Порядки величины (данные)
• Технологическая стратегия
• Пределы роста

Внешние ссылки

• Вайсштейн, Эрик В. «Проблема пшеницы и шахматной доски» . Математический мир .
• Задача о соли и шахматной доске . Вариант задачи о пшенице и шахматной доске с измерением каждого квадрата.
• Учебные материалы, связанные с математическими приключениями / Пшеница и шахматная доска в Викиверситете