Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need help with AMATYC math problem

  1. Mar 23, 2009 #1
    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. jcsd
  3. Mar 23, 2009 #2
    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
     
  4. Mar 23, 2009 #3
    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.
     
  5. Mar 23, 2009 #4
    Try using the divisibility rules for 11 and 3.
     
  6. Mar 24, 2009 #5
    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.
     
  7. Mar 31, 2009 #6
    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?
     
  8. Apr 2, 2009 #7
    Sorry for late response.
    That was the answer: 1011, 111.
    Thanks. Your explanation was very helpful.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook