Enigmas & puzzles

November 20, 2005
The virtue of greed

Gillian Bates, the richest woman in the world, recently became a convert to the Church of the Sacred Seven. Prospect has obtained from confidential sources a transcript of her first sin assessment, the Church's equivalent of a confessional.

Brother Kevin: The Church of the Sacred Seven, Sister Gill, holds the seven deadly sins to be the greatest threat to our souls. Do you know which of the seven sins is the one that most imperils your own soul?

Sister Gill: The sin of greed, Brother?

Kevin: Exactly.?

Gill: What must I do to be free of sin?

Kevin: Every week, you must give away exactly one million dollars, to randomly chosen members of the poor.

Gill: So little?

Kevin: The gifts are purely symbolic. But the sacred symbolism requires that every gift you make, in dollars, shall be a power of the holy number, namely seven. You must therefore make gifts of $1, $7, $49, $343, $2,401, $16,807, $117,649, or $823,543, to a total of one million dollars exactly.

Gill: May I make one million gifts of $1?

Kevin: No. It is written that no more than six people may receive the same sized gift.

Gill: Then how should I disburse my megabucks?

Kevin: That, you must discover for yourself. But I can give you a hint, Sister: you must make greed a virtue.

How must Gill divide her million dollars?


Scroll down for the answer


The answer

Gill can use the "greedy algorithm," in which each successive gift is as large as possible subject to being a power of seven.  This will ensure that at most six people get any given amount, because, for example, seven gifts of $49 would add up to $343, a higher power of seven which would be chosen instead. The first gift is therefore $823,543, which leaves $176,457. The next gift is $117,649, which leaves $58,808. This is followed by three gifts of $16,807, three of $2,401, three of $343, three of $49, then one of $7, and finally one of $1. This is the unique solution. It can also be found by expressing 1,000,000 in the base seven number system.

The winner is Emily Wilczek from Nottingham