solutions and sources
Last month (Aug. 2011, p. 120) we posted a trio of brainteasers, including one
as yet unsolved, concerning divisibility of numbers. Here, we offer solutions
to two of them and a remark about the third. How did you do?
1.multiples with just zeroes and ones.
Solution. You were asked to determine
whether every positive integer divides
a number containing only zeroes and
ones in its base- 10 representation.
Seems reasonable. Suppose your number is n, and someone gives you a large
random number m. If you now compute
the remainder when m is divided by n,
you get some number between 0 and
n− 1; the remainder is denoted m mod
n. If m mod n = 0, m is a multiple of n,
you might expect this to happen about
one time in n. There are infinitely many
numbers with base- 10 representations
containing only zeroes and ones, so unless there is some good reason why not,
lots of them ought to be multiples of n.
But how to prove it?
One clever way was suggested by
Muthu Muthukrishnan of Rutgers University: Consider the numbers 1, 11,
111, 1111, etc. up to 111... 1, where the
last number has n+ 1 digits. Call these
numbers m1, m2, ... , mn+ 1. Each has a
remainder when divided by n, and two
of these remainders must be the same.
Why? Because there are n+ 1 of them
but only n values a remainder can take.
This is an application of the famous
and useful “pigeonhole principle”;
that is, if n+ 1 items are put into n box-es, some box must contain at least two
Suppose the two numbers with the
same remainder are mi and mj, with i < j.
Now subtract the smaller from the larg-
er. The resulting number, mi − mj, con-
sisting of j – i ones followed by i zeroes,
must be a multiple of n.
We can stop here because we’ve
already found two numbers with the
same remainder, 11. Subtracting them
gives 11100, which must then have remainder 0; indeed, 11100 = 12 x 925.
2.multiples that are fibonacci numbers.
Solution. Does every n divide some Fibonacci number? Again, since there
are infinitely many Fibonacci numbers, it seems plausible that the answer
would be “yes.” We can tackle it the
same way as in the first solution, using
remainders mod n.
This time, it makes sense to keep
track of remainders mod n for each
consecutive pair of Fibonacci numbers. Note, if the remainders are, say,
r and s, then the remainders for the
next (overlapping) pair of Fibonacci
numbers are s and r+s mod n, and the
remainders for the previous pair of Fibonacci numbers are r and s-r mod n.
Now try this for n = 7; the remainder
pairs are ( 1, 1); ( 1, 2); ( 2, 3); ( 3, 5); ( 5, 1);
( 1, 6); ( 6,0)... Having hit a zero, you now
have our multiple of 7.
How do you know you will eventu-
ally hit a zero? It follows from three
observations: there are only finitely
many (n2, to be exact) possible pairs of
remainders; since the process can run
backward, as well as forward, it must
eventually cycle back to where it began;
and the process can start with the pair
(0, 1). The point behind the third obser-
vation is that it does no harm to imag-
ine that the Fibonacci numbers start
with 0, 1, instead of the customary 1, 1.
3.Perfect number m. Solution. The problem was to
determine whether there are any odd
perfect numbers, a famously difficult
question. But why has it attracted so
much attention over the centuries?
One possible answer is that the odd-perfect-number problem is an example
of looking for ways in which numbers
do, or do not, behave randomly. But
maybe the best answer is that such
a question is like a disease to which
some of us are immune and others
highly susceptible. You probably know
in which category you belong.
Peter Winkler ( email@example.com) is William
Morrill Professor of Mathematics and Computer science
at Dartmouth College, hanover, nh.
All readers are encouraged to submit prospective
puzzles for future columns to firstname.lastname@example.org.