Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**Festisio1****Guest**

There are a couple of problems which even the discussion board on our University website has not answered:

A variation of the birthday problem:

Find the smallest number of people you need to choose at random so that the probability that at least two of them were both born on April 1 exceeds 1/2.

Suppose that the probability that *x* is in a list of *n* distinct integers is 2/3 and that it is equally likely that *x* equals any element in the list. Find the average number of comparisons used by the linear search algorithm to find *x* or to determine that it is not in the list.

Times like this, I wish i had the student solutions guide

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,532

Hi

I am getting for the first problem and for the second problem.

*Last edited by anonimnystefy (2012-12-13 09:01:01)*

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,776

Hi Festisio1;

A variation of the birthday problem:

Find the smallest number of people you need to choose at random so that the probability that at least two of them were both born on April 1 exceeds 1/2.

Assuming 365 days ( a non leap year ) you would need 253 people.

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,532

Hi bobbym

They would need 613.

*Last edited by anonimnystefy (2012-12-13 09:00:39)*

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,776

Hi;

Not for a 365 day year.

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,532

The probability that less than 2 people have their birthdays on April 1st is (364/365)^n+n*1/365*(364/365)^(n-1). This probability needs to be less than or equal to 1/2.

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,776

The probability of having the birthday April 1 is 1 / 365. The probability than n people do not have that birthday is

So solve:

n = 252.65 which is rounded to 253.

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,532

You are not reading the question!

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,776

Hi;

You are not reading the question!

You are right we are both not reading the question. The answer is 613.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,532

Well, the expected number of people for two birthdays on the 1st of April cannot be less than for one birthday.

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,776

Hi;

You changed your answer to 613. So did I! That is correct.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,532

Now it's okay. Though I changed it 25 minutes ago, and you didn't notice...

Here lies the reader who will never open this book. He is forever dead.

Offline

**Festisio****Member**- Registered: 2012-12-13
- Posts: 5

For the birthday problem -- the book answer is 614 (book assumes 366 days a year)

I want to understand how to complete the problem.. the basic birthday concept, no prob -- but this variation is a little tough.

For the other problem, the book answer is

I have sheets and sheets of paper -- but I am not getting close -- I hate looking at the answer first, because I try to understand the concepts of obtaining them.. in these cases I could not find them

There again, I have been studying for 3 finals, which are tonight, and two more tomorrow, so I may be a little tired and missing things.

*Last edited by Festisio (2012-12-13 09:29:02)*

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,776

Hi;

Yes, it is 614 for a leap year. It is not a birthday problem it is a binomial distribution problem.

That equation must be solved.

Hi anonimnystefy;

I was working on the problem so I did not notice.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,532

Well, for the second problem, the book is wrong.

Here lies the reader who will never open this book. He is forever dead.

Offline

**Festisio****Member**- Registered: 2012-12-13
- Posts: 5

anonimnystefy wrote:

Well, for the second problem, the book is wrong.

It would not be the first time -- it is Prob 7.4 #9 from Discrete Math (rosen 7th ed)

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,776

Hi Festisio;

Discrete Math and its Applications?

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**Festisio****Member**- Registered: 2012-12-13
- Posts: 5

bobbym wrote:

Hi Festisio;

Discrete Math and its Applications?

Yes, that's correct.

McGraw has the 6th ed online here: http://highered.mcgraw-hill.com/sites/dl/free/0070648247/510610/Chapter_06_Discrete_Probability.pdf

It is page 440 #9 on there I don't know if they have the matching solutions.. but I am using the 7th edition..

*Last edited by Festisio (2012-12-13 10:05:16)*

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,776

Hi;

For the 2nd problem I am getting

also.

I have sheets and sheets of paper -- but I am not getting close

I do not know about the 7th edition but the 6th edition has the answer to this problem just a few pages away!

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**Festisio****Member**- Registered: 2012-12-13
- Posts: 5

bobbym wrote:

Hi;

For the 2nd problem I am getting

also.

I have sheets and sheets of paper -- but I am not getting close

I do not know about the 7th edition but the 6th edition has the answer to this problem just a few pages away!

I'm not understanding their examples.. I had to find help on Bayes' from youtube -- book does not even mention using a tree to simplify things..

Final is cumulative - no notes/calc anything .. there is just a vast amount of material. This last chaper (7) was basically assigned to us for finals week.. which means that we didn't really cover it.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,776

Hi;

Do you see example 8, entitled average case complexity of the linear search algorithm?

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**Festisio****Member**- Registered: 2012-12-13
- Posts: 5

bobbym wrote:

Hi;

Do you see example 8, entitled average case complexity of the linear search algorithm?

Yes,

The calculation they use.. it makes a bunch of assumptions.. they are based on prior proofs..

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,532

bobbym wrote:

Hi;

For the 2nd problem I am getting

also.

I have sheets and sheets of paper -- but I am not getting close

I do not know about the 7th edition but the 6th edition has the answer to this problem just a few pages away!

How are you getting (4n+6)/3?

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,776

Hi;

I am sorry, I am involved in forum matters and can not get to all the posts as quickly.

He has a derivation just 8 pages away from the question and it gives a formula.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,532

On which page is that?

Here lies the reader who will never open this book. He is forever dead.

Offline