Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
EventHorizon

Question

I'll start with extensions of Prof. Templeton's Birthday and SSN puzzles...

(1) How many Plutonians would you need to gather before there is a 50:50 chance that two of them have the same birthday?

The orbital period (which is essentially the length of one plutonian year)

The length of a plutonian day

Wikipedia is a good source for looking this information up.

Spoiler for Pluto facts:

Orbital Period = 90613.305 earth days = 248 years

1 plutonian day = 6.39 earth days

(2) Planet Gplex takes a googolplex (10^(10^100)) of its days to orbit its sun. Approximately how many Gplexians would you need to gather before there is a 50:50 chance that two of them have the same birthday? Prove that your estimate is a good one. (yeah, I'm trying to make direct computation impossible, and yes I have an answer/proof)

And now, a somewhat related original puzzle...

(3) You are given a stack of cards numbered 1 to n, and their order is randomized. What is the probability that two consecutively numbered cards (lets say, a and a+1) are found consecutively (a immediately before a+1) somewhere in the stack?

Edited by EventHorizon

Share this post


Link to post
Share on other sites

20 answers to this question

  • 0
1) how many days is in their year?

2)10^(10^100)/2?

3)does n stand for a variable?

1) look it up. (though I did include the information needed in the spoiler)

2) nope....

3) Yes, n is a variable.

Share this post


Link to post
Share on other sites
  • 0
Guest

(n-1)/n!

I'll start with extensions of Prof. Templeton's Birthday and SSN puzzles...

(1) How many Plutonians would you need to gather before there is a 50:50 chance that two of them have the same birthday?

The orbital period (which is essentially the length of one plutonian year)

The length of a plutonian day

Wikipedia is a good source for looking this information up.

Spoiler for Pluto facts:

Orbital Period = 90613.305 earth days = 248 years

1 plutonian day = 6.39 earth days

(2) Planet Gplex takes a googolplex (10^(10^100)) of its days to orbit its sun. Approximately how many Gplexians would you need to gather before there is a 50:50 chance that two of them have the same birthday? Prove that your estimate is a good one. (yeah, I'm trying to make direct computation impossible, and yes I have an answer/proof)

And now, a somewhat related original puzzle...

(3) You are given a stack of cards numbered 1 to n, and their order is randomized. What is the probability that two consecutively numbered cards (lets say, a and a+1) are found consecutively (a immediately before a+1) somewhere in the stack?

Share this post


Link to post
Share on other sites
  • 0

Largaroth: Remember, it is a probability. This means it needs to be between 0 and 1.

Avalanche5x: You answer fails for n=3. the probability is 1/2, and you have 1/3.

123<-has both 12 and 23

132

213

231<-has 23

312<-has 12

321

3 out of 6 rows have two consecutive numbers, so the probability is 1/2.

Share this post


Link to post
Share on other sites
  • 0
Guest
nope. For n=3, it is 1/2, but your equation gives 1/3.

Now wait a second...does "a followed by a+1" include the possibility of having the last card as "a" then the first card as "a+1"? If you include that as a possibility, then you are right. Otherwise, my answer still stands...

Share this post


Link to post
Share on other sites
  • 0
Now wait a second...does "a followed by a+1" include the possibility of having the last card as "a" then the first card as "a+1"? If you include that as a possibility, then you are right. Otherwise, my answer still stands...

I think my labeling the cards a and a+1 made the problem a little confusing. There is no wrap around, and a is not a specific card, just one that has the card with the number one greater right after it.

Look at my example for n=3 in my previous post.

Share this post


Link to post
Share on other sites
  • 0
1) how many days is in their year?

2)10^(10^100)/2?

3)does n stand for a variable?

For 2, I said "nope...." when I should have said, you can get a better estimate...and to use spoilers ;)

Share this post


Link to post
Share on other sites
  • 0

Just a thought...

For a year of N days, all we have to do is to solve the equation:

(N-1)*(N-2)* ...*(N-x)/Nx = 1/2

Share this post


Link to post
Share on other sites
  • 0
Looks like there's 14180.5 days in a year

Spoiler for So, that makes it:

141

yup, there's the answer to the first question. It's fitting that you got it first.

Any ideas on the next two?

Share this post


Link to post
Share on other sites
  • 0
...

And now, a somewhat related original puzzle...

(3) You are given a stack of cards numbered 1 to n, and their order is randomized. What is the probability that two consecutively numbered cards (lets say, a and a+1) are found consecutively (a immediately before a+1) somewhere in the stack?

I can calculate this probability as a series, but I haven't found a polynomial solution yet.

Let's calculate the probability of no two sequential cards in the deck. Then we can subtract that from 1 to get the probability that some of them are in sequence.

For n cards there are n! total permutations. If the number of permutations in a deck of n where no two cards are in sequence is Pn, then the probability is Pn/n!.

So here is the formula for the number of permutations in a deck of n where no two cards are in immediate succession that I have derived thus far:

Pn = (n-1)*Pn-1 + (n-2)*Pn-2

The series has that Fibonacci flair. Each successive member is calculated from previous two.

Example:

By experiment we can find that for the deck of 1 card, P1=1; and for the deck of 2 cards P2=1.

Then we have:

P3 = 2*1 + 1*1 = 3; thus the probability is 3/3!=1/2

P4 = 3*3 + 2*1 = 11; prob=11/4!=11/24

P5 = 4*11 + 3*3 = 53; prob=53/5!=53/120

... and so on. Of course, the probability above was for no two cards in sequence. We need to subtract that from 1 to get the answer to the problem.

The recursive reasoning for the derivation of that formula is as follows:

Suppose, the number of permutations whith no two cards in sequence is Pn for n cards.

