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