Set $T$ consists of $66$ points in plane, and $P$ consists of $16$ lines in plane. Pair $(A,l)$ is good if $A \in T$, $l \in P$ and $A \in l$. Prove that maximum number of good pairs is no greater than $159$, and prove that there exits configuration with exactly $159$ good pairs.
Problem
Source:
Tags: linear algebra, matrix, function, inequalities, combinatorics
09.04.2011 19:09
count good pairs in two ways an note that two lines can have at most one point in common one of my friends told me the example uses block designs.
09.04.2011 22:48
Not quite so immediate. Consider a $66 \times 16$ matrix, where the rows are associated to the points and the columns to the lines. Entry $(i,j)$ in the matrix is $1$ if point $i$ lies on line $j$ (i.e. the pair $(i,j)$ is good), and $0$ otherwise. Denote by $r_i$ the numbers of entries $(i,j)$ equal to $1$ on row $i$. Then the total number of good pairs will be $N = \sum_{i=1}^{66} r_i$. Let us count the number $M$ of pairs of entries equal to $1$ on the rows of the matrix. On one hand, $M = \sum_{i=1}^{66} \binom {r_i} {2} = \sum_{i=1}^{66} \dfrac {r_i(r_i - 1)} {2}$. On the other hand, for each of the $\binom {16} {2} = 120$ pairs of columns, there is at most one such pair of entries equal to $1$, since two lines meet at at most one point. Thus $M \leq 120$. The function $f(x) = \dfrac {x(x-1)} {2}$ being convex, we have $120 \geq M \geq \dfrac {66} {2} \dfrac { \sum_{i=1}^{66} r_i} {66} \left ( \dfrac {\sum_{i=1}^{66} r_i} {66} - 1 \right ) = \dfrac {1} {2} \dfrac { N(N-66)} {66}$. From this inequality $N^2 - 66N - 66\cdot 240 \leq 0$ follows $N \leq 163$ (by calculating its positive root). But equality in the Jensen inequality occurs for all $r_i$ equal to some value $r$, and so $r = \dfrac {N} {66}$, so $2<r<3$. Since the $r_i$'s must be integer, we cannot have the equality case, so the closest possible match in the inequality will occur for $\alpha$ values $r_i$ equal to $2$ and $\beta$ values $r_i$ equal to $3$, obeying the restrictions $\alpha + \beta = 66$ and $\alpha + 3\beta \leq 120$, whence $\beta \leq 27$. But then $N = 2\alpha + 3\beta \leq 159$. The model will have to exhibit a configuration of $66$ points and $16$ lines, with $\alpha = 39$ points lying on two lines each, and $\beta = 27$ points lying on three lines each. Start with a general configuration of $16$ lines, having $\binom {16} {2} = 120$ points of intersection. Reserve $39$ of them for the points lying on exactly two lines each. The remaining $81$ points will be grouped in $27$ groups of three, accounting for the $27$ points lying on three lines each, and the configuration needs be distorted so that each of the three points in a group are made to coincide. Probably a more geometric model can be described, but, definitely, this has nothing to do with block design theory.