Problem 444

[gauravjoshi]

It seems that I have resolved this problem with its central issues resolved, but the unnecessary final Summation is playing a spoil sport and i can't post my final answer due to that and see the approaches by others. I am posting my solution here so that if my initial approach and findings are correct then either provide me the final solution or provide me the way through which i can come to it. In a straight recursive way i can always get the final answer but computer processors have their limits and i do not want to calculate unnecessary intermediate terms.

The first issue in the problem was calculating E(n), the expected number of players left on the table. At each time, there would always be the first person left on the table with a one pound. So E(1) = 1. Doing some more iterations and analysis E(2) would be either 1 or 2 and....similarly E(n) would be either 1 or 2 or 3 or....n.
Since the probability of all these events is same so E(n) would be the simple average...so it would be
E(n) = (1 + 2 + 3 + 4 +....N)/n,
Since (1+2+3+4....N) is an arithmatic progression so its sum would be n * (first term + last term)/2 = n (1+n)/2 So,
E(n) = (n (1+n)/2)/n = (n +1)/2

So E(1) =1, E(2)=1.5, E(3)=2, E(4)=2.5

Now S1(N) = E1 + E2 + E3 + E4.....En = 1 + 1.5 + 2 + 2.5 + 3 + 3.5 +.......which again is an Arithmatic Series.
So S1(N) = (1+En)n/2

So E(10e14) = (1 + 10e14)/2 = 50000000000000.5
and S(1)(10e14) = (1+En)n/2 = (1+50000000000000.5) * 10e14/2 = 2500000000000075000000000000.0

Now comes the spoil sport for me
What does Sk(N) = Sk-1(p) for k > 1 mean here (forgive me for not being able to paste the image of sigma here)

Is it, Sk(N) = S(k-1)1 + S(k-1)2......+S(k-1)N
so Sk(N) = S(k-2)1 + S(k-2)2 + S(k-2)1+.....S(k-2)N+S(k-2)(N-1)+..S(k-2)1
till...we have Sk(N) in terms of S1's....

I was able to reduce S1(N) to a formula in terms of n and En to calculate its value directly. I was also able to correctly get the value of En.

But i am not able to do so with Sk(N). There is no order, harmony or anything i am able to find, so that i can reduce it to a formula in terms of n and E(n).....I do not want to calculate E(N-1), E(N-2) etc....since calculating values of E(N) in a for loop for all the values from 1 to 10e14 is not possible and time saving, ...So i wanted to reduce Sk(N) to a direct formula where in i pass E(N) and N Or S1(N) and get the final value. But this is playing a spoil sport here. I can always apply a recursive loop, but that would get me to calculate useless terms like E(N-1), E(N-2) in a for loop.....and if i get the solution, it would be hours of processing.

[Marcus_Andrews]

1. Please do not post potential spoilers like these in public.

2. The problem statement already gives you a sample value: E(111) = 5.2912. Your strategy would imply that E(111) = 56. Try to get E(n) working first before you take the next step.

[PurpleBlu3s]

I would like to clarify the meaning of option two: "The player can trade his unscratched ticket for a previous player's scratched ticket..."

Does this mean that the current player can trade their ticket for ANY previous player's ticket (e.g. player p can trade with any player who hasn't left), or just the player directly before them?

I assume the former from the use of "a previous" rather than "the previous".

Thanks.

[Marcus_Andrews]

The former, yes -- any previous player's ticket, not just the one before them.

[PurpleBlu3s]

Thanks for the clarification.

[pismobiker]

It seems to me that there are situations where the choice is ambiguous. Suppose p = 3 and suppose the first person has a 2. Then the second person's optimal choice is ambiguous as both have a value of 2. But it one case the expected number of people at the end is 2.5 while it's 1.5 in the other case. Clearly I'm misunderstanding something, but can't see it. I'd appreciate some constructive feedback. Thanks.

[pismobiker]

Please ignore my last post. I realize the mistake in my thinking.