sorry for the pretty ambiguous title. It's otherwise hard to describe this problem without stating it in full.
There are $n$ points drawn on a whiteboard. Between every pair of points $X$ and $Y$ there are drawn either an arrow from $X$ to $Y$, from $Y$ to $X$, or both. You are only allowed to ask the question, "Is there an arrow between points $X$ to $Y$?" or "Is there an arrow between points $Y$ to $X$?" for any two points. You want to find a point connected to all other points by only arrows pointing to itself: that is, there are only arrows pointing from other points to this point, and no arrows pointing away from this point. Prove using induction that if such a point exists, it can be found by asking at most $3(n-1)$ questions.
Now, I'm stumped here. Using induction, I would assume this is true for $n$ points, and then use that fact to try proving this for $n+1$ points. This gives me $3(n+1-1) = 3n$ questions, which is 3 more than $n$ points would give me. This is where I'm stuck though: if I'm given an arrangement of $n$ points which I know has some point connected to all other points by only arrows to itself, how could I determine whether or not $n+1$ points still has a point connected by only arrows in such fashion?
Knowing the previous blue point, $A$, I've tried looking at this through some of the different questions I could ask.
- Is the $(n+1)$th point connected by an arrow from $A$?
If no, then they must be connected by an arrow to $A$, I know $A$ is connected to all other points by arrows to itself, and I'm done. If yes then
- Is the $(n+1)$th point connected by an arrow to $A$?
If yes, then I know that there is no point connected to all others by only by arrows to itself. This is because all of the arrows pointing at $A$ means all of those other points have arrows pointing away from them. Therefore the $(n+1)$th point, since it also has an arrow pointed away from it, is invalid too. If no, then there's still the chance that the $(n+1)$th point IS the new point connected with all others only by arrows to itself.
And this is where I'm stuck. I have one question left, but I don't know how I can determine if there are only lines from the other points to the $(n+1)$th. If anyone could help me, that would be greatly appreciated.
Let's say point $X$ is a "sink" if there are no arrows from $X$ to other points.
Let $S$ be the set of points such that you don't know whether $S$ is a sink. So initially $S$ has $n$ members. Whenever $S$ has at least two members, take two of them (say $A$ and $B$), and ask "is there an arrow from $A$ to $B$?" If the answer is yes, then you know $A$ is not a sink. If the answer is no, then there must be an arrow from $B$ to $A$, so you know $B$ is not a sink. Either way, $S$ loses one member. So after $n-1$ questions, $S$ has only one member (call it $s$), and you only need to determine whether that member is a sink. This requires asking at most $n-1$ more questions, for a total of $2(n-1)$.