4
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ross Millikan
    Commented Sep 26, 2022 at 3:05
  • 1
    $\begingroup$ Seems like a Graph theory problem. Luckily for me, I am totally ignorant of Graph theory. $\endgroup$
    – user2661923
    Commented Sep 26, 2022 at 4:32
  • 1
    $\begingroup$ @RossMillikan You’re probably thinking of linear code or something similar? $\endgroup$
    – VTand
    Commented Sep 26, 2022 at 4:37
  • $\begingroup$ @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. $\endgroup$
    – Ross Millikan
    Commented Sep 26, 2022 at 4:38
  • $\begingroup$ What contest is this from? $\endgroup$
    – Parcly Taxel
    Commented Sep 26, 2022 at 7:07

1 Answer 1

Reset to default
2
$\begingroup$

This is impossible.

What you are looking at is a constant weight binary code. You can apply the (see Theorem 2 Wikipedia) Johnson bound to get an upper bound on the number of codewords.

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.$

$\endgroup$
6
  • 1
    $\begingroup$ 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). $\endgroup$
    – radekzak
    Commented Sep 26, 2022 at 14:51
  • 1
    $\begingroup$ 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$? $\endgroup$
    – kodlu
    Commented Sep 26, 2022 at 17:13
  • 1
    $\begingroup$ 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)$ $\endgroup$
    – radekzak
    Commented Sep 27, 2022 at 18:49
  • 1
    $\begingroup$ @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$. $\endgroup$
    – VTand
    Commented Sep 28, 2022 at 18:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – radekzak
    Commented Sep 29, 2022 at 21:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .