From the 2003 South African Maths Olympiad:
The first four digits of a positive integer n are 1137. Prove that the digits of n can be shuffled in such a way that the new number is divisible by seven.
This seems hard to believe. Then again, it appeared in a competition, so it’s probably true.
Even if it is true, it does not look at all easy to prove…
Enough chit-chat. It must be the case that the digits 1137 themselves can be arranged to form a multiple of seven, otherwise the statement is false. So which arrangement works?
1137? No, that leaves remainder 3 when divided by seven.
1173? No, that leaves remainder 4.
1317? No, remainder 1.
1371? No, remainder 6.
This is going well…
1713? No, remainder 5.
1731? No, remainder 2.
That’s all the arrangements starting with a 1.
3117? No remainder 2.
3171? Yes! 3171 is a multiple of 7. Finally.
That took a while. Actually, we hit every possible remainder when dividing by 7: 0, 1, 2, 3, 4, 5 and 6.
Hang on – we can get any remainder we like by picking a suitable arrangement of 1137.
I think we’re done. Whatever n looks like, we can move the 1137 from the start to the end, and then rearrange these four digits to obtain a multiple of seven, as desired.
To be clear, suppose n = 11379. Move the 1137 to the end: 91137. Now, 90000 leaves remainder 1 when divided by 7, and 1371 leaves remainder 6. So 91371 is a multiple of 7.
Another example. Suppose n = 1137420. Move the 1137 to the end: 4201137. Now, 4200000 is a multiple of 7, and 3171 is a multiple of 7. So 4203171 is also multiple of 7!
Incredible. By taking ages to find a multiple of 7 among the digits 1137, we’ve actually solved the problem. There is enough flexibility in those four digits to control divisibility by 7 for n itself.
What an interesting problem. At first, it seemed surprising, if not totally unbelievable. Then, it took quite a bit of time to find the multiple of 7 in the simplest case – just the digits 1137 on their own. But in the end that was almost all the work required for a complete solution.