1
$\begingroup$

Let number of elements in a set be $1,2,3...n^2$ , for a given "n" . I want to know the number of subsets having "n" elements such that any two sub-sets have at most one element in common.

Example: For $n=2$, we have $\{1,2,3,4\}$ in the set. And number of subsets satisfying the above criteria is $\{1,2\}, \{3,4\}, \{1,3\},\{1,4\},\{2,4\},\{2,3\}$.

$\endgroup$
1
  • $\begingroup$ This is a variant on the Kirkman schoolgirls problem, which see. $\endgroup$ May 29, 2012 at 12:29

2 Answers 2

2
$\begingroup$

Note that any 2-element subset cannot occur as a subset of a chosen n-element subset more than once. Moreover, each n-element subset involves ${n}\choose{2}$ such subsets So $\frac{{n^2}\choose{2}}{{n}\choose{2}}$ is an upper bound. This is divisible by n, so there are no problems with us not being able to distribute subsets having different elements equally. Looking at a few example, this seems possible to achieve. eg.

1 2 3

1 4 5

1 6 7

1 8 9

2 4 8

2 5 7

2 6 9

3 4 6

3 5 9

3 7 8

4 7 9

5 6 8

$\endgroup$
2
$\begingroup$

Here's a construction that works if $n$ is a prime.

Instead of calling the elements $1,2,\dots,n^2$, I'll call them $(a,b)$ with $a,b$ running from 0 to 4. Given any two points $(a,b)$ and $(c,d)$, they define a unique line --- but do the arithmetic modulo $n$, and you'll get a line with exactly $n$ points. For example, let's take $n=5$, and consider the line through $(1,2)$ and $(4,3)$. It also goes through $(7,4)$, $(10,5)$, and $(13,6)$; working modulo 5, those points are $(2,4)$, $(0,0)$, and $(3,1)$.

The formula in Wonder's answer gives you the number of lines, and no two lines intersect in more than one point.

The technical name for all this is "the affine plane over the field of $n$ elements."

The construction doesn't work so well when $n$ isn't prime. E.g., when $n=4$, the line through $(0,0)$ and $(1,0)$ and the line through $(0,0)$ and $(1,2)$ intersect at two points, $(0,0)$ and $(2,0)$. Technically, what's happening here is that the integers modulo 4 don't form a field. But there is a field of 4 elements, and you can do the construction there, and get your 20 lines. This works as long as $n$ is a prime power, but fails otherwise. E.g., there is no field of 6 elements, so we need another idea if $n=6$.

$\endgroup$

You must log in to answer this question.

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