Home > Science and Puzzles > A Challenging Number Theory Proof – May or May Not Rely on Induction?

A Challenging Number Theory Proof – May or May Not Rely on Induction?

Prove that, for any positive integer N, there exists some positive integer X such that 2^N evenly divides X, where X is composed of N digits which are each either a 1 or a 2.

For example, if N = 2, X = 12, because 2^2 divides 12 and 12 is a 2-digit number composed of 1’s and 2’s.

If N = 3, X = 112, because 2^3 divides 112 and 112 is a 3-digit number composed of 1’s and 2’s.

It may be the case that this proof relies on an inductive argument, showing that it is possible to proceed from N = k to N = k+1 by adding either 10^(k+1) or 2*10^(k+1).

Alternatively, perhaps there is a way to convert an N-digit number composed of 1’s and 2’s into a binary representation by some systematic method that would make the proof more obvious.

Or perhaps we can combinatorially consider all possible values of such an N-digit number and systematically demonstrate that at least one must be the target value.

Good luck.

Advertisements
  1. August 11, 2009 at 8:28 AM

    I have prepared a formal inductive proof.

    To start I will put the facts in plain English, then I will give the actual proof. The facts are simply this: You either add 10^n or 2*10^n when you want to get the (n+1)th term. You add 10^n when your previous number of interest was an odd multiple of 2^n, and you add 2*10^n when your previous number of interest was an even multiple of 2^n. Now to prove that this always works:

    Let P_n be the claim that, for a positive integer n, there exists a positive integer x_n which is divisible by 2^n and whose decimal representation consists of n digits, all of which are digits 1’s or 2’s.

    First off, establish that P_1 is true. Choose x_1 = 2. Clearly 2 is divisible by 2^1 and is a 1-digit number whose decimal representation is, well, 2.

    Now, assume that P_k is true for some positive integer k. Thus we have some x_k such that:

    2^k | x_k

    which is logically equivalent to the statement:

    x_k = (2^k)*q

    where q is some positive integer. Now, q can be even, or q can be odd. There are no other options. If q is even, then it follows that (q/2) is some positive integer, and thus:

    x_k = (2^k)*q = (2^k)*(q/2)*2 = (2^(k+1))*(q/2)

    Thus we have that x_k is divisible by 2^(k+1), which is logically equivalent to the congruence:

    x_k = 0 mod 2^(k+1)

    If q is odd, then it follows that q = 2a + 1 for some positive integer a. Thus we can say:

    x_k = (2^k)*q = (2^k)*(2a + 1) = (2^(k+1))*a + 2^k

    The above equation is logically equivalent to the congruence:

    x_k = 2^k mod 2^(k+1)

    Thus we have shown that x_k must either be congruent to 0 or 2^k mod 2^(k+1).

    If x_k = 0 mod 2^(k+1)

    Then x_k + 2*10^(k) = 0 mod 2^(k+1)

    Because 2*10^(k) = 0 mod 2^(k+1) because 2*10^(k) has k+1 factors of 2 in it.

    If x_k = 2^k mod 2^(k+1)

    Then x_k + 10^(k) = 0 mod 2^(k+1)

    Because 10^(k) = 2^k mod 2^(k+1) because 10^k has only k factors of 2 in it, like the argument used when q is odd.

    Therefore, P_k implies P_(k+1). Since P_1 is true, P_n is true for all positive integers n.

  2. UnicornAnarchist
    August 18, 2010 at 4:43 PM

    You’ve proven existence. For every natural number n, there exists an integer of length n composed solely of digits 1 and 2 which is divisible by 2^n. Now, prove uniqueness! (In fact, there is exactly one number of the form k mod 2^n for every k, 0 < k < 2^n – 1.)

    Can you extend your findings to other pairs of digits? What can you say about collections of digits, like numbers composed solely of the digits {3, 5, 6}? How about collections of digits in other bases? There's much more to be done here!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s