Pick-up Sticks and the Fibonacci Factorial
Aidan Sudbury, Arthur Sun, David Treeby, Edward Wang · 2025
Read Pick-up Sticks and the Fibonacci Factorial by Aidan Sudbury, Arthur Sun, David Treeby, Edward Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19911.txt.
Introduction
Four mathematicians, Aidan Sudbury, Arthur Sun, David Treeby, and Edward Wang, study a chance puzzle about broken sticks. They imagine stick lengths drawn at random, then ask how likely it is that no three of them can form a triangle.
Their answer links the puzzle to the famous Fibonacci numbers. The chance of avoiding a triangle equals one divided by the product of the first Fibonacci numbers, one for each stick. The paper proves this neat result and then extends the same idea to four-sided shapes and to shapes with more sides. It is a short, clean piece of probability work with a surprising pattern at its core.
Catalog record
| CREATOR | Aidan Sudbury, Arthur Sun, David Treeby, Edward Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 10 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19911
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pick-up Sticks and the Fibonacci Factorial
Aidan Sudbury, Arthur Sun, David Treeby, Edward Wang
Abstract
. We present a variation of the broken stick problem in which n n stick lengths are sampled uniformly at random. We prove that the probability that no three sticks can form a triangle is the reciprocal of the product of the first n n Fibonacci numbers. Extensions to quadrilaterals and general k k -gons are also discussed.
1.
Picking up (not breaking) sticks
The
broken stick problem
asks: what is the probability that three segments can form a triangle when a stick is broken at two random points? This problem dates back at least to L. J. Rogers in 1897
[
5
]
, and is now considered a classic in geometric probability. The modern treatment appears in the work of von Mises and was popularised by Feller in his seminal probability text. Since then, the broken stick problem has inspired numerous generalizations. Andrea and Gómez
[
1
]
extended it to arbitrary numbers of break points, while Mukerjee
[
3
]
recently gave closed-form expressions for the probability that a random selection of
k
pieces from a stick broken into
n
parts can (or cannot) form a
k
-gon, using order statistics and linear transformations.
Verreault
[
6
]
approached the broken stick problem from a discrete perspective using MacMahon Partition Analysis, providing generating functions for configurations that avoid
k
-gon formation and give exact enumerative results.
By contrast, in the “pick-up sticks” or
stick sampling
model, we select
n
stick lengths independently and uniformly at random from the interval
[0,1]
. This changes the nature of the problem substantially: the segments are no longer constrained to sum to 1, and their lengths are statistically independent. Peterson and Tenner
[
4
]
considered the probability that
n
such sticks can form an
n
-gon, showing that this occurs with probability
1-\frac{1}{(n-1)!}
. Equivalently, the probability that the
n
sticks
cannot
form an
n
-gon is
\frac{1}{(n-1)!}
.
In this paper, we examine a novel variation within the stick sampling model: we determine the probability that
no three
of the
n
sampled sticks can form the side lengths of a triangle. The surprising result is that this probability is given by
\frac{1}{F_{1}F_{2}\cdots F_{n}},
where
F_{n}
denotes the
n
th Fibonacci number. This reveals an uncommon appearance of the
Fibonorial
in a natural probabilistic context. Later, we extend our method to determine the probability that no four sampled sticks can form a quadrilateral, and more generally, to configurations avoiding any
k
-gon.
2.
Main result
Theorem 1
.
If
n
real numbers are chosen uniformly from the unit interval
[0,1]
, the probability that no three of the numbers can form a triangle is
\prod_{i=1}^{n}\frac{1}{F_{i}},
where
F_{n}
are the Fibonacci numbers defined by
F_{1}=1
,
F_{2}=1
, and
F_{n}=F_{n-1}+F_{n-2}
for
n>2
.
Proof.
Let
U_{1},U_{2},\dots,U_{n}
be independent and identically distributed uniform random variables on
[0,1]
, each representing the length of a stick. Their
order statistics
, denoted
U_{(1)},U_{(2)},\dots,U_{(n)}
, are obtained by sorting them into an increasing sequence, such that
U_{(1)}\leq U_{(2)}\leq\dots\leq U_{(n)}.
The criterion that no triangle can be formed from any triple translates into satisfying
U_{(a)}+U_{(b)}<U_{(c)}
for all
a<b<c
, which reduces to satisfying
(1)
U_{(i)}+U_{(i+1)}<U_{(i+2)}
for all
1\leq i\leq n-2
.
It is well known that the cumulative sums of exponential variables give a uniform distribution
[
2
]
. In other words, we may write
U_{(1)}=\frac{X_{1}}{S},U_{(2)}=\frac{X_{1}+X_{2}}{S},\dots,U_{(n)}=\frac{X_{1}+\dots+X_{n}}{S},
where
S=X_{1}+\dots+X_{n+1}
for independent and identically distributed exponential variables
X_{i}\sim\mathrm{Exp}(1)
each having the probability density function
f(x)=e^{-x}
.
Substituting this into (
1
) yields
\displaystyle\frac{X_{1}+\dots+X_{i}}{S}+\frac{X_{1}+\dots+X_{i+1}}{S}
\displaystyle<\frac{X_{1}+\dots+X_{i+2}}{S}
\displaystyle X_{1}+\dots+X_{i}
\displaystyle<X_{i+2},
where
1\leq i\leq n-2
. This amounts to ensuring all of
\displaystyle X_{1}
\displaystyle<X_{3}
\displaystyle X_{1}+X_{2}
\displaystyle<X_{4}
\displaystyle\mathmakebox[\widthof{{}<{}}][c]{\vdots}
\displaystyle X_{1}+\dots+X_{n-2}
\displaystyle<X_{n},
hold simultaneously, with
X_{1}
and
X_{2}
being unbounded between
0
and infinity. Denoting
P_{n}
as the probability that no triangle can be formed from
n
sticks, we repeatedly integrate
X_{i}
whilst satisfying the above inequalities to obtain
\displaystyle P_{n}
\displaystyle=\int_{0}^{\infty}e^{-x_{1}}\int_{0}^{\infty}e^{-x_{2}}\int_{x_{1}}^{\infty}\dots\int_{x_{1}+\dots+x_{n-2}}^{\infty}e^{-x_{n}}\,dx_{n}\cdots dx_{3}\,dx_{2}\,dx_{1}
\displaystyle=\int_{0}^{\infty}\int_{0}^{\infty}\int_{x_{1}}^{\infty}\dots\int_{x_{1}+\dots+x_{n-2}}^{\infty}e^{-(x_{1}+\dots+x_{n})}\,dx_{n}\cdots dx_{3}\,dx_{2}\,dx_{1}.
The innermost integral evaluates to
\int_{x_{1}+\dots+x_{n-2}}^{\infty}e^{-(x_{1}+\dots+x_{n})}\,dx_{n}=e^{-(2(x_{1}+\dots+x_{n-2})+x_{n-1})}.
We can prove inductively that after integrating
i
times, we are left with integrals of the form
I_{i}=\frac{1}{F_{1}\cdots F_{i}}\int_{x_{1}+\dots+x_{n-i-2}}^{\infty}e^{-(F_{i+2}(x_{1}+\dots+x_{n-i-1})+F_{i+1}x_{n-i})}\,dx_{n-i}.
The base case obviously holds, and the induction is completed with the fact that
I_{i}
evaluates to
I_{i}=\frac{1}{F_{1}\cdots F_{i}F_{i+1}}e^{-(F_{i+3}(x_{1}+\dots+x_{n-i-2})+F_{i+2}x_{n-i-1})}.
We thus obtain
\displaystyle P_{n}
\displaystyle=\int_{0}^{\infty}\int_{0}^{\infty}I_{n-3}\,dx_{2}\,dx_{1}
\displaystyle=\int_{0}^{\infty}\int_{0}^{\infty}\frac{1}{F_{1}\cdots F_{n-2}}e^{-(F_{n}x_{1}+F_{n-1}x_{2})}\,dx_{2}\,dx_{1}
\displaystyle=\int_{0}^{\infty}\frac{1}{F_{1}\cdots F_{n-1}}e^{-(F_{n}x_{1})}\,dx_{1}
\displaystyle=\frac{1}{F_{1}\cdots F_{n}},
which is the desired result.
∎
3.
Quadrilateral extension
Let us now explore a generalization, extending the problem to finding the probability that no
quadrilateral
can be formed from any
four
sticks.
Theorem 2
.
If
n
real numbers are chosen uniformly from the unit interval
[0,1]
, the probability that no four of the numbers can form a quadrilateral is
\frac{1}{T_{n}-T_{n-2}}\prod_{i=1}^{n-1}\frac{1}{T_{i}},
where
T_{k}
are the
Tribonacci
numbers defined by
T_{1}=1
,
T_{2}=1
,
T_{3}=2
,
T_{k}=T_{k-1}+T_{k-2}+T_{k-3}
for
k>3
.
Proof.
Again, the inequality can be reduced to simultaneously satisfying
U_{(i)}+U_{(i+1)}+U_{(i+2)}<U_{(i+3)}
for all
1\leq i\leq n-3
.
We utilize the same method of rewriting the order statistics as sums of exponential variables, getting the inequality
\displaystyle\frac{X_{1}+\dots+X_{i}}{S}+\frac{X_{1}+\dots+X_{i+1}}{S}\frac{X_{1}+\dots+X_{i+2}}{S}
\displaystyle<\frac{X_{1}+\dots+X_{i+3}}{S}
\displaystyle 2(X_{1}+\dots+X_{i})+X_{i+1}
\displaystyle<X_{i+3}
which needs to be satisfied for all
i
, leaving
X_{1},X_{2}
and
X_{3}
unbounded.
As before, we must integrate over all the variables to obtain the probability, which we denote
P_{n}
. This gives us
\displaystyle P_{n}
\displaystyle=\int_{0}^{\infty}e^{-x_{1}}\int_{0}^{\infty}\dots\int_{2(x_{1}+\dots+x_{n-3})+x_{n-2}}^{\infty}e^{-x_{n}}\,dx_{n}\,\cdots\,dx_{2}\,dx_{1},
\displaystyle=\int_{0}^{\infty}\int_{0}^{\infty}\dots\int_{2(x_{1}+\dots+x_{n-3})+x_{n-2}}^{\infty}e^{-(x_{1}+\dots+x_{n})}\,dx_{n}\,\cdots\,dx_{2}\,dx_{1}.
Let the integral obtained after
i
integrations be denoted
I_{i}
. For example, we have
I_{0}=\int_{2(x_{1}+\dots+x_{n-3})+x_{n-2}}^{\infty}e^{-(x_{1}+\dots+x_{n})}\,dx_{n}=e^{-(3(x_{1}+\dots+x_{n-3})+2x_{n-2}+x_{n-1})}.
We will show that
I_{i}=\frac{1}{\prod_{k=1}^{i}T_{k}}\int_{2(x_{1}+\dots+x_{n-3-i})+x_{n-2-i}}^{\infty}e^{-(R_{i+1}(x_{1}+\dots+x_{n-2-i})+S_{i+1}x_{n-1-i}+T_{i+1}x_{n-i})}\,dx_{n-i},
where
T_{k}
are the
Tribonacci
numbers defined as
T_{1}=1
,
T_{2}=1
,
T_{3}=2
,
T_{k}=T_{k-1}+T_{k-2}+T_{k-3}
. When we perform the integration, we see that
I_{i}=\frac{1}{\prod_{k=1}^{i+1}T_{k}}e^{-((R_{i+1}+2T_{i+1})(x_{1}+\dots+x_{n-3-i})+(R_{i+1}+T_{i+1})x_{n-2-i}+S_{i+1}x_{n-1-i})}.
It is easy to show that
T_{k}
satisfies the Tribonacci recursion if
\displaystyle R_{k}
\displaystyle=R_{k-1}+2T_{k-1}
\displaystyle S_{k}
\displaystyle=R_{k-1}+T_{k-1}
\displaystyle T_{k}
\displaystyle=S_{k-1},
as seen in the exponent. Hence by induction, we see that
I_{n-4}=\frac{1}{\prod_{k=1}^{n-3}T_{k}}e^{-(R_{n-2}x_{1}+S_{n-2}x_{2}+T_{n-2}x_{3})},
giving us
P_{n}=\int_{0}^{\infty}\int_{0}^{\infty}\int_{0}^{\infty}\frac{1}{\prod_{k=1}^{n-3}T_{k}}e^{-(R_{n-2}x_{1}+S_{n-2}x_{2}+T_{n-2}x_{3})}\,dx_{3}\,dx_{2}\,dx_{1}.
Evaluating this integral yields
P_{n}=\frac{1}{T_{1}\cdots T_{n-2}S_{n-2}R_{n-2}}.
From the recursive definitions of
R
and
S
previously, we have that
S_{n-2}=T_{n-1}
, and that
R_{n-2}=T_{n}-T_{n-2}
, ultimately giving us
P_{n}=\frac{1}{(T_{n}-T_{n-2})T_{1}\cdots T_{n-1}},
as desired.
∎
Observe the presence of a ‘correction term’,
T_{n}-T_{n-2}
. This disrupts an otherwise perfect generalization of Theorem
1
.
4.
An open problem
Our results for triangles and quadrilaterals suggest a deeper underlying structure in the probability that no subset of
n
independently sampled stick lengths can form a
k
-gon. While we have generalized the recursive approach and obtained formulae for small values of
k
, no closed-form expression is known for general
k
, although this has been solved in the “broken-stick” analogue of the problem by Verreault
[
6
]
. This leads us to pose the following problem:
Given
n
independent real numbers chosen uniformly from
[0,1]
, what is the probability that no
k
of them can be arranged to form the side lengths of a
k
-gon?