Suppose three direction on the plane . We draw $ 11$ lines in each direction . Find maximum number of the points on the plane which are on three lines .
Problem
Source:
Tags: induction, inequalities, combinatorics proposed, combinatorics
16.05.2009 23:05
This is a Russian question, most possibly a 4th round question of 9th grades - 4th question maybe. I couldn't find the year - even anything about it - on Internet about it but anyways.
21.05.2009 03:12
Is it $ 11 + 2 \times (10 + 9 + 8 + 7 + 6) = 91$ ?
21.05.2009 12:15
Yes, it is.
15.07.2009 15:07
Why can't it larger than 91?I find it hard to prove.
01.12.2011 14:16
here we go, I hope it's not wrong : by an affine transformation, you may assume that the three directions are these directions: 1) parallel to the $x$-axis of the cartesian plane. 2) parallel to the $y$-axis. 3) parallel to the line $x=y$. now fix the lines of the first two groups, so they form a $11\times 11$ table. call a point of the plane which is on three of the lines special, and call each line of the third group good. an easy induction (omiting the first row and the first column) shows that we can have at most $1$ good line with $11$ special points on it, at most $3$ good lines with $10$ special points on it, at most $5$ good lines with $9$ special points on it, at most $7$ good lines with $8$ special points on it, at most $9$ good lines with $7$ special points on it, and at most $11$ good lines with $6$ special points on it. now using these inequalities, we obtain that there can be at most $11+2(10+9+8+7+6)=91$ special points. its example is easy to construct.