Alice and Bob play the game. The rules are as follows:
- Initially, there are n cards on the table, each card has a positive integer written on it.
- At the beginning Alice writes down the number 0 on the sheet of paper. Then players pick cards from the table alternately. When a player picks a card, he/she writes down the greatest common divisor of a number that is written on a card and the number that was last written on the sheet of paper.
- Then the player throws this card away, so it can never been taken again.
Lossing conditions :
A player loses if after his/her turn the number, written on the piece of the paper is 1.
A player also loses, if he/she isn't able to make a move.
What will be the probability of Alice's victory if she makes the first move and the both players play optimally and what is the probability of Alice's victory if she makes the first move and the both players make moves randomly
Note : If player makes moves randomly, he/she chooses a card with equal probability among those that remained on the table.
Example :
Let their are 5 cards initially with values : 6 10 15 22 28
Then here answer will be 0 for first case and 0.4 for second case.
How to solve this problem?Please help me