- #1

- 18,391

- 8,264

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Greg Bernhardt
- Start date

- #1

- 18,391

- 8,264

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

- 16,939

- 6,772

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

- #3

- 210

- 10

But that's probably not what you intended :P

- #4

- 473

- 13

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.

- #5

- 16,939

- 6,772

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.

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

Share: