Opinion
Computing Applications Last byte

Puzzled: 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?
Posted
  1. 1. Multiples with just zeroes and ones.
  2. 2. Multiples that are Fibonacci numbers.
  3. 3. Perfect number m.
  4. Author

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 boxes, some box must contain at least two items.

Suppose the two numbers with the same remainder are mi and mj, with i < j. Now subtract the smaller from the larger. The resulting number, mimj, consisting of ji ones followed by i zeroes, must be a multiple of n.

Now try it for n = 12; the numbers m1 through m13 and their remainders begin:

ueq01.gif

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 × 925.

Back to Top

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 eventually 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 observation is that it does no harm to imagine that the Fibonacci numbers start with 0, 1, instead of the customary 1, 1.

This cute puzzle was given to me over lunch by Richard Stanley of MIT. For more, Gregg Musiker of the University of Minnesota recommends a paper by D.D. Wall: “Fibonacci Series Modulo m” in American Mathematical Monthly 67 (1960), 525–532.

Back to Top

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.

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More