acm-header
Sign In

Communications of the ACM

Last byte

Puzzled: Solutions and Sources


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

Author

Peter Winkler ([email protected]) is William Morrill Professor of Mathematics and Computer Science at Dartmouth College, Hanover, NH.


©2011 ACM  0001-0782/11/0900  $10.00

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.

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


 

No entries found