Jump to content
BrainDen.com - Brain Teasers
  • 0


EventHorizon
 Share

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
Link to comment
Share on other sites

20 answers to this question

Recommended Posts

  • 0

(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?

Link to comment
Share on other sites

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

Link to comment
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.

Link to comment
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.

Link to comment
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...

Link to comment
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

Link to comment
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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...