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

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

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

Задачу можно решить простым сложением . На шахматной доске 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 году нашей эры). [...] Дополнительным аргументом в пользу индийского происхождения этого расчета служит арабское название квадрата шахматной доски (بيت, «бейт»), «дом». [...] Ибо это, несомненно, имеет историческую связь с его индийским названием коштхагара, «склад», «житница» [...].

Решения

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

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-е число Мерсенна .

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

В технологической стратегии «вторая половина шахматной доски» — это фраза, придуманная Рэем Курцвейлом . ^{[ 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 метрических тонн . Это более чем в 1600 раз превышает мировое производство пшеницы (729 миллионов тонн в 2014 году и 780,8 миллиона тонн в 2019 году). ^{[ 9 ]}

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

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

См. также

Ссылки

^ В период 2020–2021 годов это составило примерно 772,64 миллиона метрических тонн, «Мировая статистика производства пшеницы с 1990 года» . Проверено 25 мая 2022 г.
^ «Пенни, удваивающийся каждый день в течение 30 дней = 10,7 миллиона долларов» – через www.bloomberg.com.
^ «Удвоение пенни» . Mathforum.org . Проверено 9 августа 2017 г.
^ Клиффорд А. Пиковер (2009), Книга математики: от Пифагора до 57-го измерения , Нью-Йорк: Стерлинг. ISBN 9781402757969 . п. 102
^ Тахан, Мальба (1993). Человек, который считал: Сборник математических приключений . Нью-Йорк: WW Norton & Co. стр. 113–115. ISBN 0393309347 . Проверено 5 апреля 2015 г.
^ Макдонелл, А.А. (1898). «Происхождение и ранняя история шахмат». Журнал Королевского азиатского общества Великобритании и Ирландии . 30 (1): 117–141. дои : 10.1017/S0035869X00146246 . S2CID 163963500 .
^ Курцвейл, Рэй (1999). Эпоха духовных машин: когда компьютеры превосходят человеческий интеллект . Нью-Йорк: Пингвин. п. 37. ИСБН 0-670-88217-8 . Проверено 6 апреля 2015 г.
^ «Британская энциклопедия: Зерно, единица веса» . 29 апреля 2004 года . Проверено 2 марта 2017 г.
^ «ФАОСТАТ» . faostat3.fao.org . Архивировано из оригинала 11 января 2019 года . Проверено 2 марта 2017 г.
^ Саган, Карл (1997). Миллиарды и миллиарды: мысли о жизни и смерти на пороге тысячелетия . Нью-Йорк: Ballantine Books. п. 17 . ISBN 0-345-37918-7 .
^ Медоуз, Донелла Х., Деннис Л. Медоуз, Йорген Рандерс и Уильям В. Беренс III (1972). Пределы роста , с. 21, в Google Книгах . Нью-Йорк: Университетские книги. ISBN 0-87663-165-0 . Проверено 5 апреля 2015 г.

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

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

[1] В период 2020–2021 годов это составило примерно 772,64 миллиона метрических тонн, «Мировая статистика производства пшеницы с 1990 года» . Проверено 25 мая 2022 г.

[2] «Пенни, удваивающийся каждый день в течение 30 дней = 10,7 миллиона долларов» – через www.bloomberg.com.

[3] «Удвоение пенни» . Mathforum.org . Проверено 9 августа 2017 г.

[4] Клиффорд А. Пиковер (2009), Книга математики: от Пифагора до 57-го измерения , Нью-Йорк: Стерлинг. ISBN 9781402757969 . п. 102

[5] Тахан, Мальба (1993). Человек, который считал: Сборник математических приключений . Нью-Йорк: WW Norton & Co. стр. 113–115. ISBN 0393309347 . Проверено 5 апреля 2015 г.

[6] Макдонелл, А.А. (1898). «Происхождение и ранняя история шахмат». Журнал Королевского азиатского общества Великобритании и Ирландии . 30 (1): 117–141. дои : 10.1017/S0035869X00146246 . S2CID 163963500 .

[7] Курцвейл, Рэй (1999). Эпоха духовных машин: когда компьютеры превосходят человеческий интеллект . Нью-Йорк: Пингвин. п. 37. ИСБН 0-670-88217-8 . Проверено 6 апреля 2015 г.

[8] «Британская энциклопедия: Зерно, единица веса» . 29 апреля 2004 года . Проверено 2 марта 2017 г.

[9] «ФАОСТАТ» . faostat3.fao.org . Архивировано из оригинала 11 января 2019 года . Проверено 2 марта 2017 г.

[10] Саган, Карл (1997). Миллиарды и миллиарды: мысли о жизни и смерти на пороге тысячелетия . Нью-Йорк: Ballantine Books. п. 17 . ISBN 0-345-37918-7 .

[11] Медоуз, Донелла Х., Деннис Л. Медоуз, Йорген Рандерс и Уильям В. Беренс III (1972). Пределы роста , с. 21, в Google Книгах . Нью-Йорк: Университетские книги. ISBN 0-87663-165-0 . Проверено 5 апреля 2015 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]