Birthday Problem

[Sandra]

I was given this problem for extra credit and I am just stuck !
BTW - I am not asking for source code and I am not asking anyone to do
my homework as I do want to learn .. I just need a hint or two to get
moving and I need to know if what I have written so far is leading me
in the right direction ~

Ok - The problem is to find out how many people need to be in a room
for a 95% chance that someone in that room will match my birthday

I wrote a program that will calculate that percentage for any 2
bithdays to match, but that is not the same thing :)

Here is what I have so far:


#include "stdafx.h"
#include <time.h>
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
int sample[1000];
int i=1,j=1;
int a =0;
srand( (unsigned)time( NULL ) );

while (a != 325)
{ sample[i]=rand()%365+1;
//cout<<" "<<sample[i];
a = sample[i];
i++;
if (a==325) cout<<"\n\n\n Match "<<a<<" at "<<i<<"\n";
}

return 0;

This puts random numbers from 1-365 in an array - reads the array and
tries to detect an exact match
The problem is that the match is so random - how do I come up with a
95% chance? Is there any exact answer ?

As I said - just need some hints to move along..

Any replies will be appreciated,

Thanks,

Sandra

[osmium]

Re: Birthday Problem

Sandra writes:
[color=blue]
> I was given this problem for extra credit and I am just stuck !
> BTW - I am not asking for source code and I am not asking anyone to do
> my homework as I do want to learn .. I just need a hint or two to get
> moving and I need to know if what I have written so far is leading me
> in the right direction ~
>
> Ok - The problem is to find out how many people need to be in a room
> for a 95% chance that someone in that room will match my birthday
>
> I wrote a program that will calculate that percentage for any 2
> bithdays to match, but that is not the same thing :)
>
> Here is what I have so far:[/color]
<snip>[color=blue]
> This puts random numbers from 1-365 in an array - reads the array and
> tries to detect an exact match
> The problem is that the match is so random - how do I come up with a
> 95% chance? Is there any exact answer ?[/color]

You are off to a bad start. There are two ways to approach this, simulate
it and compute it. I think your instructor want you to compute it and you
are simulating.

Given a bazillion people in a room.
The fist person will not match anyone. The next person will have a
*different* birthday with probability 364/365. The next 363/365. And so on.

Now write a program, monitoring for the 95% threshold as you go. I think
there is an algorithm *too* but I don't think that is wanted here.

Yes, there is an exact answer to the question posed.

[Claudio Puviani]

Re: Birthday Problem

"Sandra" <s.cantrell@min dspring.com> wrote[color=blue]
> I was given this problem for extra credit and
> I am just stuck ! BTW - I am not asking for
> source code and I am not asking anyone to do
> my homework as I do want to learn .. I just
> need a hint or two to get moving and I need
> to know if what I have written so far is leading
> me in the right direction ~
>
> Ok - The problem is to find out how many
> people need to be in a room for a 95% chance
> that someone in that room will match my birthday
>
> I wrote a program that will calculate that percentage
> for any 2 bithdays to match, but that is not the same
> thing :)
>
> Here is what I have so far:
>
>
> #include "stdafx.h"
> #include <time.h>
> #include <iostream>
> using namespace std;
>
> int _tmain(int argc, _TCHAR* argv[])
> {
> int sample[1000];
> int i=1,j=1;
> int a =0;
> srand( (unsigned)time( NULL ) );
>
> while (a != 325)
> { sample[i]=rand()%365+1;
> //cout<<" "<<sample[i];
> a = sample[i];
> i++;
> if (a==325) cout<<"\n\n\n Match "<<a<<" at "<<i<<"\n";
> }
>
> return 0;
>
> This puts random numbers from 1-365 in an
> array - reads the array and tries to detect an
> exact match The problem is that the match is
> so random - how do I come up with a 95%
> chance? Is there any exact answer ?
>
> As I said - just need some hints to move along..[/color]

This is a problem that should be solved analytically rather than with brute
force, unless you were specifically told to use brute force. If it's the
latter, consider a naive way to do it by hand: check the probability if the
group is of size 1. Then check if the group is of size 2. And so on, until
you hit 95%. There are more sophisticated ways to search that space, but
you're better off taking things one step at a time (no pun intended). Again,
if you have a choice, solve it analytically (any beginning text on
probabilities will have that very example).

Claudio Puviani

[John Carson]

Re: Birthday Problem

"osmium" <r124c4u102@com cast.net> wrote in message
news:c5ee03$n5v p$1@ID-179017.news.uni-berlin.de[color=blue]
>
> Given a bazillion people in a room.
> The fist person will not match anyone. The next person will have a
> *different* birthday with probability 364/365. The next 363/365. And
> so on.[/color]


Right answer to the wrong question.

--
John Carson
1. To reply to email address, remove donald
2. Don't reply to email address (post here instead)

[Christopher Benson-Manica]

Re: Birthday Problem

Sandra <s.cantrell@min dspring.com> spoke thus:
[color=blue]
> Ok - The problem is to find out how many people need to be in a room
> for a 95% chance that someone in that room will match my birthday
> As I said - just need some hints to move along..[/color]

The following code, I believe, calculates the number of people that
must be in a room for there to be a 95% chance that at least two
people will have the same birthday - perhaps you can make use of the
general idea for your problem. Or perhaps I will prove to be very
wrong, in which case you should not listen to me ;)