If we add one more card, we could insert it into n different places in each arrangement from Pn. (There are n+1 total places to insert an extra card, but one of those places would create a sequential pair.) So there are n*Pn ways to construct non-sequential arrangement that way.

Another way to construct non-sequential arrangements (different from above ) is to take an arrangement with just a single sequential pair and break that pair with the new card (insert it between the two sequential cards.)

In the deck of n cards there are n-1 different sequential pairs. But, how many arragements with a single pair in the deck of n cards are there? If we treat that pair as one unbreakable entity, then we have the same situation as a deck of n-1 cards. And so the number of different pairs (n-1) times the number of arrangements of it with the remaining cards Pn-1 and a single placement of the new (n+1st) card gives us another term of the equation.

Thus, Pn+1=n*Pn+(n-1)Pn-1

But I suppose, EH is looking for a polynomial solution. Is that so?

Or is the problem to calculate probability for two specific cards? But that would be too simple, not EH-like problem.

Share this post


Link to post
Share on other sites
  • 0
I can calculate this probability as a series, but I haven't found a polynomial solution yet.

Let's calculate the probability of no two sequential cards in the deck. Then we can subtract that from 1 to get the probability that some of them are in sequence.

For n cards there are n! total permutations. If the number of permutations in a deck of n where no two cards are in sequence is Pn, then the probability is Pn/n!.

So here is the formula for the number of permutations in a deck of n where no two cards are in immediate succession that I have derived thus far:

Pn = (n-1)*Pn-1 + (n-2)*Pn-2

The series has that Fibonacci flair. Each successive member is calculated from previous two.

Example:

By experiment we can find that for the deck of 1 card, P1=1; and for the deck of 2 cards P2=1.

Then we have:

P3 = 2*1 + 1*1 = 3; thus the probability is 3/3!=1/2

P4 = 3*3 + 2*1 = 11; prob=11/4!=11/24

P5 = 4*11 + 3*3 = 53; prob=53/5!=53/120

... and so on. Of course, the probability above was for no two cards in sequence. We need to subtract that from 1 to get the answer to the problem.

The recursive reasoning for the derivation of that formula is as follows:

Suppose, the number of permutations whith no two cards in sequence is Pn for n cards.

If we add one more card, we could insert it into n different places in each arrangement from Pn. (There are n+1 total places to insert an extra card, but one of those places would create a sequential pair.) So there are n*Pn ways to construct non-sequential arrangement that way.

Another way to construct non-sequential arrangements (different from above ) is to take an arrangement with just a single sequential pair and break that pair with the new card (insert it between the two sequential cards.)

In the deck of n cards there are n-1 different sequential pairs. But, how many arragements with a single pair in the deck of n cards are there? If we treat that pair as one unbreakable entity, then we have the same situation as a deck of n-1 cards. And so the number of different pairs (n-1) times the number of arrangements of it with the remaining cards Pn-1 and a single placement of the new (n+1st) card gives us another term of the equation.

Thus, Pn+1=n*Pn+(n-1)Pn-1

But I suppose, EH is looking for a polynomial solution. Is that so?

Or is the problem to calculate probability for two specific cards? But that would be too simple, not EH-like problem.

Very nice. I'll consider this one solved. Though here's an equation that will blow your mind ;)

1-(round( (n+1)!/(ne) )/n!)

And, yes, this equation is exact (I have no idea how, but it is). Though obvious, I thought I would define these.

e = 2.71828...yeah...that e

round() is nearest integer

So as n->infinity, P=1-(1/e) = approx 63%

Inspiration: I grade homework assignments, and when entering scores the program automatically advances to the next student (alphabetically) automatically. However, I don't sort them before entering grades, so this automatic advance isn't all that useful. I do seem to use it at least once every other time I enter scores, so I wondered about the exact probabilities. It seems (using the equation) that there's about a 62% chance that I'll use it at least once when entering scores for a given assignment.

So that just leaves question 2...

Share this post


Link to post
Share on other sites
  • 0
Very nice. I'll consider this one solved. Though here's an equation that will blow your mind ;)
1-(round( (n+1)!/(ne) )/n!)

And, yes, this equation is exact (I have no idea how, but it is). Though obvious, I thought I would define these.

e = 2.71828...yeah...that e

round() is nearest integer

So as n->infinity, P=1-(1/e) = approx 63%

Inspiration: I grade homework assignments, and when entering scores the program automatically advances to the next student (alphabetically) automatically. However, I don't sort them before entering grades, so this automatic advance isn't all that useful. I do seem to use it at least once every other time I enter scores, so I wondered about the exact probabilities. It seems (using the equation) that there's about a 62% chance that I'll use it at least once when entering scores for a given assignment.

So that just leaves question 2...

That is interesting! The ubiquitous e. I suppose, whenever you get a series with a mixture of factorials and exponents, you can always look how to convert the series into f(ex).

A correction to my post with the birthday (question 2) equation.

The equation to solve is:

N! / ((N-x)!*Nx) = 1/2

or

(N - 1)(N - 2)*...*(N - x + 1) / Nx-1 = 1/2

Share this post


Link to post
Share on other sites
  • 0
That is interesting! The ubiquitous e. I suppose, whenever you get a series with a mixture of factorials and exponents, you can always look how to convert the series into f(ex).

A correction to my post with the birthday (question 2) equation.

The equation to solve is:

N! / ((N-x)!*Nx) = 1/2

or

(N - 1)(N - 2)*...*(N - x + 1) / Nx-1 = 1/2

Yup, that's the equation to start with.
Sterling's approximation for factorials.

n! = approx sqrt(2*pi*n)*(n/e)^n

There's a slightly better approximation, but it eventually reduced to Sterling's in my derivation.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×