The general was inspecting his troops as they stood two abreast ready to march into battle. He was dismayed to find that there was one man left over.

‘That’s odd,’ he muttered to himself, and then ordered his men to reform in threes. But now things were worse than before – there were two men left over.

And when he tried fours, there were three left over. With fives there were four left over, with sixes five over, with sevens, six over.

‘Alas and alack,’ groaned the general holding his head. ‘If it is this hard putting the men in formation, what is the fighting going to be like?!’

It was all too much for him, so he deferred the battle for another day. Now knowing that there were not more than 800 troops on parade, exactly how many were there?

Hint 1

This is a divisibility problem.

Hint 2

Can you change this problem with remainders into a related problem in which 2, 3, 4, 5, 6 and 7 are exact divisors?

Solution

As a first step, we might try the following. Let N be the total number of soldiers on parade. Then from the given information we know that for some integers a, b, c, d, e and f:

     N = 2a + 1 = 3b + 2  = 4c + 3  = 5d + 4  = 6e + 5  = 7f + 6.

This is starting to look complicated, and anyway we are not really interested in all these extra integers. But look now at the integer N + 1.

We have N + 1 = 2a + 2 = 3b + 3 = ... . That is, N + 1 is exactly divisible by 2, 3, 4, 5, 6 and 7. The smallest such number with this property is

     N + 1 = 2 x 2 x 3 x 5 x 7 = 420.

This gives N = 419.

Is this the only possible solution? The next smallest number N + 1 with this divisibility property is twice this, i.e. 420 x 2 = 840. This would give N = 839. But we are told that there were not more than 800 men on parade. So the general was marshalling 419 men.

Extensions

1. What would be the solution to the problem if there was just one man over for each formation of the men?

2. A given set of counters can be placed in rectangular arrays of widths 2, 3, 4, 5, 6 and 7. What is the smallest number of counters in the set?

Hint 1

Hint 2

Solution

Extensions