Combinatorics + Game Theory Puzzle
Source: Random search on http://math.stackexchange.com/
Problem:
Two players A and B play the following game:
Start with the set S of the first 25 natural numbers: S={1,2,…,25}.
Player A first picks an even number x_0 and removes it from S: We have S:=S−{x_0}.
Then they take turns (starting with B) picking a number x_n∈S which is either divisible by x_n-1 or divides x_n-1 and removing it from S.
The player who can not find a number in S which is a multiple or is divisible by the previous number looses.
Which player has the winning strategy and what is it?
This comment has been removed by the author.
ReplyDeleteB wins. Pair up the numbers in 1...25, except for 1 and primes more than 11, as below:
ReplyDelete(2,14) (3,15)
(4,16) (5,25)
(6,12) (7,21)
(8,24) (9,18)
(10,20) (11,22)
When A chooses one of the above numbers, B responds with the other in its pair, which will ensure B always has a number to choose. A will eventually have to pick 1, to which B responds with 23 for the win.
A wins. He chooses 16 on his first chance, and on his next he chooses a multiple of 3. After a few moves, B will be forced to choose 1, when A chooses 23
ReplyDeleteCertainly B wins as pointed out by Mike Earnest, but the pairs of number as response for B is not unique.
DeleteCertain pairs are uniquely determined. They are:
(22,11); (18,9); (2,14); (10,20); (5,25); (3,15); (21,7)
They have also been pointed out by Mike. But for other the following three sets of possibility are there:
1st : (4,16); (8,24); (6,12) % Same as that pointed by mike
2nd : (8,16); (4,24); (6,12)
3rd : (8,16); (4,12); (6,24)
so say if A chooses 24, then B can respond with 8, 6 or 4.
The substantive question is if n is any natural number, is there always a wining strategy for B?
if n=27, then A has a winning strategy,
DeleteA will choose 18. then the remaining numbers are paired thus:
(2,14) (3,15)
(4,16) (5,25)
(6,12) (7,21)
(8,24) (9,27)
(10,20)(11,22)
(13,26)
unpaired nos. are {1,17,19,23}
A will follow the strategy of completing pair. ultimately B will choose 1, then A will choose 23.
Note that B starts. I claim that B wins.
ReplyDeleteB chooses 23, A has to choose 1
B chooses 17, A has nothing to choose!
I think that u have to start with a even number
Delete