4
$\begingroup$

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!

  • 1
    Maybe you should think of a better name for your question. This one is too vague.2011-11-01

1 Answers 1

4

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.

  • 0
    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)$....2011-11-01