Interview Question Developer Program Engineers
Country: United States
Consider the x co-ordinates. There will be at least 3 odd, or 3 even.
In those 3 points, consider the y-coordinates. At least two will be of same parity. Pick those two points.
Example: (1,3), (4,8), (9,0), (16,7), (32, 5)
(4,8), (16,7) and (32,5) all have even x co-ordinates.
Among these
(16,7) and (32,5) both have odd x co-ordinates and their midpoint (24,6) has integer co-ordinates.
To complete the proof: After you pick those two points, the difference of their y will be even, and so will the difference of their x. Therefore, half of the x difference and half of the y difference will both be integer amounts, and since the endpoints are at integer coordinates too, the midpoint will have integer coordinates.
Generalizing this a little, we can see that in n dimensions, we need 2^n + 1 points for at least one pair to have a midpoint that has integer coordinates.
@Anonymous commentor (not answer poster).
What a strange way to try and "complete" the proof. It is obvious if two numbers have the same parity then their sum will be even and hence the midpoint will have integer co-ordinates.
Talking about difference etc is just pointless and there really is no need to attempt a "completion" of the proof.
Also, the talk about _need_ 2^n+1 points requires proof. Yes, 2^n+1 are _sufficient_, but you talk about it being necessary.
Maybe it is an easy proof (an example will do), but you need to provide that before you can claim the need.
Yes, the part where I mentioned that "Generalizing this a little, we can see that in n dimensions, we need 2^n + 1 points for at least one pair to have a midpoint that has integer coordinates" does require further proof. Having completed the previous proof, I just wanted to look forward a little.
"It is obvious if two numbers have the same parity then their sum will be even and hence the midpoint will have integer co-ordinates."
Yes, but that was not stated in the original proof. The proof ended with "Pick those two points." I felt that was a bit abrupt and needed the conclusion to be mentioned. "Pick those two points" is not a conclusion. You can talk about sum or about difference; either works, but one argument or another should be made.
It's not like I had any doubt about the original answerer's correctness, or that they knew the correct proof. I just wanted to fill in the omitted section.
@ANonymous:
You didn't get my point. My quibble was with the usage of the word "need".
For instance, what prevents every set of 2^n -1 to have a pair whose midpoint is on the grid?
A proof by induction proves that every set of 2^n+1 points has a grid midpoint point. My point was that is a sufficient condition, while your statement comes across as being necessary.
As to the original proof, i think you are being overly pedantic. The proof is perfectly fine IMO.
As for the original proof, I just thought I'd fill in the details a little more in case anyone found it helpful. Ironically, this thread is now more likely to confuse people because of the debate.
Yes, to say that we "need" at least 2^n+1 points is misleading and was an unfortunate choice of words. I had meant those words in the context of the original problem statement, where the points are chosen at random and we want to be guaranteed an integer midpoint. A more precise statement would have been "If the points are chosen at random, we need at least 2^n+1 points with integer coordinates to always be guaranteed that at least one midpoint has integer coordinates." Every configuration of 2^n+1 points (with integer coords) has such a midpoint, and for every natural number n there is a configuration of 2^n points (with integer coords) that does not have this property. I was trying to indicate that the bound of 2^n+1 is tight.
Looks like I failed to achieve any of my objectives in this thread.
1) if P[i]={xi, yi} ...mid point lies on grid iff sum x1+x2 and y1+y2 is even
2) Odd+odd= even, even+even=even and odd+even=odd
3)pigeon-hole principle:
Lets group the points on x co-ordinates only. Hence it is guaranteed that ATLEAST three will be of same cardinality.
4) from above 3 At least 2 will be of same cardinality.
Hence at least 1 point will lie on grid.
the proof is very simple:
- sandeep July 25, 2012on the co-ordinate axes there can be only 4 different set of points (even,even), (odd,odd), (even,odd) , (odd,even)
ny two points belonging to one of the four sets will have a mid-point. so at max we can hav atmost 4 points one from each set so that dey do not hav a mid point. wen we add the 5th point then there are atleast 2 points from the same set and hence atleast one mid point.