Again just a sketch. Define a number greater than $k$ to be PURE if it has only prime factors at most $k$, and call the TYPE of a number the set of prime factors $\le k$ it has. We wish to prove that good/bad-ness depends only on the type. First prove that the smallest integer of any particular type $T$ is pure. Then just use induction as follows. Consider a number $n$ with type $T$ and let $t$ be the smallest number of type $T$ (here $n > t$). If $t$ is a winning position, then some losing position $x$ is accessible from it. We may assume $x$ is pure by the lemma; thus we can move from $n$ to $x$ as well. Conversely, suppose $n$ is winning, and we can access some pure losing position $x$ from it. Obviously $t \neq x$ since $\gcd(n,x)=1<\gcd(n,t)$. If $t > x$ then we can move from $t$ to $x$, implying $t$ is winning. If $t < x$ then we can move from $x$ to $t$, also implying $t$ is winning. Hence $n$ is winning if and only if $t$ is winning as required.

lyukhson wrote: Fix an integer $k>2$. Two players, called Ana and Banana, play the following game of numbers. Initially, some integer $n \ge k$ gets written on the blackboard. Then they take moves in turn, with Ana beginning. A player making a move erases the number $m$ just written on the blackboard and replaces it by some number $m'$ with $k \le m' < m$ that is coprime to $m$. The first player who cannot move anymore loses. An integer $n \ge k $ is called good if Banana has a winning strategy when the initial number is $n$, and bad otherwise. Consider two integers $n,n' \ge k$ with the property that each prime number $p \le k$ divides $n$ if and only if it divides $n'$. Prove that either both $n$ and $n'$ are good or both are bad. The initial idea is of-course from basic concept of game theory. But the crucial idea seemed merely inductive to me. One idea follows strikes from the previous. If for an $n\geq k$, there is an $m$ with $(m,n)=1$ so that, $n>m\geq k$ and $m$ is good, then $n$ is bad. Otherwise, if for every $m$ with $m<n$ and $(m,n)=1$ is bad, then $n$ is good. For every move from $n$ to $m$, $m<n$, so the operation ends after a certain time. Obviously, $k$ itself, is good and any two good positive integers must have common prime factors(call it $\mbox{fact }1$. We will use just $\mbox{good }n$ or $\mbox{bad }n$ instead of $n$ is a good number or $n$ is a bad number, for brevity. Call $n$ and $n'$ to be $\mbox{brothers}$ "with the property that each prime number $p \le k$ divides $n$ if and only if it divides $n'$. Moreover, say, $n$ is $\mbox{inside }k$ if it does not have a prime factor $p>k$. Lemma 1: If $m$ is a multiple of a good $n$, then $m$ is good too. Proof: If $m$ is bad, then there must be a move to $r$ with $r$ good. But that would imply $r$ is co-prime to $n$. That's impossible from fact 1. Lemma 2: If $m$ and $n$ are so that $mn\geq k$ and $mn$ is bad, then $m^2n$ is bad too. Proof: Since $mn$ is bad, then there is a move to $r$ so that, $r$ is good. So, $r$ is co-prime to $m^2n$ and we can consider the move $m^2n$ to $r$ too. This means $m^2n$ must be bad itself. Lemma 3: If $p$ is a prime greater than $k$ and $n$ is bad, then, $np$ must be bad. Proof: If not, choose $n$ to be minimal. Since $n$ is bad, again, we have a move to a good $m$. But $np$ doesn't have a move to $m$. So, $m$ must be divisible by $p$. Let $m=p^es$ with $p\not|s$. Certainly, $s>1$ and co-prime to $np$. Take $l$ to be $s^l< k\leq s^{l+1}$. Then, $s^{l+1}<sk<ps=\dfrac{m}{p^{e-1}}<\dfrac{n}{p^{e-1}}$. Thus, $n>p^{e-1}s$ and all of $s^{l+1}p^i$ for $i=0,1,...,e$ is bad(since $n$ is minimal). This produces a contradiction of lemma $1$. Lemma 4: For $n\geq k$ with $n$ divisible by a prime $p\leq k$, it has a brother $m$ with $n\geq m\geq k$ and no prime $q>k$ divides $m$. Proof: There is nothing to prove if $n$ itself is inside $k$. Let $P=\prod_{p\leq k,p|n}p$. For a prime $p\leq k$, take the minimal $l$ with $m=p^lP\geq k$. Now, it is almost obvious that, $m$ satisfies the desired property. Lemma 5: Two good $n$ and $m$ have a common prime factor $p\leq k$. Proof: If not, there are at least two $n$ and $m$ so that $n\geq m\geq k$ and for all prime $p|n,m$, we have $p> k$(if there is only one, our claim becomes true). Now, just consider the minimal $m$. Then, $m$ must share a common prime factor with $k$ since it is good. Therefore, $n>m$ and using lemma $4$, we can easily deduce that this leads to $n'\geq m\geq k$ of the similar conditions with $n'<n$, introducing a contradiction. Now, let's get back to the original proof. Let $n$ and $n'$ be brothers with $n$ bad and $n'$ good. Then, $n$ has a move to $m$ for some good $m$. From lemma $5$, there is a prime $p\leq k$ so that $p|n',m$. But this shows that, $p|n$ too since $n'$ is a brother of $n$. A contradiction! Such a tedious proof!

