Zeroes, Ones, and Twos

27 Mar 2012

I thought I would practice Google CodeJam on 22dn of March. Today is 27th of March already. Gosh, I'm so dead.

Anyway, here is the today's problem:

Problem Statement

Let `n` be a natural number.

Prove that:

The 1st axiom

First of all, a natural number is 1, 2, 3, and so on.

Let's say `x = ny. We say that ``x` is a multiple ofn``, or `nhas a multiple ``x```.

We need to prove that `x` multiplies some number will result in something look like 11011101.

How on earth do we prove that?

Let's try some weird number, for example, 7. 7 multiplies something and results in `x`.

Wow, this is difficult.

Let's analyze a single term:

What is the point? Let's think in a different way. Ok, I don't have any other idea… Let's look at the solution.

The solution

It's actually quite genius. This is how the book finds a wanted multiple.

Let's say we have a set of {1, 11, 111, 1111, 11111, 111111, 1111111, 11111111}.

The set contains 8 numbers. `x mod 7` can generate only 7 different residues.

Therefore, there must be at least 2 numbers having the same residue.

In this case, they are 1111111 and 1 having the same residue, which is 1. Therefore, 1111111 - 1 = 1111110 is a multiple of 7. (On a side note, 111111 also happens to be a multiple of 7.)

This also shows that we won't go beyond `n+1` digits. Genius!

The 2nd axiom

Ok, this time I'll prove it myself.

We probably can use the same technique. It's called the pigeon-hole theory, by the way.

Here is the technique:

  1. We construct a set of (2^n+1) numbers. It guarantees that at least 2 of them have the same residue.
  2. Any pair subtracting each other must result in something like 12121221.

A subtraction of 2222222 and 1010101 will result in a valid number. Oh god, I'm stupid.

ํYou know? There are 2^n number from 0 to 1111… (n digits). What a coincidence!

Plan A

What if I prove that the set {0 ,1 , 10, …, 1111…(n digits)} can generate every number from 0 to 2^n-1?

Why the fuck do I keep coming back to this equation? You can see how desperate I am... Let's analyze ```10^a mod 2^n``` where a < n.

I've got nothing.

Plan B

If {0 ,1 , 10, …, 1111…(n digits)} can generate every number from 0 to 2^n-1, it must map 1-1.

From i-th to (i+1)-th, we shall add 1 or 8..89.

a[i+1] = a[i] + 1 if (a[i]%2) == 0

a[i+1] = a[i] + 88..89 if (a[i]%2) == 1

Still going nowhere.

Giving up

Let's look at the solution.

So, the book uses induction…

Let's say we have a number `xcontaining only 1s and 2s, and assume that ``x``` is divisible by 2^k.

If we put 1 in front, we will have `x + (2^k 5^k)`.

If we put 2 in front, we will have `x + 2(2^k 5^k) = x + 2^k 5^k + 2^k 5^k`.

The book claims that either of them must be divisible by `2^(k+1)`.

Since `x = y 2^k, then ``(y 2k) + (2k 5k) = (y + 5k) 2^k```

And `x + 2(2^k 5^k) = (y 2^k) + (2^k 5^k) + (2^k 5^k) = (y + 2 5^k) 2^k`

if `yis divisible by ``2`, then(y + 2 5^k) 2^k`` is divisible by `2^(k+1)`.

if `yis NOT divisible by ``2`, then(y + 5^k)`` is divisible by `2, which means ``(y + 5k) 2k` is divisible by2^(k+1)``.

Wow, what the heck that is! This just proves that we can start with `k=1and walk to any ``k```…

So, the 2nd axiom is proved.

Reflection

I have no chance whatsoever to solve this problem.

The solution seems arbitrary to me. The two axioms are so similar, but the solutions are very different.

And the solutions require more than a few mental steps.

For example, when the book says that it is divisible by `2^(k-1)`, it took me like 15 minutes to figure out why it is the case….

Gosh, I'm stupid.

Give it a kudos