Skip to main content
1 of 9
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

You are not using the positions at all. You have 50 points. $S$ is the set of all $\binom{50}{5}=2118760$ subsets of 5 points. You want a subset $B \subset S$ such that any $s \in S$ intersects at least one $b \in B$ in at least 2 points. That is an interesting problem and does not immediately strike me as familiar. If you wanted every pair to be in a block then you would need at least $130$ blocks (since every point is in 49 pairs and every block uses up 4 of those pairs).

I could wonder why $50$ but I won't. Call a member of $B$ a block. A given block intersects $152026$ members of $S$ in 2 or more points. This gives a lower bound of $14$ for the possible size of $B$. Of course this a weak bound since two disjoint blocks have determine $200$ members of $s$ intersecting one in 2 points and the other in 3 and another $4000$ intersecting each in 2 points. If my calculations are correct, that raises the lower bound to at least $19$ blocks. I doubt that $20$ would suffice.

Here is a solution with 30 blocks. In brief: split the points into two sets of 25, consider each as the points of an affine geometry and choose 3 parallel classes from each. Below is a picture of half the points and the 15 blocks they determine. You can see that for any 3 points of these 25, some pair is on a block. If we make another copy of this with 25 more points then any element of $S$ will have 3 points in the same group of 25.

alt text http://img845.imageshack.us/img845/6853/ag25w.png

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104