![Rope burning puzzle](https://upload.wikimedia.org/wikipedia/commons/6/6c/Rope_burning_puzzle.svg)
In
recreational mathematics
Recreational mathematics is mathematics carried out for recreation (entertainment) rather than as a strictly research and application-based professional activity or as a part of a student's formal education. Although it is not necessarily limited ...
, rope-burning puzzles are a class of
mathematical puzzle
Mathematical puzzles make up an integral part of recreational mathematics. They have specific rules, but they do not usually involve competition between two or more players. Instead, to solve such a puzzle, the solver must find a solution that sati ...
in which one is given lengths of rope,
fuse cord, or
shoelace
Shoelaces, also called shoestrings (US English) or bootlaces (UK English), are a system commonly used to secure shoes, boots, and other footwear. They typically consist of a pair of String (cord), strings or cords, one for each shoe, finished o ...
that each burn for a given amount of time, and
match
A match is a tool for starting a fire. Typically, matches are made of small wooden sticks or stiff paper. One end is coated with a material that can be ignited by friction generated by striking the match against a suitable surface. Wooden matc ...
es to set them on fire, and must use them to measure a non-unit amount of time. The fusible numbers are defined as the amounts of time that can be measured in this way.
As well as being of recreational interest, these puzzles are sometimes posed at
job interview
A job interview is an interview consisting of a conversation between a job applicant and a representative of an employer which is conducted to assess whether the applicant should be hired. Interviews are one of the most popularly used devices for ...
s as a test of candidates' problem-solving ability, and have been suggested as an activity for middle school mathematics students.
Example
A common and simple version of this problem asks to measure a time of 45 seconds using only two fuses that each burn for a minute. The assumptions of the problem are usually specified in a way that prevents measuring out 3/4 of the length of one fuse and burning it end-to-end, for instance by stating that the fuses burn unevenly along their length.
One solution to this problem is to perform the following steps:
*Light one end of the first fuse, and both ends of the second fuse.
*Once the second fuse has burned out, 30 seconds have elapsed, and there are 30 seconds of burn time left on the first fuse. Light the other end of the first fuse.
*Once the first fuse burns out, 45 seconds have elapsed.
Many other variations are possible, in some cases using fuses that burn for different amounts of time from each other.
Fusible numbers
In common versions of the problem, each fuse lasts for a unit length of time, and the only operations used or allowed in the solution are to light one or both ends of a fuse at known times, determined either as the start of the solution or as the time that another fuse burns out. If only one end of a fuse is lit at time
, it will burn out at time
. If both ends of a fuse are lit at times
and
, it will burn out at time
, because a portion of
is burnt at the original rate, and the remaining portion of
is burnt at twice the original rate, hence the fuse burns out at
:
.
A number
is a fusible number if it is possible to use unit-time fuses to measure out
units of time using only these operations. For instance, by the solution to the example problem,
is a fusible number.
One may assume without loss of generality that every fuse is lit at both ends, by replacing a fuse that is lit only at one end at time
by two fuses, the first one lit at both ends at time
and the second one lit at both ends at time
when the first fuse burns out.
In this way, the fusible numbers can be defined as the set of numbers that can be obtained from the number
by repeated application of the operation
, applied to pairs
that have already been obtained and for which
.
The fusible numbers include all of the non-negative
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s, and are a
well-order
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-orde ...
ed subset of the
dyadic rational
In mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in compute ...
numbers, the fractions whose denominators are
powers of two
A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent.
In a context where only integers are considered, is restricted to non-negative ...
. Being well-ordered means that, if one chooses a decreasing sequence of fusible numbers, the sequence must always be finite. Among the well-ordered sets, their ordering can be classified as
, an
epsilon number (a special case of the infinite
ordinal number
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the least n ...
s). Because they are well-ordered, for each integer
there is a unique smallest fusible number among the fusible numbers larger than
; it has the form
for some
. This number
grows very rapidly as a function of
, so rapidly that for
it is (in
Knuth's up-arrow notation
In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976.
In his 1947 paper, R. L. Goodstein introduced the specific sequence of operations that are now called ''hyperoperati ...
for large numbers) already larger than
. The existence of this number
, for each
, cannot be proven in
Peano arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
.
Lighting more than two points of a fuse
If the rules of the fuse-burning puzzles are interpreted to allow fuses to be lit at more points than their ends, a larger set of amounts of time can be measured. For instance, if a fuse is lit in such a way that, while it burns, it always has three ends burning (for instance, by lighting one point in the middle and one end, and then lighting another end or another point in the middle whenever one or two of the current lit points burn out) then it will burn for 1/3 of a unit of time rather than a whole unit. By representing a given amount of time as a sum of
unit fraction
A unit fraction is a rational number written as a fraction where the numerator is one and the denominator is a positive integer. A unit fraction is therefore the reciprocal of a positive integer, 1/''n''. Examples are 1/1, 1/2, 1/3, 1/4, 1/5, et ...
s, and successively burning fuses with multiple lit points so that they last for each unit fraction amount of time, it is possible to measure any
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
of units of time. However, keeping the desired number of flames lit, even on a single fuse, may require an infinite number of re-lighting steps.
The problem of representing a given rational number as a sum of unit fractions is closely related to the construction of
Egyptian fractions, sums of distinct unit fractions; however, for fuse-burning problems there is no need for the fractions to be different from each other. Using known methods for Egyptian fractions one can prove that measuring a fractional amount of time
, with