Divide the coins arbitrarily into piles of 30, 30, and 41 coins, calling these respectively A, B, and C. Now weigh A against B. If these balance, then X must be in C; combine A and B and weigh 41 of these coins against the 41 coins in C and you’ll find out whether X is heavy or light.

If A and B don’t balance, then one of those groups contains the bad coin. For definiteness, suppose that A goes down in the weighing. That means either that A contains the bad coin and it’s heavy or that B contains the bad coin and it’s light. So determining where X is will also tell us its relative weight.

Divide A in half and weigh these halves against each other. If they balance then the coins are all good and X must be in B. If they don’t balance then X is in A.

(Obviously the same plan will work with certain pile sizes other than 30, 30, and 41, but that arrangement will do the job.)

Think of the stones as tennis players and put them through a singles tournament. There are no upsets: In each match (weighing), the better (heavier) player always wins and goes on to the next round. With 32 players, this will produce a tournament with five rounds, comprising 16, 8, 4, 2, and 1 matches, successively, enough to produce 31 losers and identify the best (heaviest) stone.

Now, the second-heaviest stone must have “lost” to the heaviest at some point in the tournament (since that was the only “player” strong enough to beat it). So take the five players beaten by the heaviest stone and put them through a little tournament of their own. Four matches will be enough to find the strongest of these five, and that must be the second-heaviest stone overall.

(Via Ross Honsberger’s Mathematical Delights, 2004.)

If there were only 3 matches in the original pile, A would lose — he could withdraw 1 or 2 matches, but then B could immediately withdraw the remainder and win the game. If there were 4 or 5 matches in the original pile then A could saddle B with a losing 3-match pile, but if there were 6 in the original pile, then by the same principle B could saddle A with the 3-match pile.

The winning strategy, then, is always to leave your opponent a quantity that’s a multiple of 3. A can accomplish this on his first turn by taking 2 matches from the pile of 500, leaving 498 = 3 × 166 matches for B, who cannot now escape his fate.

Think of the stones as tennis players in a singles tournament. The heavier the stone, the better the player. Each weighing in the balance represents a game between two players, with the better (heavier) player going on to the next round of the tournament.

Since there are 32 players, the tournament will have 5 rounds, with 16, 8, 4, 2, and 1 matches. Each match produces a loser, so this system will eliminate 31 of the 32 players. The best player is unbeatable, so he’ll emerge as the winner no matter how the early rounds are arranged.

How can we find the second-best player? He didn’t win the tournament, so he must have been eliminated at some point. But the only player good enough to beat him is the strongest player, so the two of them must have faced one another in some match. If we refer to the record of the pairings, we can find the five players that the champion eliminated on his way to the top. One of these is the second-best player.

Now if these five players hold a mini-tournament among themselves, the second-best player will win it. This can be done in another four matches, for a total of 35 matches.

From the Leningrad Mathematical Olympiad, via Ross Honsberger’s Mathematical Delights, 2004.

Make a list of all possible subsets of the students, including the empty set and the full set, and suppose you let in all of these groups. Each weight would spend half its time in the left pan and half in the right, so the total weight for each pan is the same. Since the empty set produces a tip to the right, there must be some other set that produces a tip to the left.