An economist and a statistician play a game on a calculator which does only one operation. The calculator displays only positive integers and it is used in the following way: Denote by $n$ an integer that is shown on the calculator. A person types an integer, $m$, chosen from the set $\{ 1, 2, . . . , 99 \}$ of the first $99$ positive integers, and if $m\%$ of the number $n$ is again a positive integer, then the calculator displays $m\%$ of $n$. Otherwise, the calculator shows an error message and this operation is not allowed. The game consists of doing alternatively these operations and the player that cannot do the operation looses. How many numbers from $\{1, 2, . . . , 2019\}$ guarantee the winning strategy for the statistician, who plays second? For example, if the calculator displays $1200$, the economist can type $50$, giving the number $600$ on the calculator, then the statistician can type $25$ giving the number $150$. Now, for instance, the economist cannot type $75$ as $75\%$ of $150$ is not a positive integer, but can choose $40$ and the game continues until one of them cannot type an allowed number Proposed by Serbia
Problem
Source:
Tags: combinatorics
cadaeibf
12.09.2020 14:48
The answer is 951 . To see this we note that we only care about the exponent fo 2 and 5 in n. Of course the one who wins is the first one who gets to a number $n_0$ with $(n_0;10)=1$. Also the moves possible in terms of the two exponents of 2 and 5 are $(a,b)$ goes to one of these $(a-1;b),(a-2,b),(a,b-1),(a-1,b-1),(a-2,b-1),(a,b-2),(a-1,b-2),(a-2,b-2)$(because we're always dividing by a divisor of 100 bigger than 1). We claim the second player wins if the starting is of the form $n=2^{3k}5^{3l}t$ with $(t;10)=1$. If the starting number is not of that form, the first player easily reconducts the game to a starting number of that kind, and so we only need to check the strategy for the second player. His strategy is to always reconduct himself to another number of the same form. If the first player performs a move of type $(-a,-b)$ he does the move $(+a,+b)$ (numbers taken mod 3). In this way at the end the second player will end with a number coprime to 10, to which the first player can'tl respond. Therefore, we just need to count the numbers of the form $n=8^k125^lt$. After a quick calculation, we should have that the final number is 951