Головоломка со сжиганием веревки

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

Эти головоломки не только представляют развлекательный интерес, но и иногда задаются на собеседованиях как проверка способности кандидатов решать проблемы. ^[1] и были предложены в качестве занятия для учащихся-математиков средней школы. ^[2]

Пример

Распространенная и простая версия этой задачи требует измерить время в 45 секунд, используя только два предохранителя, каждый из которых горит в течение минуты. Допущения задачи обычно формулируются таким образом, чтобы не отмерить 3/4 длины одного предохранителя и сжечь его встык, например, констатируя, что предохранители горят неравномерно по длине. ^[1]^[2]^[3]^[4]

Одним из решений этой проблемы является выполнение следующих шагов: ^[3]

Подожгите один конец первого предохранителя и оба конца второго предохранителя.
После перегорания второго предохранителя прошло 30 секунд, а на первом предохранителе осталось 30 секунд времени горения. Подожгите другой конец первого предохранителя.
После перегорания первого предохранителя проходит 45 секунд.

Возможны многие другие варианты, в некоторых случаях с использованием предохранителей, которые горят разное время друг от друга. ^[5]

Плавкие числа

В обычных вариантах задачи каждый предохранитель действует в течение единичного периода времени, и единственные операции, используемые или разрешенные в решении, - это зажигание одного или обоих концов предохранителя в известное время, определяемое либо как начало решения, либо как начало решения. как раз сгорит еще один предохранитель. Если одновременно горит только один конец предохранителя $x$ , со временем он сгорит $x+1$ . Если оба конца предохранителя время от времени загораются $x$ и $y$ , со временем он сгорит $(x+y+1)/2$ , поскольку часть $y-x$ сжигается с первоначальной скоростью, а оставшаяся часть $1-(y-x)$ сгорает в два раза быстрее первоначальной скорости, следовательно, предохранитель перегорает со скоростью

x+(y-x)+[1-(y-x)]/2=(x+y+1)/2

.

Число $x$ является плавким числом, если для измерения можно использовать плавкие предохранители единичного времени. $x$ единицы времени, используя только эти операции. Например, при решении примера задачи, ${\tfrac {3}{4}}$ является плавким числом. ^[7]

Без ограничения общности можно предположить, что каждый предохранитель горит с обоих концов, заменяя предохранитель, который горит только с одного конца за раз. $x$ двумя предохранителями, первый из которых загорается с обоих концов одновременно $x$ а второй горит с обоих концов одновременно $x+1/2$ когда сгорит первый предохранитель.Таким образом, плавкие числа можно определить как набор чисел, которые можно получить из числа $0$ путем многократного применения операции $x,y\mapsto (x+y+1)/2$ , применяется к парам $x,y$ которые уже получены и для которых $|x-y|<1$ . ^[7]

Плавкие числа включают в себя все неотрицательные целые числа и представляют собой упорядоченное подмножество двоично-рациональных чисел, дробей, знаменателями которых являются степени двойки . Быть хорошо упорядоченным означает, что если кто-то выбирает убывающую последовательность плавких чисел, эта последовательность всегда должна быть конечной. Среди хорошо упорядоченных множеств их порядок можно классифицировать как $\varepsilon _{0}$ , эпсилон-число (частный случай бесконечных порядковых чисел ). Поскольку они хорошо упорядочены, для каждого целого числа $n$ Среди плавких чисел, больших, чем $n$ ; он имеет форму $n+1/2^{k}$ для некоторых $k$ . ^[7] Этот номер $k$ очень быстро растет в зависимости от $n$ так быстро, что за $n=3$ оно (в обозначениях Кнута со стрелкой вверх для больших чисел) уже больше, чем $2\uparrow ^{9}16$ . ^[8] Существование этого номера $k$ , для каждого $n$ , не может быть доказано в арифметике Пеано . ^[7]

Освещение более двух точек предохранителя

Если правила головоломок о горении предохранителей интерпретируются так, что предохранители могут загораться в большем количестве точек, чем их концы, можно измерить больший набор периодов времени. Например, если предохранитель зажечь так, что, пока он горит, у него всегда горят три конца (например, зажигая одну точку посередине и один конец, а затем зажигая другой конец или другую точку посередине). всякий раз, когда перегорает одна или две из текущих горящих точек), то она будет гореть 1/3 единицы времени, а не всю единицу. Представляя заданное количество времени как сумму долей единиц и последовательно сжигая предохранители с несколькими горящими точками так, чтобы они работали в течение каждой доли времени, можно измерить любое рациональное количество единиц времени. Однако для поддержания желаемого количества пламени даже на одном предохранителе может потребоваться бесконечное количество шагов повторного зажигания. ^[4]

Проблема представления данного рационального числа в виде суммы единичных дробей тесно связана с построением египетских дробей , сумм отдельных единичных дробей; однако для решения проблем с перегоранием предохранителей нет необходимости в том, чтобы фракции отличались друг от друга. Используя известные методы расчета египетских дробей, можно доказать, что измерение дробного количества времени $x/y$ , с $x<y$ , нужно только $O({\sqrt {\log y}})$ предохранители (выраженные большой буквой О ). ^[9] Недоказанная гипотеза Пауля Эрдеша о египетских дробях предполагает, что меньшее количество предохранителей, $O(\log \log y)$ , всегда может быть достаточно. ^[10]

