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!

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