The author is grateful to Professor
Zaks for suggesting the problem.
Liu, Decomposition of Graphs into Trees, Proc. 8th
Graph Theo~ and Computing,
Fermat's Last Theorem in Combinatorial Form
Department of Philosophy, Harvard University, Cambridge,
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
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
zn if and only if A
D, which is to say, if and only
if the statement above holds.
Difference Equation for Strings of Ones
Mathematics Department, King College, Bristol,
The classic proof
pp. 122-31 that
almost every number in its binary expansion contains arbitrarily
long strings of the digit
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
be the half
open interval [0, 1). For each positive integer n, let Bn be the set of numbers in
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
n, let Y,(k) be the