636
ANDREW
SIMOSON
[August-September
The author is grateful to Professor
S.
Zaks for suggesting the problem.
REFERENCES
1.
S.
Zaks
and
C.
L.
Liu, Decomposition of Graphs into Trees, Proc. 8th
S. E.
conf.,
Combinatorics,
Graph Theo~ and Computing,
643-654.
Fermat's Last Theorem in Combinatorial Form
W.
V.
QUNE
Department of Philosophy, Harvard University, Cambridge,
MA
02138
Fermat's Last Theorem can be vividly stated in terms of sorting objects into a
row of bins, some of which are red, some blue, and the rest unpainted. The theorem
amounts to saying that when there are more than two objects, the following
statement is never true:
STATEMENT.The number of ways of sorting them that shun both colors is equal to
the number of ways that shun neither.
I shall show that this statement is equivalent to Fermat's equation xn
+
yn
=
zn,
when n is the number of objects, z is the number of bins, x is the number of bins
that are not red, and y is the number of bins that are not blue. There are zn ways of
sorting the objects into bins; xn of these ways shun red and yn of them shun blue.
So where A is the number of ways that shun both colors, B is the number of ways
that shun red but not blue, C is the number of ways that shun blue but not red, and
D is the number of ways that shun neither, we have
xn=A+B, yn=A+C, zn=A+B+C+D.
These equations give xn
+
yn
=
zn if and only if A
=
D, which is to say, if and only
if the statement above holds.
A
Difference Equation for Strings of Ones
ANDREWSIMOSON
Mathematics Department, King College, Bristol,
TN
37620
The classic proof
[2,
pp. 122-31 that
almost every number in its binary expansion contains arbitrarily
long strings of the digit
1
(*
>
can be translated into an elegant difference equation argument, as shown below.
In this note, for each number such as which has a dual binary expansion,
interpret its binary expansion as the one terminating in all zeroes. Let
I
be the half
open interval [0, 1). For each positive integer n, let Bn be the set of numbers in
I
containing no string of n 1's in their binary expansions. To prove
(*)
it is sufficient
to show that Bn has measure zero. For all integers k
2
0, 0
I
j
<
n, let Y,(k) be the