Skip to main content
4 of 9
added 197 characters in body
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$ selections 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 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.

There is a solution with 60 blocks: split the points into two sets of 25 and use the 30 lines of an affine plane of order 5 on each. This is overkill because any 3 element set has two points in a block.

corrected If the points are partitioned into 4 groups of 13 (with one point allowed to live in 3 groups) and then (for each group) the lines of a projective plane of order 3 were taken as blocks this would give a solution with 52 blocks (of size 4). Now there are sets of 4 points no two in the same block. But any set of 5 points has at least two in the same group and such a pair determines a unique block. Of course we can arbitrarily add a fifth point to each block and get a solution with 52 blocks. This certainly makes it seem as if the optimal number is quite a bit lower.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104