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

Challenge 24: 7-digit numbers

  1. Dec 16, 2014 #1
    Submitted by @PeroK

    Consider all 7-digit numbers which are a permutation of the digits 1-7. How many of these are divisible by 7?

    Can you prove the answer algebraically, rather than simply counting them?

    Please make use of the spoiler tag
     
  2. jcsd
  3. Dec 16, 2014 #2

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Well that was fun and kept me up another 20 minutes when I should be sleeping ... :oops:
     
  4. Dec 16, 2014 #3
    Well I can solve it easily in base 14. A number divisible by 7 ends either in 7 or 0. Since 0 is excluded, that leaves us only with numbers ending in 7. Thus the remaining 6 digits can have any permutation of the 6 integers 1 to 6, and the answer would be 6! = 720.

    But that's probably not what you intended :P
     
  5. Dec 17, 2014 #4
    The urge to count them was irresistible... but I did think about it first.
    The pattern of 10^k mod 7 is {1,3,2,6,4,5,1} with the repeat just starting. As far as I could see there was nothing favouring one outcome of modulo 7 result over another, so my initial expectation was that one-seventh of all possible permutations would be divisible by 7 - and so it turned out, 7!/7 = 6! = 720.

    But that was luck. All permutations of 1..8 gave not 8!/7 =5760, but 5768 numbers divisible by 7.

    I haven't yet come up with a good non-brute-force derivation of 720.
     
  6. Dec 17, 2014 #5

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    The naive expectation is true for all numbers except 3, 6, and 9 (the naive expectation being number of permutations of 1-k divisible by k is (k-1)!). For example:
    For 2: 12, 21, where one ((2-1)! = 1! = 1) of them is divisible by two.
    For 3: 123, 231, 312, 132, 321, 213 - all of them divisible by three.
    You now have a + b + 2c + 3d + 4e + 5f + 6g mod 7, where a-g are is a permutation of 1-7. The trick here is to show that for a given permutation which is divisible by 7, there are also 6 which are not - any element of the permutation group with order 7 should do (although some may be more suited than others).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Challenge 24: 7-digit numbers
Loading...