6
$\begingroup$

Louis van Gaal has compiled a list of 20 soccer teams, ordered by how good he thinks they are, but strictly refuses to share the ranking. Alex Ferguson knows the names of the 20 teams, but does not know the ranking. Ferguson may mention three arbitrary teams $A,B,C$ to Van Gaal, and Van Gaal will then choose one of the following two options:

  • Van Gaal may announce to Ferguson which he thinks is the weakest team of the three ("I think that team $X$ is the weakest team among these three teams").

  • Van Gaal may announce to Ferguson which he thinks is the strongest team of the three ("I think that team $X$ is the strongest team among these three teams").

Alex Ferguson may do this as many times as he likes.

Problem: Determine the largest integer $n$ such that Ferguson can guarantee to find a sequence $T_1, T_2, \ldots, T_n$ of $n$ teams with the property that he knows that Van Gaal thinks that $T_i$ is better than $T_{i+1}$ for $i=1,\ldots,n$.

$\endgroup$
  • 1
    $\begingroup$ something tells me you support man u ;) $\endgroup$ – Beastly Gerbil Jan 29 '16 at 16:16
7
$\begingroup$

I think the longest sequence Ferguson can get is of length

$n=10$.

First we find that this is an upper bound

van Gaal can divide the set of twenty teams into ten pairs (1st with 2nd, 3rd with 4th, etc...) so that whenever Ferguson asks about a particular triplet which contains two teams from the same pair, he can obscure their relationship by saying whether the other team is the strongest/weakest hence preventing Ferguson from distinguishing 1st from 2nd, 3rd from 4th, etc and allowing him to identify a maximum of one from each pair, that is $n \le 10$

On the other hand this is also a lower bound.

Given any pair of teams $a$, $b$ Ferguson can always either determine how this pair compares with every other team or will be able to distinguish who is the stronger between $a$ and $b$ (by comparing $a$, $b$, $c$ for every other team $c$). In the worst case scenario, he will be able to determine ten pairs of teams so he can put the pairs in order but not necessarily the teams within each pair, hence $n \ge 10$

$\endgroup$
  • $\begingroup$ The generalization of mine I was a bit slower on. Nicely done. $\endgroup$ – Matt Jan 29 '16 at 17:45
3
$\begingroup$

As a rough start, $n \le 18 $.

Suppose in Van Gaal's ranking, $T_1 > T_2 > ... > T_{20}$, and Ferguson asks about every possible $(T_i, T_j, T_k)$ combination. If for every instance of $(T_1, T_2, T_k)$, Van Gaal responds that he believes $T_k$ is the weakest, then Ferguson cannot differentiate between $T_1$ and $T_2$. A similar situation holds at the bottom of the rankings, and so Ferguson cannot distinguish between $T_{19}$ and $T_{20}$.

$\endgroup$
  • $\begingroup$ What if for some $k$ he declares that $T_1$ is the strongest among them? You would in principle not know how $T_2$ and $T_k$ relate. $\endgroup$ – Fimpellizieri Jan 29 '16 at 17:23
  • $\begingroup$ Only if $k=3$, but then you would also know how $T_1$ and $T_2$ relate. $\endgroup$ – Matt Jan 29 '16 at 17:44
  • $\begingroup$ I think you didn't understand my comment; either that, or I did't understand yours. $\endgroup$ – Fimpellizieri Jan 29 '16 at 17:45
  • $\begingroup$ Suppose $k > 3$. If we ask about $(T_2, T_3, T_k)$ we will find out either that $T_2$ is stronger or $T_k$ is weaker, but either way we still know the relationship between $T_2$ and $T_k$. If $k=3$, the only way we don't know the relationship between $T_2$ and $T_3$ is if for every $k > 3$, the answer to $(T_2, T_3, T_k)$ is that $T_k$ is weaker. In either case, there is exactly one relationship (at the top of the order) that we don't know, so the most $n$ can be is 18. Mumble something about symmetry at the bottom, and the most $n$ can be is $18$. $\endgroup$ – Matt Jan 29 '16 at 17:53

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.