Friday, December 29, 2006

Math is Fun

Here's another math problem to wrestle with while counting down to the New Year.

Find the smallest positive integer (base 10), composed entirely of the digits 0 and 1 that is divisible by 225.

7 comments:

Kimota94 aka Matt aka AgileMan said...

All numbers are divisible by 225, silly!

Jimmy said...

evenly divisible by 225....billy.

Kimota94 aka Matt aka AgileMan said...

Based on the fact that I don't even know how to begin to solve this, I'm going to guess it has something to do with using calculus to determine a minimum (something I can't even remember how to do, without looking it up).

I think I could write a Java program to determine the answer, through brute force, faster than I could ever figure this out mathematically. Sigh.

cjguerra said...

Heh - look at the last problem - that will give you a hint. First take the number 225 and prime factor it. This is a good idea with any number-theory problems - kinda like putting fractions into lowest-common-denominators. We have 5*5*3*3 or 5^2*3^2.

From here, I'm stuck. All I know for sure is that the last number has to be a 2 because 5*2 ends in 0. 225*52 is a reasonable guess (11700), but that is a simple multiplication and not a proof, which is what is needed.

Kimota94 aka Matt aka AgileMan said...

But 11700 has that nasty "7" in it, Chris. Did I misunderstand what the question was asking?

Jimmy said...

Chris is on the right track...

Notice that 225 = 9*25.

Think about what properties multiples of both those number have... (see previous post about divisibility rules too...)

Anonymous said...

Since 225 = 9x25, we know the number in question has to end in 00.

Also, you can quickly determine if any positive integer is divisible by 9 by adding up the (base 10) digits in that number.

Using those two facts, the smallest positive base 10 integer that (a) consists of only the digits 0 and 1, and (b) is equal to 225 * k, where k is also an integer, must be:

11,111,111,100