Poison, antidote, water
Problem
Let's play a game ....
I have a large set of cards which are printed 'Poison', 'Antidote' and 'Water'.
I shuffle up the cards and lay out a row of 5 cards, face down.
You choose any two cards which are next to each other and turn them over. Two Poison cards is still Poison, so replace these two cards with a single Poison card. The same goes for two Antidote or Water cards - replace two of these with a single Antidote or Water card respectively. Mixing Water with Poison still leaves Poison, and mixing water with Antidote still leaves Antidote (we ignore the chemistry of concentrations in this game!)
The game is to repeat this procedure until you are left with a single card, and you lose if you end up with Poison.
My question is this: Does the order in which you decide to turn over the cards Sometimes, Always or Never matter? Give examples or a clear argument to illustrate your conclusion. If the cards are totally random, what is the chance of me being Poisoned?
Now let's play a similar game based on the classic Scissors, Paper, Stone. In this game Scissors beats Paper, Paper beats Stone and Stone beats Scissors.
I lay out face down a row of 5 cards printed with one of these symbols and you turn over two cards next to each other, replacing it with the winner of the two cards if the two cards are different or removing one of the two cards if they are the same.
My question is again this: Does the order in which you decide to turn over the cards Sometimes, Always or Never matter? Give examples or a clear argument to illustrate your conclusion.
Now consider this: What are the structural similarities and differences between the two games?
And finally: Imagine that you are given a set of cards with 3 different images on them (you choose!). Is it possible to invent a different set of rules such that the order in which the cards are turned over does not affect the result of the game?
Extension: Repeat for a game with sets of cards with 4 images on them.
Student Solutions
It was nice to see several younger solvers dipping their toes into this introduction to group theory! Whilst we have some nice thoughts so far, we feel that there is more milage in this problem, so we are leaving it open as a tough nut for the more advanced students to consider.
Shriram from Canberra Grammar in Australia noted that you win the game if you save the choice of antidotes until the end of the game, although it would be luck if this happened. However, this shows that the order does matter! Shriram felt that you would lose the game 33% of the time through luck.
dxm from Wilsons primary school attempted a nice systematic approach by noting that if you start on the left then you die most of the time.
Daniel from Savile Park Primary sent us a lovely set of thoughts, which is very impressive when his age is taken into account! We liked the fact that he created a simpler version of the problem to get a feel for the ideas and were delighted with his version of the game in which the order does not matter! His solution is as follows:
Does the order matter?
For the case that there are only 3 cards and the middle one is turned over (if it matters for this; it will matter in general, and 3 is easier than 5):
|
Cards |
Outcome |
Live or Die |
|
PPP |
P |
D |
|
PWP |
P |
D |
|
PAP |
P |
D |
|
APA |
A |
L |
|
WPW |
P |
D |
|
WWW |
W |
L |
|
AWA |
A |
L |
|
AAA |
A |
L |
|
WAW |
A |
L |
|
APP |
P/W |
D/L |
|
PPA |
W/P |
L/D |
|
WPP |
P |
D |
|
PPW |
P |
D |
|
AWW |
A |
L |
|
WWA |
A |
L |
|
PWW |
P |
D |
|
WWP |
P |
D |
|
PAA |
A/W |
L |
|
AAP |
W/A |
L |
|
WAA |
A |
L |
|
AAW |
A |
L |
|
PAW |
W |
L |
|
APW |
W |
L |
|
AWP |
W |
L |
|
PWA |
W |
L |
|
WPA |
W |
L |
|
WAP |
W |
L |
If 2As and 1P or vice versa it matters. But only 2P 1A changes survival.
Chance of being poisoned
From table chance of death=?
All 27 are equally likely starting from 5 cards because:
PP-> P
WP-> P
WW-> W
AP-> W
AW-> A
AA-> A
Scissors, Paper, Stone
The order sometimes matters.
If the 3 cards are all different then the order matters, but the middle one can't win.
e.g. Sc, P, St can be won by scissors or stone
Last Part
Cards with 1,2,3 on, largest number wins.
Order doesn't matter.
Well done Daniel!
Other solvers noted that although the game as it stands is random, for a PARTICULAR set of cards sometimes you live and sometimes you die. One unnamed solver noted that sometimes the game has a guaranteed outcome, for example if all of the cards are the same, which occurs with probability 1/81, and enumerated all other possibilities in a spreadsheet, suggesting that the chance of survival is 2/3 for the Poison, Antidote, Water game.
Another unnamed solver created a nice formal algebraic notation to aid with the analysis, although this is a 'formal' representation, as adding of + infinity and - infinity is undefined in arithmetic:
If you mix antidote and poison together you end up with water. If you mix either with water nothing happens. But if you mix one substance with the same substance nothing happens. Therefore the effects must be like the list below. Poison = -i (standing for infinity) Antidote = +i (standing for infinity) Water = 0 Taking one of my example cases (involving 2 poisons, 1 water and 2 antidotes): -i-i = -i -i+0 = -i i-i = 0 0+i = i I survived But if you rearranged the order in which this occurred: i+i = i i+0 = i i-i = -i -i-i = -i I would have died Taking another circumstance (involving 3 poisons and 2 waters): 0-i = -i -i-i = -i -i-i = -i 0-i = -i I died and there was nothing I could do about it. The order sometimes matters, but not always.
If anyone has any other thoughts concerning this problem do let us know; solutions will be left open!
Update - March 2016. Aneesh has sent us an induction-style argument to explain why the probability of not surviving is 1/3:
Consider the case with only two cards:
Here are the number of ways of getting poison (PP, WP, PW)
Here are the number of ways of getting water (WW, PA, AP)
Here are the number of ways of getting antidote (AW, WA, AA)
Meaning there is a 1/3 chance of getting poison, water or antidote for the case with only two cards.
I conjectured that the number of ways of getting poison for n cards is always 1/3. I believe I can show this as follows:
Suppose the number of ways of getting poison for n cards is 1/3.
Consider a pile of 'n+1' cards in a row:
1 2 3 4 ...... n (n+1)
We must start with combining some two adjacent cards. Say we combine x and x+1, so we have:
1 2 3 4 ... (x + (x+1)) ..... n (n+1)
Now consider (x + (x+1)) as one 'object' in this row, so we effectively have only n cards in a row.
Now we know that for all cards excluding (x + (x+1)) there is an equal likelihood of a water, antidote or poison being under these cards.
If we can show that there is an equal likelihood of water, antidote or poison being under the (x + (x+1)) card, then we have shown that upon combining ANY two cards, we just receive a uniformly distributed row of n cards, which will mean that the probability of losing ( receiving poison ) will just be 1/3 again by hypothesis.
But we already know that the number of ways of getting poison, water, or antidote is 1/3 for two cards ( as shown above), so that the likelihoods of water, antidote or poison under the (x + (x+1)) card are all equal (1/3).
This means that we effectively are dealing with n cards, and the probability of getting poison at the end will just be (1/3).
So really we only need to consider the case with 2 cards, and then just induct upwards and we have proved that it is 1/3 for the case with any number of cards on the table.