История

В буклете об этих головоломках под названием « Загадки с часами на шнурках» , созданном Диком Хессом для конференции Gathering 4 Gardner 1998 года , Хесс называет гарвардского статистика Карла Морриса своим первоначальным источником этих головоломок. ^[4]

См. также

Головоломка с проливом воды , еще один класс головоломок, включающий комбинацию измерений.

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Монган, Джон; Киндлер, Ной Суоянен; Жигер, Эрик (2012), «Горящие предохранители» , «Разоблаченные интервью по программированию: секреты получения следующей работы» (3-е изд.), John Wiley & Sons, стр. 234, ISBN 978-1-118-28720-0
^ Jump up to: Перейти обратно: ^а ^б Брамбо, Дуглас К. (2013), Преподавание математики в средней школе , Routledge, стр. 191 , 309 , ISBN 978-1-136-75622-1
^ Jump up to: Перейти обратно: ^а ^б Хазельбауэр, Натан (2020), 60-секундные головоломки без карандашей: короткие головоломки от простого до почти невозможного , Fair Winds Press, стр. 77 , 121 , ISBN 978-1-63159-927-9
^ Jump up to: Перейти обратно: ^а ^б ^с Винклер, Питер (2004), «Использование предохранителей», Математические головоломки: Коллекция знатоков , AK Peters, стр. 2, 6, ISBN 1-56881-201-9
^ Хесс, Дик (2009), «Часы на шнурках» , Головоломки Математиков всех звезд , Официальные книги головоломок Mensa, стр. 9, ISBN 978-1-4027-5528-6
^ Джефф Эриксон, Плавные числа
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Эриксон, Джефф; Ниваш, Габриэль; Сюй, Цзюньян (июнь 2021 г.), «Плавкие числа и арифметика Пеано» , Труды 36-го ежегодного симпозиума ACM/IEEE по логике в информатике (LICS 2021) , IEEE, стр. 1–13, arXiv : 2003.14342 , doi : 10.1109 /lics52264.2021.9470703
^ Слоан, Нью-Джерси (редактор), «Последовательность A188545» , Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS
^ Восе, М. (1985), «Египетские дроби», Бюллетень Лондонского математического общества , 17:21 , doi : 10.1112/blms/17.1.21 , MR 0766441
^ Эрдеш, Пал (1950), «Аз $\textstyle {\frac {1}{x_{1}}}+{\frac {1}{x_{2}}}+\cdots +{\frac {1}{x_{n}}}={\frac {a}{b}}$ о целочисленных решениях уравнения» [Об одном диофантовом уравнении] (PDF) , Matematikai Lapok (на венгерском языке), 1 : 192–210, MR 0043117

[mkg-1] Jump up to: Перейти обратно: ^а ^б Монган, Джон; Киндлер, Ной Суоянен; Жигер, Эрик (2012), «Горящие предохранители» , «Разоблаченные интервью по программированию: секреты получения следующей работы» (3-е изд.), John Wiley & Sons, стр. 234, ISBN 978-1-118-28720-0

[brumbaugh-2] Jump up to: Перейти обратно: ^а ^б Брамбо, Дуглас К. (2013), Преподавание математики в средней школе , Routledge, стр. 191 , 309 , ISBN 978-1-136-75622-1

[haselbauer-3] Jump up to: Перейти обратно: ^а ^б Хазельбауэр, Натан (2020), 60-секундные головоломки без карандашей: короткие головоломки от простого до почти невозможного , Fair Winds Press, стр. 77 , 121 , ISBN 978-1-63159-927-9

[winkler-4] Jump up to: Перейти обратно: ^а ^б ^с Винклер, Питер (2004), «Использование предохранителей», Математические головоломки: Коллекция знатоков , AK Peters, стр. 2, 6, ISBN 1-56881-201-9

[hess-5] Хесс, Дик (2009), «Часы на шнурках» , Головоломки Математиков всех звезд , Официальные книги головоломок Mensa, стр. 9, ISBN 978-1-4027-5528-6

[6] Джефф Эриксон, Плавные числа

[enx-7] Jump up to: Перейти обратно: ^а ^б ^с ^д Эриксон, Джефф; Ниваш, Габриэль; Сюй, Цзюньян (июнь 2021 г.), «Плавкие числа и арифметика Пеано» , Труды 36-го ежегодного симпозиума ACM/IEEE по логике в информатике (LICS 2021) , IEEE, стр. 1–13, arXiv : 2003.14342 , doi : 10.1109 /lics52264.2021.9470703

[A188545-8] Слоан, Нью-Джерси (редактор), «Последовательность A188545» , Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS

[vose-9] Восе, М. (1985), «Египетские дроби», Бюллетень Лондонского математического общества , 17:21 , doi : 10.1112/blms/17.1.21 , MR 0766441

[erdos-10] Эрдеш, Пал (1950), «Аз $\textstyle {\frac {1}{x_{1}}}+{\frac {1}{x_{2}}}+\cdots +{\frac {1}{x_{n}}}={\frac {a}{b}}$ о целочисленных решениях уравнения» [Об одном диофантовом уравнении] (PDF) , Matematikai Lapok (на венгерском языке), 1 : 192–210, MR 0043117

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]