1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ If Alice picks a number m, then since m divides m and 0, Alice will write m on the paper. So, if Bob plays optimally, he will want to choose a number p that is prime, that divides m and for which the other numbers on the remaining cards are not multiples of p. The problem is without knowing what the numbers on the cards are, how would you calculate the probability? Are you sure you have posted all relevant information for the question? $\endgroup$ – user137481 May 2 '14 at 16:44
  • $\begingroup$ @undergrad Numbers on the card are known like here 6 10 15 22 28 are known $\endgroup$ – User May 2 '14 at 20:34
  • $\begingroup$ Break the numbers into prime factors: 2.3, 2.5, 3.5, 2.11, 2.2.7. Suppose Alice starts first and then Bob picks his number optimally. There are only 3 possibilities for the GCD after Bob finishes picking. They are 2, 3 or 5. For GCD=2, there are $\binom{4}{1}3! ways$. For GCD = 3, there are $\binom{2}{1}3! ways$ and for GCD=5 there are $\binom{2}{1}3!$. So, there are a total of 48 ways for Alice to lose if the players play optimally. $\endgroup$ – user137481 May 2 '14 at 21:53
  • $\begingroup$ @undergrad What about when both play randomly and could you please elaborate your explanataion in terms of probability $\endgroup$ – User May 2 '14 at 22:02
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ And what about playing optimally and randomly?Though you reduced the question to simpler form but its still as complex as it was earlier i guess $\endgroup$ – User May 3 '14 at 2:17
  • $\begingroup$ Answering the question while playing randomly is a lot harder than looking at who has the winning strategy $\endgroup$ – Jorge May 3 '14 at 2:29
  • $\begingroup$ There might be a simple way to translate it into a nim game. $\endgroup$ – Jorge May 3 '14 at 2:34
  • $\begingroup$ Yeah i know,And could you generalise it for optimal one ? $\endgroup$ – User May 3 '14 at 2:53
  • $\begingroup$ By the theorem in my previous comment you can turn this into a nim game. But I don't see an evident way to do so. $\endgroup$ – Jorge May 3 '14 at 3:00
1
$\begingroup$

There are 5! = 120 ways to pick the 5 numbers.

Consider the following cases below where the players play randomly. Add up the ways Alice can win. It sohuld be 48 and 48/120 = 0.4

(6, 10), (10, 6), 15 - Bob Wins (4 ways)
(6, 10), (10, 6), 22, 15 - Alice Wins (2 ways)
(6, 10), (10, 6), 22, 28 - Bob Wins (2 ways)
(6, 10), (10, 6), 28, 15 - Alice Wins (2 ways)
(6, 10), (10, 6), 28, 22, 15 - Bob Wins (2 ways)
(6, 15), (15, 6) - Bob Wins (2*3! = 12 ways)
(6, 22), (22, 6), (10, 28), (28, 10), 15 - Bob Wins (4 ways)
(6, 22), (22, 6), (10, 28), 15 - Alice Wins (4 ways)
(6, 22), (22, 6), 15 - Bob Wins (4 ways)
(6, 28), (28, 6), (10, 22), (22, 10), 15 - Bob Wins (4 ways)
(6, 28), (28, 6), (10, 22), 15 - Alice Wins (4 ways)
(6, 28), (28, 6), 15 - Bob Wins (4 ways)
(10, 15), (15 or 10), (6, 22, 28) - Bob Wins (2*3*2 = 12 ways)
(10, 22), (22, 10), (6, 28), 15 - Bob Wins (4 ways)
(10, 22), (22, 10), 15 - Alice Wins (4 ways)
(10, 22), 15 - Bob Wins (4 ways)
(10, 28), (28, 10), (6, 22), (22, 6), 15 - Bob Wins (4 ways)
(10, 28), (28, 10), (6, 22), 15 - Alice Wins (4 ways)
(10, 28), 15 - Bob Wins (4 ways)
(15, 22) - Alice Wins (2*3! = 12 ways)
(15, 28) - Alice Wins (2*3! = 12 ways)
(22, 28), (28, 22), (6, 10), (10, 6), 15 - Bob Wins (4 ways)
(22, 28), (28, 22), (6, 10), 15 - Alice Wins (4 ways)
(22, 28), (28, 22), 15 - Bob Wins (4 ways)

$\endgroup$
1
  • $\begingroup$ I know to solve it.But how to generalise it for a given n ? $\endgroup$ – User May 3 '14 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.