# Generalizing tug-of-war puzzle

A puzzle at the end of a 3Blue1Brown video asks the following question (paraphrased):

From a group of 20 people, you get to send one person to participate in a tug-of-war tournament. You don't care too much who you send, as long as you don't send the weakest person. Each person has a different strength, but you don't know what it is. You get 10 tug-of-war matches of 10 vs. 10 among the group of 20 to determine who to send. How do you make sure you don't send the weakest person?

I won't spoil the solution to the puzzle, but it will likely come as no surprise that the (or at least, my) solution works for any group of $$2n$$ people, where you get $$n$$ matches of $$n$$ vs. $$n$$ people.

Can you do any better, for sufficiently large $$n$$?

Is there an $$n$$ such that you can find a non-weakest person among a group of $$2n$$ people, using only $$n - 1$$ tug-of-war matches of $$n$$ vs. $$n$$?

And, if this question has an obvious answer I did not think of, can we even characterize the behaviour?

Let $$L(k)$$ be the least number of matches required to find a non-weakest person among $$2k$$ people. What is the asymptotic behaviour of $$L$$?

• Can team composition (i.e. how to divide into two teams) for round $k$ depend on previous results? If so, I think I have a $\Theta(\log_2 n)$ solution. In fact I think it is $1 + \log_2 n$. – antkam Mar 27 at 17:33
• @antkam, I definitely think it can, and intended my question this way, although my solution to the original puzzle does not require it -- so perhaps it makes for another interesting puzzle. – Mees de Vries Mar 27 at 17:36
• (1) Curious about your spoiler: Is it equivalent to sitting the people in a circle, the red team being half the circle, and in each round shifting the red team by $1$ person clockwise? :) (2) I agree that if team membership in all rounds must be fixed before any matches, the problem is much tougher. Off the top of my head, I can't think of anything that works in $<n$ rounds in that model, but it might be possible...? – antkam Mar 27 at 20:49
• @antkam, that was indeed my solution. – Mees de Vries Mar 28 at 16:09

This answer assumes we can decide how to divide into two teams for round $$k$$ based on previous rounds' results.

Notations: Let $$X, Y$$ be sets of people. I will abuse notation a bit and write $$X+Y$$ for their combined strength. Also, suppose $$X$$ consists of $$n$$ people, then a match can be held vs the other half, which I denote as the complement $$X^c$$. Further suppose $$X$$ wins this match. I will write $$X > X^c$$, or $$X > 1/2$$ meaning $$X$$ has more than half the total strength. In other words, $$X$$ will stand for the set if set-theoretic operations are performed (unions, etc), but $$X$$ will actually stand for the total strength of the people $$\in X$$ if arithmetic operations are performed.

Assume for now $$n = 2^b$$ for integer $$b$$. Here is a solution that requires $$1+b$$ rounds.

First partition the $$2n$$ people into $$4$$ equal sets $$A, B, C, D$$ each of size $$n/2$$.

Round $$0$$: $$A \cup B$$ vs $$C \cup D$$.

Round $$1$$: $$A \cup C$$ vs $$B \cup D$$.

One of the groups has to win twice, and wolog assume it is $$A$$. Then we have $$A + B > 1/2 > B + D$$.

Define a triplet of subsets $$(X,Y,Z)$$ to be an $$m$$-triplet if (1) the $$3$$ sets are disjoint, (2) they have sizes $$(m, m, n-m)$$ respectively, and (3) $$X+ Z > 1/2 > Z + Y$$. So at the end of Round $$1, (A,D,B)$$ is an $${n\over 2}$$-triplet.

The recurrence step will be of this format: Suppose we have an $$m$$-triplet $$(X, Y, Z)$$. Divide $$X$$ into $$X_1, X_2$$ each of size $$m/2$$, and $$Y$$ into $$Y_1, Y_2$$ each of size $$m/2$$. Now match up $$W = X_1 \cup Y_2 \cup Z$$ vs $$W^c$$.

• Case 1: If $$W$$ wins, then $$W = X_1 + Y_2 + Z > 1/2$$. But we know $$1/2 > Y + Z = Y_1 + Y_2 + Z$$. So we now have a new $${m\over 2}$$-triplet $$(X_1, Y_1, Z \cup Y_2)$$.

• Case 2: If $$W$$ loses, then $$W = X_1 + Y_2 + Z < 1/2$$. But we know $$X + Z = X_1 + X_2 + Z > 1/2$$. So we now have a new $${m\over 2}$$-triplet $$(X_2, Y_2, Z \cup X_1)$$.

So with one match, we reduced an $$m$$-triplet to an $${m\over 2}$$-triplet.

Starting with $$n = 2^b$$ (recall there were $$2n$$ people total), after the first $$2$$ matches we have a $$2^{b-1}$$-triplet, and the exponent drops by $$1$$ every additional match. After $$b-1$$ more matches we have a $$2^0$$-triplet, i.e. a $$1$$-triplet $$(F,G,H)$$ where $$F+H > 1/2 > G+H$$. But this implies $$F > G$$, and since each set contains only one person, we know the person in $$F$$ is not the weakest since the person in $$G$$ is weaker.

Total number of matches $$= b + 1 = 1 + \log_2 n$$.

If $$n$$ is not a power of $$2$$, the procedure is a bit messier, but we ultimately still rely on the same recurrence. If $$m$$ is odd, we divide $$X$$ and $$Y$$ as evenly as possible, where the sizes of $$X_1$$ and $$Y_1$$ are $$\lceil {m\over 2} \rceil$$. Then in case 1 we get a new $$\lceil {m\over 2} \rceil$$-triplet whereas in case 2 we get a new $$\lfloor {m \over 2} \rfloor$$-triplet. Clearly the total number of matches $$= 1 + \lceil \log_2 n \rceil$$.

• nice! And in a way you could see this as a generalization of my solution. If $n = ab$, with $a, b > 1$ integers, you can first do the sliding window around the table in $b$ steps of $a$ people. Once you know where the jump is you need only $b - 1$ sliding window steps to get the exact person. Two more observations: you can iterate this, so if $b = a'b'$ you can reduce steps further; and $ab$ only needs to be an upper bound of $n$, not an exact product. Then your solution is this method applied to the product decomposition $n \leq 2^{\lceil \log_2(n) \rceil}$. – Mees de Vries Mar 28 at 16:12
• @MeesdeVries - that's exactly the picture I had in mind. First I found your "circle, shift-by-1" solution. Then I convinced myself shift-by-2 works. Then it's pretty obvious to try either shift-by-$\sqrt{n}$ or binary-search. I tried the latter and it worked. For the written Answer above, I just decided the set-based presentation is easier than the circle-based presentation, but in fact I think we can line up all the $X$s and $Y$s and $Z$s at all levels of the recursion in a line, and show it is "embeddable" into a circle, so to speak. – antkam Mar 28 at 17:21