# Fixing code for a combinatorics problem

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?

• 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?
– JimB
Commented Jun 24, 2023 at 18:07
• 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)$
– ydd
Commented Jun 24, 2023 at 18:26
• 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. Commented Jun 24, 2023 at 23:28

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]


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.