Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I just read this article about some tough interview questions. One of the questions (allegedly given in an interview for a Technology Analyst position in Goldman Sachs) was:

There are infinite black and white dots on a plane. Prove that the distance between one black dot and one white dot is one unit.

I'm not sure how I should interpret this. Is something missing from the question, or can it be proven?

share|improve this question
1  
Is this not a thought experiment asking you to reason that if there are an infinite number of dots then somewhere there must exist a black dot of unit length away from a white dot. Or it could be purposefully being vague on what it means to be unit length and you could argue that one unit is the distance between two points you picked. I reckon they want to see how you think. –  user17904 Jul 26 '13 at 10:23
4  
@user17904 Infinity alone is not sufficient to claim that somewhere there must exist a black dot a unit length away from a white one. I'd go with the thought experiment if no information is provided. –  Sebastialonso Jul 26 '13 at 11:02
8  
One could exploit a technicality in that the question fails to define "one unit." Arbitrarily select one black point and one white point. Define the distance between these points to be one unit. QED. –  cobaltduck Jul 26 '13 at 14:45
1  
This proof will fail as the necessary requirements are not included. According to the statement there could be an infinite number of dots at the same position, there distance would be zero. Nowhere is anything said about the distribution of points within the plane. –  Alexander Jul 26 '13 at 15:08
1  
@cobaltduck: The question is not well phrased (as is understandable, since it is being reported from memory from an interview question) but there are at least two ways to construe it as a perfectly good mathematical question: in Avitus's way, it is rather clearly false; as I, Mark and Marc construed it, it is true but nontrivial. (Honestly I did construe it Avitus's way first and started writing up an answer including both interpretations, but Avitus's answer appeared first.)... –  Pete L. Clark Jul 26 '13 at 23:17
show 4 more comments

5 Answers

up vote 16 down vote accepted

If you click on the link you find a picture which has black dots on a white background. This suggests that we color every point on the plane either white or black, making sure to use infinitely many of each color. With these constraints it is indeed the case that there must be a black point and a white point at unit distance. (In fact, "infinite" can be weakened to nonempty.)

Hint: starting with a black point, we're done unless the entire unit circle around that point is black. Now repeat that argument for each point on that unit circle: we've already generated a sizable swathe of the plane colored totally black...

share|improve this answer
4  
This is probably what was meant. This is related to the chromatic number of the plane problem en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem –  Ittay Weiss Jul 26 '13 at 11:08
    
Why is this the accepted answer? –  adi Jul 26 '13 at 13:41
1  
@adi, because it made me understand the mathematics in the question (and what was missing from the question). –  Aleksander Blomskøld Jul 26 '13 at 20:57
add comment

The statement is in general false: for example, if the black dots are all and only on the locus $x=0$, while the white ones are all and only on the locus $x=2$, then the assertion is false (we are using the Euclidean distance).

Probably there are some more hypothesis in the background OR the aim of the question is just to analyze the way the candidate faces a given mathematical problem, reaching conclusions which can be in contrast with the thesis of any given question.

share|improve this answer
9  
The statement doesn’t even make much sense: what is an infinite black and white dot? They may have meant infinitely many black and white dots, but they certainly didn’t say so. –  Brian M. Scott Jul 26 '13 at 10:37
    
@BrianM.Scott Given the context (that it's not a math assignment per se, and that this version of the question has been written by a journalist), I think one should try to add some good faith to the question, and try to figure out what clauses are missing. The version I read of this question was in a Norwegian newspaper where "plane" were translated to the Norwegian word for aeroplane... –  Aleksander Blomskøld Jul 26 '13 at 21:02
    
@Aleksander: There are three possibilities. 1. The question has been reported accurately and is intentionally defective, and that is its point. 2. The question has been reported accurately and is unintentionally defective. 3. The question has been mangled in transmission. The appropriate response is different in each case, and Ww’ve no way to tell which case is correct. And the appropriate response in the third case depends on what the original question actually was, which also cannot be determined from the available information. In short, the OP’s question is unanswerable by us. –  Brian M. Scott Jul 27 '13 at 2:37
add comment

Another counterexample. Take the real line with every integer coloured white and all other points coloured black.

On the other hand if every point in the whole plane is coloured white or black, with infinite numbers of each, and we try to build a counterexample, the following happens. There is at least one white point $P$. To avoid black points at distance $1$ we colour the circumference of the unit circle centred at $P$ white too. Then every point in the circle is unit distance from some point on the circumference, to so the interior of the circle has to be white. Eventually we conclude that the whole plane is white, which contradicts the existence of a black point.

share|improve this answer
1  
This. Basically they meant that every point on the plane is either black or white... –  UncleZeiv Jul 26 '13 at 15:49
add comment

Assuming every point of the plane is either white or black, here is a quick "constructive" way to find two points of opposite colour at distance$~1$. Since there are both white and black points, the infimum $r$ of the distances between white and black points is well defined. If $r>0$ then there exist a black-white pair at distance $d$ with $r\leq d<2r$, and the midpoint between them is at distance $d/2<r$ of either, so it cannot be black or white by the choice of $r$, a contradiction. So $r=0$, and there exists a black-white pair at distance $d<1$ of each other. The circles of radius$~1$ centered at these points intersect, and pairing the two centers with the two intersection points one gets at least one black-white pair at distance$~1$ (in fact one gets two pairs).

share|improve this answer
    
This is a nice answer. –  John Bentin Jul 26 '13 at 17:34
    
I don't think this assumption is what the interviewer had in mind, but it's such an elegant demonstration that I can't help but +1. :-) –  ruakh Jul 26 '13 at 20:21
add comment

Since we are dealing with only two colors for us to differentiate between dots of similar color (say black) we will need a white dot, and vice-versa. If not we will be having just one big dot.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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