5
$\begingroup$

Albert and Bob are playing a game. This time it works like this: there are n points and Albert can ask whether or not $2$ points are connected. Bob then decides whether or not the points are connected. If, after $k$ questions, for any two points $i$ and $j$, Albert can say whether or not a path exists between them, Albert wins. If not, Bob wins. Prove if $k<n(n-1)/2$, then Bob has a winning strategy.

$\endgroup$
2
  • 1
    $\begingroup$ " Bob then decides whether or not the points are connected." So can Bob modify connections mid-game accordingly? And we can assume the answers he provides Albert will be consistent? $\endgroup$ Oct 8, 2022 at 15:56
  • $\begingroup$ Yes. The answers will be consistent. $\endgroup$
    – NielIGuess
    Oct 8, 2022 at 15:57

1 Answer 1

8
$\begingroup$

There can be atmost $\binom{n}{2} = \frac{n(n-1)}{2}$ distinct edges (direct connections) among $n$ points, so if $k=\frac{n(n-1)}{2}$ Albert knows the entire graph structure and can easily answer all path queries.

Otherwise, Bob's strategy would be to answer "No" to every question. There will exist at least one pair of points (X,Y) such that Albert does not know whether they are directly connected.

Bob asks Albert whether there is a path between X and Y. A graph with no connections and a graph where there is only a single connection that goes from X to Y will both be consistent to all the previous answers, so Albert cannot know for sure.

$\endgroup$

Your Answer

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

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