How to Uncover a Cheater 
	(in Four Steps or Less!)

The Coin Makers Challenge
	By: Kelley Katzenmeyer

Assumptions:
	*Only one of the eight coin makers is cheating.
	* If two coins are from the same maker (and bag), they have the same weight.
	*All the coin makers are making the same type of coin.
	*We already know how much the specific coin should weigh.
	*We can take the coins out of their bags.

Let x stand for the proper weight for one coin.

To Start: 
*Take out a coin from each bag.
*If you weigh a coin, mark it.

Weighing One:
	Divide your coins in half, placing four in pile one, and four in pile two. Put the coins in pile one on the scale. If their total weight is less than 4x, then the cheater is among them. In this case, use pile one in Weighing Two. If pile one weighs equal to 4x, then there may be a cheater in pile two, and you should use pile two for the second weighing. If the weight of pile one weighs more then 4x, then you either have some very generous coin makers, or your scale may be broken.

*Don't forget to mark the coins you weigh!

Weighing Two:
	Divide your selected pile in half again, this time making piles three and four. Each pile should only contain two coins. First, weigh pile three and compare it with 2x. Using the same type of logic from Weighing One, we can determine which pile may hold a faulty coin. If pile three is less than 2x, use it in the third weighing. However, if it is equal to 2x, proceed to Weighing Three with pile four.

Weighing Three:
	Now there are only two coins remaining. If either of them is marked, you will not need to do Weighing Four. Chose one of the coins and place it on the scale. If it weighs less than x, then you have uncovered a cheater! If it is equal to x, then continue to weighing four.

Weighing Four:
	Look at the remaining coin. If it already has been marked, then the cheater is right in front of you! Having a mark means it has already been weighed. Knowing that no other coin maker is a cheat, and also knowing that this coin has been weighed, is sufficient to determine it is not the correct weight. Otherwise, the coin would not have progressed this far, because if the coin's weight was equal to 4x, it would have been removed. However, if your coin does not have a mark on it, then continue reading.
	If you have made it this far, then you may not have a cheater at all. If the remaining coin weighs less than x, you have discovered the lousy coin maker. However, if the coin is equal to x, then no one was cheating at all, and you may just be one paranoid King. Go ahead and weigh that last coin, and determine your subject's fate.