Let N be the set of natural numbers \{1, ..., n\} for a given n. We write the powerset (set of all subsets) of N as 2^N. Call a k-element subset of 2^N dobbly if each of the {k \choose 2} pairs of subsets have exactly one number in common. (Note the confusing meta subsettiness – we’re talking about subsets of the set of subsets of N!)
What’s the biggest possible k, i.e, how big is the biggest dobbly subset of 2^N?
Why should there be a maximum k? It seems that k can be arbitrarily large, unless I’m missing something.
It is known that for each n which is a power of a prime there exists a finite projective plane of order n. (And it’s conjectured that these are actually all the finite projective planes.) Such a plane has n^2 + n + 1 points, which we can number from 1 to n^2 + n + 1. (I’d prefer to number them from 0 to n^2 +n, but for the purpose of this puzzle the natural numbers start from 1. Fine, if you insist. I can do it that way too.)
For each line in this projective plane, we can then take the set of natural numbers (a subset of 2^N) which includes exactly those numbers that were assigned to the points on that line.
By the definition of a projective plane, each pair of lines intersects at exactly one point, so indeed each pair of such sets has exactly one number in common. Therefore the set of these sets is dobbly (and has n^2 + n +1 elements, because finite projective planes have the same number of lines as points.)
That means that for all k of the form n^2 + n + 1 where n is a power of a prime, we can find a set that is dobbly. Such k-s can be arbitrarily large, because primes (and powers of primes) can be arbitrarily large.
So am I missing something? The way the puzzle is worded, it seems to be that you expect there to be a biggest possible k. But I’m pretty sure that my proof shows that there is no upper limit to how high k can be.
I interpret it as asking for the biggest k relative to some particular, given value of n.
Ohh, that makes sense. I guess I misread the puzzle, taking “Let N be the set of natural numbers” to be that N is, well, the set of natural numbers, as N often indicates. I completely missed that it was actually meant to be all the natural numbers between 1 and some given n. Never mind then.
Well, we can run the same logic in reverse: each dobbly subset S of 2^N defines a finite projective plane, where each element of S defines a line through points indicated by its elements. So the question is equivalent to asking what is the largest order of finite projective plane with less than n total points. A finite projective plane of order x has x^2 + x + 1 points.
Given the conjecture that all finite projective planes are of an order that is a power of a prime, the answer to the puzzle is that the biggest k must be the largest number of the form p^a for some prime p and positive integer a such that k^2 + k + 1 is less than or equal to n.
That’s far from an nice formula for the largest such k, but it doesn’t seem like there is a better way to put it.
It’s interesting to note that this problem seems to depend on a major open problem: the proof of the conjecture that these orders of finite projective planes are the only ones to exist.
Right, N not \mathbb{N}. 
PS: And I just edited the problem statement to emphasize "for a given n". Thank you!
Dang, @zzq, you are multiple levels above me right now. But are you saying that for, say, n=57 the answer would be at most 7 because 7^2+7+1 = 57? If that’s right then I think your answer is wrong!
I’ve looked at a problem like this before, where I was essentially trying to generate dobbly sets. I ended up with something based on labelling the latices of a hypercube. Based on that, I tried to get some sort of intuitive grasp of what’s going on here, which I am sharing in the hope it helps others, and may also clarify if I’ve misunderstood the problem…
Constructing dobbly sets is (as @zzq pointed out) related to finite projective planes. One of the simplest projective planes to visualize is the Fano plane:
So here n=7, giving us N={1,…,7} . The 3-element dobbly set of subsets, if I understand the problem statement correctly, is here found by taking the points on each of the lines:
{ {1,3,2},{1,5,4},{1,7,6},{4,6,2},{4,7,3},{2,7,5},{1,4,5} }
By inspection, each set has a single element in common with every other set, so this is a dobbly set, with k=7 Of course, 7=2**2 + 2 + 1, which is of the form @zzq describes.
There are other geometric constructions for a few higher order projective planes, such as this for the third order plane:
Here, n=13, the elements of the dobbly set are things like {1,2,3,11}, and counting them we get k=13, with sets of size 4.
After some hunting, I found a pretty neat Mathematica page which allows you to produce the appropriate picture for projective planes of low orders: https://demonstrations.wolfram.com/ProjectivePlanesOfLowOrder/
So based on all this, I think the last comment from @dreev is a misunderstanding - for n=57, you would get k=57 as well, I think (corresponding to the projective plan of order 7).
This seems to produce (presumably maximal) answers for any prime n that can be expressed as x^2+x+1, for integer x: such a set is analagous to a projective plane of order x, and has a dobbly set of size n, each subset in the dobbly set containing x+1 elements.
For non-prime n, I’m still struggling. I can see how one might product similar types of constructions for some kinds non-prime n, still of the form x^2+x+1, e.g. n=21, (please excuse my crappy hand-drawing, I’m not sufficiently au fait with the graphing packages in R or Python to do this justice - and the diagonals get pretty hairy as they wrap around when you put them on a 2-d plane, but I hope you can see what I mean):
Whether this produces the maximum k for such given n, I don’t know, although it seems very likely in this special case. As for other formats of n, I’m still thinking about that…
Edit: I’ve changed around a few of the numbers in this post to fix a(nother) mistake. The underlying logic still holds, and with these numbers adjusted I think I’m right this time.
Yes, that’s more or less what I’m saying. Except that I think I have an off-by-one error there (edit: more than off by one): a finite projective plane of order m has \enclose{horizontalstrike}{m + 1} m^2 + m + 1 lines, each crossing throuh m + 1 points .
So in the language of the puzzle: for a finite projective plane of order m, there are k = m^2 +m + 1 subsets of 2^N, each with m+1 elements.
So my revised answer actually is that the biggest k must be the largest number m^2 +m + 1 less than or equal to n where m has the form p^a for some prime p and positive integer a.
In the case of n = 57, that means that the answer is 57 itself, where m = 7 ( = 7^1)
Note that I said that answer is 57, not that the answer is at most 57. Yes, the answer is at most 57 here, but also we know that 57 is a possible value for k, by taking the set of subsets of 2^N based on a finite projective plane of order 7 (which we know exists, because 7 is a power of a prime, 7 = 7^1).
Given k can’t be more than 57 and k = 57 is possible, the maximal value of k (for n = 57) is 57.
A projective plane of order 7 has 8 lines, each going throuh 8 of the 57 distinct points. k, in @dreev’s post, is defined to be the number of subsets of 2^N, which in the language of projective planes mean the number of lines. Thus k = 8 here.
Remember that the number of points in a finite projective plane is m^2 + m + 1, where m is the plane’s order. It is known that planes of any order of the form p^a where p is prime and a is a positive integer exist. It is a fairly major open question whether or not these are the only finite projective planes to exist.
But note that this is referring to the order of the finite projective plane, not the number of points that plane has.
This works, but only because 21 = 4^2 + 4 + 1, where 4 = 2^2 (a power of a prime). It’s not 21 which needs to be the power of a prime, it’s the x in the formula x^2 + x + 1.
OK, I’m obviously confused. I thought this was a projective plane of order 3:
But this seems to me to have 13 lines, each going through 4 of the 13 distinct points… so maybe I’m misunderstanding what “line” means here, and actually it’s equivalent to the 4 points of convergence, for example { {1,2,3,11},{4,5,6,11},{7,8,9,11},{13,12,10,11} }, or maybe something weirder like the possible distinct labellings of the vertices?
Based on my guess as to what this problem is really about (sets like the game Spot-it! or Dobbly), I’m not sure which @dreev is actually after - the number of (traditionally viewed) lines, i.e. 13 in this particular case (so how many cards you’d have in your Spot-it set), or the number of what’s called lines in your usage, which is maybe 4 or something for this case (which is the number of different Spot-it sets you could create of a particular size)… Maybe he will clarify…
No, you’re right. Your example indeed has 13 = 3^3 + 3 + 1 lines. I was confused because I was thinking of the number of lines which intersect each point, which is 4 (the same as the number of points on each line.)
Thanks for pointing that out, because it means that some of what I said before is a bit messed up. What I said about it being the order (not the number of points) which (probably) must be a power of a prime still holds.
But yeah, you’re right that it’s the number of lines (which is the same as the number of points) which is k in the original problem.
