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:

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.:

[ 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.:

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:

This page last changed: 6 Sep 2002 [Validate HTML]

Donate free food & 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 email or Web form