A Game Of Circles
Alice has two circles on the plane that intersect each other twice. Bob wants to know these circles. To do that, Alice plays a game with Bob. Alice selects n points from each circle in such a way that both intersections are selected (so Alice selects 2 n − 2 points). Bob then asks for the identities of k of them.
What is the smallest value of k required so that Bob can always determine the circles, even if Alice tries to prevent it? Enter your answer for the following three problems:
- n = 6
- n = 5
- n = 4
If Bob cannot figure out the circles with any k , enter 0. Otherwise, enter the minimum value of k such that Bob can always determine the circles. Concatenate your answers for all three problems. For example, if the answers are 0, 10, 100 in that order, enter 0 1 0 1 0 0 = 1 0 1 0 0 .
The answer is 980.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Moderator note:
Clear writeup that explains how to think about the condition.
Why can't the answer for n = 4 be 5?
Say the two circles are S 1 and S 2 . and they intersect in points C and D . The points A , B , C and D lie on S 1 while C , D , E and F lie on S 2 .
3 points define a circle, so when Alice discloses the 3 points on S 1 they can only be ( A , B , C ) or ( A , B , D ) (here I am considering worst case scenario and so I am not considering the case for ( C , D , A ) or ( C , D , B ) which would yield the answer to be k = 4 ).
Now for S 2 either C or D is known and we only need to ask for 2 more points.
Thus, only 5 points are sufficient for Bob to determine both the circles when n = 4 .
I hope that this proof (though not much of a proof) is valid. Please feel free to point out mistakes if any.
Log in to reply
The problem is that Alice doesn't tell that A , B , C belong to the same circle. Suppose Alice discloses A , B , C , D , E ; what prevents Bob to think that, say, ( A , C , E ) , ( B , C , D ) are the circles instead?
Log in to reply
Yea, I missed that. My bad. Thank you for explaining.
Relevant wiki: Pigeonhole Principle - Problem Solving
Call the k points that are given to be the clued points .
We claim that for n ≥ 4 , k = n + 3 . (In particular, for n = 4 , because there are only 2 n − 2 = 6 < 7 = n + 3 points available, Bob cannot figure the circles.)
First, to show that n + 2 clued points is not enough, imagine n of them are on the unit circle so that they are symmetric over the x-axis, and two more are outside this circle, also symmetric over the x-axis. These two points might belong to any of the circles that also pass a pair of symmetric points, as shown in the picture below.
This means Bob cannot figure out Alice's circles; one of them is clear, but the other cannot be determined. (There might be more possibilities, but having two possibilities is enough.) We need n ≥ 4 so that there are at least two pairs of symmetric points on the circle. ( n = 3 needs a different proof.)
Thus we need at least n + 3 points. Now we claim that this is enough.
We will prove that any circle passing 5 clued points is one of Alice's circles. The proof is simple: if it's not of Alice's circles, then it can only intersect each of Alice's circles on two points, which means a total of four points. Points not among these intersections aren't clued. This means this circle only passes at most 4 clued points, contradicting the assumption.
Now, if n ≥ 6 , we have n + 3 ≥ 9 , so by pigeonhole principle there exists one of Alice's circles that is clued by 5 points. If n = 5 , then n + 3 = 8 = 2 n − 2 , which means all of Alice's points are clued; naturally this means one of Alice's circles (and in fact both) are clued by 5 points. Either way, we can find a circle that passes 5 clued points; by the above, this is one of Alice's circles.
Since Alice clues at most n points from each circle, there are at least ( n + 3 ) − n = 3 clued points remaining. These together determine the other Alice's circle (because three points determine a circle). This completes the proof.
The answers, respectively, are 9, 8, 0.