Proof by induction regarding maximum number of questions one can ask.

Question

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.

1. 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

2. 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.

Answer 1

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