Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and the Yahoo Answers website is now in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
Finite sets and parts. For which integers N is the following possible?
Start with E a set with N elements. You want N subsets A_1,...,A_N of same cardinal k, whose union is E and such that pairwise intersections consist of exactly one element of E for all A_i, A_j,
For N = 3: E = {a,b,c} you can take {a,b} {b,c} {c,a}
For which integers N is this possible?
@husoski, the intersection of any pair of subsets must be a singleton. Ok?
@ String: sorry for not commenting earlier. Something slipped my mind, namely how to show that |e_i| = k for all i. Since, as you observed k∙n = ∑|e_i|, it suffices to show that |e_i| k is impossible.
Suppose e_1 is in A_1.....A_{k+1}. Call f_1 an element of A_1 distinct from e_1. Suppose a subset B distinct from A_1 contains f_1. Then this subset B must intersect the A_i's, 2 =
2 =
Then this subset B must intersect the A_i's, 2 =
Then this subset B must intersect the A_i's, 1
The editor has gone mad. I'll try later
@ String: sorry for not commenting earlier. Something slipped my mind, namely how to show that |e_i| = k for all i. Since, as you observed k∙n = ∑|e_i|, it suffices to show that |e_i| k is impossible.
Suppose e_1 is in A_1.....A_{k+1}. Call f_1 an element of A_1 distinct from e_1. Suppose a subset B distinct from A_1 contains f_1. Then this subset B must intersect the A_i's, 2 =
Hope it works this time!
Suppose e_1 is in A_1.....A_{k+1}. Call f_1 an element of A_1 distinct from e_1. Suppose a subset B distinct from A_1 contains f_1. Then this subset B must intersect the A_i's, 2 =
the A_i's, 2, i , k+1, at elements distinct from e_1. Moreover those spots of intersection must be all distinct since all these A_i's intersect at e_1. It follows that B would need to have at least k+1 elements, which is excluded.
The consequence is that none of the elements of A_1.....A_{k+1} is allowed to belong to more than one set except e_1. This in turn implies that there can be no other set in the collection, because of the pairwise intersection assumption. Finally we get a contradiction since in this configuration, the number of sets k + 1 and the number of elements 1+(k+1)(k-1) = k^2 can't be equal. Ok?
For some reason it blocked on the "less than" sign which I replaced by commas...
@ String Actually what we have showed is that only projective planes are solutions. Therefore the cases 6 and 10 are certainly negatively solved since this appears to be a famous conjecture in combinatorics, according to the same link.
"A finite projective plane exists when k-1 is a power of a prime. It is conjectured that these are the only possible projective planes, but proving this remains one of the most important unsolved problems in combinatorics.
@ String: right the little fiddling we did reducesthe problem to the existrence of projective planes, and combinatorists have proved existence of these planes only for certain values of m. So for the others noone knows yet, except for those mentioned by Ben in his last comment, which are excluded.
3 Answers
- BenLv 69 years agoFavorite Answer
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.
- StringLv 49 years ago
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.
- husoskiLv 79 years ago
Extending your example...
If k=2 is allowed, then it's possible for all N>2.
{a1,a2}, {a2,a3}, {a3,a4}, ... {an,a1}