#include <iostream>

using namespace std;

int main(void)
{
int i=366; // includes February 29
while( (float)i/(float) 366 > .05 )
i--;
cout << "The number is " << i << "\n";
return 0;
}

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cybers pace.org | don't, I need to know. Flames welcome.

[Buster]

Re: Birthday Problem

John Carson wrote:[color=blue]
> "osmium" <r124c4u102@com cast.net> wrote in message
> news:c5ee03$n5v p$1@ID-179017.news.uni-berlin.de
>[color=green]
>>Given a bazillion people in a room.
>>The fist person will not match anyone. The next person will have a
>>*different* birthday with probability 364/365. The next 363/365. And
>>so on.[/color]
>
> Right answer to the wrong question.[/color]

It's Step One of a correct solution.

--
Regards,
Buster.

[Christopher Benson-Manica]

Re: Birthday Problem

Christopher Benson-Manica <ataru@nospam.c yberspace.org> spoke thus:
[color=blue]
> The following code, I believe, calculates the number of people that
> must be in a room for there to be a 95% chance that at least two
> people will have the same birthday - perhaps you can make use of the
> general idea for your problem. Or perhaps I will prove to be very
> wrong, in which case you should not listen to me ;)[/color]

Holy cow, maybe I should go to lunch and get some blood sugar back in
me - that code is REALLY wrong!!! I guess on the bright side I don't
have to feel guilty about giving you undue help... I'd post something
closer to the correct answer, but I don't think I trust myself after
that egregious blunder. Sorry :(

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cybers pace.org | don't, I need to know. Flames welcome.

[Julie]

Re: Birthday Problem

Sandra wrote:[color=blue]
>
> I was given this problem for extra credit and I am just stuck !
> BTW - I am not asking for source code and I am not asking anyone to do
> my homework as I do want to learn .. I just need a hint or two to get
> moving and I need to know if what I have written so far is leading me
> in the right direction ~
>
> Ok - The problem is to find out how many people need to be in a room
> for a 95% chance that someone in that room will match my birthday[/color]

Are you supposed to calculate the answer, or (simulated) empirically
determine? From the looks of your code, it looks like you are going the
empirical route.

[Alf P. Steinbach]

Re: Birthday Problem

* s.cantrell@mind spring.com (Sandra) schriebt:[color=blue]
> I was given this problem for extra credit and I am just stuck !
> BTW - I am not asking for source code and I am not asking anyone to do
> my homework as I do want to learn .. I just need a hint or two to get
> moving and I need to know if what I have written so far is leading me
> in the right direction ~
>
> Ok - The problem is to find out how many people need to be in a room
> for a 95% chance that someone in that room will match my birthday[/color]

I think it would be better if you posted the exact assignment, because
as stated there is nothing involving C++ or even programming. With n
persons in the room the chance that none of them matches your birthday
is simply (364/365)^n (you need to think of it this way to get logical
"and" for simple multiplication of probabilities), so the chance that at
least one of them match is <censored/>; with the treshold at 0.95 that
gives 0.95 = <censored/> thus n = <censored/> ~= 1091.94. Thus


#include <iostream>
int main() { std::cout << 1092 << std::endl; }


would be one solution program, or perhaps


#include <iostream>
int main() { std::cout << 1091 + 1 << std::endl; }


if the text requires "computatio n", but I can't imagine that's what the
problem is about.

So please do post the exact assignment text.

[color=blue]
> I wrote a program that will calculate that percentage for any 2
> bithdays to match, but that is not the same thing :)
>
> Here is what I have so far:
>
>
> #include "stdafx.h"[/color]

