Study Guides (400,000)

CA (150,000)

UTSC (10,000)

Computer Science (300)

CSCA67H3 (70)

Anna Bretscher (60)

Final

Department

Computer ScienceCourse Code

CSCA67H3Professor

Anna BretscherStudy Guide

FinalThis

**preview**shows pages 1-2. to view the full**7 pages of the document.**CSCA67 Tutorial, Week 5

Oct. 6th-Oct. 10th, 2014

Compiled by G. Singh Cadieux

Adapted from

A. Bretscher, CSCA67 Week 5 Lecture Notes,

Interactive Mathematics: Singapore TOTO &

Interactive Mathematics: Probability and Poker

1Review of last week’s lecture

Introduction to probability: The Birthday Problem

Q: What is the probability that, in a group of npeople, at least 2 have the same birthday?

Let us represent the days of the year by the integers 1, 2, . . . , 365. Then we choose our sample space Sto

be {all possible combinations of nbirthdays}. That is, we include all possible combinations of ndays, with

repetition - up to nrepetitions of the same day (when all nbirthdays fall on the same day).

For example, if n= 3, we include:

•all the single days of the year (eg. (1, 1, 1), (2, 2, 2), (3, 3, 3), . . . ), in the case that all 3 birthdays

fall on the same day,

•all combinations of 2 diﬀerent days of the year (eg. (1, 1, 2), (1, 1, 3), (1, 1, 4), . . . ), in the case that

2 of the birthdays fall on the same day, and

•all combinations of 3 diﬀerent days of the year (eg. (1, 2, 3), (1, 2, 4), (1, 2, 5), . . . ), in the case that

all 3 birthdays fall on diﬀerent days

Suppose that all birthdays (and combinations of birthdays) are equally likely. Then, by the classical deﬁnition

of probability,

P({at least 2 people share a birthday}) = |{at least 2. . . }|

|S|

We know from counting principles that

|S|= # of ways to select the ﬁrst birthday ×# of ways to select the second birthday

×. . . ×# of ways to select the nth birthday

= 365 ×365 ×. . . ×365

= 365n

and that

|{at least 2. . . }| = # of arrangements of nbirthdays where 2 people share a birthday

+ # of arrangements of nbirthdays where 3 people share a birthday

+. . . + # of arrangements of nbirthdays where npeople share a birthday

1

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

So

P({at least 2 people share a birthday}) = |{2 people share a birthday}| +. . . +|{npeople share a birthday}|

365n

Note that this counting method counts ordered n-tuples: for example, where n= 3, we consider (1, 1, 2)

and (1, 2, 1) to be diﬀerent combinations of birthdays.

If we were to instead consider unordered n-tuples, we could not use the classical deﬁnition of probability,

since not all outcomes would be equally likely. For example, where n= 3, the unordered combination (1, 1,

2) is more likely than the unordered combination (1, 2, 3), since there are more ways in which the former

can occur.

However, this seems very laborious to compute, particularly if nis large.

We can instead use the complement rule to determine that

P({at least 2 people share a birthday}) = 1 −P({at least 2 people share a birthday})

= 1 −P({no shared birthdays})

= 1 −# of ways to select nunshared birthdays

365n

= 1 −365 ×364 ×. . . ×(365 −n+ 1)

365n

Notice that, if n > 365, the above calculation produces

P({at least 2. . . }) = 1 −365 ×(365 −1) ×. . . ×(365 −364) ×(365 −365) ×. . . ×(365 −n+ 1)

365n

= 1 −365 ×. . . ×0×. . . ×(365 −n+ 1)

365n

= 1 −0

365n

= 1 −0 = 1

Why does this make sense?

By the pigeonhole principle, if we have nobjects to place in fewer than npigeonholes, at least 1 pigeonhole

will contain multiple objects. In this case, if there are more than 365 birthdays to distribute over 365 days,

at least 2 birthdays will fall on the same day. Thus, the probability of at least 2 people sharing a birthday

is 1, or absolutely certain.

2Probability problems

2.1 Singapore TOTO

In the Singapore lottery game of TOTO, 6 (distinct) winning numbers plus one “additional” winning number

are drawn at random from the numbers 1 to 45. In the ordinary game, players choose 6 numbers/ticket in

the hope of matching some or all of the winning numbers and becoming instant millionaires.

Prizes

Group Prize Amount Winning Numbers Matched

1 33% of prize pool 6

2 13% of prize pool 5 + additional number

3 13% of prize pool 5

4 13% of prize pool 4 + additional number

5 $30 per winning combination 4

6 $20 per winning combination 3 + additional number

2

###### You're Reading a Preview

Unlock to view full version