You may also like

problem icon

DOTS Division

Take any pair of two digit numbers x=ab and y=cd where, without loss of generality, ab > cd . Form two 4 digit numbers r=abcd and s=cdab and calculate: {r^2 - s^2} /{x^2 - y^2}.

problem icon

Common Divisor

Find the largest integer which divides every member of the following sequence: 1^5-1, 2^5-2, 3^5-3, ... n^5-n.

problem icon

Hypotenuse Lattice Points

The triangle OMN has vertices on the axes with whole number co-ordinates. How many points with whole number coordinates are there on the hypotenuse MN?

Zodiac

Stage: 4 Challenge Level: Challenge Level:3 Challenge Level:3 Challenge Level:3

Siobhan has sent us her work on this problem. Well done, Siobhan!

The problem says that $t_8^2$ has two cycles, whereas $t_8^3$ has one cycle and $t_8^4$ has four cycles. I noticed that in each of these examples the number of cycles in $t_8^k$ is the highest common factor of $8$ and $k$. I decided to test this on shuffles of lengths $9$ and $10$.
Powers of the cycle (1 2 3 4 5 6 7 8 9)
Powers of the cycle (1 2 3 4 5 6 7 8 9 10)
Here are the tables I got:

$$\begin{eqnarray} t_9^0 & = & (1)\\ t_9^1 & = & (1 2 3 4 5 6 7 8 9)\\ t_9^2 & = & (1 3 5 7 9 2 4 6 8)\\ t_9^3 & = & (1 4 7)(2 5 8)(3 6 9)\\ t_9^4 & = & (1 5 9 4 8 3 7 2 6)\\ t_9^5 & = & (1 6 2 7 3 8 4 9 5)\\ t_9^6 & = & (1 7 4)(2 8 5)(3 9 6)\\ t_9^7 & = & (1 8 6 4 2 9 7 5 3)\\ t_9^8 & = & (1 9 8 7 6 5 4 3 2)\\ \end{eqnarray}$$

$$\begin{eqnarray} t_{10}^0 & = & (1)\\ t_{10}^1 & = & (1 2 3 4 5 6 7 8 9 10)\\ t_{10}^2 & = & (1 3 5 7 9)(2 4 6 8 10)\\ t_{10}^3 & = & (1 4 7 10 3 6 9 2 5 8)\\ t_{10}^4 & = & (1 5 9 3 7)(2 6 10 4 8)\\ t_{10}^5 & = & (1 6)(2 7)(3 8)(4 9)(5 10)\\ t_{10}^6 & = & (1 7 3 9 5)(2 8 4 10 6)\\ t_{10}^7 & = & (1 8 5 2 9 6 3 10 7 4)\\ t_{10}^8 & = & (1 9 7 5 3)(2 10 8 6 4)\\ t_{10}^9 & = & (1 10 9 8 7 6 5 4 3 2) \end{eqnarray}$$

This agrees with my prediction: the number of cycles in $t_n^k$ is the highest common factor of $k$ and $n$. (Of course, $(1)$ really means $(1)(2)(3)\ldots (n)$ so has $n$ cycles.)

In $t_n^1$, consecutive numbers are $1$ apart ($1$, $2$, $3$, \ldots, $n$). When we do this twice, they are two apart, because, for example, $1$ goes to $2$ which goes to $3$ so $1$ goes to $3$. When we work out $t_n^3$, the numbers that were $2$ apart become $3$ apart, because, for example, $1$ goes to $3$ which goes to $4$ so $1$ goes to $4$. It's quite easy to see that this will keep happening, because each time we apply $t_n$ we move the numbers $1$ further apart. So in $t_n^k$ the numbers are $k$ apart. But now we can see that the number of cycles we get will be the highest common factor of $k$ and $n$; this is like the Stars problem mentioned in this question.