# Path from $(1, 1)$ to $(4, 4)$ with least number of lattice points within a certain distance

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.

-
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
Maybe you should think of a better name for your question. This one is too vague. – Oltarus Nov 1 '11 at 7:44

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?
+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