CS206 -Discrete Mathematics II
Instructor: Chitoor V.Srinivasan.
PROBLEM SET 6 SOLUTIONS

(19).
According to Theorem2.6.1 (Larsen's book pg59), we have

displaymath129

Let  B  be the event ``the program compiles on it's first run'', and   tex2html_wrap_inline177   be the event ``the program is written in COBOL'', and   tex2html_wrap_inline179   be the event ``the program is written in FORTRAN,'' and we get

displaymath130

(20).
After we recall example 2.2.4, we let  (x,y)  denote the allocation scheme whereby  x  white chips and  y  black chips are put into urn I. And we get the probability of survive as following,

displaymath131

Notice here the probability of urn I or urn II is chosen is same, 1/2. When   tex2html_wrap_inline189 , we get the optimized result, which is  14/19.

(21).
According to Theorem 2.6.1 (Larsen's book pg59), we have

displaymath129

Let  R  be the event ``R will win'',   tex2html_wrap_inline195   be the event ``  tex2html_wrap_inline195   will be nominated'', we get tex2html_wrap121

(23).
Let   tex2html_wrap_inline199   denote the actual weather, sunny, cloudy or rain, and let   tex2html_wrap_inline201   denote the weather forecasted to be sunny,cloudy or rain.

(a).
tex2html_wrap122

(b).
tex2html_wrap123

(c).
tex2html_wrap124

(24).
Let  B  be the event ``the chip ultimately drawn from urn I is red'', and  RR  be the event ``we draw a red chip from urn I and draw a red chip from urn II'', and  RW  be the event ``we draw a red chip from urn I and draw a white chip from urn II'', and  WR  be the event ``we draw a white chip from urn I and draw a red chip from urn II'', and  WW  be the event ``we draw a white chip >from urn I and draw a white chip from urn II'', and we get,

eqnarray24

(28).
This can be solved by using a continuous analog of Theorem2.6.1. If  B  is a event dependent on the value of  x, then   tex2html_wrap_inline217 , where  f(x)  is the probability function for  x. Let  B  be the event that the second point is at a distance  < q  from  x. f(x)=1, since point  x  occurs everywhere in the interval (0,1) equally. Thus the probability that the second point lies in an interval (a,b) is b-a. When point  x  is in the interval  (0,q), the points in the interval  (0,x+q)  are less than a distance of  q  from the point  x. When point  x  is in the interval  (q,1-q), the points in the interval  (x-q,x+q), are less than a distance of  q  from the point  x. And when point  x  is in the interval  (1-q,1), the points in the interval  (x-q,1), are less than a distance of  q  from the point  x. Hence we get

eqnarray26

(29).
  tex2html_wrap_inline263 , tex2html_wrap_inline265 . Since the numerator of   tex2html_wrap_inline267   is non-negative and the denominator is positive,   tex2html_wrap_inline267   is non-negative, it satisfies Axiom1.   tex2html_wrap_inline271 , it satisfies Axiom2. And if   tex2html_wrap_inline177   and   tex2html_wrap_inline179 are two mutually exclusive events,

displaymath133

Since   tex2html_wrap_inline277   and   tex2html_wrap_inline279   also are mutually exclusive and P satisfies axiom 3,

displaymath134

Hence we get

displaymath135

Thus it also satisfies Axiom3.

(30).
Let  B  be the event ``the third chip drawn is white'', and let  RR  be the event ``we first draw a red chip then a red chip'', and let  RW  be the event ``we first draw a red chip then a white chip'', and  WR be the event ``we first draw a white chip then a red chip'', and let  WW  be the event ``we first draw a white chip then a white chip'', and we get,

eqnarray55

(32).
From Theorem 2.3.6, we have

displaymath136

And from Theorem 2.3.1, we have

displaymath137

Thus we get following

displaymath138

displaymath139

(33).

displaymath140

displaymath141

From theorem 2.3.6, we have

displaymath142

Hence we get

displaymath143

displaymath144

(35).
Consider the possible ways sets A and B could be related.
Case 1: A and B are mutually exclusive.
tex2html_wrap_inline291 . Thus, the condition reduces to tex2html_wrap_inline293 . This is equivalent to the condition,

displaymath145

Obviously, this is true if and only if tex2html_wrap_inline295
Case 2: A tex2html_wrap_inline297 B.
tex2html_wrap_inline299 . Thus, the condition reduces to tex2html_wrap_inline301 . This is equivalent to the condition,

displaymath146

Obviously, this is true if and only if tex2html_wrap_inline303
Case 3: A and B are not mutually exclusive and A is not a subset of B. Again rewriting the condition in terms of the sizes of the sets involved we get,

displaymath147

displaymath148

Note that   tex2html_wrap_inline305   (I)
Since   tex2html_wrap_inline307   and tex2html_wrap_inline309   (since A is not a subset of B),   tex2html_wrap_inline311   (II)
Since tex2html_wrap_inline313   and tex2html_wrap_inline315   (since A and B are not mutually exclusive),   tex2html_wrap_inline317   (III)
Now (I), (II), and (III) imply that

displaymath149

Which means that the condition is not true in this case. In summation, the condition is true if and only if (B=S or B= tex2html_wrap_inline319 ).

(36).
Base case:   tex2html_wrap_inline321 .
Inductive step: Assume  P(n)  holds. show that  P(n+1)  holds.
We have following assumption

displaymath150

Thus we get

eqnarray98

(37).
Let W(n) and R(n) be the events that we pick repectively, a white and red chip from the  nth  urn and let P[n] be the probability of picking white. Now,

eqnarray105

Solving the recurrence we get :

displaymath151