1

I've played around with this for a while and I've managed to make sets of size 1, 2, 3, 4, 5, 6, 8, and 12 elements where each set is of the same size and has only 1 element in common with every other set.

For example, for sets of size 3, this is one solution:

1. [1, 2, 3]
2. [1, 4, 5]
3. [1, 6, 7]
4. [2, 4, 6]
5. [3, 4, 7]
6. [2, 5, 7]
7. [3, 5, 6]

For sets of size 4, this is one solution:

1. [1, 2, 3, 4]
2. [1, 5, 6, 7]
3. [1, 8, 9, 10]
4. [1, 11, 12, 13]
5. [2, 5, 8, 11]
6. [2, 6, 9, 12]
7. [2, 7, 10, 13]
8. [3, 5, 9, 13]
9. [3, 6, 10, 11]
10. [3, 7, 8, 12]
11. [4, 5, 10, 12]
12. [4, 6, 8, 13]
13. [4, 7, 9, 11]

For sets of size 5:

1. [1, 2, 3, 4, 5]
2. [1, 6, 7, 8, 9]
3. [1, 10, 11, 12, 13]
4. [1, 14, 15, 16, 17]
5. [1, 18, 19, 20, 21]
6. [2, 6, 10, 17, 18]
7. [2, 7, 11, 16, 19]
8. [2, 8, 12, 15, 20]
9. [2, 9, 13, 14, 21]
10. [4, 6, 11, 15, 21]
13. [4, 7, 10, 14, 20]
11. [4, 8, 13, 17, 19]
12. [4, 9, 12, 16, 18]
14. [5, 6, 12, 14, 19]
15. [5, 7, 13, 15, 18]
16. [5, 8, 10, 16, 21]
17. [5, 9, 11, 17, 20]
18. [3, 6, 13, 16, 20]
19. [3, 7, 12, 17, 21]
20. [3, 8, 11, 14, 18]
21. [3, 9, 10, 15, 19]

For each of these collections of sets, every set has only 1 element in common when compared to every other set.

I found that if N is the size of each set, then the maximum possible amount of sets that can be made such that each set has exactly 1 in common with every other set is (N^2 - N + 1) or (N(N-1) + 1), and that is also the amount of numbers that all the sets span (or the amount of numbers in the universal set).

I would like to find a way to construct these sets of any size, such as 7 and 9. The only way I have found so far is an algorithm I wrote based off a pattern I found, which only works for some even numbers (including 6, 8, and 12, but not 10), and through trial and error.

Andrés E. Caicedo
  • 79,201
David
  • 11
  • 1
  • I believe these are known as "finite projective planes" & recommend you carry out a search for that phrase (and then report back to us on what you have found). – Gerry Myerson Jan 08 '20 at 22:37
  • A projective plane of order $N-1$ exists if there is a field of order $N-1$, i.e., if $N-1$ is a prime number or a power of a prime number, so e.g. $N=9$ and $N=10$ are fine. It is not known if there are any other orders where projective planes exist. – bof Jan 08 '20 at 23:33
  • Wikipedia article on projective planes – bof Jan 08 '20 at 23:41
  • I think you meant to include another condition, namely, that each pair of points is covered by one of your sets. Without that condition, you can trivially enlarge your $7$ $3$-element sets to $7$ $k$-element sets for any $k\gt3$. With that condition (and a further condition that there is more than one set in the collection) what you have is a projective plane of order $N-1$. – bof Jan 09 '20 at 07:26
  • @bof You're right, I'm looking for another condition: there are N^2 - N + 1 total sets, and N^2 - N + 1 total symbols in the unviersal set of all the sets. Doing some research, I found that it was proved impossible to do this for N = 7 (7 elements per set, 43 total sets) as well as for a few other numbers. – David Jan 09 '20 at 17:45
  • Yes, what you're talking about is precisely a projective plane of order $N-1$. A projective plane of order $q$ is a finite geometry consisting of $q^2+q+1$ points and $q^2+q+1$ lines, with exactly $q+1$ points on each line and $q+1$ lines through each point; two lines meet in exactly one point, and two points lie on exactly one line. A projective plane of order $q$ is known to exist if $q=p^n$ where $p$ is a prime number and $n$ is a positive integer. It is known not to exist for $q=6$, $q=10$, and certain other cases. – bof Jan 10 '20 at 01:48

0 Answers0