20 replies to this topic

[Professor H]

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]

Spoiler for No.1

Looks like there's 14180.5 days in a year

Spoiler for So, that makes it:

141

[Prime]

Just a thought...

Spoiler for B-days

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]

Spoiler for answer

2 there day is longer then there year

[EventHorizon]

Spoiler for No.1

Looks like there's 14180.5 days in a year

Spoiler for So, that makes it:

141

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

Spoiler for sequential probability

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.

Spoiler for sequential probability

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

Spoiler for simple equation for problem 3, and inspiration for the problem

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

Spoiler for simple equation for problem 3, and inspiration for the problem

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.

Spoiler for B-day 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