2 Sets,functions and relations(20 points)

(i)Is  it  true  that,for  two  arbitrary  sets  A  and  B,A-(A-B)=B?Prove  your  claim(4  points).

(ii)Define  a  relation  R  on  functions  from  N  to  R+as  fRg  if  and  only  if  |f-g|=0(n).Is  this relation transitive,reflexive,or symmetric?Prove your claim(4 points).

(iii)Let R be an arbitrary equivalence relation on set A.Define a new relation R as R=A×A-R.

Is  the  new  relation  R  a)transitive,b)reflexive,c)symmetric?Prove  your  claim(4  points).  (iv)Consider   two    arbitrary   functions    f,g:N→R+such   that    f(n)=Ω(g(n)),is   it    true   that

ef(n)=Ω(e9(n))?Prove  your  claim(4  points).

(v)Let f,g be two functions from natural numbers to positive real numbers,such that 2f(n)= 2f(n-1)+2f(n-2)for   any   n≥2,and    g(n)=n+√n   for    any   n≥0.Which    of  the   following statements is true?Justify your answer(4 points):

(a)f(n)=0(g(n))but    f(n)is    not    in    Ω(g(n)).

(b)f(n)=Ω(g(n))but   f(n)is   not   in   O(g(n)).

(c)f(n)=0(g(n)).

3    Counting(20  points)

(i)Let  A  be  a  set  with  |A|=5.Count  the  number  of  distinct  equivalence  relations  that  can  be

constructed  on  A.(4  points)   (ii)Consider  the  following  board:

How many ways are there to tile it with  1×2  tiles?(4 points).

(iii)Suppose  that  one  needs  to  power  68  individual  lamps,but  there  are  only  2  sockets  on  the wall.Then,what  is  the  minimum  number  of  4-outlet  power  extenders  needed?Assume  that the extenders and sockets do not have any limitation of power.(4 points)

(iv)Let  x1,C₂,…,240  be   any  sequence  of  40  distinct  numbers.Show  that  it  must  contain  a subsequence  of  7  numbers  that   is  either  increasing  or  decreasing.That  is,there  exists  a sequence     i1Ti₂>…>Si┐ ·(4 points)

(v)Count  the  number  of  permutations  of  1,2,3,...,20  such  that  neither  the  longest  increasing subsequence nor the longest decreasing subsequence  [see Question 3(iv)for the definition]is longer  than  18.You  may  keep  the  factorials  in  the  unexpanded  form(e.g.,20!-10!)in  your answer(4   points).

4    Probability and random variables(20 points)

(i)Suppose you roll a fair dice for multiple times.Define L to be the number of rolls you have to make until either of the following is satisfied:

·Consecutively getting two numbers larger or equal to 5.

● The total number of rolls reaches 5.

Determine  the  expectation  of L.(4  points)

(ii)A  fire  detector  has  quite  high   accuracy:Whenever  a  fire  occurs,it  detects  the   fire  with probability  90%.A  false  signal(e.g.,someone  smoking)has  a   10%probability  to  trigger  the

detector.Estimation  shows  that  the  ratio between  false  signals  and  (real)fires  is  2:1.

a)If  the  fire  detector  is  triggered,what  is  the  probability  that  there  is  indeed   a  fire?(4 points)

b)Suppose that the alarms generated by the detector are independent.Show an upper bound on the probability that more than 30 out of 100 alarms are false  signals rather than fires. Explain your claim (4 points).

(iii)a)Randomly  and  independently  drop  4  balls   on  a  disk.(For  simplicity,treat  the  balls   as dimensionless  points.)What  is  the  probability  that  they  belong  to  the  same  half-disk?(4 points)

b)Consider  the  same  setting  with  n  balls,where  n∈N.What  is  the  probability  that  they belong to the  same half-disk?(4 points)