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 feel that this problem is too obvious, this makes me really confused. If someone could just confirm whether I am right or wrong would be awesome.

We consider paths from (1, 1) to (4, 4) in the Cartesian plane. Now check each point having integer coordinates, such as (2, 3) or (0, 4), and color it blue if it lies within 0.95 units of some point on the path. What is the smallest possible number of blue points one could obtain?

I simply think that you can go from (1,1) to (4,1) then up to (4,4) leaving a total of 7 blue dots.

Thanks in advance!

share|improve this question
2  
But is that the smallest possible number of blue points? Or are there other paths that would give fewer points? You would need to prove that 7 is the smallest possible number of blue points. –  Arturo Magidin Nov 1 '11 at 3:54
    
Hi, thanks for the response. Yeah you are right I do need to prove it, but I wanted a confirmation from someone on my answer. –  Kevin Xu Nov 1 '11 at 4:10
1  
Maybe you should think of a better name for your question. This one is too vague. –  Oltarus Nov 1 '11 at 7:44
add comment

1 Answer 1

I think 7 is the right answer, but it definitely requires proof that someone couldn't come up with a clever curvy path that avoids most points.

Think of the analogous problem where the path goes from $(1,1)$ to $(2,2)$. The "obvious" piecewise linear path through $(2,1)$ would have 3 blue dots. Clearly there will be at least 2 blue dots, namely $(1,1)$ and $(2,2)$ themselves. Can you prove that no matter what the path is, there must be at least a 3rd blue dot somewhere?

If you can solve that "smaller" version of the problem, I bet you could solve the version you stated.

share|improve this answer
    
+1 for iterative thinking, I think it may be the only way to prove that: first from $(1;1)$ to $(2;2)$, then to $(3;3)$ and then to $(n;m)$ –  Oltarus Nov 1 '11 at 7:42
    
Of course, some paths from $(1,1)$ to $(4,4)$ start out going southwest and circle way around and never get close to $(2,2)$.... –  Greg Martin Nov 1 '11 at 20:34
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.