Slaves are fighting in an arena. Each fight involves two slaves and results in one winner and one loser. Two slaves may fight one another only if they have an identical number of wins.
A slave with $3$ losses will be kicked out of the arena.
A slave with $12$ wins will be freed from the arena.
How many slaves do we need at least to free one slave?
Start with $43$ fighters named $f_1, f_2, f_3, \ldots, f_{43}$, each of whom has neither won nor lost a fight.
The ten fighters $f_{33}, f_{35}, \ldots, f_{42}$ each fight three fighters from among $\{f_1, f_2, \ldots, f_{32}\}$, losing each fight (so those ten fighters are thrown out), and $f_{43}$ fights two of the remaining fighters, losing both fights. We now have $32$ fighters each with one win and no losses, and one fighter (whom we will not use again) with two losses and no wins.
Next, the eight fighters $f_{25}, f_{26}, \ldots, f_{32}$ each fight three fighters from among $\{f_1, f_2, \ldots, f_{24}\}$, losing each fight, and are thrown out. We now have $24$ fighters each with two wins and no losses.
Next, the six fighters $f_{19}, \ldots, f_{24}$ lose three fights each with fighters among $\{f_1, f_2, \ldots, f_{18}\}$, so we then have $18$ fighters each with three wins and no losses.
Next, $f_{14}$ loses fights with $f_1$ and $f_2$, then $f_{15}$, $f_{16}$, $f_{17}$, and $f_{18}$ each lose three fights with fighters among $\{f_3, f_4, \ldots, f_{14}\}$. We now have $13$ fighters with four wins and no losses, and one fighter ($f_{14}$) with four wins and two losses.
Next, the four fighters $f_{11}$, $f_{12}$, $f_{13}$, and $f_{14}$ lose a total of $10$ fights (one loss for $f_{14}$, three for each of the others) against the ten fighters in $\{f_1, f_2, \ldots, f_{10}\}$. We now have $10$ fighters with five wins and no losses.
Next, $f_6$ loses fights with $f_7$ and $f_8$, then $f_9$ and $f_{10}$ each lose three fights with the fighters among $\{f_1, f_2, \ldots, f_6\}$. We now have seven fighters with six wins and no losses, and one fighter ($f_6$) with six wins and two losses.
Next, $f_7$ and $f_8$ each lose three fights against the six fighters in $\{f_1, f_2, \ldots, f_6\}$. We now have five fighters with $7$ wins and no losses, and one fighter ($f_6$) with $7$ wins and two losses.
Next, $f_1$ beats $f_2$, $f_2$ beats $f_3$, $f_3$ beats $f_4$, $f_4$ beats $f_5$, and $f_5$ beats $f_6$, in that order. This eliminates $f_6$ and we are left with one fighter ($f_1$) with $8$ wins and no losses and four fighters with $8$ wins and one loss each.
Next, $f_2$ beats $f_1$, $f_3$ beats $f_4$, and $f_1$ and $f_4$ each beat $f_5$. At that time, $f_5$ is eliminated, $f_1$, $f_2$, and $f_3$ each have $9$ wins and one loss, and $f_4$ has $9$ wins and two losses.
Next, $f_1$ beats $f_2$, $f_2$ beats $f_3$, and $f_3$ beats $f_4$. This eliminates $f_4$; $f_1$ has $10$ wins and one loss, and $f_2$ and $f_3$ have $10$ wins and two losses each.
Next, $f_2$ beats $f_1$, then $f_1$ beats $f_3$ (eliminating $f_3$). Now $f_1$ and $f_2$ have $11$ wins and two losses each.
Finally, $f_1$ beats $f_2$ and is freed.
The description above is a proof by construction that $43$ fighters are sufficient to free one fighter. Now we show that $43$ fighters are necessary; that is, it is not possible for a fighter to be freed if we start with fewer than $43$.
First, some definitions. Round $n$ consists of all fights between fighters with $n - 1$ previous wins. Since every fight in round $1$ is between fighters with no previous fights, and for $n>1$ every fight in round $n$ is between fighters who fought in round $n - 1$, whatever sequence of fights leads to a fighter being freed, we can reorder the fights so that all fights of round $n$ precede all fights of round $n+1$ for each $n$.
At any given time, a fighter who has previously won $W$ fights and lost $L$ fights (which we'll abbreviate as "a $(W,L)$ fighter") has a "value" $v(W,L)$. The idea is to assign values so that the sum of values of all the fighters can never increase, and so that the sum of values of all fighters who have not yet been thrown out is always a reasonably tight lower bound of the number of fighters we had to start with in order to produce fighters with these win-loss records.
Clearly $v(0,0) = 1$ works for the value of the fighters at the start, and $v(W,3) = 0$ works for fighters who have been thrown out after any number of wins. In round $1$, after each fight we subtract $\frac13$ from the loser's value, so that at the end of the round all $(0,3)$ fighters have value $0$. Hence $v(0,L) = 1 - \frac13L$ for $0 \leq L \leq 3$. But we set $v(1,L) = \frac43(1 - \frac13L)$, which means a $(0,0)$ fighter gains $\frac13$ by winning a fight, a $(0,1)$ fighter gains $\frac29$, and a $(0,2)$ fighter gains $\frac19$. This maintains the requirement that the sum of values never increases, but reflects that fact that to get $3N$ fighters with $(1,0)$ records, it is necessary and sufficient to have $4N$ fighters at the beginning.
The general formula will be $v(W,L) = (1 - \frac13L)(\frac43)^W$. So in round $W+1$, each loss reduces the loser's value by $\frac13(\frac43)^W$ and increases the winner's value by either $\frac13(\frac43)^W$, $\frac29(\frac43)^W$, or $\frac19(\frac43)^W$, depending on whether the winner had $0$, $1$, or $2$ losses already.
Now, working from the desired final state (a fighter with $12$ wins) backward, since the loser of the last fight in round $n$ never advances to round $n+1$, we must have had one fight in round $12$, two in round $11$, three in round $10$, and so forth. In particular, in the rounds after round $6$ we must have $6 + 5 + 4 + 3 + 2 + 1 = 21$ fights to promote a single fighter to $12$ wins, which means $21$ losses. Moreover, these $21$ losses, plus whatever losses the fighters in round $7$ already had at the start of the round, must add up to less than three times the number of fighters in that round, since more losses than that would get them all thrown out. That is, if the $k$th fighter in round $7$ had $L_{7,k}$ losses at the start of the round, then over those fighters, $\sum(3-L_{7,k}) \geq 22$.
It follows that at least $\lceil 22/3\rceil = 8$ fighters had to win round $6$ to advance to round $7$. So at the start of round $6$ there are at least $29$ fights to go and at the beginning of that round we must have $\sum(3-L_{6,k}) \geq 30$ summed over the fighters in that round.
But $\left(\frac13\sum(3-L_{6,k})\right)(\frac43)^5$ is exactly the value at the start of round $6$ of all the $(5,L_{6,k})$ fighters who fight in that round. Therefore the value of those fighters is at least $\frac13 \cdot 30 \cdot (\frac43)^5 \approx 42.14$, so we must have started with more than $42$ fighters, that is, at least $43$ fighters.
Assuming there are no fatalities.
For $n$ fighters and we fight until there are no more fights we can schedule by the rules given.
There must be exactly one fighter with no wins.
Win-less fighters can only fight win-less fighters, and somebody must lose that fight.
There cannot be two win-less fighters, or they would square off until there was only one.
For $n<12$ fighters there is one fighter for each $k, 0\le k< n$ wins.
If there are 13 fighters one fighter will amass 12 wins.
