Natural numbers $1,2,...,500$ are written on a blackboard. Two players $A$ and $B$ consecutively make moves, $A$ starts. Each move a player chooses two numbers $n$ and $2n$ and erases them from the blackboard. If a player cannot perform a valid move, he loses. Which player can guarantee a win?
Problem
Source: Latvia TST for Baltic Way 2020 P5
Tags: combinatorics
SomeonecoolLovesMaths
15.07.2024 20:00
bump....
crezk
15.07.2024 23:51
Let $S_1=\{1,3,5,7,9,..,125,...249\}$ and construct discrete trees and $T_i$ be tree for each $i\in S_1$ such that for every number $i, i$ is the first vertex of tree $T_i$ and For the largest number $j$ that satisfies the inequality $i*2^j\leq 500$, the number $i*2^j$ is the last vertex of the $T_i$ tree.Let $T=\{T_i | i\in S_1\}$.Now let's define the operation to delete two consecutive vertices on any $T_i$ tree.Let's make an observation on a tree. Let $v_n$ be the leaf of any tree and let's take the path $v_n v_a v_b$.If a player chooses $v_n$ and $v_a$, he has to delete the edges $(v_n v_a)$ and $(v_av_b)$, in which case the number of edges of the tree decreases by $2$. If a player chooses $v_a v_b$, he has to delete the edges that are $(v_n v_a), (v_a v_b)$ and $(v_jv_{j+1})$, so in this case the number of edges decreases by $3$.We also know that for discrete trees, there are trees consisting of (represent (number of trees $\rightarrow$ number of edges of these trees)) $1\rightarrow 8$ edges, $1 \rightarrow 7$ edges, $4 \rightarrow 5$ edges, $8 \rightarrow 4$ edges, $15\rightarrow 3$ edges,$ 32 \rightarrow 2$ edges and $62\rightarrow 1$ edges.Also we can say that For trees consisting of $1,2,3,6,7,8$ edges, the first player to make a move for each tree in the game to be played on these trees wins this tree (I am not talking about the first player in the game in general, but the first player to start the game specifically for these trees).For trees consisting of $4$ or $5$ edges, the first player to start the game loses the tree.