There is an old riddle concerning the clever burning of fuses. It is originally attributed to Carl Morris, and usually boils down to something like the following:
You have two fuses, each guaranteed to burn for one time unit. They may burn at irregular rates mid-fuse, but if you light an end, it will reliably reach the other end in exactly one time unit. Using these two fuses, can you measure out a time of 3/4 time units?
The time units involved may be either minutes or hours, and the fuses might also be ropes, string, or other common burnable lengths. The solution requires a spot of lateral thinking:
If you were to light one fuse at both ends, they will both burn through to somewhere in the middle in exactly 1/2 time units, because it is burning twice as fast as when only a single end is lit. Thus, lighting both ends of fuse A and one end of fuse B will burn through A completely in 1/2 time unit, leaving exactly 1/2 time unit of fuse B remaining. Lighting the second end of fuse B now will burn through the remaining 1/2 time unit twice as fast, resulting in 1/2 + 1/4 = 3/4 time units.
____ __ t = 3/4
/ \
_|_ | __ t = 1/2
/ \ |
| | |
| | |
| | | __ t = 0
Of course this is a neat little puzzle, but can't you do more with it, besides just integral, 1/2 and 3/4 time units? Which times can you exactly measure with an infinite set of 1 time unit fuses?
Enter the fusible numbers.
Consider a new mathematical operator, the ~, defined by
a ~ b = 1⁄2(a + b + 1)
Conceptually, a ~ b (read "a fuse b") represents the time at which a fuse burns out when one end is lit at time a and the other at time b. It only works properly for |a - b| < 1, as you can't light a fuse's end longer than 1 time unit after you lit the other one, but other than that, the model fits perfectly. Some properties:
x ~ y = y ~ x [~ is commutative]
(x ~ y) ~ z ≠ x ~ (y ~ z) [~ is not associative]
(x ~ y) + z = (x + z) ~ (y + z) [+ distributes over ~]
k(x ~ y) ≠ kx ~ ky [* does not (k ≠ 1)]
Using the ~ operator, the set of fusible numbers is defined as follows:
- 0 is a fusible number
- If a and b are fusible numbers, a ~ b is fusible
- Only numbers constructed by the preceding rules are fusible
So what are the first few fusible numbers?
This infinite sequence contains all of the fusible numbers less than 1. Since each of these compounds upon the next in the same fashion, we can take a limit:
limn → ∞ 0 ~ (1 - 2-n) = limn → ∞ 1 - 2-n-1 = 1
This limit value of 1 could also have been derived another way: define an x such that 0 ~ x = x, and solve for it. And, in fact, the infinite sequence of 0 ~ (0 ~ (0 ~ (0 ~ ...))) with the first fuse's second end starting at any number* equals 1. This is a specific case of a more general statement about infinite sequences of n ~ (n ~ (n ~ (n ~ ...))), derived in the way just described:
n ~ x = x
1⁄2(n + x + 1) = x
n + x + 1 = 2x
x = n + 1
That is, that whatever number you begin from, an infinite number of fuses sequentially applied on top of it will mark out closer and closer to the time one time unit after the time when you lit the first end. This is confirmed by some intuitive reasoning—as the burn reaches closer and closer to one time unit after the lighting, the added fuses are closer and closer to being fully extended, as the second end is lit later and later each time.
The astute reader will notice that the operands of
a ~
b must satisfy |
a -
b| < 1, so
n ~ (
n + 1) is not valid; however, this result is an
infinite limit, not an actual fuse
configuration, and in the same way that
an infinitely jagged staircase approaches the limit of √2, there is some leeway in terms of which restrictions apply (and how). Further, there was no pretense of made of this being a
rigorous proof;
the reader is welcome to attempt one of their own. It is
noteworthy, however, that
a ~
a =
a + 1/2, so (
a ~
a) ~ (
a ~
a) =
a + 1, i.e.
a + 1 can still be represented using only fuses.
:
: __ __ (a ~ a)
__.——. —— / \ ~ (a ~ a)
__/_ \ \ __ | |
/ \ | | | |
_|_ | | | __ _|__|_ __ a ~ a
/ \ | | | / \
| | | | | | |
| | | | | | |
| | | | | __ t = 0 | | __ a
- L I M I T S - - A D D I N G O N E -
Having investigated this aspect thoroughly using the power of simple algebra, let's move on to more ambitious omphaloskepsis.
First, we recognize that an fusible number can be written out as a string of 0 and ~, grouped by parentheses. For instance, 3/4 is 0 ~ (0 ~ 0) or (0 ~ 0) ~ 0, and 9/8 is any valid commutative equivalent of (0 ~ 0) ~ ((0 ~ 0) ~ 0). These presentations can be considered as binary trees, with 0s for leaves and ~ operators at every node.
9 % 8 = (0~0)~(0~(0~0))
/ \
/ \
1%2 3%4
/ \ / \
0 0 0 \
1%2
"x%y" is x / \
divided by y 0 0
This isn't particularly relevant to all too much (until you get into the highly technical business), but it provides a nice visualization of the underlying structure of fusible numbers, especially when you consider also the restriction stated earlier, wherein the two fused numbers cannot have a time difference larger than 1 unit between them.
Next, we can define a function. Let m(x)—'m' for margin—be the difference between x and the smallest fusible number > x. It is not immediately clear how to go about finding values for this function, so let's at least reason through some of the first few meaningful values.
m(0) is obviously 1/2, as this is the smallest non-zero fusible number. m(1) can be found by pretty much brute force: 9/8 (depicted above) is the smallest fusible number > 1, so 9/8 - 1 = 1/8, or 2-3. m(2) is significantly harder to find, owing to the varying change in density of the fusible numbers, but m(2) is 1/1024, or 2-10.
value | × 1024 | app.
2+m(2) -----------+--------+------
______↓______ __ 2049/1024 | 2049 | 2.00
_/___ \ __ 961/512 | 1922 | 1.87
/ _\_ | __ 465/256 | 1860 | 1.82
| / _\___ | __ 225/128 | 1800 | 1.76
| | / _\_ | __ 105/64 | 1680 | 1.64
| | | / _\_|___ __ 49/32 | 1568 | 1.53
| | | | / | _\_ __ 21/16 | 1344 | 1.31
| | | | | _|_/_ \ __ 9/8 | 1152 | 1.13
_|_ | | | | / \ | __ 15/16 | 960 | 0.94
/ _\_|_|_ | | | | | __ 7/8 | 896 | 0.86
| / _\_|_|_|_ | | __ 3/4 | 768 | 0.75
| | / _\___|_|_ __ 1/2 | 512 | 0.50
| | | / \ __ 0 | 0 | 0.00
It is at this point that all hell breaks loose.
Jeff Erickson, the original presenter of the idea of fusible numbers at the 2010 Gardner event at UIUC—an annual celebration of mathematics named after the recreational mathematician Martin Gardner—gave a recursive formula for m(x) as
m(x) = 1⁄2 m(x - m(x - 1))
with the mathematics behind the proof a little technical, but not too bad. (See below.) It predicts −log2 m(3) = 1,541,023,937. However, at 33/16 = 2.0625, this formula can be proven to break down, as its prediction for m(31/16) is in direct conflict with the result of m(33/16), mathematically. Therefore, it is liable to be incorrect for values ≥ 33/16.
Another mathematician, Junyan Xu, published a mathematical paper in February 2012 regarding fusible numbers, directly dissecting Erickson's analysis, alongside going into some very rigorous analysis of his own, and even posing an intriguing conjecture that has yet to be proven, potentially linking it to fields like proof theory. The ability to give exact answers for m(x) does not rely on the conjecture, however, and Xu gives a Mathematica program that gives these results. Xu's −log2 m(3) is somewhere on the order of 2 ↑9 16, where ↑9 is Knuth's ninth up-arrow operator. Cutting a long story very short, this value is nothing short of mind-boggingly enormous, making the actual margin value at 3 inordinately small.
For those interested in more information, my continued regurgitation will hardly do it any justice. Sources:* Yes, any valid number: fusibility is considered only in the positive rationals, because (a) there are no negative fusible numbers, and (b) you can't light something earlier than the first time you light something (so it's not accepted by the situation that the model models); and the |a - b| < 1 restriction prevents the second number being greater than 1. And even if all those numbers were allowed, they would still technically make the expression approach 1, though not by the model's specifications.