Is there an optimum strategy for this ????

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Moonbeam
Posts: 289
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

Is there an optimum strategy for this ????

Postby Moonbeam » Fri Apr 10, 2015 6:28 pm UTC

I was in my local last night, playing along in the quiz .... hoping to win my share of the prize (free beer !!).
Well, the last round consisted of 10 questions.
It was very similar to the Million Pound Drop Game.
A question is read out and you are given 4 possible answers.
You are given 5 points to gamble as you see fit.
If you are 100% certain of the answer, you'd place all 5 points on your choice and if, when the quiz is marked, you're correct, then you receive 5 points.
If you're undecided between other answers, then you can split the 5 points up as you see fit. You must, however, leave 1 answer with no points on, so you can only place points on 3 answers max. So, for example, you could place your points 0,3,2,0 or 2,1,0,2 or 0,5,0,0 or 1,3,0,1 ..... etc.
When the questions are marked, you receive the number of points that you placed on the correct answer.
If you're a clever clogs and you know all the answers, you could theoretically pick up 50 points in this round.

Well ..... it got me thinking ..... assuming I don't have any idea at all, of any of the answers, is there an optimum strategy to maximise the number of points you receive ??
Assume all the answers are completely random and A,B,C,D has an equal 25% chance of being correct.

Is it better to gamble all 5 points on one selection; or split it over 2 , or 3 ??

Any ideas please ??

User avatar
Moonbeam
Posts: 289
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

Re: Is there an optimum strategy for this ????

Postby Moonbeam » Fri Apr 10, 2015 7:58 pm UTC

Afterthought - when I say " is there an optimum strategy to maximise the number of points you receive ??"

.... I suppose what I really mean is, "to maximise the average number of points", if the same strategy is applied over a long run of 10 questions.

Obviously you can only score a maximum of 50 points, if you place 5 points on 1 answer for all 10 questions; but it also increases your chances of scoring nothing for each question.
Spreading your points over 3 answers (say 2, 2 and 1), lowers your maximum possible score to only 20 but your chances of scoring 0 are reduced.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Is there an optimum strategy for this ????

Postby Qaanol » Sat Apr 11, 2015 5:28 am UTC

No there is not. Each mark you place somewhere has an expected return of 0.25 points. The linearity of expectation implies that the expected result of placing N marks is N/4 points.

What you do have control over is the variance. If you always place 5 marks on a single answer, you will maximize your variance. If you always go 2-2-1 you will minimize your variance.
wee free kings

User avatar
SirGabriel
Posts: 42
Joined: Wed Jul 16, 2014 11:54 pm UTC

Re: Is there an optimum strategy for this ????

Postby SirGabriel » Tue Apr 14, 2015 6:36 pm UTC

Moonbeam wrote:is there an optimum strategy to maximise the number of points you receive ??

You're asking the wrong question. Here's the question you should be asking: is there an optimum strategy to maximize my chance of winning?

The answer to that question is very different. As the other posters indicated, there is no way to maximize the average number of points you receive. There is, however, a way to maximize your chance of getting at least a certain number of points. For instance, say you need at least 47 points in order to win. In that case, you maximize your chance of winning by betting 5 points on 1 answer for any 9 of the questions and then at least 2 points each on 2 different answers on the remaining question.
Obviously, we have no way to estimate how many points you would need to win, and the problem would become more complicated if instead of considering a single minimum value you took into account the probability of winning with each possible score, but once you establish those parameters, an optimal strategy should exist.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Is there an optimum strategy for this ????

Postby Qaanol » Thu Apr 16, 2015 6:15 am UTC

SirGabriel wrote:As the other posters indicated

I count as a plural now? Sweet!
wee free kings

User avatar
SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

Re: Is there an optimum strategy for this ????

Postby SPACKlick » Thu Apr 16, 2015 2:19 pm UTC

For all 50 target scores here's how you're best to play

Spoiler:
There are 5 ways of splitting your money on each question (answer order doesn't matter because the answers are random)
[5,0,0,0], [4,1,0,0], [3,2,0,0], [3,1,1,0], [2,2,1,0] {Shorthand [5],[4],[3a],[3b],[2]

From these 5 there are 1001 possible ways to play (question order doesn't matter because the answers are random)
from 10@[5] to more complex ones like 4@[4],3@{3a],1@[3b],2@[2]

There are a binary million 4^10 = 1,048,576 possible sets of answers (this can be narrowed because each strategy has 2 answers with the same result but I prefer equiprobable results)

Then we can use nCr and nPr to... Umm... I'll get back to you when my maths is further on. Brain fart


My math sucks and my coding's not much better. I'm brute forcing it but it'll take 8 hours to run every game with every strategy results in the morning.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Is there an optimum strategy for this ????

Postby Qaanol » Fri Apr 17, 2015 4:59 am UTC

Here’s the full strategy table. Entries encode the optimal move (or the highest-numbered optimal move if several are tied), by the following method:
-1: There is no possible move you can make to win.
0: Go with (2, 2, 1, 0)
1: Go with (3, 1, 1, 0)
2: Go with (3, 2, 0, 0)
3: Go with (4, 1, 0, 0)
4: Go with (5, 0, 0, 0)

Each row represents the number of additional points you need to win, with the top row being “You need 0 more points to win” and the bottom row “You need 50 more points to win”.

Each column represents the number of rounds remaining to be played, with the left column being “There are 0 rounds remaining” and the right column “There are 10 rounds remaining”.

To follow an optimal strategy, start in the right-hand column (because there are 10 rounds) at the row corresponding to the number of points you think you’ll need in order to win (recall the top row is “0” and the bottom row is “50”). Each round, use the strategy encoded by the entry you are on, then move to the left one column and up a number of rows equal to the points you just gained (so stay at the same row if you got 0 points that round).

Interestingly, the only time that (4, 1, 0, 0) is strictly superior to (5, 0, 0, 0) is when you need exactly 6 points and there are exactly 3 rounds remaining, and even then (as seen later) the move (3, 1, 1, 0) is just as good.

Code: Select all

-1,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4
-1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1
-1,  2,  0,  0,  0,  0,  0,  0,  0,  0,  0
-1,  4,  2,  0,  0,  0,  0,  0,  0,  0,  0
-1,  4,  4,  2,  0,  0,  0,  0,  0,  0,  0
-1,  4,  4,  4,  2,  0,  0,  0,  0,  0,  0
-1, -1,  4,  3,  1,  0,  0,  0,  0,  0,  0
-1, -1,  4,  4,  0,  0,  0,  0,  0,  0,  0
-1, -1,  4,  4,  4,  2,  0,  0,  0,  0,  0
-1, -1,  4,  4,  4,  4,  2,  0,  0,  0,  0
-1, -1,  4,  4,  4,  4,  4,  4,  2,  0,  0
-1, -1, -1,  4,  4,  4,  1,  1,  1,  0,  0
-1, -1, -1,  4,  4,  4,  4,  0,  0,  0,  0
-1, -1, -1,  4,  4,  4,  4,  4,  4,  2,  0
-1, -1, -1,  4,  4,  4,  4,  4,  4,  4,  2
-1, -1, -1,  4,  4,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1,  4,  4,  4,  4,  4,  4,  1
-1, -1, -1, -1,  4,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1,  4,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1,  4,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1,  4,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  4


Or, at least, that’s an optimal strategy table if I wrote my dynamic-programming solution correctly. Here’s the code, written in Swift:
Spoiler:
The “move” array ends up storing the optimal move (as the index of its row in “moves”), and the “prob” array ends up storing the probability of winning under optimal play. And they’re both transposed from what I posted above, meaning eg. move[col][row] is the entry in the col’th column of the row’th row of what I posted above.

Code: Select all

let moves = [[2, 2, 1, 0],
             [3, 1, 1, 0],
             [3, 2, 0, 0],
             [4, 1, 0, 0],
             [5, 0, 0, 0]]

let odds = 0.25
let rounds = 10
let points = 50

let baseMove = [Int](count: points+1, repeatedValue: -1)
var move = [[Int]](count: rounds+1, repeatedValue: baseMove)

let baseProb = [Double](count: points+1, repeatedValue: 0.0)
var prob = [[Double]](count: rounds+1, repeatedValue: baseProb)

prob[0][0] = 1.0

func nextMove(r:Int, n:Int) {
    for i in 0 ..< moves.count {
        var thisProb = 0.0
       
        for j in 0 ..< moves[i].count {
            let k = moves[i][j]
            if k >= n { thisProb += odds }
            else { thisProb += odds * prob[r-1][n-k] }
        }
       
        if (thisProb >= prob[r][n]) && (thisProb > 0) {
            prob[r][n] = thisProb
            move[r][n] = i
        }
    }
}

for r in 1 ... rounds {
    for n in 0 ... points {
        nextMove(r, n)
        if prob[r][n] == 0.0 { break }
    }
}


And to display the result in the transposed manner I used:

Code: Select all

for n in 0 ... points {
    for r in 0 ... rounds { print("\(prob[r][n]), ") }
    println()
}

for n in 0 ... points {
    println()
    for r in 0 ... rounds { print("\(move[r][n]), ") }
}



And if, for some reason, you decide you want an optimal strategy table with minimum variance rather than maximum (but obviously the same probabilities of winning), here it is. Made by the same code, just replacing “if (thisProb >= prob[r][n]) && (thisProb > 0)” with “if thisProb > prob[r][n]”.

Spoiler:

Code: Select all

-1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
-1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
-1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
-1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0
-1,  3,  2,  0,  0,  0,  0,  0,  0,  0,  0
-1,  4,  4,  4,  2,  0,  0,  0,  0,  0,  0
-1, -1,  0,  1,  1,  0,  0,  0,  0,  0,  0
-1, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0
-1, -1,  1,  1,  4,  2,  0,  0,  0,  0,  0
-1, -1,  3,  3,  4,  4,  2,  0,  0,  0,  0
-1, -1,  4,  4,  4,  4,  4,  4,  2,  0,  0
-1, -1, -1,  0,  1,  1,  1,  1,  1,  0,  0
-1, -1, -1,  0,  0,  0,  0,  0,  0,  0,  0
-1, -1, -1,  1,  1,  4,  4,  4,  4,  2,  0
-1, -1, -1,  3,  3,  4,  4,  4,  4,  4,  2
-1, -1, -1,  4,  4,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1,  0,  1,  1,  1,  1,  1,  1
-1, -1, -1, -1,  0,  0,  0,  0,  0,  0,  0
-1, -1, -1, -1,  1,  1,  4,  4,  4,  4,  4
-1, -1, -1, -1,  3,  3,  4,  4,  4,  4,  4
-1, -1, -1, -1,  4,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1,  0,  1,  1,  1,  1,  1
-1, -1, -1, -1, -1,  0,  0,  0,  0,  0,  0
-1, -1, -1, -1, -1,  1,  1,  4,  4,  4,  4
-1, -1, -1, -1, -1,  3,  3,  4,  4,  4,  4
-1, -1, -1, -1, -1,  4,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1,  0,  1,  1,  1,  1
-1, -1, -1, -1, -1, -1,  0,  0,  0,  0,  0
-1, -1, -1, -1, -1, -1,  1,  1,  4,  4,  4
-1, -1, -1, -1, -1, -1,  3,  3,  4,  4,  4
-1, -1, -1, -1, -1, -1,  4,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1,  0,  1,  1,  1
-1, -1, -1, -1, -1, -1, -1,  0,  0,  0,  0
-1, -1, -1, -1, -1, -1, -1,  1,  1,  4,  4
-1, -1, -1, -1, -1, -1, -1,  3,  3,  4,  4
-1, -1, -1, -1, -1, -1, -1,  4,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1,  0,  1,  1
-1, -1, -1, -1, -1, -1, -1, -1,  0,  0,  0
-1, -1, -1, -1, -1, -1, -1, -1,  1,  1,  4
-1, -1, -1, -1, -1, -1, -1, -1,  3,  3,  4
-1, -1, -1, -1, -1, -1, -1, -1,  4,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1,  0,  1
-1, -1, -1, -1, -1, -1, -1, -1, -1,  0,  0
-1, -1, -1, -1, -1, -1, -1, -1, -1,  1,  1
-1, -1, -1, -1, -1, -1, -1, -1, -1,  3,  3
-1, -1, -1, -1, -1, -1, -1, -1, -1,  4,  4
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  0
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  0
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  1
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  3
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  4
wee free kings

User avatar
SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

Re: Is there an optimum strategy for this ????

Postby SPACKlick » Fri Apr 17, 2015 8:35 am UTC

I worked the numbers a little differently. You have made an optimal strategy for if you know how many points you get after each question, hence the use of knowing with 5 questions left what to pick. My numbers work for picking all 10 first. Except I've made an error in the code somewhere so most strategies get 0 far too rarely by checking the answer for question 7 against the right answer for question 1. Bugger. won't have access to this computer tomorrow either.

From the numbers and accounting for the error As you get higher multiples of 5, and nearer the top 5n-1 and possibly 5n-2 you want to go all 5's.

hope my couple of optimisations during the fix work.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Is there an optimum strategy for this ????

Postby Qaanol » Fri Apr 17, 2015 11:41 pm UTC

SPACKlick wrote:I worked the numbers a little differently. You have made an optimal strategy for if you know how many points you get after each question, hence the use of knowing with 5 questions left what to pick. My numbers work for picking all 10 first.

Ah, good point.
wee free kings

User avatar
SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

Re: Is there an optimum strategy for this ????

Postby SPACKlick » Sat Apr 18, 2015 12:35 am UTC

Full list from an accurate brute force of 1billion games

Spoiler:
Need: Strategies [guesses@type,guesses@type] or [guesses@type] Odds

1: [n@3b, 10-n@2] 1048575/1048576
2: [10@2]1048565/1048576
3: [10@2]1048500/1048576
4: [10@2]1048200/1048576
5: [10@2]1047090/1048576
6: [10@2]1043718/1048576
7: [10@2]1034988/1048576
8: [10@2]1015548/1048576
9: [10@2]977703/1048576
10: [10@2]913133/1048576
11: [10@2]815848/1048576
12: [10@2]686708/1048576
13: [10@2]535328/1048576
14: [10@5] or [9@5,1@4] 497452/1048576
15: [10@5] 497452/1048576
16: [9@5, 1@3b] or [9@5, 1@2] 357484/1048576
17: [9@5,1@2], [9@5,1@3a] or [8@5, 2@2] 296248/1048576 <------This result confuses me
18: [8@5, 1@3a, 1@3b] 241816/1048576
19: [10@5] or [9@5,1@4] 235012/1048576
20: [10@5] 235012/1048576
21: [9@5, 1@3b] or [9@5, 1@2] 143158/1048576
22: [9@5, 1@2] or [9@5, 1@3a] 112540/1048576
23: [9@5,1@3a], [8@5,2@4],[9@5,1@3b],[9@5,1@4] or [10@5] 81922/1048576
24: [10@5] or [9@5,1@4] 81922/1048576
25: [10@5] 81922/1048576
26: [9@5, 1@3b] or [9@5, 1@2] 41098/1048576
27: [9@5,1@3a] or [9@5,1@2] 30892/1048576
28: [9@5,1@3a], [8@5,2@4],[9@5,1@3b],[9@5,1@4] or [10@5] 20686/1048576
29: [10@5] or [9@5,1@4] 20686/1048576
30: [10@5] 20686/1048576
31: [9@5, 1@3b] or [9@5, 1@2] 357484/1048576
32: [9@5,1@3a] or [9@5,1@2] 5944/1048576
33: [9@5,1@3a], [8@5,2@4],[9@5,1@3b],[9@5,1@4] or [10@5] 3676/1048576
34: [10@5] or [9@5,1@4] 3676/1048576
35: [10@5] 3676/1048576
36: [9@5, 1@3b] or [9@5, 1@2] 1084/1048576
37: [9@5,1@3a] or [9@5,1@2] 760/1048576
38: [9@5,1@3a], [8@5,2@4],[9@5,1@3b],[9@5,1@4] or [10@5] 436/1048576
39: [10@5] or [9@5,1@4] 436/1048576
40: [10@5] 436/1048576
41: [9@5, 1@3b] or [9@5, 1@2] 85/1048576
42: [9@5,1@3a] or [9@5,1@2] 58/1048576
43: [9@5,1@3a], [8@5,2@4],[9@5,1@3b],[9@5,1@4] or [10@5] 31/1048576
44: [10@5] or [9@5,1@4] 31/1048576
45: [10@5] 31/1048576
46: [9@5, 1@3b] or [9@5, 1@2] 3/1048576
47: [9@5,1@3a] or [9@5,1@2] 2/1048576
48: [9@5,1@3a], [8@5,2@4],[9@5,1@3b],[9@5,1@4] or [10@5] 1/1048576
49: [10@5] or [9@5,1@4] 1/1048576
50: [10@5] 1/1048576

So your best strategies are

[10@5] 22 targets
[9@5,1@2] 14 targets
[9@5,1@4] 14 targets
[9@5,1@3a] 13 targets
[9@5,1@3b] 13 targets
[10@2] 13 targets
[8@5,2@4] 6 targets
[n@3b,10-n@2] 1 target

Assuming all targets are equiprobable [10@50] has the best odds of winning


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 3 guests