The Vault: Robbers

Here I present one of my favourites; a problem of rare invention. From the 1998 Tournament of the Towns:

(Two-person case) Two robbers stole a bag of coins from a merchant. Each coin is worth an integer number of pennies. It is known that if any single coin is removed from the bag, then the remaining coins can be divided fairly among the two robbers (that is, they both get coins with the same total value in pennies).

Prove that after one coin is removed, the number of coins remaining is even.

(General case) A gang of robbers stole a bag of coins from a merchant. Each coin is worth an integer number of pennies. It is known that if any single coin is removed from the bag, then the remaining coins can be divided fairly among the robbers (that is, they all get coins with the same total value in pennies).

Prove that after one coin is removed, the number of coins remaining is divisible by the number of robbers.

In reading the problem, it appears that something quite fundamental about numbers is being claimed. Despite all the apparent freedom we have to assign values to coins, the condition of fairness alone is enough to force the number of coins to obey a particularly strict law.

I solved this puzzle quite a while ago, but I can still recall (i) its difficulty and (ii) my awe at its creation. Though I cannot quite remember how I came to have what I believe is the crucial insight required to solve it, I suspect that it came from trying out small cases, deciding what I wanted to be true, and then trying to show that I could have what I wanted after all.

Suppose there are n robbers and k coins with values a_1, a_2, ..., a_k. Let S=a_1+a_2+\cdots +a_k be the total value of all the coins in the bag.

Claim:

The value of each coin leaves the same remainder upon division by n.

Proof:

Take any two coins a_i and a_j. The fairness condition implies that n divides both S-a_i and S-a_j, so n must also divide a_i-a_j = (S-a_j)-(S-a_i). That is to say, a_i-a_j must be a multiple of n; equivalently, a_i and a_j leave the same remainder upon division by n.

Notice that there was nothing special about a_i or a_j, and the above argument holds for any two coins.

This means we can write each coin value as a_i=q_in+r, where r is the (common) remainder when each value is divided by n.

So S=(q_1n+r)+(q_2n+r)+\cdots +(q_kn+r)=(q_1+q_2+\cdots +q_k)n+kr.

If we remove any single coin a_i=q_in+r, the new total is divisible by n. It follows that n divides

S-(q_in+r)=(q_1+q_2+\cdots +q_k-q_i)n+(k-1)r,

and hence that n divides (k-1)r. (*)

The solution now seems to be very close: all we are aiming for is to prove that n divides k-1 (**), i.e. that the number of coins in the bag (after a single coin is removed) is a multiple of the number of robbers. In fact if only we knew that n and r had no common factors, then we could move straight from (*) to (**) and complete the proof on the spot.

Now here comes the crucial insight: incredibly, we can insist that n and r have no factors in common, for if we divide every coin value by the highest common factor (hcf) of all the values, the fairness condition is preserved!

To see this, imagine that a single coin has been removed, and the remaining coins have been fairly distributed among the robbers. If we divide each coin value by the hcf of all the values, then each robber’s earnings are reduced by exactly the same factor, and so the distribution is still fair. Note also that, as desired, n and r now have no factor in common; if they did, say d, then d would divide the value of every coin q_in+r, which is impossible since we have already divided every value by the hcf of all the values.

This means is that at the start of our solution, we may simply divide all values by their highest common factor, and run through the argument presented above, where this time we are allowed to make the leap from (*) to (**), thus completing the proof.

This problem really has to be seen to be believed. It possesses many of the hallmarks of an outstanding mathematics problem: an interesting context, a simple premise, a surprising result and a difficult-to-find but elegant solution. It is the sort of problem I aspire to create, and I can only hope it brings you as much joy as it brought me.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s