Um problema da Olimpíada de Matemática de Leningrado (atual São Petersburgo): você tem 32 pedras, cada uma com um peso diferente. Como você pode encontrar as duas mais pesadas em 35 pesagens com uma balança de braços iguais?
(A problem from the Leningrad (now Saint Petersburg) Mathematical Olympiad: you have 32 stones, each of a different weight. How can you find the two heaviest in 35 weighings with an equal-arm balance?)
PCFilho
(pescado no sempre ótimo Futility Closet)
Here's a hint: think about a sports tournament of 32. :)
ResponderExcluirBefore we start, we state the following two principles, which will be used extensively to solve the problem:
Excluir1. A stone which is lighter than another stone cannot be the heaviest.
2. A stone which is lighter than a stone which is lighter than still another stone cannot be the second heaviest.
First, we pair off the 32 stones into 16 pairs. For each pair, we weigh the stones of the pair against each other, and assign one label—say, ‘H’—to the heavier stone and another label—say, ‘L’—to the lighter stone. This uses up 16 of the 35 allotted measurements. After these measurements, we have 16 stones labelled ‘H’ and 16 stones labelled ‘L’. The only stone in the ‘L’ group that has a chance to be the second-heaviest is the heaviest stone in that group, but we need to determine which stone that is. To do that, we first note which ‘H’ stone beat which ‘L’ stone, then we pair off the ‘H’ stones and measure the stones in each pair against one another (another 8 measurements, bringing the total to 24). To the heavier stone of each pair, we add another ‘H’ to its label, while to the lighter, we add an ‘L’ to its label. For each stone now labelled ‘HL’ we discard from the running the ‘L’ stone that that stone beat out in the first measurement. This leaves us with eight ‘HH’ stones, eight ‘HL’ stones, and eight ‘L’ stones. Now we pair the ‘HH’ stones and measure the stones of each pair against one another (we’re up to 28 measurements now). Again, we add an ‘H’ to the winners’ labels and an ‘L’ to those of the losers. And again, we discard from the running all stones that were beaten by a stone that just got an ‘L’ added to its label, but now we also discard from the running all ‘L’ stones that were beaten by a stone that just got so discarded. So, now we are left with four ‘HHH’ stones, four ‘HHL’ stones, four ‘HL’ stones, and four ‘L’ stones. After the next round of measurements (which will bring the total number of measurements to 30) we will have two ‘HHHH’ stones, two ‘HHHL’ stones, two ‘HHL’ stones, two ‘HL’ stones, and two ‘L’ stones. The 31st measurement will weed out four of these ten stones, leaving one each of ‘HHHHH’, ‘HHHHL’, ‘HHHL’, ‘HHL’, ‘HL’ and ‘L’. The ‘HHHHH’ stone is therefore the heaviest stone, but we have no idea which of the other five stones is the second-heaviest. So, we use the remaining four measurements this way: we weigh any two of these five stones against each other (this is the 32nd measurement). The heavier stone stays on the scale while the lighter one is discarded and replaced by another. We repeat this process three more times (using up the last three of our allotted measurements). After all is said and done, the stone left on the scale will be the second-heaviest. We have thus determined the two heaviest stones out of the original group of 32.
Well done, Jake!
ExcluirIn sports terms: put the stones through a round-of-32 tournament. In each "match", the heavier "player" wins and goes on to the next round. 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 heaviest stone.
The 2nd-heaviest stone must have lost to the heaviest one at some point in the tournament (since that was the only "player" strong enough to beat it). So take the five stones beaten by the heaviest stone and put them through a little tournament of their own. Four matches will be enough to find the heaviest of these five, and that one must be the second-heaviest overall.