Discrete math recurrence relations

[aliciac]

Hi !!! I have no idea how to do this question help please !!
Sylvester caught n mice which he arranged in a circle and numbered them 1,2,...,n in clockwise order. Starting with mouse number 1, Sylvester went around the circle in clockwise order, skipping over one mouse and eating the next one. He went round and round by the same rule, until only one mouse was left. This lucky mouse was then set free. Denote f(n) as the number assigned to the lucky mouse initially. Now f(1)=1, f(2)=1, f(3)=3, f(4)=1, and f(5)=3
a) Express f(2n) and f(2n+1) in terms of f(n)
b) given that f(530)=37, determine f(2121).

Thank you !!

 

[daon2]

Hi !!! I have no idea how to do this question help please !!
Sylvester caught n mice which he arranged in a circle and numbered them 1,2,...,n in clockwise order. Starting with mouse number 1, Sylvester went around the circle in clockwise order, skipping over one mouse and eating the next one. He went round and round by the same rule, until only one mouse was left. This lucky mouse was then set free. Denote f(n) as the number assigned to the lucky mouse initially. Now f(1)=1, f(2)=1, f(3)=3, f(4)=1, and f(5)=3
a) Express f(2n) and f(2n+1) in terms of f(n)
b) given that f(530)=37, determine f(2121).

Thank you !!

This was a fun problem, and I'll show you how to do part of (a). If you would like additional help, please make a solid attempt first.

We start with 1,2,3,4,5,...2n-3,2n-2, 2n-1, 2n

Then the even mice get eaten and we are left with: 1,3,5,...,2n-3, 2n-1

There are exactly n mice, and we can put them into a 1-1 correspondence with 1,...,n.

\(\displaystyle \begin{array}
\, 1 & 3 & 5 & 7 & \cdots & 2n-3 & 2n-1\\
1 & 2 & 3 & 4 & \cdots & n-1 & n
\end{array}\)

That is, we send k to 2k-1. Call this function \(\displaystyle g(k)\).

Then the value of \(\displaystyle f(n)\) is the result of playing the game on the values in row 2. It is the same as playing the game on the upper row even though the "names" of the mice have changed. It is the position that is important. So if the value of \(\displaystyle f(n)\) is \(\displaystyle N\), that means we ended up on the \(\displaystyle N^{th}\) position in the lower row. So the \(\displaystyle N^{th}\) position of the upper row is the winner for the 2n game, and that is \(\displaystyle g(N)=2N-1\). By definition, \(\displaystyle f(n)=N\) and by construction \(\displaystyle f(2n)=g(N) =2f(n)-1\)