Two players play the following game. They alternately write divisors of $100!$ on the blackboard, not repeating any of the numbers written before. The player after whose move the greatest common divisor of the written numbers equals $1,$ loses the game. Which player has a winning strategy?
Problem
Source: 16-th Hungary-Israel Binational Mathematical Competition 2003
Tags: greatest common divisor, combinatorics unsolved, combinatorics
31.03.2007 00:05
$100! = 2^{97}\cdot 3^{48}\cdot 5^{24}\cdot 7^{16}\cdot 11^{9}...$ As we see, some primes divide $100!$ even, and some odd number of times. Let's say A is the set of those primes which divide even number of times, and B is the set of those primes, which divide odd number of times . If one of the players writes a number on the blackboard, that is divisible by some primes from A (say that number is n), then the second player can answer with a number, in which powers of divisors of n from B stay unchanged, and powers of all divisors from A change from $c$ to $a_{n}+1-c$, where $a_{x}$ is the greatest natural number, such that $x^{a_{x}}| 100!$ (x is a number from A or B). now we'll show that the begining player has a wining strategy. On the begining, he writes a number z, divided only by primes from B, and divided by all primes from B, such that: $z = c_{1}^{a_{c_{1}}}+c_{2}^{a_{c_{2}}}+...$ so it will be: $2^{48}\cdot 11^{5}\cdot 13^{4}...$ now, if his oponent writes a number divisible by a prime from A, he can act as it was written before. If his oponent writes a number, divisible only by primes from B, lets say: $3^{d_{1}}\cdot 5^{d_{2}}\cdot 7^{d_{3}}...$ then player one can write a number: $3^{a_{3}+1-d_{1}}\cdot 5^{a_{5}+1-d_{2}}\cdot ...$ note: player on uses only the primes that his oponent used, to construct his number from his oponents number.
01.08.2007 09:59
I think the second player has the winning strategy, and here's a simple solution: Observe that because we have at least $ 2$ odd powers in $ 100! = 2^{97}\cdot 3^{48}\cdot 5^{24}\cdot 7^{16}\cdot 11^{9}...$ , for any $ p$ prime dividing $ 100!$, we have an even number of divisors divisible with $ p$(for example if $ p=2$ we have the number of divisors divisible by $ 2$ : $ 97\cdot(48+1)\cdot(24+1)\cdot(16+1)\cdot(9+1)\dots$. If player one begins with a power of a prime, then the game will end when all the divisors divisible with that prime end, which number is even in total, so player two will always have an odd number of choices, so he will win. If player one does not begin with a power of a prime(of course he won't start with $ 1$ , just if he wants to end this nightmare immediately), then player two will choose a power of a prime dividing it. But then it's the same as case 1, just that one divisor is "consumed" already, so player two will win again.