Two players are playing game. Players alternately write down one natural number greater than $1$, but it is not allowed to write linear combination previously written numbers with nonnegative integer coefficients. Player lose a game if he can't write a new number. Does any of players can have wiining strategy, if yes, then which one of them? Journal "Kvant" / Aleksandar Ilic
Problem
Source:
Tags: combinatorics
11.01.2017 18:25
Any solution?
11.01.2017 20:30
OMO Fall 2015 Problem #20 was an extended version of this problem. Problems pdf Solutions pdf
14.10.2024 13:11
This is also 2023 PKU Autumn Camp T5(first problem of that day), many people failed solving it. Say Alice is first and Bob is second, then Alice has a winning strategy in the game. Alice starts by writing $5.$ If Bob writes $y,$ Alice then writes $4y-5$. Suppose Bob now has a winning strategy. Let $x$ be the number Bob writes. Then by mcnugget theorem $x < 4y - 5$ and $x$ cannot be expressed linearly using 5 and $y,$ $4y - 5 - x$ can be expressed linearly using $5$ and $y$. That is, there exist $u, v$ such that $4y - 5 - x = 5u + yv$. This implies that $4y - 5$ can be expressed linearly using $x$, $5,$ and $y$. However, instead of writing $4y - 5,$ Alice can write $x$ in second round. This means now Alice have the winning, contradiction! Therefore, Alice has a winning strategy.$\Box$