Let the greatest prime factor of k be z. Note that if it is your move, and the number is k+z, you lose. Now assume if the number is a multiple of z and less than or equal to k+cz and it is your move, you lose. You also lose if the number is k+(c+1)z as you change it to a number that is not a multiple of z, and your opponent can change it to the greatest number that is less than your number that is a multiple of z. Thus, we have proved by strong induction that a number is good if and only if it is a multiple of the smallest prime factor of k. Since the smallest prime factor of k is less than k, n contains it if and only if n' does, so n is good if and only if n' is.

Let good numbers be black, and bad numbers be white. I prove the following lemma.

Now I prove the following lemma.

Now let's prove the following lemma.

I like this problem, but there are a lot of details that must be taken care of unless one manages to find a clever re-wording of the solution, which I was unable to do.

To determine coprimality, it suffices to focus on the set $S_n$ of prime divisors of $n$. So the game board looks like this (e.g. for $k=6$): \begin{tabular}{c||c|c|c|c|c|c|c|c|c|c} $n$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ & $12$ & $13$ & $14$ & $15$ \\ \hline $S_n$ & $\{2,3\}$ & $\{7\}$ & $\{2\}$ & $\{3\}$ & $\{2,5\}$ & $\{11\}$ & $\{2,3\}$ & $\{13\}$ & $\{2,7\}$ & $\{3,5\}$ \end{tabular}Since A can't move from $n=k$, $k$ is good. So numbers coprime to $k$ are bad: A can move to $k$. But multiples of $k$ are good: A can only move to a number coprime to $k$, and then B takes it to $k$. The game is finite, so all numbers are either good or bad. Suppose the first $m$ good numbers are: $n_1=k<n_2<\dots<n_m$. Then some $n>n_m$ is bad if we can move from it to a good number, and so the next good number $n$ is the smallest $n>n_m$ from which we can't move to any other good number. Hence, if we imagine $S_{n_m+1},\dots$ incoming like in Tetris, the next good $n$ is the one where $S_n$ intersects all of $S_{n_1},\dots,S_{n_m}$. Let's make a few observations: Any two good sets (sets of the form $S_n$ where $n$ is good) intersect. If $n$ is good, then $S_{n'}\supset S_n$ implies $n'$ is good, because all good sets share an element with $S_n$, so when it is time to determine whether $n'$ is good, it can't be bad, so it's good. But if say $\{2,3\}$ and $\{2,3,7\}$ are good sets, any new good set intersecting $\{2,3,7\}$ must also intersect $\{2,3\}$. What this means is that in determining whether a new set is good, we only need to look at whether it intersects all the preceding atomic sets (i.e., the good sets with no good proper subset). If we could prove that all the atomic sets only have prime divisors $\le k$, would we be done? Well, it's clear that $n$ turns out to be good if $S_n$ contains some atomic set, as it intersects all preceding good sets. Also, if $n$ is good, then $S_n$ must contain some atomic set. So if $n,n'$ have the same $\le k$ prime divisors, $n$ is good iff $S_n$ contains some atomic set -- and assuming this only depends on the $\le k$ prime divisors of $n$, this holds iff $S_{n'}$ contains some atomic set iff $n'$ is good. So yes, we'd be done! To finish, all we need is: Claim. All atomic sets have only prime divisors $\le k$. Proof. Suppose there is an atomic set $S_n$ with prime divisors $p_1,\dots,p_r>k$, and suppose we took the smallest $n$. Then write $n=n_0(p_1^{\alpha_1}\dots p_r^{\alpha_r})$ where $n_0$ only has $\le k$ prime divisors. Since $S_n\cap S_k\neq \emptyset$, $n_0$ has a prime divisor $q$. We're going to show that $S_n$ isn't atomic after all by finding a good $N$ with $S_N\subsetneq S_n$; to do this, we need to ensure that $S_N$ intersects all preceding atomic sets, which we can manage if we ask $k\le N<n$ and that $S_N=S_{n_0}$ (this is the only way we could possibly do this). If $n_0\ge k$, pick $N=n_0$. If $n_0<k$, try to pick some $N=n_0\cdot q^t$; there will surely be an $N$ of this form in the range $[k;qk]$. Luckily, then $N\le qk<n_0\cdot p_1\le n$, so $N$ works. So... done! We showed that $S_n$ isn't atomic after all, contradiction! $\blacksquare$

For obvious reasons, we'll call a good number a losing position, and a bad number a winning position. The first step is to create a workable reformulation of the problem. Let $S_n$ be the set of losing positions that are less than $n$ (note that a number less than $k$ is neither winning nor losing). If $n$ is relatively prime to any element of $S_n$, then the player can simply go to that element, and win. So if $\gcd(n,s)=1$ for some $s\in S_n$, then $S_{n+1}=S_n$. However, if $\gcd(n,s)>1$ for all $s\in S_n$, then $S_{n+1}=S_n\cup\{n\}$. Thus, if $S=S_n$ for some $n$, then the next real addition to $S$ is the smallest $x$ such that $\gcd(x,s)>1$ and $x>s$ for all $s\in S$. Using this algorithm, we can recursively construct the entire set $L$ of losing positions. To re-iterate, to get the next element of the list/set, simply take the first number that is not coprime to any number written in the list so far (and bigger than any number written). Our goal is to show that membership to $L$ (the set of losing positions) depends only on the number's set of prime factors that are at most $k$. To do this end, define $\rho(x)$ to be the smallest number that is at least $k$, and which has the same set of prime factors that are at most $k$ as $x$. We wish to show that $x\in L\iff\rho(x)\in L$. This is now split into two parts. But first, we need a super crucial lemma about $\rho(x)$. Lemma: $\rho(x)$ has prime factors all at most $k$. Proof of Lemma: Suppose $x=p_1^{e_1}\cdots p_r^{e_r}n$ where $p_i\le k$ for all $i$ and all the prime factors of $n$ are bigger than $k$. Now, $\rho(x)=p_1\cdots p_r m$ where $m$ is the smallest possible, and has all prime factors either $p_i$ or bigger than $k$. We want to show that in fact $m$ has all prime factors of the form $p_i$. Here, $m$ has to be at least $\lceil k/(p_1\cdots p_r)\rceil$, so we want to show the least integer at least $k/(p_1\cdots p_r)$ that has all prime factors either of the form $p_i$ or bigger than $k$ actually only has prime factors of the form $p_i$. Let $\ell=\lceil \log_{p_1\cdots p_r}k\rceil-1$. We see that \[(p_1\cdots p_r)^\ell\ge\frac{k}{p_1\cdots p_r},\]yet at the same time $\ell\le \log_{p_1\cdots p_r}k$, so $(p_1\cdots p_r)^\ell\le k$. Therefore, we have shown a value of $m$ (maybe not the smallest) that is at least $k/(p_1\cdots p_r)$ and with prime factors only of the form $p_i$, and that is at most $k$. Thus, the optimal value of $m$ will be at most $k$, meaning it will have prime factors only of the form $p_i$, as desired. $\blacksquare$ First, we show that if $\rho(x)\in L$, then $x\in L$. Suppose $\rho(x)=p_1^{e_1}\cdots p_r^{e_r}$. We know from the lemma then that $p_1\cdots p_r\mid x$. For all $s\in L$ with $s<\rho(x)$, we have $\gcd(s,p_1\cdots p_r)>1$, so $\gcd(s,x)>1$. For all $s\in L$ with $s>\rho(x)$ must share some common factor with $\rho(x)$, so suppose $p_i$ is shared. Again, we have $\gcd(s,x)>1$. Therefore, for all $s\in L$, we have $\gcd(s,x)>1$, so when applying the algorithm, we would be forced to include $x$ in $L$, as desired. Now, we show that if $x\in L$, then $\rho(x)\in L$. We proceed by strong induction on $x$. We see that $\min L=k$, and we have $\rho(k)=k$, so the statement is certainly true in the base case $x=k$. Now suppose $y\in L\implies\rho(y)\in L$ for all $y<x$. Suppose for sake of contradiction that $\rho(x)\not\in L$, so there is some $z<\rho(x)\le x$ such that $\gcd(\rho(x),z)=1$ where $z\in L$. The statement $\gcd(\rho(x),z)=1$ is the same as $\gcd(x,\rho(z))=1$ (by the lemma), but since $\rho(z)\in L$ (by induction hypothesis), we have that $\gcd(x,\rho(z))=1$. This is a contradiction as we know that $x\in L$, so it was not coprime to any former members of $L$, which $\rho(z)$ certainly is. Therefore, we must have $\rho(x)\in L$, as desired. Thus, we have $x\in L\iff\rho(x)\in L$, as desired. $\blacksquare$

I have a short proof without induction , but I don't know if it's right. First, WLOG we can suppose that $ n > n' $. Claim 1: $ x $ is good $ \iff $ any $ t \in [k,x-1] $ which is coprime to x is bad. (and define set $ K(x) := $ {$ t |t \in [k,x-1] $ which is coprime to x } ) Claim 2 : $ n $ is good $ \implies n' $ is good. Proof Obviously $ K(n') \subset K(n) $, so it's easy to see the proposition above is right. Claim 3 : $ n' $ is good $ \implies n $ is good. Proof If not , we restate it as there is a good number $ t \in K(n)/K(n') $ By the definition of good number and Claim 1 , we see that $ (t,n)=1 $. So $ n' \in K(t) $ ,but we have known that $ n' $ is good , from Claim 1 we get a contradiction! So from Claim 2 and Claim 3, we know $ n $ is good $ \iff n' $ is good. As desired.

Note that $x$ wins iff everything in $[k, x)$ loses and $x$ loses iff something in $[k, x)$ wins. Let the primeset of $n$ be the set of all prime factors of $n$ that are at most $k$. Let $B(n)$ be the smallest number greater than $k$ with the same primeset of $n$. Claim: $B(n)$ has no prime factors greater than $k$. Proof: Let the primeset be $\{p_1, ..., p_j\}$, and let $B(n)=p_1...p_jz$ for some $z$. Letting $m$ be the smallest integer such that $(p_1...p_j)^m\le k$, we find that if $z=(p_1...p_j)^m$, then $B(n)>k$ and $z$ satisfies all necessary conditions; thus, we have $z\le (p_1...p_j)^m\le k$. Hence, $z$ clearly has no prime factors more than $k$, and thus so does $B(n)$. To finish, use strong induction. Suppose $B(n)$ loses, then there exists $a<B(n)$ such that $\gcd(a, B(n))=1$ and $a$ wins, so by inductive hypothesis, $B(a)$ wins as well. Also $\gcd(B(a), B(n))=1$, so $\gcd(B(a), n)=1$, meaning that $n$ loses because we already know $B(a)<n$ wins. Next suppose $n$ loses, then there exist $a<B(n)$ such that $\gcd(a, B(n))=1$ and $a$ wins. This means $\gcd(B(a), B(n))=1$ as well, and by inductive hypothesis $B(a)$ wins (since $a$ wins). But note that if $B(n)>B(a)$ then $B(n)$ loses, and if $B(n)<B(a)$ then $B(n)$ also loses, so either way $B(n)$ loses. Hence, we have $n$ loses iff $B(n)$ loses, and we are done.

I don't seem to be using induction; is this correct? Call a number winning if Ana can win given that number initially. Call a position losing if no matter what Ana does, she loses; a losing position is equivalent to a good position. Note that a number $N$ is winning iff there exists some $k\le \ell < N$ coprime to $N$ with $\ell$ losing. And $N$ is losing iff all coprime to $N$ less than $N$ are winning. We want to show that the condition for $N$ winning depends only on the set of prime factors of $N$ at most $k$. Say the primes $p_1,\ldots,p_r \le k$ divide $N$. Let $f(N)$ be the smallest number at least $k$ which is divisible by all of $p_1,\ldots,p_r$. Clearly $f(N)\le N$. Lemma: The prime factors of $f(N)$ are all at most $k$. Proof: Similar to above proofs. Just exponentiate $p_1\cdots p_r$ till you get something that works; this shows that $f(N)/(p_1\cdots p_r)$ is at most $k$, hence it cannot have prime factors more than $k$. $\square$ Now we will show that $N$ is winning iff $f(N)$ is winning; this would finish. Supose $N$ is winning. Then there exists an $\ell<N$ coprime to $N$, and hence also coprime to $f(N)$, with $\ell$ losing. If $f(N) > \ell$, then $f(N)$ is winning again by the definition of winning, so we're done. If $f(N) < \ell$, then since $f(N)$ is coprime to $\ell$ with $\ell$ losing, $f(N)$ is winning (since $\ell$ losing implies all coprime to $\ell$ less than $\ell$ are winning). Suppose $f(N)$ is winning. Then there exists an $\ell<f(N)$ coprime to $f(N)$ with $\ell$ losing. We want to show $N$ is winning, i.e. there exists an $\ell'<N$ coprime to $N$ with $\ell'$ losing. But by the lemma, all prime factors of $\ell$ are at most $k$, so since $\ell$ is coprime to $f(N)$, $\ell'=\ell$ works. (There are no other prime factors of $\ell$ we have to worry about that might also divide $N$.) This completes the proof.

Define the root of a number to be the product of its distinct prime factors $\le k$, and its primitive root to be the smallest number $\ge k$ which shares its root. It is not hard to see that primitive roots have no prime factors larger than $k$. So, if a player can choose a number $c$ on their turn, they can also choose $c$'s primitive root. Now, we will show with induction that the goodness of $n$ is equal to that of its primitive root. The base case $n=k$ is clear, since its primitive root is $k$. Now, if $n$ has primitive root $r$ which is bad, note that from $r$, a player can choose a good number $g$. However, by inductive hypothesis, $g$'s primitive root is also good, and can be achieved by $n$ since its prime factors are all distinct from $n$'s. Hence, $n$ is bad. On the other hand, if $r$ is good, note that if Ana chooses $n'>r$, Banana will choose $r$ and win, and if she chooses $n'<r$, then the same number could've been achieved if $n=r$, and it must be a bad position by the goodness of $r$. Hence, $n$ is good, and the induction is complete.

$\mathrm{ }$

Looks like I somehow have skipped this problem before

redacted

Solved with nukelauncher. For all \(n\), let \[\operatorname{sad}(n)=\prod_{\substack{p\mid n\\ p\le k}}p,\]and let \(\operatorname{mad}(n)\) be the least integer \(m\ge k\) with \(\operatorname{sad}(m)=\operatorname{sad}(n)\). Claim: Let \(m=\operatorname{mad}(n)\). Then \(\operatorname{rad}(m)=\operatorname{sad}(m)\). Proof. Observe that \(m\le k\operatorname{sad}(n)\), since we can take \(\operatorname{sad}(n)\) and keep on multiplying by primes that divide \(\operatorname{sad}(n)\) until the product is at least \(k\). Then since \(\operatorname{sad}(n)\) divides \(m\) and \(m/\operatorname{sad}(n)\le k\), its prime factors are all at most \(k\), and therefore all its prime divisors also divide \(\operatorname{sad}(n)\). \(\blacksquare\) Now, we will show that \(n\) is bad if and only if \(\operatorname{mad}(n)\) is bad by induction on \(n\). Let \(n'\) be Ana's choice when \(\operatorname{mad}(n)\) is on the board, and let \(n''\) be Ana's choice when \(n\) is on the board. If \(\operatorname{mad}(n)\) is bad by Ana choosing \(n'\), then \(n\) is also bad by Ana choosing \(n''=\operatorname{mad}(n')\). If \(\operatorname{mad}(n)\) is good, i.e.\ all relatively prime numbers \(n'<\operatorname{mad}(n)\) are bad, then \(n\) is also good since: if Ana chooses \(n''<\operatorname{sad}(n)\), then \(n''\) must be bad; and if Ana chooses \(n''>\operatorname{mad}(n)\), then Banana can choose \(\operatorname{mad}(n)\), which is good. The problem follows.

Bad writeup, but nice problem. Let $\{a_i\}_{i\ge 1}$ be the sequence of good numbers in order. It is easy to show (by the definition of the game) that $a_1=k$ and for all $m,$ $a_m$ is the smallest positive integer greater than $a_{m-1}$ such that $\gcd(a_m,a_i)>1$ for all $i<m.$ Call a number $\emph{tall}$ if all its prime factors are greater than $k,$ and $\emph{tiny}$ if all its prime factors are at most $k.$ Additionally, let the $\emph{base}$ of a number be its largest tiny factor. The key claim is the following. $\textbf{Claim: }$ For all positive integers $i,j,$ $\gcd(a_i,a_j)$ is not tall. $\emph{Proof: }$ Suppose FTSOC there exists a pair $i<j$ such that $\gcd(a_i,a_j)$ is tall, and let $a_t=M$ be the smallest value of $a_i$ among all such pairs. Let $m$ be the base of $M.$ Choose $c<k$ such that $\text{rad}(c)\mid\text{rad}(m)$ and $c$ is as close to $k$ as possible. By construction, $cm$ is tiny and $k\le cm<M.$ By the minimality of $M,$ we know $M$ shares a tiny prime factor with each earlier member of the sequence. But since $cm$ has exactly the same tiny prime factors as $M,$ we know $cm$ also shares a tiny prime factor with $a_i$ for all $i<t$. Therefore, $cm$ must in fact equal $a_i$ for some $i<t.$ This implies that for all $j>t,$ $a_j$ shares a tiny prime factor with $cm$ and thus $M.$ This contradicts our original assumption, so we are done. $\blacksquare$ Now let $u$ be the base of $n$ and let $v$ be the base of $n'.$ Remark that $\text{rad}(u)=\text{rad}(v).$ The above claim implies that every two members of the sequence share a tiny prime factor. Therefore, if $n$ is in the sequence, then $u$ shares a prime factor with all other members of the sequence, so $v$ does as well. This implies that $n'$ is in the sequence eventually. By symmetry, the other direction holds as well.

If $k = p^a$ it is trivial the winning set for $B$ are multiples of $p$. Otherwise, we call the radical (set) of a winning number for $B$ genuine if no smaller $n$ is both winning for $B$ and has radical which is a subset of the aforementioned radical. Thus notice any two genuine radicals have a nonempty intersection. Now notice if some $p > k$ is in a genuine radical, then it cannot be alone in the set, so let another prime in the set be $p'$. Then there is a power of $p'$ between $k$ and $p'k < p'p$, so that power must be a genuine radical, which is a contradiction by definition. Thus all genuine radicals have only primes at most $k$. Now notice any number is winning for $B$ if and only if its radical is disjoint with all genuine radicals, so we are done as the question desires.

A simple proof: We'll first prove that a good number has a part that is good, (by part i mean power of a prime), note that the power of that prime that are greater than k would be all good, it can be proved that good * any kind of number is a good number, if two bad numbers multiply to a good number that's a contradiction but since both m and n are co prime to a good number, you can make their product co prime with the good number which would be a contradiction. Now note that only one of the primes that divide k can have their power be good and they have to be \leq k, now if $n$ is good, it implies that a good prime also divides $n'$ which implies that n' is also good. So, we're done.

Write $x \iff y$ if $x$ good implies $y$ good and vice versa. Obviously, $k$ is bad, hence every number coprime to $k$ is good, and every multiple of $k$ is also bad. The problem is mostly solved with two lemmas: Lemma 1: If $ap \geq k$, then $ap \iff ap^2$, where $p$ is any prime. Proof: If $ap$ is good, then there exists some integer $m \in [k,ap)$ coprime to $ap$ that is bad. But then we can also move from $ap^2$ to $m$, so $ap^2$ is good as well. If $ap$ is bad, then every integer in $[k,ap)$ coprime to $ap$ is good. Therefore, if $ap^2$ is good, then some integer $m$ coprime to $ap^2$ (and therefore $ap$) in $(ap,ap^2)$ is bad. But $m$ is actually good, since we can move from $m$ to $ap$ which is bad: contradiction.This implies the result. $\blacksquare$ Lemma 2: Let $p>k$ be a prime. Then for all $p \nmid a$ and $a \geq k$, we have $a \iff ap$. Proof: We will induct on $a$, with the base case of $a=k$ being clear, since both $k$ and $kp$ are bad. In general, if $a$ is bad, then similar reasoning to before implies that $ap$ is bad as well. If $a$ is good, but some integer in $[k,a)$ coprime to $ap$ is bad, then similar reasoning to before implies that $ap$ is good as well. Therefore we only have to consider the case where $a$ is good, and some integer $[k,a)$ coprime to $a$ but not to $ap$ (i.e. divisible by $p$) is bad. Let this integer be $mp$. Clearly $m$ has some prime divisor $q \leq k$, since otherwise it is coprime with $k$ and therefore good, ruining our assumption. By lemma 1, we have the "chain" of iffs: $$mp \iff mpq \iff mpq^2 \iff \cdots.$$Take the least $t \geq 0$ such that $mq^t \geq k$. I will prove that $mq^t\leq a \implies mpq^t\leq ap$. If $t=0$ then this is obvious. Otherwise, if $t \geq 1$, we must have $mq^{t-1} \leq k$. But then $mq^t \leq qk \leq mk \leq mp \leq a$, as desired. Therefore by inductive hypothesis, $mq^t \iff mpq^t$, so $mq^t \in [k,a)$ is bad as well. Furthermore, it is coprime to $a$ (but not necessarily $ap$, since we could have $p \mid m$), and its $p$-adic valuation is one less than that of $mp$. Therefore, repeatedly applying this process, we can eventually find some bad integer in $[k,a)$ coprime to $a$ and not divisible by $p$, hence it is coprime to $ap$ as well and thus $ap$ is good, since we can move to this integer. $\blacksquare$ To finish the problem, for any $(n,n')$ take an integer $N$ such that and $n, n' \mid N$ and for any prime $p<k$, we have $(p \mid n \iff p \mid n') \iff p \mid N$. Then by repeatedly applying the first two lemmas, we can find that $n \iff N$ and $n' \iff N$, hence $n \iff n'$ as desired. $\blacksquare$

really nice

What in the world. This is an amazing problem, like genuinely one of the best I've done. First we set up some notation. Denote by $T(n)$ the set of prime factors $p \leq k$ that divide some $n$. For each possible subset $S$ of $p \leq k$, denote $M(S)$ as the smallest $n > k$ such that $T(n) = S$. Define $n$ to be magical if it winning for Banana. Then we wish to show that the set $T(n)$ of any initial $n$ determines whether that $n$ is magical or not. Consider all possible subsets of primes less or equal to $k$, and denote them by $S_a$, $S_b$ and so on. Note that if there are $r$ primes less than or equal to $k$, then there are exactly $2^r$ subsets. Order the subsets in increasing order of their $M(S)$ value, \begin{align*} \{ S_1, S_2, \dots, S_{2^r}\} \end{align*}Namely $S_i$ is placed before $S_j$ if and only if $M(S_i) < M(S_j)$. Define $M(S_i) = c_i$. Consider the values, \begin{align*} \{c_1, c_2, \dots, c_{2^r} \} \end{align*}Now assign each $S_i$ a type, $1$ or $2$ depending on whether the first player wins, or the second player wins when $n = c_i$, respectively. To assign these ``types" consider the following algorithm. Begin with $c_1$, and note that by definition $c_1 = k$, and thus $S_1$ is type $2$. Now assume we have assigned values to all $S_i$ till some $S_q$ and we wish to assign $S_{q+1}$ a type. To assign its type, Consider the respective subset of $c_{q+1}$, namely $S_{q+1}$ and all subsets with lower $M(\cdot)$ value, namely $S_1$, $S_2$, and so on till, $S_q$. Refer to a good subset $S_i$ for some $i \leq q$ as a subset satisfying $S_i \cap S_{q+1} = \emptyset$. Over all good subsets, if there exists some type $2$ subset, assign $S_{q+1}$ as type $1$. Else if there exist only type $1$ subsets, assign $S_{q+1}$ as a type $2$ subset. Now this algorithm has defined whether each $S_i$ is winning or losing, by deciding whether $c_i$ is winning or losing. Thus it suffices to show that this algorithm works. Namely for any $n$ with $T(n) = S_i$, if $S_i$ is type $1$ Ana will win, else Banana will win. Thus we present the killing claim: Denote by $d$ the smallest divisor of $k$, noting that $d$ is prime. Claim: The prime $d$ appears in some subset $S_i$ if and only if $S_i$ is a type $2$ subset. Equivalently all magical $n$ are divisible by $d$, whereas all non-magical $n$ aren't. Proof. Assume for the sake of contradiction some subset $S_i$ is type $2$, yet does not contain $d$. Then we first show that $M(S_i) > k + d$. Indeed assume again for the sake of contradiction that $M(S_i) \in [k, k + d - 1]$. However it is easy to note that \[\gcd(k, k + d - 1) = \gcd(k, d - 1) = 1\]Then we must have that either $M(S_i) = k + d$, implying that $d \in S_i$ or $M(S_i) > k + d$. The first clearly fails as it would imply that $d \mid M(S_i) \iff d \in S_i$, which goes against our original assumption. Then we must have $M(S_i) > k + d$. Then let Ana make the reduction $M(S_i) \mapsto k + d$ on her turn. We claim this is a losing position for Banana, and hence $M(S_i)$ is type $1$. Indeed note that Banana may not make the reduction $k + d \mapsto k$ as $\gcd(k + d, k) = k > 1$. Thus he makes the reduction $k + d \mapsto k + d - r$ for some $r < d$. However then on Ana's next turn she may make the reduction $k + d - r \mapsto k$, which shows that $S_i$ is a type $1$ subset, contradiction. Now we show that if some subset $S_i$ is type $1$ it cannot contain $d$. Indeed if it did then Ana would be forced to reduce to some lower type $1$ subset as all type $2$ subsets contain the prime $d$. However then Banana has a winning strategy and thus $S_i$ must be a type $2$ subset, contradiction. $\square$ This sets up the base cases for whether an $n$ is magical, depending on its type, for all $n \in [k, Q]$ where $Q$ is the product of all primes less than $k$. Now we claim that this finishes. Consider inducting. Note that for any $n$ with a type $2$ subset $T(n) = S_i$, Ana must reduce $n \mapsto n'$ where $T(n') = S_j$ is a type $1$ subset, as all $n$ with a type $2$ subset have a common divisor, namely $d$. However then Banana will have a winning strategy by downwards induction. Namely as he is the first player in the game starting from $n' < n$, which has a type $1$ subset, he has a winning strategy. Alternatively, for any $n > k + d$ with a type $1$ subset, Ana may reduce $n \mapsto k + d$ which is a type $2$ subset. Otherwise for any $k < n < k + d$ Ana may reduce $n \mapsto k$. However then Banana is guaranteed to lose from our induction, as he is playing first on a type $2$ subset. This finishes the problem as by induction all $n$ with type $1$ subsets are winning for Ana, and all $n$ with type $2$ subsets are winning for Banana. Remarks: My brain is fried currently, will probably add these later.

Assume WLOG that $n' > n$. Now if, $n'$ is good, that means all positions that $n'$ can go to are winning. However, if $n$ can go to some position, so can $n'$. So, all positions that $n$ can go to are also winning. So, if $n'$ is good so is $n$. So, for the problem statement to be false, we must have $n'$ is bad and $n$ is good. This means that $n'$ can go to some $r$ such that $n' > r > n$ and $r$ is a losing position. But, $\gcd(r, n') = 1$ so $\gcd(r, n) = 1$, and thus we can take $r$ to $n$ and since $n$ is good, $n$ is a losing position, contradicting the fact that $r$ was losing.

I am so confused, my solution feels so simple: Consider the smallest integer, say $m$, that has the same prime factors as $n$ and is $\ge k$. If $m$ is a winning position, say in the winning strategy, the person moves to another number coprime to $m$. This number will be coprime to $n$ as well so the person can move to the same number, proving $n$ is winning as well. Similarly, if $m$ is losing, after moving to another integer (say $a$) from $n$, the next person can move from $a$ to $m$ if $a > m$ or the next person can simply mirror the strategy for $m$ is $a < m$.

Solution path only because I am dying. Firstly, show that we need only consider the primes $\leq k$ because we can replace any primes $>k$ with those less than(needs proving). Secondly to show that the problem is true we show that $n$ wins if and only if $a$ wins for Beto, where $a$ is the minimum number $\geq k$ where all primes that divide $a$ if and only if they divide $n.$ This is casework which needs proving$.\blacksquare$

Solution path only because I am dying. Firstly, show that we need only consider the primes $\leq k$ because we can replace any primes $>k$ with those less than(needs proving). Secondly to show that the problem is true we show that $n$ wins if and only if $a$ wins for Beto, where $a$ is the minimum number $\geq k$ where all primes that divide $a$ if and only if they divide $n.$ This is casework which needs proving$.\blacksquare$