A.E

In case you feel like writing something down, I made a post here: math.stackexchange.com/questions/1078342/…

I have to go, I will keep thinking about it. Thanks for the help, guys.

:)

Yes, each subset is of size Q drawn uniformly from P elements

Pr{A specific element belongs to all N subsets} = (Q/P)^n

@TedShifrin mind giving your input? I have Pr{A specific element belongs to all N subsets}, and I want to calculate Pr{Any element belongs to all N subsets}

I would think we need a factor of P, to account for the P choices of a specific element appearing in all N subsets

No

@Studentmath So this gives me the probability of a specific element appearing in all N subsets: (Q/P)^N.

@Studentmath Well those are independent, so it should just be the product (Q/P)^2

@Studentmath The form I wrote simplifies to Q / P, so then the probability of a specific element not appearing in a given subset is just 1 - Q/P

@Studentmath Yes

Sorry, @stud

*|S|

Given a subset S of P, the probability of some e in P appearing in S is (P - 1 choose |S| - 1) / (|P| choose S)

@TedShifrin, no :P I am just still at a loss on how to count this probability of at least one element appearing in all the subsets.

Right.

Right, so I want to count the probability of some element appearing in every subset.

Yes

No, the intersection of {1, 2, 3} and {1, 3, 4} and {5, 6, 7} is empty

That their intersection is empty

I meant to say

I should clarify: I don't mean mutually disjoint

Hm.

@TedShifrin, I looked at simple cases like where N = 2, but I am struggling with N > 2. I know I need to apply inclusion-exclusion somehow, but I am not sure how

I am struggling with a discrete probability question. Given a finite set of size P, what is the probability that N random Q-subsets (uniformly drawn) will be disjoint?

well, i'll let you all toy with it as you will. it's very late my time and i've been thinking about this problem for far too long today. thanks for hearing me out, i hope one of you gains some insight on the problem.

well at least I'm not alone then! it's been troubling me for almost a week now.

Good luck, I'll check back in when I'm off work. If I have an insight I'll post on your question.

*exchange assignments within the second solution..

Then progressively exchange the second solution to look like the greedy one, and demonstrate that it never lowers in production.

Claim your solution is optimal, and assume there is some other "optimal" solution that disagrees with your assignment at some point.

Prove it, via exchange argument.

But, here is how you can know for sure:

I think it is

I don't have time right now to try and prove whether or not a greedy solution works

Thats what I'm saying.

I might be missing something.

but that still seems greedy

where f(z) is a function that defines how much additional production you yield by assigning the nth item of food to mine X/Y

OPT(n) = max { OPT(n-1) + f(X) , OPT(n-1) + f(Y) }

You could characterize it as a dynamic program though, by defining a recursive function on the sequence of length $n$.

I'm trying to think of a sequence were the greedy method of "give the package to the mine that will yield the highest production" fails..

Question though: if you are given the sequence AABBCC, you would be able to split it up like X:ABC and Y:ABC, right?

But the problem seems like it can be solved with a greedy algorithm.

Seems greedy to me.

whats up?

I'm at work

Gotta be quick