4

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!

Harish Chandra Rajpoot
  • 37,450
Kevin Xu
  • 41
  • 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 01 '11 at 03: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 01 '11 at 04:10
  • 1
    Maybe you should think of a better name for your question. This one is too vague. – SteeveDroz Nov 01 '11 at 07:44

1 Answers1

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.

Greg Martin
  • 78,820
  • +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)$ – SteeveDroz Nov 01 '11 at 07: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 01 '11 at 20:34