Need help with AMATYC math problem

[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 across this problem in an old AMATYC contest question.

Any help would be much appreciated.

 

[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

 

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

 

[alligatorman]

Try using the divisibility rules for 11 and 3.

 

[carlsjo]

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

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

 

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

if the answer is 1,10c,def:

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?)

if the answer is 1,0bc,def:

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?

 

[carlsjo]

Sorry for late response.
That was the answer: 1011, 111.
Thanks. Your explanation was very helpful.