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

Визуализация головоломки с горением веревки: горизонтальная ось обозначает прошедшее время в секундах, а вертикальная ось обозначает оставшееся время горения веревки (а не ее длину).

1. Если зажечь один конец (красная линия) веревки (коричневая линия), она сгорит за 60 с.
2. При освещении обоих концов он сгорает за 30 с.
3. Стандартное решение с двумя веревками: изначально у первой горят оба конца, а у второй - только один. Перегорание первой веревки вызывает зажигание второго конца второй веревки (синяя стрелка), которое сгорает в общей сложности за 45 с.
4. Альтернативное решение, когда вторая веревка изначально не зажжена. Перегорание первой веревки вызывает загорание обоих концов и случайной точки второй веревки. Каждый раз, когда сгорает сегмент, на оставшейся веревке загорается случайная точка. Теоретически вторая веревка сгорает за 15 с, что в сумме дает 45 с.

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

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

Пример

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

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

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

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

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

Визуализация наименьших плавких чисел больше 0, 1 и 2: ⁠ 1 / 2 ⁠ , 1 ⁠ 1/8 ​ ⁠ и 2 ⁠ 1/1024 ⁠ шрифт ) соответственно (жирный

В обычных вариантах задачи каждый предохранитель действует в течение единичного периода времени, и единственные операции, используемые или разрешенные в решении, - это зажигание одного или обоих концов предохранителя в известное время, определяемое либо как начало решения, либо как начало решения. как раз сгорит еще один предохранитель. Если одновременно горит только один конец предохранителя $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}}$ является плавким числом.

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

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

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

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

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

История

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

См. также

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