 Up to Home Maths Site Map | Text version

# 1's and 0's - Puzzle + Solution

## The Puzzle

This puzzle was posted at www.mathpuzzle.com:

 This week's puzzle comes from Juha Saukkola, who helped me tremendously with my Leaper's page.   3x37=111, 4*25=100, 6*185=1110, 1999*5502751375687899=11000000000000110101.  Is any integer n a perfect divisor of a larger integer N which consists entirely of ones and zeroes?  If so, prove it ( Send Proof).  Rick Heylen has calculated n = 1 to 2000. Does anyone see any patterns or revalations?

## An elegant proof of the existence of N

This proof was devised by Erich Friedman:

Divide n into 1, 11, 111, 1111, 11111 .... and note the remainder. By the Pigeonhole Principle, eventually a remainder will repeat. Subtract.

## Fred's Tortuous (but directly constructive!) Solution

The answer is yes - any positive integer n is a perfect divisor of some number N which consists entirely of ones and zeroes.  The requirement that N > n is trivial since if n = N can only occur if n itself is a series of 1's and 0's ; take N = 10n.

Proof:

I've tried to make this proof understandable to people who aren't into number theory.  The decimal expansion of 1/n is a pattern:
<leading digits> <decimal point> <0 or more non-repeating digits> <r =1-or-more digits, infinitely repeated>, e.g.:

 n 1/n leadingdigits decimalpoint 0 or more non-repeating digits r digitsrepeated forever r 1 1.0000 ... 1 . 0 1 22 0.0454545 ... 0 . 0 45 2 42 0.02380950238095 ... 0 . 0 238095 6 96 .0104166666 ... 0 . 01041 6 1

[ Note: If you haven't seen that result before, the statement can be seen to be true by looking what happens in the process of expanding 1/n by long division of n into 1.00000 ; at each step in the long division, you have to carry over a remainder ; the remainder is < n, so there are only so many remainders you can carry over, so you eventually have to repeat yourself by carrying over some previously carried-over remainder - all further digits obtained in the expansion after that point will be repeats of digits previously expanded ]

Once we have the expansion ending in 'r' repeating digits, we can multiply by 10^r and subtract the original to get a terminating decimal, e.g.:

 n r (# of digitsrepeated) 10^r 1 1 10 10/n 10.0... 1/n 1.0... 9/n 9.0... 22 2 100 100/n 4.54545... 1/n 0.04545... 99/n 4.50000... 42 6 1000000 1000000 / n 23809.5238095238095... 1 / n 0.0238095238095... 999999 / n 23809.5000000000000... 96 1 10 10 / n 0.1041666666... 1 / n 0.0104166666... 9 / n 0.0937500000...

In each case we end up with:

999...999/n = <some number with k decimal places>   (there are r 9's)

We can multiply both sides by 10^k to obtain:

999...999000...000 / n = <some number>       (there are k zeros)

999...999000...000 = n * <some number>

Dividing both sides by 9 we get

111...111000...000 = n * <some number> / 9
or written another way:
(r 1's) (k 0's)

If the left side has 'd' digits altogether (r 1's and k 0's so d=r+k), we can multiply both sides by the number:

1 (d 0's) 1 (d 0's) .... 1 (d 0's) 1       where there are 9 1's, each separated by d 0's.
This number is divisible by 9 (since the sum of its digits = 1+1+1+1+1+1+1+1+1 = 9)

We end up with:

(r 1's)(k 0's)(r 1's)(k 0's)(r 1's)(k 0's)(r 1's)(k 0's)(r 1's)(k 0's)(r 1's)(k 0's)(r 1's)(k 0's)(r 1's)(k 0's)(r 1's)(k 0's)
= n * <some number> / 9 *     1 (d 0's) 1 (d 0's) 1 (d 0's) ....
= n * <some number> / 9 * <some other number> * 9
= n * <some number> * <some other number>

I.e. n is an exact divisor of some number whose decimal representation consists only of 1's and 0's.

Examples:

 n 1 9 = 9 * 1 / 1 1 = 1 111111111 = 1 x 111111111 (ok, that's overkill) 22 990 = 22 * 45 110 = 22 * 45 / 9 110110110110110110110110110 = 22 * 45 * some-horrible-number 42 9999990 = 42 * 238095 1111110 = 42 * 238095 / 9 111111011111101111110111111011111101111110111111011111101111110 =  42 * yuck 96 900000 = 96 * 9375 100000 = 96 * 9375 / 9 100000100000100000100000100000100000100000100000100000 = 96 * yuck This pagelast changed:6 Sep 2002 [Validate HTML] Donate freefood & land Anzwers Google Websters Dict. Wiktionary Roget's Thes. Open Directory WikiPedia Google News FTP -- English FTP -- Russian Tellaseek Tucows FileDudes Debian Linux MetaCrawler Alta Vista Yahoo RPM Find Perl Modules Search4Science f2.org - This site for Feedback by emailor Web form