Need help with AMATYC math problem

1. Mar 23, 2009

carlsjo

Does anyone know how to solve this problem:

"Let N be the smallest number divisible by 33 which is greater than 1,000,000 and whose digits are all 0’s and 1’s. What are N’s leading four digits?"

I ran accross this problem in an old AMATYC contest question.

Any help would be much appreciated.

2. Mar 23, 2009

confinement

It is doubtful that the contest would have wanted my one-line Mathematica solution:

In :=
First@Select[
First /@ RealDigits /@
Select[Range[1000000, 2000000], IntegerQ[#/33] &],
Function[s, And @@ (If[# > 1, False, True] & /@ s)]]

Out : =

{1, 1, 0, 1, 1, 1, 1}

Therefore the winner is 1101111 = 33367 * 33

3. Mar 23, 2009

confinement

By a trivial extension of my method we also solve the problem for the case where the lower bound is a billion, so the answer is 1000011111, and when the lower bound is a trillion so that the answer is 1000000101111.

4. Mar 23, 2009

alligatorman

Try using the divisibility rules for 11 and 3.

5. Mar 24, 2009

carlsjo

Using Mathematica is definitely not an option, but very effective. Nice program. Thanks.

I'll try working throught the divisibilty rules for 11 and 3 like aligatorman suggests and see what I can come up with.

6. Mar 31, 2009

Georgepowell

Using the rules:

Division by three: The sum of the digits is divisible by 3.

Division by eleven: The alternating sum of the digits is divisible by 11 (or is 0). i.e. for 1111, +1-1+1-1=0 so it is divisible by 11.

First, I presumed that the answer is 7 digits long with the first digit being one.

The digit sum could be 6 or 3.

Presuming the digit sum is 6:

If the numbers digits are 1,a,b,c,d,e,f then a+b+c+d+e+f = 5 (meaning that there is only one 0)

This zero could go in any of the 6 places, but if you take into account for the division by 11 rule, the smallest number possible to make with 6 ones in it is:

1,101,111

Presuming the digit sum is 3:

We know that a+b+c+d+e+f=2 and that a-b+c-d+e-f = 0. If we want a smaller answer, then we also know that either a=0, or a=1 and b=0. I will check each possibility for solutions.

c+d+e+f=1 and -c+d-e+f = 0. There are NO solutions in this form! (because how can the sum of just one one be zero?)

b+c+d+e+f=2 and b-c+d-e+f=-1. There are NO solutions in this form either! (because how can the sum of 2 ones be -1?)

So the correct answer is the one mentioned before:

1,101,111.

Is this right?

7. Apr 2, 2009

carlsjo

Sorry for late response.
That was the answer: 1011, 111.