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
The game is not changed at all if we turn each of the number into the square-free number with the same prime divisors. Now for a certain set of cards we consider the set $\{p_1,p_2,p_3\dots p_n\}$ of all the primes in the composition of the cards. when player 1 picks the first card with primes $q_1,q_2,\dots q_n$ we are restricted to only picking cards that have a prime divisor in $\{q_1,q_2,q_3\dots q_n\}$ and moreover the primes dividing the common divisor will be a subset of $\{q_1,q_2\dots q_n\}$ So then we can look at all of the numbers of the cards as a subset of primes. and every time we chose a number we get a subset of the set of primes we had previously.
Thus the game can be thought of as the following game. There are $n$ finite sets on a board. Player $1$ picks a set ,writes it down in a sheet and deletes it from the board. Then player two selects another set and writes down the intersection of the selected set and the initial set, writes it down on the sheet and deletes the set he just selected from the board. After that players take turns selecting elements from the board, taking the intersection of the set on the board and the last element written on the sheet and deleting the selected set. A player loses if he writes down the empty set, or finds himself in a position where the board is empty.