# can one select 102 17-element subsets of a 102-element set so that the intersection of any two of the subsets has at most 3 elements

Can one select 102 17-element subsets of a 102-element set so that the intersection of any two of the subsets has at most 3 elements?

I'm not sure how to approach this problem. I think it might be useful to try to find a generalization of the result so one can work with smaller numbers and try to find useful lemmas/properties. In particular, $$17$$ is prime, so one could replace that with $$p$$. Then $$p(p+1)/3 = 102.$$ So it might be reasonable to guess that one can always select $$p(p+1)/3$$ $$p$$-element subsets of a $$p(p+1)/3$$-element set so that the intersection of any two of the subsets has at most $$3$$ elements. Also, $$17\cong 2\mod 3, 17\cong 2\mod 5.$$ For $$p=2,3$$ the problem is straightforward. For $$p=5,$$ we need to find $$10$$ $$5$$-element subsets of a 10-element set so the intersection of any two has at most $$3$$ elements. I'm not sure how to find the subsets in this case.

It might be useful to consider something related to modular arithmetic modulo the prime p.

• Usually problems like this have simple solutions if you find the right thing to count. The simple solutions often allow coarse approximations to be made. As you tagged it contest-math there is probably a clever trick needed to get this close or a clever construction that succeeds. There is a whole field of study of these questions, but I forget what it is called to give you a search term. The fact that $17$ is a factor of $102$ may be important. Sep 26, 2022 at 3:05
• Seems like a Graph theory problem. Luckily for me, I am totally ignorant of Graph theory. Sep 26, 2022 at 4:32
• @RossMillikan You’re probably thinking of linear code or something similar? Sep 26, 2022 at 4:37
• @VTand: That is the sort of clever construction I was thinking about. It seems natural to select our subsets as disjoint groups of $6$. We need $17$ of those. There might be a known code that does this, but it is not known to me. Sep 26, 2022 at 4:38
• What contest is this from? Sep 26, 2022 at 7:07

Here $$q=2,w=17,n=102,$$ giving $$d=2\times17-3=31$$ and $$e=(31+1)/2=16.$$ I get that the maximum possible number of codewords in such a code must obey $$A_2(102,31,17)\leq \left\lfloor \frac{102}{17} \left\lfloor \frac{101}{16} \right\rfloor \right\rfloor=36$$ since $$A_q(n,d,w)\leq \left\lfloor \frac{nq^\ast}{w} \cdots \left\lfloor \frac{(n-w+e)q^\ast}{e} \right\rfloor \cdots \right\rfloor$$ with $$q^\ast=q-1$$ since $$d\leq 2w.$$
• I think $d$ is actually equal to $28$, since two $17$-element subsets with three common elements differ on $2 \cdot (17-3)$ places (their symmetric difference). So the Johnson bound gives something like $1740$ (we have four terms, so the situation gets much worse). Sep 26, 2022 at 14:51
• Sorry but if the 3 elements are common don't you just use PIE $N(A)+N(B)-N(A \cap B) = 2\times 17-3$? Sep 26, 2022 at 17:13
• But, if I understand correctly, we don't want to look at $A \cup B$, we want to look at the places where these subsets differ, which is $(A \cup B) \setminus (A \cap B)$ Sep 27, 2022 at 18:49
• @radekzak I believe $d$ is the minimum Hamming distance among any pair of codes. The Hamming distance could be anywhere from $2 \times 17 - 3$ to $2 \times 17$, so $d = 2 \times 17 - 3 = 31$. Sep 28, 2022 at 18:10
• Moreover, here we can even find a counterexample: take a projective plane over $\mathbb{F}_8$ and a projective plane over $\mathbb{F}_7$. Together they have $100$ points. Now take subsets consisting of a line in $\mathbb{PF}_7$ paired with another line from $\mathbb{PF}_8$, so that lines in distinct subsets don't repeat. We make $43$ subsets in this way (using all the lines mod $7$, although we will have some spare lines over $\mathbb{F}_8$), and intersection of any two of them has cardinality at most two. Now, if we calculated $d$ in a correct way, we would have at most $36$ subsets. Sep 29, 2022 at 21:05