Problem 503
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Problem 503
If I were Alice I would go on till no numbers are left. It is fair to give a score of zero then, but that would make for a silly game. So?
Re: Problem 503
She wouldn't get a score of 0, but a score equal to the value of the last card, as per step 3.
Re: Problem 503
Hi there,
I seem to be doing something wrong validating the given results for F(4) = 15/8, or 45/24. I keep getting the expected value to be 44/24 and cannot spot the error in my thinking. Using the rules given for the first 2 cards, 12 of the combinations stop with total EV of 20. For the 3rd card, I tried stopping if any previous cards were higher and also only stopping if the number of previous higher cards was 2. In each case, the total EV for the remaining 12 combinations is 24.
I did this on an excel spreadsheet just to understand the problem before attempting to implement a solution.
Any insight would be greatly appreciated.
I seem to be doing something wrong validating the given results for F(4) = 15/8, or 45/24. I keep getting the expected value to be 44/24 and cannot spot the error in my thinking. Using the rules given for the first 2 cards, 12 of the combinations stop with total EV of 20. For the 3rd card, I tried stopping if any previous cards were higher and also only stopping if the number of previous higher cards was 2. In each case, the total EV for the remaining 12 combinations is 24.
I did this on an excel spreadsheet just to understand the problem before attempting to implement a solution.
Any insight would be greatly appreciated.

 Posts: 364
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Problem 503
I did the same. Interestingly, I get a total EV of 25 for both your cases.markmcb wrote: ..For the 3rd card, I tried stopping if any previous cards were higher and also only stopping if the number of previous higher cards was 2. In each case, the total EV for the remaining 12 combinations is 24.
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Re: Problem 503
Thanks for the reply. Here are the expected values I have for the 12 combinations that are left over. Formatting is not helping, but I am showing which combinations continued and which stopped. The last number is the actual value for that combination.MuthuVeerappanR wrote:I did the same. Interestingly, I get a total EV of 25 for both your cases.markmcb wrote: ..For the 3rd card, I tried stopping if any previous cards were higher and also only stopping if the number of previous higher cards was 2. In each case, the total EV for the remaining 12 combinations is 24.
Stop on 2
1 2 3 C 4 4
1 2 4 C 3 3
1 3 2 C 4 4
1 3 4 C 2 2
1 4 2 C 3 3
1 4 3 C 2 2
2 3 1 S 1
2 3 4 C 1 1
2 4 1 S 1
2 4 3 C 1 1
3 4 1 S 1
3 4 2 C 1 1
Unless I am missing something, I get the EV for these 12 combinations to be 24, not 25. Same thing if I use stop on anything for the 3rd card:
Stop on any
1 2 3 C 4 4
1 2 4 C 3 3
1 3 2 S 2
1 3 4 C 2 2
1 4 2 S 2
1 4 3 S 3
2 3 1 S 1
2 3 1 S 1
2 3 4 C 1 1
2 4 1 S 1
2 4 3 S 3
3 4 1 S 1
3 4 2 C 1 1
Which still works out to 24. Like I said, I am sure I am missing something, just not seeing it.

 Posts: 364
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Problem 503
In "Stop on any", why is the permutation '2 3 1 S 1' case considered twice? Also in the last case "Stop on any", shouldn't it be 2?
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Re: Problem 503
I just accidentally copied it twice. Originally, I had the two columns sidebyside and that did not look good at all, so I moved the stop on any below. Regarding the last comment, that is exactly the case that for some reason, I just kept over looking while I was trying to model this case. Thank you very much for pointing that out.MuthuVeerappanR wrote:In "Stop on any", why is the permutation '2 3 1 S 1' case considered twice? Also in the last case "Stop on any", shouldn't it be 2?
Cheers,
Mark

 Posts: 6
 Joined: Fri Apr 27, 2018 6:17 pm
Re: Problem 503
i must be missing something obvious. i coded a brute force solution that just goes through all permutations and uses the "optimal stopping rule" that can be found with google.
i am getting the following results:
F(3) = 1.666666666666666666666666666666667
F(4) = 1.875
F(5) = 2.1
F(6) = 2.333333333333333333333333333333333
F(7) = 2.476190476190476190476190476190476
F(8) = 2.625
F(9) = 2.916666666666666666666666666666667
F(10) = 3.025
given that the first two are identical to the provided example answers but F(10) is not, i must assume that my approach is incorrect and i am not using the optimal strategy. however, i have absolutely no idea what this mysterious optimal strategy could be, and going through all imaginable strategies is not an option due to my limited lifetime. can someone give me a hint?
i am getting the following results:
F(3) = 1.666666666666666666666666666666667
F(4) = 1.875
F(5) = 2.1
F(6) = 2.333333333333333333333333333333333
F(7) = 2.476190476190476190476190476190476
F(8) = 2.625
F(9) = 2.916666666666666666666666666666667
F(10) = 3.025
given that the first two are identical to the provided example answers but F(10) is not, i must assume that my approach is incorrect and i am not using the optimal strategy. however, i have absolutely no idea what this mysterious optimal strategy could be, and going through all imaginable strategies is not an option due to my limited lifetime. can someone give me a hint?
Re: Problem 503
All of your values F(n) are too big for n>4, for example F(5)=2.05
A brute force program should NOT assume any strategy, but find out which moves turn out to be optimal without preselection.
Try to see which cases (trees in the game) for n=5 are omitted by your brute force program. After the brute force program delivers correct values you can try to detect the pattern/rules of the best moves.
A brute force program should NOT assume any strategy, but find out which moves turn out to be optimal without preselection.
Try to see which cases (trees in the game) for n=5 are omitted by your brute force program. After the brute force program delivers correct values you can try to detect the pattern/rules of the best moves.

 Posts: 6
 Joined: Fri Apr 27, 2018 6:17 pm
Re: Problem 503
this problem is frustrating.
i have absolutely no idea how i could even write a brute force algorithm for this given that i have no idea how to calculate the expected value of a given sitation since that's the thing i need to find out.
i have never run into this problem with any other euler problem, and i did quite a few involving recursive solutions and probabilities (like the blood test problem)
i have absolutely no idea how i could even write a brute force algorithm for this given that i have no idea how to calculate the expected value of a given sitation since that's the thing i need to find out.
i have never run into this problem with any other euler problem, and i did quite a few involving recursive solutions and probabilities (like the blood test problem)
Re: Problem 503
A strategy is just a function from "what has happened so far" to "what to do next". There are only n cards and games can't go on forever, so there's a finite number of possibilities for "what has happened so far" and a finite number of possible strategies. For small n it's possible to test all of them.