First Week, January 10. Golden Coins. You are given five gold coins. Although they all look identical, no two of the coins have the same weight. You have an old-fashioned scale which can tell you, for any pair of coins, which is the heavier of the two. If you are allowed to use the scale up to seven times, can you put the coins in order from lightest to heaviest? Similarly, can you sort nine coins by using the scale 19 times? How many times do you need to use the scale to sort n coins? (I came up with this problem when I was thinking about sorting algorithms such as bubble-sort, quick-sort etc. By the way, none of these standard algorithms solve my problem!)

See previous problems of the week.

Note: I am not giving out solutions to "Problems of the Week". But I am very happy to discuss these problems with you, including any partial or attempted solutions that you might have. I am always interested in hearing about interesting or creative solutions, so let me know if you have any!

Back to Homepage: