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,919

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 94,901

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.**

**If it ain't broke, fix it until it is.**

**Online**

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

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 94,901

Hi;

Not for a 365 day year.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

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

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 94,901

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.**

**If it ain't broke, fix it until it is.**

**Online**

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

You are not reading the question!

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 94,901

Hi;

You are not reading the question!

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

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

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

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

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 94,901

Hi;

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

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

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

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

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

The knowledge of some things as a function of age is a delta function.

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: 94,901

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.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

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

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

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

The knowledge of some things as a function of age is a delta function.

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: 94,901

Hi Festisio;

Discrete Math and its Applications?

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 94,901

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!

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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: 94,901

Hi;

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

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

**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,919

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?

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 94,901

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.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

**Online**

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

On which page is that?

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

The knowledge of some things as a function of age is a delta function.

Offline