Two people, $A$ and $B$, play the following game: $A$ start choosing a positive integrer number and then, each player in it's turn, say a number due to the following rule: If the last number said was odd, the player add $7$ to this number; If the last number said was even, the player divide it by $2$. The winner is the player that repeats the first number said. Find all numbers that $A$ can choose in order to win. Justify your answer.
Problem
Source: Cono Sur 1991-problem 2
Tags: inequalities, number theory unsolved, number theory
ZetaX
29.05.2006 19:44
For starting values $>21$, this value is never reached again (proof by simple inequalities on the size of the number after two steps). So checking gives that only $1,2,4,7,8,14$ work.
DavidSummer
24.07.2022 05:31
. If the first number is 1: then the sequence is 1(A), 8(B), 4(A), 2(B), 1(A), A is the winner. . If the first number is 2: then the sequence is 2(A), 1(B), 8(A), 4(B), 2(A), A is the winner. . If the first number is 3: then the sequence is 3(A), 10(B), 5(A), 12(B), 6(A), 3(B), B is the winner. . If the first number is 4: the sequence is: 4(A), 2(B), 1(A), 8(B), 4(A), A is the winner. . If the first number is 5: the sequence is 5(A), 12(B), 6(A), 3(B), 10(A), 5(B), B is the winner. . If the first number is 6: the sequence is 6(A), 3(B), 10(A), 5(B), 12(A), 6(B), B is the winner. . If the first number is 7: the sequence is 7(A), 14(B), 7(A), A is the winner . If the first number > 7: In the sequence, after an odd, an even follows, so the sequence has the following form: (First number), E, ..., E, O_1, E, ... , E, O_2, E, ... , E, O_3, ... O_i > (O_i +7)/2 if only if O_i >7, then, If O_i >7, then O_(i+1) < O_i because O_(i+1) is less than or equal to (O_i +7)/2 < O_i. It's clear that if an even of the sequence is less than first number then the next term is also less than first number. So the first number won't be in the sequence a second time if all numbers of the sequence are > 7, then there exists a number N =< 7 in the sequence. In the first cases (where the first number was 1,2,3,4,5,6,7) we saw what numbers can follow in the sequence after N=< 7, so the first number can only be 8, 10, 12, 14 since these are the only numbers >7 that are after some number less than or equal to 7. *) the first number is 8: the sequence is: 8(A), 4(B), 2(A), 1(B), 8(A), A is the winner *) the first number is 10: the sequence is: 10(A), 5(B), 12(A), 6(B), 3(A), 10(B), B is the winner *) the first number is 12: the secuence is: 12(A), 6(B), 3(A), 10(B), 5(A), 12(B), B is the winner *) the first number is 14: the sequence is: 14(A), 7(B), 14(A), A is the winner So A will win if only if A chooses 1, 2, 4, 7, 8 or 14.