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=rand()%365+1;
//cout<<" "<<sample;
a = sample;
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]

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:

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 ?

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]

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=rand()%365+1;
//cout<<" "<<sample;
a = sample;
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..

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]

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.

Right answer to the wrong question.

 

[Christopher Benson-Manica]

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

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;
}

 

[Buster]

Right answer to the wrong question.

It's Step One of a correct solution.

 

[Christopher Benson-Manica]

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

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

 

[Julie]

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

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]

* (e-mail address removed) (Sandra) schriebt:

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 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 "computation", but I can't imagine that's what the
problem is about.

So please do post the exact assignment text.

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"

You absolutely don't need that.

#include <time.h>

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.

#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])

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.

 

[osmium]

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 ?

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]

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

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*=366;
}
cout << "The number is " << 366-i+1 << "\n";
return 0;
}

 

[Alf P. Steinbach]

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

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.

 

[Christopher Benson-Manica]

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

But I don't think it's complete - it solves a subtly different
problem, and perhaps a really different problem

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.

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

 

[Alf P. Steinbach]

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

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

 

[Christopher Benson-Manica]

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

And I won't mind it a bit

 

[Erik]

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 <math.h>
#include <iostream>

const bool i_am_born_on_feb_29 = false;

int main() {
std::cout << (int)std::ceil(std::log(0.05) /
(std::log(i_am_born_on_feb_29 ? 365.0 : 364.25) - std::log(365.25)));
}

 

[Alf P. Steinbach]

...

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

Be advised most people, on seeing such a posting, will think of you as an
an uncaring Swedish idiot -- and certainly I do.

Perhaps that's why you're posting anonymously?

 

[John Carson]

It's Step One of a correct solution.

Perhaps. Provided you are prepared to go around the world a couple of times
in order to get there.

 

[Erik]

Please DO NOT post what you think is a complete answer to someone

else's homework problem.

I don't think his teacher will accept that answer, unless he's studying
mathematics, in which case he probably wouldn't ask in this NG.

If he can't solve a problem like that analytically, he will most definitely
fail his mathematics classes.

And if he does hand in my suggestion, the teacher will hopefully learn
from his mistake and create a more meaningful question for next year
(one that can't be more easily solved using mathematics than programming).
I guess this assignment was part of the first programming class, in which
it is important to show the students what programming can be used for,
not teach more complex methods to solve simple mathematical problems.

However, I did give him one hint (that he must handle the Feb 29 case).

Be advised most people, on seeing such a posting, will think of you as an
an uncaring Swedish idiot -- and certainly I do.

You can see me as anything you want to, but not many others do.

Perhaps that's why you're posting anonymously?

That's more of a religious issue. I don't like giving out my name, and
certainly not my email address, on the internet.

 

[Alf P. Steinbach]

I don't think his

Are you sure that Sandra is a "he"?

teacher will accept that answer, unless he's studying
mathematics, in which case he probably wouldn't ask in this NG.

You're an idiot all right.

Did you notice that Sandra wrote


I am not asking for source code and I am not asking anyone to do
my homework as I do want to learn


Did you read the FAQ before posting,


<url: http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.2>


as you're required to do?

Perhaps your English is not quite up to the task? What kinds of
moron students are they admitting these days at Lund's?

I don't like giving out my name, and certainly not my email address,
on the internet.

That's quite understandable.