## Interview Question for Developer Program Engineers

Country: United States

Comment hidden because of low score. Click to expand.
5
of 5 vote

the proof is very simple:
on 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.

Comment hidden because of low score. Click to expand.
0

Yes this is simpler than the other proof.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Don't beat yourself up. See the post by Sandeep, whose answer justifies your usage of the word need...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use pegion hole principle

Comment hidden because of low score. Click to expand.
0
of 0 vote

Anonoymous people just try to prolong the conversations always in posting. Question is finished but they will keep it going for no life they have. Just disturb and disturb others.

-Guest DS

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.