14th November 19:19
i have a word problem that may be really simple but i'm not sure how to go
if we have a set of lines (streets) that are infinetly long in both
and want to count each intersection of 2 or greater streets how do we go
The problem is actually worded:
1. A contractor has to order traffic lights for a city.
All streets in the city are straight and infinitely long in both
No matter how many streets have the same crossing, there will be a need
for only one
traffic light per crossing. Knowing only the number of streets n, how
lights the contractor is to order to make sure he will not run out
thanks so much for previous explanations on proof by induction - it was a
M i c h e l e ' s M y o c a r d i u m:
D i g i t a l A r t G a l l e r y
22nd November 15:31
"Aldar Chan" <email@example.com> schrieb im Newsbeitrag
I am not sure, whether I understood correctly your problem, but I solved the
If you pick randomly M k-subsets of P, what is the probability, that these M
subsets are pairwise disjoint.
In this case I assume n>=M*k, otherwise the possibility is 0.
Picking M subsets randomly, all combinations have the same probability,
hence you just have to count the number of possible combinations and of the
For the possible combinations there are two possibilities: Picking the M
subsets you want to consider, that you want to pick the same k-subset twice
or not, ie. do you want to be able to pick the k-subset A1 twice or not.
If you do so, then the number of possible combinations are
Binomial(Binomial(n, k)-1+M, M), otherwise Binomial(Binomial(n, k), M).
For the "valid" combinations consider the following: Picking M k-subsets
first you have to pick one k-subset A1, then all other k-subsets must not
contain elements from A1. For A1 you have Binomial(n, k) possibilities. For
all other k-subsets you have to pick from the left n-k elements from P.
Hence for the second k-subset A2 you have Binomial(n-k, k) possibilities.
For the third k-subset A3 you have Binomial(n-2k, k) possibilities and so
on. Doing this you have counted each combination M! times, hence the number
of "valid" combinations is Binomial(n, k)*Binomial(n-k,
k)*...*Binomial(n-(M-1)*k, k)/M! =
Hence the possibility is the ratio between "valid" combinations and possible
I also thought about another possibility of your problem, that the family of
k-subsets is given, and if you pick any M subsets out of this family then
these M subsets have no common intersection. But in this case you will need
more information about the family - and since the family is given you will
have more information, I think you have to know what k-subsets are in this
family end then you can consider, whether the statement "Any M subsets have
no common intersection" holds (then possibility is 1) or not (then
possibility is 0).
Perhaps you meant that you pick randomly M k-subsets and this M subsets have
together no common intersection (in contrary to pairwise disjoint) or
perhaps you want to know the possibility, that you randomly pick a family of
subsets and then the statement "Any M subsets have no common intersection"