Enrico draws a square in the plane, and then secretly picks a point $P$ that is either situated

  • inside the square,
  • or outside the square,
  • or on the boundary of the square.

Damiano sees the square drawn by Enrico, but does not know the position of the secret point $P$. Damiano may choose a straight line $\ell$ in the plane and show $\ell$ to Enrico. Enrico then truthfully answers Damiano whether the secret point $P$ lies on line $\ell$, and in case the point is not the line, on which side of $\ell$ this secret point is located.

Question: What is the smallest possible number of lines that Damiano can query so that he will discover with absolute certainty whether the secret point is inside, outside, or on the square?

  • 6
    $\begingroup$ After my first rash answer, I think there is no answer. It doesn't matter where Enrico puts the point. Damiano would need to do something like binary search to find the $X$ and $Y$ coordinates. If $P$ has irrational coordinates, then $P$ will never be found for any $N$. $\endgroup$
    – Trenin
    Oct 20, 2015 at 16:58
  • 8
    $\begingroup$ Are we trying to find the coordinates to $P$, or whether it's inside or outside the square? $\endgroup$
    – JonTheMon
    Oct 20, 2015 at 16:59
  • $\begingroup$ @JonTheMon Must be trying to find if $P$ is inside or outside the square. $\endgroup$
    – Trenin
    Oct 20, 2015 at 17:18
  • 2
    $\begingroup$ What the heck does the square have to do with anything? $\endgroup$ Oct 20, 2015 at 22:50

2 Answers 2


I'm guessing the minimum is


Do a diagonal. If not on the line, do the other diagonal. You now know the quadrant. Now pick the side of the square in your quadrant. Now you know if the point is inside/outside/on the square.

If the first line or second line are on the point, you can still use one of the adjacent sides of the square to figure out if the point is inside/outside the square

Two queries are not sufficient since you need 3 lines to create the minimum bounding area. With 2 lines, you either have 4 distinct regions (or 3 if parallel), but they are unbound, so the point could be anywhere in that region, either in or out of the square.


The answer is four: Draw the lines so that they are coincident with the sides of the square. Based on Enrico's responses, we will then know where the point is. Any fewer lines and we will not know for sure where the secret point is.


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.