Guys this problem really bothers me (I don`t know how to prove it) please help:
What is the maximum number of points in convex position on a $n\times m$ grid?
(My guess would be $2*(m+n)-4$.)
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Your guess is correct. There are at most two vertical sections which contain more than 2 points. So, totally we have at most $m+m+(n-2)2=2m+2n-4$ points. The example is the perimeter of the grid.
answered Aug 5, 2017 at 12:27
-
$\begingroup$ oh yes right, thank you very much .... $\endgroup$– KhandanCommented Aug 5, 2017 at 12:37
-
$\begingroup$ i am thinking now what would happen if we consider the grid made of two sets of concentric circles instead of lines ?! $\endgroup$– KhandanCommented Aug 5, 2017 at 12:38
-
$\begingroup$ Dear Petrov , as you have a clear vision about this question , may i please ask for your opinion about the circle case : maximum number of points in convex position on a grid made by two sets of concentric circle , one set m circle and another n circles ?.....thank you very much $\endgroup$– KhandanCommented Aug 5, 2017 at 12:56
-
$\begingroup$ I do not know immediately, this looks a solvable, but not trivial problem. I recommend to post it in a separate MO question. $\endgroup$ Commented Aug 5, 2017 at 14:45