Communications of the ACM

Last byte

Puzzled: Solutions and Sources

By Peter Winkler
Communications of the ACM, September 2011, Vol. 54 No. 9, Page 110
10.1145/1995376.1995401
Comments

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 m₁, m₂, ..., m_n+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 m_i and m_j, with i < j. Now subtract the smaller from the larger. The resulting number, m_i − m_j, consisting of j − i ones followed by i zeroes, must be a multiple of n.

Now try it for n = 12; the numbers m₁ through m₁₃ and their remainders begin:

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 (n², 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

The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.

---

No entries found