11
$\begingroup$

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?

$\endgroup$
  • 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 '15 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 '15 at 16:59
  • $\begingroup$ @JonTheMon Must be trying to find if $P$ is inside or outside the square. $\endgroup$ – Trenin Oct 20 '15 at 17:18
  • 2
    $\begingroup$ What the heck does the square have to do with anything? $\endgroup$ – user2357112 Oct 20 '15 at 22:50
27
$\begingroup$

I'm guessing the minimum is

3

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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