Answer: King of the Jungle Plays Tug of War

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 20 mousepower and the tapir has 100, and the King plays against the two of them and ties, then the king has 120 mousepower.

You might hit upon the answer that the mouse has one mousepower, the echidna has two, mowgli has four, the tapir eight, elephant 16, and whale 32. Then the king could make any number up to 63 by combining those mammals, and n_{max} = 63.

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 n_{max} for this method directly. Suppose the King has m mammals to choose from. (In our case, m=6.) In a given game of tug-of-war, each mammal has three choices:

  1. play with the King
  2. play against the king
  3. sit it out

That gives 3^m 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 3^m 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 3^m different possible measurements. If we’re clever, perhaps we can choose the mammals’ mousepower so that the 3^m values the King can measure are 1, 2, 3, \ldots 3^m.

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 k, there is a corresponding useless one that measure whether it is -k. 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 n_{max}.

n_{max} \leq \frac{3^m - 1}{2}

For m=6, that gives an upper bound of 364 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 1 + 3 + 9 = 13. We want to be able to measure 14. We’ll do it by introducing a new mammal with 13+14=27 mousepower. That way, if the King has mousepower 14, then he and all the other mammals can just tie the newcomer. If the King’s real strength is something else, say, 22, we can create a tie by taking whatever arrangement of the original mammals would have measured his strength at 5, switch their sides to measure -5, then adding in the newcomer opposing the King to measure -5 + 37 = 22.

In general, let the mousepower of the k^{th} animal be 3^{k-1}. Then the highest mousepower we could measure is

\sum_{k=1}^m3^{k-1} = \frac{3^m-1}{2}.

(you can check the sum by

3\sum_{k=1}^m3^{k-1} = \sum_{k=1}^m3^{k} = \sum_{k=2}^{m+1}3^{k-1} = \sum_{k=1}^m3^{k-1} - 1 + 3^m

and then solve for

\sum_{k=1}^m3^{k-1}.)

Additionally, we can measure any number from one to this upper bound. This is obviously true for m=1. If it is true for m=j then it will be true for m=j+1 because all the numbers up to (3^j-1)/2 are already covered and all the numbers up to (3^{j+1}-1)/2 can be written in the form 3^j \pm r with r\leq(3^j-1)/2.

This method saturates the upper bound created above, so that

n_{max} = \frac{3^m-1}{2}.

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 1, 3, 9, \ldots, 3^{m-1} we picked them to be 2, 6, 18, \ldots ,2*3^{m-1}, 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 49, that’s no problem. He can still tell that his mousepower is greater than 48 by winning one game, and less than 50 by losing another. 49 is all that’s left over. This lets the King double n_{max}.

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 5 + 7 = 12.

In general, if the highest amount we can currently tie is t_k, then we want to add a new mammal that will generate a tie when the King’s mousepower is t_k + 2 and all the previous mammals and the King are teamed up against the newcomer. The next mammal should have mousepower 2t_k + 2. Introducting this new mammals improves the maximum mousepower the King can measure by

t_{k+1} = t_k + (2t_k+2) = 3t_k + 2.

This recursion relation is satisfied by

t_k = C*3^k - 1

while the initial condition

t_1 = 1

fixes

C = \frac{2}{3}.

This is nicely written as

t_k = 2*3^{k-1}-1,

which for k=6 evaluates to 485, a modest improvement over the previous 364.

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 209, but if he can’t construct a tie for it, he needs to be able to construct ties for 208 and 210. 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 1 and 485 there’s a streak of length l \geq 2 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 x, so it is x, x+1, \ldots, x+l-1. Let’s look at the longest such streak.

The King can construct a tie to measure mousepower x-1 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 x-1 had the mouse on his side. Then he could construct a new game where the mouse sits out, and that would measure x, 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 x. So the mouse must be working against him when we measure x-1 by tie, because that’s the only possibility left.

Now suppose the King’s tie game that measures x-1 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 x-1 to measuring x+1, 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 x+1, 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 k=1, k=2. The k^{th} animal has mousepower 4*3^{k-2}, which we get by subtracting the previous formula for t_{k-1} from t_{k}. If this animal were on the King’s side, while all the animals before were against the king, he could drop the k^{th} animal from his side and make all the smaller ones switch sides. This would be a net change on his side of -4*3^{k-2} + 2*(2*3^{k-2}-1) = -2. The first term is from making the k^{th} animal sit out. The second term is from switching all the smaller animals. It’s 2*t_{k-1}, 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 x+1, which we said was impossible to measure. That means the k^{th} 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 1 to 485. There are no streaks longer than two in the measurable range.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: