Math problem (easy)

[perceval]

I played a game with my 7 year old son this week end:

The players have cards on their hands, numbered from 1 to 9.

One of the player throws 2 dice.

Then all players must try to match the total of the dice by playing 1,2 or,3 cards, such that they can match the dice sum by substracting or adding the values of the cards played.

For example, if the total of the dice is 5:
you can play:
-1 card "5" OR
- 2 card "3" + "2" OR

- 2 cards "7" - "2" OR
- 3 cards "3" +"1" + "1" OR
- 3 cards "3" +"3" - "1" (you can mix substraction and additions)
etc....

If you cannot match the dice sum with the cards in hand, you must draw a card.
The winner if the first one to get rid of all his cards

Question:
what is the hand of cards that maximize the probability that you will finish next turn, ie play all your cards at once to match the dice sum ?


(you can play at most 3 cards to match the dice sum).
i have a proposal but i am not sure that it is the optimum

Bonus Question (just thought of it ):
if you remove the 3 cards limitation to match the sum , is there a hand to be sure to finish next turn ? which hand ?

[entropi]

Is there a clever trick to solve, or do we have to think of dice outcome probability histogram and find the sequence of cards covering the biggest range?

[perceval]

that s not a book problem but a problem i thought of while playing, so i don't know of a pleasant trick.
i jus tried to find the hand with the max proba manually.

[Magicwand]

Is there a clever trick to solve, or do we have to think of dice outcome probability histogram and find the sequence of cards covering the biggest range?

two dice... #6 is the most common out come.
so i solved half of the problem

[perceval]

Is there a clever trick to solve, or do we have to think of dice outcome probability histogram and find the sequence of cards covering the biggest range?

two dice... #6 is the most common out come.
so i solved half of the problem

actually with 2 dice 7 is the most common outcome
proba for each dice sum outcome hidden:

7 has proba 6/36 = 1/6 proba, wheras 6 (and 8) have proba 5/36.
General formula:
p (n)=[6-abs(n-7)]/36 for 2<n<12

[Tryss]

Question:
what is the hand of cards that maximize the probability that you will finish next turn, ie play all your cards at once to match the dice sum ?

Probably 1,2 and 6, with this hand you win with : 3, 5, 7 and 9

it represent 44.44% of winning

Bonus Question (just thought of it ):
if you remove the 3 cards limitation to match the sum , what is the minimal hand to be sure to finish next turn ?

Is the number of card limited?

If it's not limited, then you can't be sure to finish next turn. If you have only even card and the dice is odd, you've lost

[entropi]

Is there a clever trick to solve, or do we have to think of dice outcome probability histogram and find the sequence of cards covering the biggest range?

two dice... #6 is the most common out come.
so i solved half of the problem

For 4, you need 1-3; 3-1; 2-2
For 5, you need 1-4; 4-1; 2-3; 3-2
For 6, you need 1-5; 5-1; 2-4; 4-2; 3-3
For 7, you need 1-6; 6-1; 2-5; 5-2; 3-4; 4-3
For 8, you need 2-6; 6-2; 3-5; 5-3; 4-4
For 9, you need 3-6; 6-3

So 7 is more probable than 6

It should be such a card sequence that covers 6, 7, 8


So, if you have two cards as 1 and 7, you cover 6 and 8 (but miss 7 itself ). Anyway, with 1 and 7 the probability you finish next round is 10/36. Not bad

[hyperpape]

1,1,7 is not bad--you win on 6,7,8.

but 1,2,6 wins on 3,5,7,9.
I bet that's better.

[entropi]

1,1,7 is not bad--you win on 6,7,8.

but 1,2,6 wins on 3,5,7,9.
I bet that's better.

1,1,7 gives you 5,7,9

But of course 1,2,6 is much better because it additionally covers 3. The question is whether something better exists

[Wildclaw]

Question:
what is the hand of cards that maximize the probability that you will finish next turn, ie play all your cards at once to match the dice sum ?

The two first cards are 1 and 2. The final card can be either 6 7 or 8. All three give you the same 16/36 chance on winning.

Bonus Question (just thought of it ):
if you remove the 3 cards limitation to match the sum , is there a hand to be sure to finish next turn ? which hand ?

No. If a hand contains an even number of even cards it will only be able to produce even results. If a hand contains an odd number of even cards it will only be able to produce odd results.

[daniel_the_smith]

Three way tie.

winners:
[1 2 6] [5 9 3 7] 0.4444444444444444
[1 2 7] [4 8 6 10] 0.4444444444444444
[1 2 8] [5 9 7 11] 0.4444444444444444

every other combination:
[1 1 1] [3] 0.05555555555555555
[1 1 2] [4 2] 0.1111111111111111
[1 1 3] [5 3] 0.16666666666666666
[1 1 4] [4 2 6] 0.25
[1 1 5] [5 3 7] 0.3333333333333333
[1 1 6] [4 8 6] 0.3611111111111111
[1 1 7] [5 9 7] 0.38888888888888884
[1 1 8] [8 6 10] 0.3611111111111111
[1 1 9] [9 7 11] 0.33333333333333337
[1 2 2] [5 3] 0.16666666666666666
[1 2 3] [4 2 6] 0.25
[1 2 4] [5 3 7] 0.3333333333333333
[1 2 5] [4 8 2 6] 0.3888888888888889
[1 2 6] [5 9 3 7] 0.4444444444444444
[1 2 7] [4 8 6 10] 0.4444444444444444
[1 2 8] [5 9 7 11] 0.4444444444444444
[1 2 9] [8 12 6 10] 0.3888888888888889
[1 3 3] [5 7] 0.2777777777777778
[1 3 4] [8 2 6] 0.3055555555555556
[1 3 5] [9 3 7] 0.3333333333333333
[1 3 6] [4 8 2 10] 0.3333333333333333
[1 3 7] [5 9 3 11] 0.33333333333333337
[1 3 8] [4 12 6 10] 0.3333333333333333
[1 3 9] [5 7 11] 0.33333333333333337
[1 4 4] [9 7] 0.2777777777777778
[1 4 5] [8 2 10] 0.25
[1 4 6] [9 3 11] 0.2222222222222222
[1 4 7] [4 12 2 10] 0.2222222222222222
[1 4 8] [5 3 11] 0.2222222222222222
[1 4 9] [4 12 6] 0.25
[1 5 5] [9 11] 0.16666666666666666
[1 5 6] [12 2 10] 0.1388888888888889
[1 5 7] [3 11] 0.1111111111111111
[1 5 8] [4 12 2] 0.1388888888888889
[1 5 9] [5 3] 0.16666666666666666
[1 6 6] [11] 0.05555555555555555
[1 6 7] [12 2] 0.05555555555555555
[1 6 8] [3] 0.05555555555555555
[1 6 9] [4 2] 0.1111111111111111
[1 7 7] [] 0
[1 7 8] [2] 0.027777777777777776
[1 7 9] [3] 0.05555555555555555
[1 8 8] [] 0
[1 8 9] [2] 0.027777777777777776
[1 9 9] [] 0
[2 2 2] [2 6] 0.16666666666666669
[2 2 3] [3 7] 0.2222222222222222
[2 2 4] [4 8] 0.2222222222222222
[2 2 5] [5 9] 0.2222222222222222
[2 2 6] [2 6 10] 0.25
[2 2 7] [3 7 11] 0.2777777777777778
[2 2 8] [4 8 12] 0.25
[2 2 9] [5 9] 0.2222222222222222
[2 3 3] [4 8 2] 0.25
[2 3 4] [5 9 3] 0.2777777777777778
[2 3 5] [4 6 10] 0.3055555555555555
[2 3 6] [5 7 11] 0.33333333333333337
[2 3 7] [8 12 2 6] 0.33333333333333337
[2 3 8] [9 3 7] 0.3333333333333333
[2 3 9] [4 8 10] 0.3055555555555555
[2 4 4] [2 6 10] 0.25
[2 4 5] [3 7 11] 0.2777777777777778
[2 4 6] [4 8 12] 0.25
[2 4 7] [5 9] 0.2222222222222222
[2 4 8] [2 6 10] 0.25
[2 4 9] [3 7 11] 0.2777777777777778
[2 5 5] [8 12 2] 0.19444444444444448
[2 5 6] [9 3] 0.16666666666666666
[2 5 7] [4 10] 0.16666666666666666
[2 5 8] [5 11] 0.16666666666666666
[2 5 9] [12 2 6] 0.19444444444444445
[2 6 6] [2 10] 0.1111111111111111
[2 6 7] [3 11] 0.1111111111111111
[2 6 8] [4 12] 0.1111111111111111
[2 6 9] [5] 0.1111111111111111
[2 7 7] [12 2] 0.05555555555555555
[2 7 8] [3] 0.05555555555555555
[2 7 9] [4] 0.08333333333333333
[2 8 8] [2] 0.027777777777777776
[2 8 9] [3] 0.05555555555555555
[2 9 9] [2] 0.027777777777777776
[3 3 3] [9 3] 0.16666666666666666
[3 3 4] [4 2 10] 0.19444444444444442
[3 3 5] [5 11] 0.16666666666666666
[3 3 6] [12 6] 0.16666666666666669
[3 3 7] [7] 0.16666666666666666
[3 3 8] [8 2] 0.16666666666666669
[3 3 9] [9 3] 0.16666666666666666
[3 4 4] [5 3 11] 0.2222222222222222
[3 4 5] [4 12 2 6] 0.2777777777777778
[3 4 6] [5 7] 0.2777777777777778
[3 4 7] [8 6] 0.2777777777777778
[3 4 8] [9 7] 0.2777777777777778
[3 4 9] [8 2 10] 0.25
[3 5 5] [3 7] 0.2222222222222222
[3 5 6] [4 8 2] 0.25
[3 5 7] [5 9] 0.2222222222222222
[3 5 8] [6 10] 0.2222222222222222
[3 5 9] [7 11] 0.2222222222222222
[3 6 6] [9 3] 0.16666666666666666
[3 6 7] [4 2 10] 0.19444444444444442
[3 6 8] [5 11] 0.16666666666666666
[3 6 9] [12 6] 0.16666666666666669
[3 7 7] [3 11] 0.1111111111111111
[3 7 8] [4 12 2] 0.1388888888888889
[3 7 9] [5] 0.1111111111111111
[3 8 8] [3] 0.05555555555555555
[3 8 9] [4 2] 0.1111111111111111
[3 9 9] [3] 0.05555555555555555
[4 4 4] [4 12] 0.1111111111111111
[4 4 5] [5 3] 0.16666666666666666
[4 4 6] [2 6] 0.16666666666666669
[4 4 7] [7] 0.16666666666666666
[4 4 8] [8] 0.1388888888888889
[4 4 9] [9] 0.1111111111111111
[4 5 5] [4 6] 0.2222222222222222
[4 5 6] [5 3 7] 0.3333333333333333
[4 5 7] [8 2 6] 0.3055555555555556
[4 5 8] [9 7] 0.2777777777777778
[4 5 9] [8 10] 0.2222222222222222
[4 6 6] [4 8] 0.2222222222222222
[4 6 7] [5 9 3] 0.2777777777777778
[4 6 8] [2 6 10] 0.25
[4 6 9] [7 11] 0.2222222222222222
[4 7 7] [4 10] 0.16666666666666666
[4 7 8] [5 3 11] 0.2222222222222222
[4 7 9] [12 2 6] 0.19444444444444445
[4 8 8] [4 12] 0.1111111111111111
[4 8 9] [5 3] 0.16666666666666666
[4 9 9] [4] 0.08333333333333333
[5 5 5] [5] 0.1111111111111111
[5 5 6] [4 6] 0.2222222222222222
[5 5 7] [3 7] 0.2222222222222222
[5 5 8] [8 2] 0.16666666666666669
[5 5 9] [9] 0.1111111111111111
[5 6 6] [5 7] 0.2777777777777778
[5 6 7] [4 8 6] 0.3611111111111111
[5 6 8] [9 3 7] 0.3333333333333333
[5 6 9] [8 2 10] 0.25
[5 7 7] [5 9] 0.2222222222222222
[5 7 8] [4 6 10] 0.3055555555555555
[5 7 9] [3 7 11] 0.2777777777777778
[5 8 8] [5 11] 0.16666666666666666
[5 8 9] [4 12 6] 0.25
[5 9 9] [5] 0.1111111111111111
[6 6 6] [6] 0.1388888888888889
[6 6 7] [5 7] 0.2777777777777778
[6 6 8] [4 8] 0.2222222222222222
[6 6 9] [9 3] 0.16666666666666666
[6 7 7] [8 6] 0.2777777777777778
[6 7 8] [5 9 7] 0.38888888888888884
[6 7 9] [4 8 10] 0.3055555555555555
[6 8 8] [6 10] 0.2222222222222222
[6 8 9] [5 7 11] 0.33333333333333337
[6 9 9] [12 6] 0.16666666666666669
[7 7 7] [7] 0.16666666666666666
[7 7 8] [8 6] 0.2777777777777778
[7 7 9] [5 9] 0.2222222222222222
[7 8 8] [9 7] 0.2777777777777778
[7 8 9] [8 6 10] 0.3611111111111111
[7 9 9] [7 11] 0.2222222222222222
[8 8 8] [8] 0.1388888888888889
[8 8 9] [9 7] 0.2777777777777778
[8 9 9] [8 10] 0.2222222222222222
[9 9 9] [9] 0.1111111111111111

Edit: added more detail

extra: for 2x 10 sided dice, the best you can do is:

[1 2 9] [8 12 6 10] 0.30000000000000004

for 3x 6 sided dice, it's:

the same:
[1 2 9] [8 12 6 10] 0.38425925925925924

[hyperpape]

No. If a hand contains an even number of even cards it will only be able to produce even results. If a hand contains an odd number of even cards it will only be able to produce odd results.

I think you're slightly off: [1,2,3] can produce 2,4,6. [1,2,3,4] can produce 2,4,6,8,10.

It seems to be that the true constraint is that if the sum of cards is even, you can only produce even amounts, if the sum is odd, you can only produce odd amounts, using all your cards. If you subtract a card worth n instead of adding, you reduce the total by 2n. That shows that there is no hand guaranteed to go out. The best you can do is 50% odds, achieved with 12 1s or 12 2s.

[shapenaji]

This game sounds like fun,

I've thought of a variant which might be enjoyable too:

Roll 4 six-sided dice, now you may use any of the cards in your hand to add/subtract/multiply/divide to get the final outcome. (With the caviat that you may not multiply/divide by 1)

So, for example, say the dice come down 18, and you hold 1,4,7,3

You remove the 3-card limit, and 3*7-(4-1) = 18

You might need to have more cards in hand to play this way though, it would be quite easy to run out fast.


