Kimia has a weird clock; the clock's second hand moves 34 or 47 seconds forward instead of each regular second, at random. As an example, if the clock displays the time as $\text{12:23:05}$, the following times could be displayed in this order: $$\text{12:23:39, 12:24:13, 12:25:00, 12:25:34, 12:26:21,\dots}$$Prove that the clock's second hand would eventually land on a perfect square.
Problem
Source: Iran MO second round 2024 P1
Tags: number theory, combinatorics
18.04.2024 21:49
19.04.2024 12:47
A solution I came up with during the exam: Let $x_1 = 2 , x_2 = 15$ and $x_n$ to be the remainder when $x_{n-1}+13$ is divided by $60$. Note that every integer between $0$ and $59$ is in the sequence because $gcd(13,60) = 1$ Now note that every time we go from $x_n$ to $x_{n-1}$ or $x_{n-2}$, so we will eventually reach $15$ or $2$ or land on a perfect square. If we reach $2$ on the next move we will either reach $49$ or $36$. If we reach $15$ on the next move we will reach $2$ or $49$. So the clock's hand will eventually land on a perfect square.
29.04.2024 21:57
Very Nice : The key observation is that $2\times 47\equiv 34 \pmod{60}$. This means that if we start at $x$ in a move we can move to $x+47$ or $x+2\times 47$. However notice that $49$ and $49+47\equiv 36$ are both perfect squares. Since $(47,60)=1$, Kimia must eventually land on one of those numbers.
01.07.2024 23:00
A graphical solution First take two rows of a grid. On the first, list the odd numbers $(mod 60)$ starting with $47$ and adding $34$ each time to get to the next number: This would look like: $$47,21,55,29,3,37,11,45,...,13 $$On the second row, list the even numbers $(mod60)$ starting with $0$ and adding $34$ each time to get to the next number: This would look like:$$0,34,8,42,19,50,24,58,32,...,26$$Also shift the numbers in such a way that $34$ is under $47$, and the rest follows. Note that each time we add $47$ twice to a number we have essentially just added $34$ to that number. (Since $47+47 \equiv 34(mod60)$) $\star$By construction we know that if a number on the bottom row is $k$ then the number exactly above that is $k+13$ $\star$ Now we interpret the behavior of the operation on this grid of numbers: Adding $34$ takes us one number to the right of the same row.(i.e. $34 \rightarrow 8$) Adding $47$ to a number on the bottom row takes us from the $i^{\text{th}}$ column to the $(i+1)^{\text{th}}$ column on the top row.(i.e. $34\rightarrow 21$) Adding $47$ to a number on the top row takes us from the $i^{\text{th}}$column to the $i^{\text{th}}$ column on the bottom row.(i.e $21\rightarrow 8$) It's also imortant to note that $13$ loops back to $0, 47$ and $26$ loops back to $0$ $\textcolor{blue}{Claim:}$ Doing an operation twice on this grid, gives us at least one of the numbers on the next column $\textcolor{blue}{Proof:}$ This follows from the fact that in each step we go right or right on the opposite row. Now note that $36,49$ are in different rows ; thus we will encounter one of them by taking the steps by the above claim. and we are done.