My first shot would be: 6908733

You can choose each of the 13 elements as 'intersecting element'. Each of the remaining 12 Elements can either be in Set1, Set2, or in none of these (3 possibilities).

This would be 13*3^12=6908733

Ok, I misread the question and solved something else. :)

+1 uclabb. I am going for 78, by the way.

But that's after 1-2 mins thinking about it.

Well, Tru is a teacher (want to say professor at WKU?) so...

No, Tru Ninja's master student right now, not a prof. I think he's getting his MAT.

After reading the question again my second shot would be 13. :)

That would be the sets: {1}, {1,2}, {1,3}, ..., {1,13}

I think mr.A is right.
Any 2 intersect at exactly 1 element, means all sets must intersect in just one element, so no two sets can intersect in more than 1 element... that means there is 13 sets.

Nope, I'm still working on my undergrad :( This is homework for my discrete math class. I can tell you all that the answer cannot be greater than the number of elements in A, so 78 is out.

78 is the answer if you have 13 choose 2 to determine the number of subsets of A such that no subset is a subset of another one.

There are 2^13 subset possibilities.

Mr A is correct that there are 13 subsets, but that's not a proof to the question. It's simply one answer that happens to be correct. If I were to say that all of the subsets had the same number of elements, how would you answer? (The answer is still 13).

{1234}, {1567}, {18910}, {1111213},{25811}, {26912}, {271013}, {35913}, {351012},{36812},{36911}, {37812},{37911}

42

If we have the set, {1,2,...,n} and a number of sets that satisfy the condition. Clearly there exists 1 <= a <= n such that {a} would be in the sets.

Continuing from that, you can easily follow the same reasoning as Mr_A and find that there are only (n-1) sets left that do follow the conditions.

whoops... I messed up the end of my post... the last 3 should start with a 4 and the whole idea is just to permute through the first 4 subsets... what I posted is kinda all over the place, though.

but that doesn't answer the question why it is at most, because it assumes {a} is in the set, which isn't a necessary condition

I think you can't solve the problem with equally sized subsets for each n. n=4 appears to be tricky for instance.

Btw. the problem I tried to solved in my first reply (misreading the op) was:
In how many ways can you divide {1,...,13} into two subsets intersecting by exactly one element.

{1234}, {1567}, {18910}, {1111213},{25811}, {26912}, {271013}, {351012}, {36813}, {37911}, {45913},{461011}, {47812}

There. Fixed.

You can follow that general form for all n = x(x+1) + 1. I will think about other n later if you want, but I have topology and quantum mechanics p-sets to do myself.

@Mr A, yes, you can solve the problem with equally sized subsets however, you're limited to the number of subsets. For example, with 8-element sets or higher, you can have exactly 1 subset that satisfies the condition that any two subsets have exactly one element in common.

In fact, all subsets must have the same number of elements if there are any subsets with n > 2 elements. The only time you can have subsets of varying sizes is if you have as you posted earlier with {1}, {1, 2}, ... , {1, 13}.

@ Mittag: I like where you started with your proof. I'm going to continue the logic and see where I get.

@ uclabb, not sure where you're going with your most recent post, but I agree with the 4-element subsets (with missing commas) as a good example.

@Tru-

Not sure what you are saying about having to have the same number of elements with n>2. For example, the set of sets {{1,2},{1,3},...{1,n}, {2,3,4,5,6,...,n}} works for any n and has a subset of size n-1

The general form I refer to for subsets of the same size for n = x(x+1) +1 for integer x is, loosely,
{{1,2,3,...(x+1)},{1, x+2,...},...{1,...n},{x sets that have a 2},{x sets that have a 3},...{x sets that start with a (x+1)}}, like in the example for n=13, x=3 I posted above.

If I were to try to prove that 13 (or more generally n) is the largest number of sets possible, I would probably think of it in a graph theoretical sense (is that what you are doing now in discrete math). It seems very possible to me that you could reduce this question to one about hamiltonian paths, but I'd have to think about it a bit.

There's a fairly straightforward method using matrices. Simply write out the collection of subsets (let's say there are N of them) as a matrix, each row representing a subset, and each column, an integer from 1 to n. Entry a_ij is 1 if the i-th subset contains j, 0 otherwise. Call this matrix B. B has N rows and n columns.

Consider M = BBt (Bt is B transpose)

M has 1 at all non-diagonal locations, and m_ii is the the size of the ith subset. This matrix isn't singular (see below for why), so rank(M) = N. Remember that you essentially took B and linearly combined its columns in several different ways to get M. So N = rank(M) <= rank(B) <= n ( the number of columns of B )

or N <= n which says that the number of subsets is at most the number of distinct elements you had at the start, but we know we can achieve equality already, so N = n.

----

Now for the bit about showing why that matrix isn't singular, the rows look like
a11111...
1b1111...
11c111...

and out of a,b,c... at most one of them is 1, all the others are larger. It is immediate that these vectors are all linearly independent (just linearly shifted versions of vectors pointing along different axes), completing the proof.

^awesome proof!. Except that linearly shifting a set of linearly independent vectors may not preserve the linear independence. For instance, (1,0,0) (0,1,0) (0,0,1) are linearly independent, but shifting them all by (-1/3,-1/3,-1/3) gives (2/3,-1/3,-1/3), (-1/3,2/3,-1/3), (-1/3,-1/3,2/3) all of which lie in the plane x+y+z=0

But in this case, we can find the determinant using Gaussian elimination, and show that it is not 0.

for the cardinality of a = 10, this is just 13 choose 10. so if you have a choose button on your calculator, do that.

for the intersection question, i'm not convinced you have to pick a specific element to be the intersecting element across all sets, but if that is true, then choose for each element if it's going to be in your set or not, assuming the one number is. that one would be 2^(13-1).

so my guesses are 286 and 4096. assuming a single intersecting element. but actually now that i read that you say "I can tell you all that the answer cannot be greater than the number of elements in A, so 78 is out."... maybe you're talking about independent subsets, so it would be a different answer.

actually if the subsets were independent there would not be any intersecting elements. so i guess i'm confused. oh well, that's all i have.

oops. i failed... but 286 is still right. so take that to the bank

if you're right that the number of elements cannot be greater than the number of elements in A, then it is the cardinality of A, because you could have {1,2} {2,3}...{12,13}{13,1}. and that has 13 subsets in it.

That doesn't work, bolshoi. {1,2} and {12,13} have no intersection.

haha. yeah that's true... i am an idiot. but here is the real answer. {1} {1,2}...{1,13} so still 13 sets. done.

actually i see the answer was already posted.

what uclabb wrote really is messing with me. It's good stuff... I'm about to write a program that brute forces this bugger to see what the true answer is...

http://f.images.memegenerator.net/instances/400x/15152861.jpg

Sorry if this has already been caught (I've been scanning), but uclabb's answer and MrA's answer are both right, but the question is... which one has more subsets?

The idea of brute forcing it in a computer program just got a lot more complicated...

Damn, should have read into the thread before replying...
It's been a while since linear algebra, but I can see a lot of merit in santosh's reply. Seems like the proof would be a whole lot easier by using linear algebra concepts.

If you like uclabb and santosh's contributions, you might find this interesting

http://www.renyi.hu/~p_erdos/1948-01.pdf