Finite sets and parts. For which integers N is the following possible?

Projective planes provide some sparse examples, namely for

N=1, 3, 7, 13, 21, 31, 57, 73, 91, 133, ...

But your arrangements need not be projective planes. You have enforced the axiom that each pair of lines intersect in exactly one point. You have not enforced the "trivial" axiom of having four points no three of which are collinear, and you have not enforced that each pair of points determines a line.

I can't at the moment come up with an example that doesn't spring from a projective plane, nor can I think of a reason that forcing the same number of points as lines should force the arrangement to be a projective plane...I'll keep working on it, but I wanted to point out the projective planes in the meantime.

EDIT: I haven't had time to read through your arguments, but if it's true that each point is in the same number of intersections, then it follows that each point is in the same number of sets A_i (or "lines" or "blocks"). This is another key consequence of projective planes; in fact I noticed that Wolfram's definition is different from the one I'm used to, and we now have their axioms 3 and 4 (but they take as given that the number of points is of the form n^2+n+1...)

Just as a quick guide, projective planes are a set of "points" and a collection of sets of points called "lines" that satisfy three axioms. First, to prevent some trivial things, there must be four points, no three of which are on a line. Second, each pair of points "determines" a line, i.e. there is a unique line containing them. Third (and dual to the second), each pair of lines "intersects" in exactly one point. It can be proven that these imply that the number of points in each line is the same (call it n+1), the number of lines passing through one point is always also n+1, the number of points and lines are both n^2+n+1. Projective planes of "order n" exist whenever n is a prime power; it is conjectured that for other n projective planes do not exist (though these days there is significant doubt about the truth of the conjecture). I believe n=6 and n=10 have been ruled out (10 having used a lot of computer checking); n=12 is the next undecided case.

I prefer n instead of N. Then there is nC2 pairs of subsets.

For any element e_i of E consider the number |e_i| = the number of subsets A_1,...,A_n that contains e_i. Then {e_i} is the intersection singleton for |e_i|C2 pairs. From this it follows that

nC2 = ∑|e_i|C2, i=1 through n

and

k∙n = ∑|e_i| or put otherwise: n divides the sum ∑|e_i|

This provides a way of excluding some values of n (and k).

Answer to gianlinos comment:

_____________________________

If I get you right, gianlino, you mean that we cannot have any |e_i|>k since it would imply that any set A_j not containing |e_i| would have a size of |A_j|≥|e_i|>k contradicting |A_j|=k. Thus {e_i} would be the intersection of every pair. But this leads to another contradiction, since it implies |e_i| = |e_i|(k-1)+1 <=> |e_i| = 1/(2-k) which only has a positive integer as solution when k=1=n=|e_i| which is useless and not satisfying |e_i|>k.

Finally we have (just about) solved the problem:

------------------------------------------

This is actually a quite interesting point, I should think, as it shows that there must be some sort of symmetry since every element of E is in the same amount of intersections. Furthermore it simplifies the two equations above (the second can actually just be left out now) so that

nC2 = n(kC2) or put otherwise n(n-1)/2 = n·k(k-1)/2 <=> (n-1) = k(k-1)

This shows that n has to be an integer one higher than a product of consecutive integers. For m = k-1 we get n = m²+m+1 which is the formula for projective planes given in gianlinos link. So n must be found among:

3, 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, ...

If the two lists match we have proven exactly what was asked for (as a collaborate job by Ben, gianlino and me). I consider the problem as good as solved :). Then Ben proved the existence of certain solutions and gianlino and I proved that no other exists...

@gianlino:

I am not sure how we have showed that only projective planes are solutions. What is the argument that no setup with n=43 and k=7 is possible for the sets? Maybe it is because I don't understand projective planes well enough.

Extending your example...

If k=2 is allowed, then it's possible for all N>2.

{a1,a2}, {a2,a3}, {a3,a4}, ... {an,a1}