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

Математическая задача

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

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

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

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

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

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

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

Макдоннелл также исследует более раннее развитие темы. ^[6]

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

Решения

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

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

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

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

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

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

и, представленный с заглавной буквой «сигма», как:

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

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

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

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

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

Умножим каждую часть на 2:

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

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

${\displaystyle {\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}}}$

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

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

где — первый член ряда, — знаменатель ряда, — число членов ряда. ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle n}$

В этой задаче , и . ${\displaystyle a=1}$ ${\displaystyle r=2}$ ${\displaystyle n=64}$

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

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

для любого положительного целого числа. ${\displaystyle n}$

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

Число зерен равно 64-му числу Мерсенна .

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

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

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

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

Число зерен пшеницы на второй половине шахматной доски равно 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 метрических тонн . Это более чем в 1 600 раз превышает мировое производство пшеницы (729 миллионов метрических тонн в 2014 году и 780,8 миллионов тонн в 2019 году). ^[9]

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

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

Смотрите также

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

Ссылки

1. В период 2020–2021 гг. этот показатель оценивался в 772,64 млн метрических тонн, «Статистика мирового производства пшеницы с 1990 года» . Получено 25.05.2022 .
2. «Пенни удваивается каждый день в течение 30 дней = 10,7 млн ​​долларов» – через www.bloomberg.com.
3. "Удвоение пенни". Mathforum.org . Получено 2017-08-09 .
4. Клиффорд А. Пиковер (2009), Книга по математике: от Пифагора до 57-го измерения , Нью-Йорк: Sterling. ISBN 9781402757969. стр. 102 
5. Тахан, Мальба (1993). Человек, который считал: Сборник математических приключений. Нью-Йорк: WW Norton & Co., стр. 113–115. ISBN 0393309347. Получено 2015-04-05 .
6. Macdonell, AA (1898). «Происхождение и ранняя история шахмат». Журнал Королевского азиатского общества Великобритании и Ирландии . 30 (1): 117–141. doi :10.1017/S0035869X00146246. S2CID  163963500.
7. Курцвейл, Рэй (1999). Эпоха духовных машин: когда компьютеры превосходят человеческий интеллект. Нью-Йорк: Penguin. С. 37. ISBN 0-670-88217-8. Получено 2015-04-06 .
8. "Encyclopedia Britannica: Grain, unit of weight". 29 апреля 2004 г. Получено 2 марта 2017 г.
9. "FAOSTAT". faostat3.fao.org . Архивировано из оригинала 11 января 2019 . Получено 2 марта 2017 .
10. Саган, Карл (1997). Миллиарды и миллиарды: мысли о жизни и смерти на пороге тысячелетия. Нью-Йорк: Ballantine Books. стр. 17. ISBN 0-345-37918-7.
11. Meadows, Donella H., Dennis L. Meadows, Jørgen Randers и William W. Behrens III (1972). Пределы роста , стр. 21, в Google Books . Нью-Йорк: University Books. ISBN 0-87663-165-0 . Получено 05.04.2015. 

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

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