2
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – antkam Mar 27 at 17:33
  • $\begingroup$ @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. $\endgroup$ – Mees de Vries Mar 27 at 17:36
  • $\begingroup$ (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...? $\endgroup$ – antkam Mar 27 at 20:49
  • $\begingroup$ @antkam, that was indeed my solution. $\endgroup$ – Mees de Vries Mar 28 at 16:09
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – Mees de Vries Mar 28 at 16:12
  • 1
    $\begingroup$ @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. $\endgroup$ – antkam Mar 28 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.