[EventHorizon]

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 February 13, 2009 by EventHorizon

[Guest]

how many days is their year?

[Guest]

1) how many days is in their year?

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

3)does n stand for a variable?

[EventHorizon]

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.

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

[EventHorizon]

(n-1)/n!

nope. For n=3, it is 1/2, but your equation gives 1/3.

[Guest]

On #3, can "consecutive" be n+1 then n, or does it have to be n then n+1?

[Guest]

3)n^n

[Guest]

If consecutive is only a then a+1. Then...

There is a 1/n probability.

[EventHorizon]

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.

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

[EventHorizon]

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.

[EventHorizon]

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

[Prof. Templeton]

Looks like there's 14180.5 days in a year

Spoiler for So, that makes it:

141

[Prime]

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)/N^x = 1/2

[Magic_luver101]

2 there day is longer then there year

[EventHorizon]

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?

[Prime]

...

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 P_n, then the probability is P_n/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:

P_n = (n-1)*P_n-1 + (n-2)*P_n-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, P₁=1; and for the deck of 2 cards P₂=1.

Then we have:

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

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

P₅ = 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 P_n for n cards.

If we add one more card, we could insert it into n different places in each arrangement from P_n. (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*P_n 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 P_n-1 and a single placement of the new (n+1st) card gives us another term of the equation.

Thus, P_n+1=n*P_n+(n-1)P_n-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.

[EventHorizon]

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 P_n, then the probability is P_n/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:

P_n = (n-1)*P_n-1 + (n-2)*P_n-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, P₁=1; and for the deck of 2 cards P₂=1.

Then we have:

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

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

P₅ = 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 P_n for n cards.

If we add one more card, we could insert it into n different places in each arrangement from P_n. (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*P_n 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 P_n-1 and a single placement of the new (n+1st) card gives us another term of the equation.

Thus, P_n+1=n*P_n+(n-1)P_n-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...

[Prime]

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(e^x).

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

The equation to solve is:

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

or

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

[EventHorizon]

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(e^x).

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

The equation to solve is:

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

or

(N - 1)(N - 2)*...*(N - x + 1) / N^x-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.