You absolutely don't need that.

[color=blue]
> #include <time.h>[/color]

In C++ write


#include <ctime>


but you don't need that either, unless it's really a requirement to use
Monte Carlo method or some such.

[color=blue]
> #include <iostream>
> using namespace std;
>
> int _tmain(int argc, _TCHAR* argv[])[/color]

In standard C++ this is not a valid 'main' function. In standard
C++ one possible declaration of the 'main' function is


int main()


As for the rest of the code, as others have replied it's doubtful
that the intention is to do a simulation.

But that of course depends on the exact text of the assignment.

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[osmium]

Re: Birthday Problem

Sandra writes:
[color=blue]
> This puts random numbers from 1-365 in an array - reads the array and
> tries to detect an exact match
> The problem is that the match is so random - how do I come up with a
> 95% chance? Is there any exact answer ?[/color]

There is not any exact answer by using the Monte Carlo simulation you are
started on. You could compute till doomsday and you still wouldn't have an
exact answer. That's one reason why analysis is preferred to simulation in
simple problems such as this. Also, simulation doesn't give you much in the
way of insight into the problem and what a a good solution might be. In
general, in real problems, simulation is much easier than analysis.

[Christopher Benson-Manica]

Re: Birthday Problem

Christopher Benson-Manica <ataru@nospam.c yberspace.org> spoke thus:
[color=blue]
> The following code, I believe, calculates the number of people that
> must be in a room for there to be a 95% chance that at least two
> people will have the same birthday - perhaps you can make use of the
> general idea for your problem. Or perhaps I will prove to be very
> wrong, in which case you should not listen to me ;)[/color]

FWIW, here is something that might actually compute the correct
answer. Yeesh, Mondays...

#include <iostream>

using namespace std;

int main(void)
{
int i=366; // includes February 29
double numerator=i, denominator=i;
while( numerator/denominator > .05 ) {
numerator*=--i;
denominator*=36 6;
}
cout << "The number is " << 366-i+1 << "\n";
return 0;
}

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cybers pace.org | don't, I need to know. Flames welcome.

[Alf P. Steinbach]

Re: Birthday Problem

* Christopher Benson-Manica <ataru@nospam.c yberspace.org> schriebt:[color=blue]
>
> FWIW, here is something that might actually compute the correct
> answer. Yeesh, Mondays...[/color]

Please DO NOT post what you think is a complete answer to someone
else's homework problem.

I shall not call you an idiot, moron, etc., here.

But I reserve the right to hold that opinion, and be advised that's the
opinion most will (very privately) have on seeing such a posting.

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Christopher Benson-Manica]

Re: Birthday Problem

Alf P. Steinbach <alfps@start.no > spoke thus:
[color=blue]
> Please DO NOT post what you think is a complete answer to someone
> else's homework problem.[/color]

But I don't think it's complete - it solves a subtly different
problem, and perhaps a really different problem :)
[color=blue]
> But I reserve the right to hold that opinion, and be advised that's the
> opinion most will (very privately) have on seeing such a posting.[/color]

I would hope that if I'm annoying people, they'd just tell me - I'm
very bad at catching subtle hints :(

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cybers pace.org | don't, I need to know. Flames welcome.

[Alf P. Steinbach]

Re: Birthday Problem

* Christopher Benson-Manica <ataru@nospam.c yberspace.org> schriebt:[color=blue]
>
> I would hope that if I'm annoying people, they'd just tell me - I'm
> very bad at catching subtle hints :([/color]

You can be sure that at least I will be very clear about such things... ;-)

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Christopher Benson-Manica]

Re: Birthday Problem

Alf P. Steinbach <alfps@start.no > spoke thus:
[color=blue]
> You can be sure that at least I will be very clear about such things... ;-)[/color]

And I won't mind it a bit :)

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cybers pace.org | don't, I need to know. Flames welcome.