here’s the problem.
Let’s begin by supposing the King of the Jungle wants to play tug-of-war and get a tie. For example, if Mowgli has mousepower and the tapir has , and the King plays against the two of them and ties, then the king has mousepower.
You might hit upon the answer that the mouse has one mousepower, the echidna has two, mowgli has four, the tapir eight, elephant , and whale . Then the king could make any number up to by combining those mammals, and .
This is a good start, but it ignores the possibility of giving the King some teammates. Instead, let the mouse have one mousepower, and the echidna three. Then we have
1 = mouse
2 + mouse = echidna
3 = echidna
4 = mouse + echidna
So if the King has mousepower 1, 2, 3, or 4, he can find a way to make a tie with this arrangement.
Let’s try to estimate for this method directly. Suppose the King has mammals to choose from. (In our case, .) In a given game of tug-of-war, each mammal has three choices:
- play with the King
- play against the king
- sit it out
That gives possible different tug-of-war matches. In each of those matches, there will be a tie only if and only if the King has just the right mousepower to balance out the two sides, meaning that once we find a tie, we can work backwards to get the King’s mousepower. If we pick the mammals’ mousepower wisely, those matches should be nondegenerate, meaning each one should require the king to have a different mousepower to result in a tie. So we get at most different possible measurements. If we’re clever, perhaps we can choose the mammals’ mousepower so that the values the King can measure are .
It doesn’t quite work like that. The matchup where everyone sits out doesn’t help – it measures whether the King’s mousepower is zero. Only half of the remaining matches are useful, because for each useful one that measures whether the king’s mousepower is , there is a corresponding useless one that measure whether it is . The useless setup is the one where everyone switches sides, and there is more mousepower helping the king than pulling against him. That leaves us with an upper bound on .
For , that gives an upper bound of mousepower. To show that we can actually get to the upper bound, we need to explicitly state what the mousepower of the various mammals should be.
The mouse has mousepower one, and we pointed out above that the echidna should have mousepower three. That would allow us to measure up to four. Now let Mowgli have mousepower nine. That way, by putting the echidna and mouse on the King’s side against Mowgli, we can measure five. Drop the mouse and we can measure six. Add the mouse back in but on Mowgli’s side this time and we measure seven, etc. The most we can now measure is . We want to be able to measure . We’ll do it by introducing a new mammal with mousepower. That way, if the King has mousepower , then he and all the other mammals can just tie the newcomer. If the King’s real strength is something else, say, , we can create a tie by taking whatever arrangement of the original mammals would have measured his strength at , switch their sides to measure , then adding in the newcomer opposing the King to measure .
In general, let the mousepower of the animal be . Then the highest mousepower we could measure is
(you can check the sum by
and then solve for
Additionally, we can measure any number from one to this upper bound. This is obviously true for . If it is true for then it will be true for because all the numbers up to are already covered and all the numbers up to can be written in the form with .
This method saturates the upper bound created above, so that
The King can actually do a little better than this, though, because the upper bound was made with a faulty assumption. I assumed that the King measures his mousepower by arranging matches until he participates in a tie. Then he can figure out his own mousepower by arithmetic. But he can use some deduction to expand his measuring power.
If instead of our current solution that the mousepowers are we picked them to be , the King could still find his mousepower. That’s because if it were even, he could find a matchup that results in a tie. If his mousepower were odd, say , that’s no problem. He can still tell that his mousepower is greater than by winning one game, and less than by losing another. is all that’s left over. This lets the King double .
Unfortunately this strategy is not allowed, because he has to use the mouse, which has one mousepower. He can’t start with the first mammal at mousepower two.
Instead, make the echidna have mousepower four. That way, if the King has mousepower two, he can still measure it because it’s between one and three, both of which he can measured by tie matches. The next mousepower the King can’t measure is six. Let’s let Mowgli have the biggest possible mousepower to allow the King to measure a mousepower six. That means mousepower seven should result in a tie, so we can bookend mousepower six. To do that, Mowgli needs mousepower .
In general, if the highest amount we can currently tie is , then we want to add a new mammal that will generate a tie when the King’s mousepower is and all the previous mammals and the King are teamed up against the newcomer. The next mammal should have mousepower . Introducting this new mammals improves the maximum mousepower the King can measure by
This recursion relation is satisfied by
while the initial condition
This is nicely written as
which for evaluates to , a modest improvement over the previous .
We don’t know for sure yet that this will work. What if there are holes the King can’t fill in? He doesn’t need to be able to construct a tie if his mousepower is, say , but if he can’t construct a tie for it, he needs to be able to construct ties for and . If there are two mousepowers in a row he can’t measure through ties, he can’t distinguish between them, and he’s stuck.
Fortunately, that never happens. We’ll show it by contradiction.
Suppose somewhere between and there’s a streak of length of numbers for which the King can’t construct a tie, meaning he can’t distinguish between the numbers in the streak when trying to measure his mousepower. The streak begins at , so it is . Let’s look at the longest such streak.
The King can construct a tie to measure mousepower because if he couldn’t we could add it to the streak. That would make the streak longer, but by hypothesis it’s the longest streak.
Suppose the King’s tie game that measure had the mouse on his side. Then he could construct a new game where the mouse sits out, and that would measure , which is supposed to be impossible. So the mouse isn’t on his side. Also, it’s not sitting out, because if it were it could work against him to measure . So the mouse must be working against him when we measure by tie, because that’s the only possibility left.
Now suppose the King’s tie game that measures had the echidna on his side. (The echidna has mousepower 4.) Then he could have the echidna sit out, and switch the mouse from the opposing team to his team. That would take him from measure to measuring , which is impossible by hypothesis. If the echidna were sitting out, he could again bring it in on the opposing side, switch the mouse from the opposing side to his own, and measure , so the echidna can’t be sitting it out. The only possibility is that the echidna is working against him.
We now hypothesize that all the animals must be working against the king, and prove it by induction. We already have it for . The animal has mousepower , which we get by subtracting the previous formula for from . If this animal were on the King’s side, while all the animals before were against the king, he could drop the animal from his side and make all the smaller ones switch sides. This would be a net change on his side of . The first term is from making the animal sit out. The second term is from switching all the smaller animals. It’s , with the factor of two coming in because the animals go from working against him to working for him. The King’s help gets weaker by two, so this measures a tie when the King gets stronger by two, so it measure , which we said was impossible to measure. That means the animal isn’t on his side. It’s not sitting out either, since then it could join the opposite side, all the smaller animals could switch sides, and the same situation would result.
That means that if there’s a streak of at least two consecutive mousepowers the King can’t measure, all the animals must be working against him just before the streak. But if that’s true, the streak takes place above the maximum of the measurable range from to . There are no streaks longer than two in the measurable range.