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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ something tells me you support man u ;) $\endgroup$
    – Beastly Gerbil
    Jan 29, 2016 at 16:16

2 Answers 2

Reset to default
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$

Improve this answer
$\endgroup$
1
  • $\begingroup$ The generalization of mine I was a bit slower on. Nicely done. $\endgroup$
    – Matt
    Jan 29, 2016 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}$.

Improve this answer
$\endgroup$
4
  • $\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$
    – Fimpellizzeri
    Jan 29, 2016 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, 2016 at 17:44
  • $\begingroup$ I think you didn't understand my comment; either that, or I did't understand yours. $\endgroup$
    – Fimpellizzeri
    Jan 29, 2016 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, 2016 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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