m i c h e l e c d

hi guys,
i have a word problem that may be really simple but i'm not sure how to go
about it:

if we have a set of lines (streets) that are infinetly long in both
directions,
and want to count each intersection of 2 or greater streets how do we go
about it?

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
directions.
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
many traffic
lights the contractor is to order to make sure he will not run out
lights.

thanks so much for previous explanations on proof by induction - it was a
great help!@
Michele

--

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
http://micheles-myocardium.com/

jim nastos

Consider 2 streets, then three streets, and no on, and assume that every
newly added street could possibly intersect all previous streets. Write an
expression of the sum of all these intersections.

J

m i c h e l e c d

thanksvery much again - needed to realize that we were dealing with more
than the perpendicular (which would be n/2^2)

Michele

--

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
http://micheles-myocardium.com/

aldar chan

Given a k-subset family of an n-set P (that is, drawing k elements
randomly from P to form a subset), how to find a closed form
probability that any M subsets have no common intersection?

koch dénes

"Aldar Chan" <aldar@comm.utoronto.ca> schrieb im Newsbeitrag
news:HLsDHA.6Kn@campus-news-reading.utoronto.ca...

I am not sure, whether I understood correctly your problem, but I solved the
following one:
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
"valid combinations".
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! =
n!/(k!*(n-k)!)*(n-k)!/(k!*(n-2k)!)*...*(n-(M-1)*k)!/(k!*(n-M*k)!)/M! =
n!/((k!)^M*(n-M*k)!*M!)
Hence the possibility is the ratio between "valid" combinations and possible
combinations.

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"
holds.