1
$\begingroup$

The problem I am solving is:

Determine all possible values of positive integer $n$, such that there are $n$ different $3$-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.

I already know that every $n=4k$ satisfies the conditions. I am verifying this with the following code:

n = 4;
sets = Subsets[Range[n], {3}]
AllTrue[Length /@ Intersection @@@ Subsets[sets, {2}], # != 1 &]

However, when I set $n = 8$, the result is False, which is incorrect.

How can I fix my code?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I'm not following. There are 56 different 3-element subsets when $n=8$. Do you mean that one can find a set of 8 of those 56 that satisfy your restriction? Or am I missing something? $\endgroup$
    – JimB
    Commented Jun 24, 2023 at 18:07
  • 4
    $\begingroup$ there are more than n different 3-element subsets that satisify this condition for any integer n>3. In fact (kind of unrelated but interesting), there is a closed form for the number of 3-element subsets satisfying your condition: $\frac{1}{72} (-3 + n) (-2 + n) (-1 + n) n (38 + (-9 +n) n)$ $\endgroup$
    – ydd
    Commented Jun 24, 2023 at 18:26
  • 1
    $\begingroup$ Your code tests every pairwise intersection of all the 3 element subsets of 8 element set. This is not exactly what you want. Restating your problem, there exists a collection of n different subsets agreeing with condition. You need to find them. A strategy is to partition your 4k set into k 4 element sets and then 3 subset each 4 element set. The 4 element will always satisfy your conditions: {1,2,3}, {1,2,4}, {2,3,4}, {1,3,4}: each intersection length 2. $\endgroup$
    – ubpdqn
    Commented Jun 24, 2023 at 23:28

1 Answer 1

Reset to default
4
$\begingroup$

See my comment.

Here is a way to construct sets of size 4 k fulfilling requirement.

fun[n_? (Mod[#, 4] == 0 &) ] : = Module  [ {p = Partition [Range [n], 4]},Join @@ (Subsets [#, {3}] & /@ p) ]

Testing

fun[8]

enter image description here

Now testing that is it satisfies condition:

test[u_]:=AllTrue[Intersection @@@Subsets[u, {2}], Length[#] != 1 &] 


test[fun [8]]

gives True, as does:

test[fun [12]]

I apologize for the formatting. I don’t have access to computer. This was done from phone and Wolfram cloud. Of course, I apologize for any errors or misunderstanding.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.