As to the original problem, I imagine backgammon has already solved this one.

[Wildclaw]

I think you're slightly off: [1,2,3] can produce 2,4,6. [1,2,3,4] can produce 2,4,6,8,10.

Ah yeah. I meant an even number of odd numbers makes the sum even.

[perceval]

I think Tryss gave a good solution first, wildclaw was the first to give all 3.

but dts gave the brute force proof (you either did that by computer or you are crazy )

but brute force is useful: i didnt even try with even numbers and actually its a tie with odd numbers

a proof without listing all cases ?

i wondered if there was a proof other than case exhaustion (ugly programer trick ! booooh ), actually the parity argument makes it possible to have one:
as observered, the parity you can obtain is fixed.
in addition, with 1 card you cover 1 number, with 2 at most 2, with 3 at most 4 (you have 2*2*2= 8 total ways to choose the signs but by symmetry half those number will be negative or 0.)
So the optimum is a 3 card hand, allowing to finish with 4 outcomes of the same parity.
The best you can do is take the 4 outcome with the higher probability.

The most probable odd numbers are 7, p=6/36 5,9 p=4/36, and 3 and 11 p=2/36 in that order.you can only have 4 of those 5 numbers So being able to cover 7,5,9, 3 or 7,5,9, 11 is optimum for odd number (aye! symmetry breaking)
for even number 4,6,8,10 is optimum ( its symmetric by reflexion around 7 so we have 1 solution instead of 2 for odd numbers)
all 3 have a proba (2*5+2*3)/36=(6+2*4+2)/36=16/36=4/9

When you have the set of numbers N1,N2,N3,N4 (ordered)extracting the hand of A,B, C is easy:
you have N4=A+B+C
N3=A+B-C
N2 = A-B+C
N1=A-B-C
=>C= (N4-N3)/2 in all 3 cases here its 1
B= (N4-N2)/2 in all 3 cases here its 2
A = N4-3


So i think we have a kind of proof, backed up by numeric evidence

So a good strategy is to try to stay at 3 cards with a 1 and a 2 in hand i guess.
(when you have more than 3 cards you often have a choice of the way you want to match the sum)