Problem 503

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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.

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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
albert
Posts: 53
Joined: Sat Aug 02, 2008 11:36 am

Problem 503

Post by albert » Sat Feb 14, 2015 11:31 pm

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?

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

Re: Problem 503

Post by TripleM » Sun Feb 15, 2015 2:41 am

She wouldn't get a score of 0, but a score equal to the value of the last card, as per step 3.

markmcb
Posts: 3
Joined: Mon Apr 27, 2015 7:15 pm

Re: Problem 503

Post by markmcb » Mon Apr 27, 2015 8:01 pm

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.

MuthuVeerappanR
Posts: 364
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 503

Post by MuthuVeerappanR » Tue Apr 28, 2015 5:41 am

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.
I did the same. Interestingly, I get a total EV of 25 for both your cases.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

markmcb
Posts: 3
Joined: Mon Apr 27, 2015 7:15 pm

Re: Problem 503

Post by markmcb » Tue Apr 28, 2015 6:12 pm

MuthuVeerappanR wrote:
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.
I did the same. Interestingly, I get a total EV of 25 for both your cases.
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.

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.

MuthuVeerappanR
Posts: 364
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 503

Post by MuthuVeerappanR » Tue Apr 28, 2015 6:28 pm

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?
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

markmcb
Posts: 3
Joined: Mon Apr 27, 2015 7:15 pm

Re: Problem 503

Post by markmcb » Tue Apr 28, 2015 7:18 pm

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?
I just accidentally copied it twice. Originally, I had the two columns side-by-side 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.

Cheers,
Mark

hamsterofdeath
Posts: 6
Joined: Fri Apr 27, 2018 6:17 pm

Re: Problem 503

Post by hamsterofdeath » Sun Sep 08, 2019 4:55 pm

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?

User avatar
Animus
Administrator
Posts: 1701
Joined: Sat Aug 16, 2014 12:23 pm

Re: Problem 503

Post by Animus » Sun Sep 08, 2019 8:32 pm

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.

hamsterofdeath
Posts: 6
Joined: Fri Apr 27, 2018 6:17 pm

Re: Problem 503

Post by hamsterofdeath » Sun Sep 08, 2019 11:02 pm

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)

DJohn
Posts: 50
Joined: Sat Oct 11, 2008 11:24 am

Re: Problem 503

Post by DJohn » Mon Sep 09, 2019 3:49 pm

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.

Post Reply