Challenge 24: 7-digit numbers

[Greg Bernhardt]

Main Question or Discussion Point

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

 

[Orodruin]

Well that was fun and kept me up another 20 minutes when I should be sleeping ...

 

[Boorglar]

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

 

[Joffan]

Spoiler

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.

 

[Orodruin]

Spoiler

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.

Spoiler

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