Skip to main content
6 of 9
added 303 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. It is convenient to allow B to have some blocks with less than 5 points, we can easily bring all blocks up to 5 points.

update: Here is my best result so far. I am leaving in my earlier constructions in case they inspire someone to improve them. I would guess that 30 blocks might be enough but I don't have any justification for that.

42 blocks Split the points into 3 groups of sizes 40,5 and 5. For the large group use the 40 lines of a projective $3$ space of order 3 as 40 blocks each with 4 points. Let the two small group be blocks. Any set in $S$ has two points in the same group and they will be in a common block.


44 blocks. Split into 4 groups of size 21,21,4 and 4. For each of the large sets take the 21 lines of a projective plane of order 4 and let the two small groups be 4 point blocks. Now any set in $S$ has at least two points in a common group and those two pints determine a unique block.

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 some block.

52 blocks 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. Since we only have 4 points in each block, it seems as if the optimal number is quite a bit lower.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104