There are $n$ people in line, counting $1,2,\cdots, n$ from left to right, those who count odd numbers quit the line, the remaining people press 1,2 from right to left, and count off again, those who count odd numbers quit the line, and then the remaining people count off again from left to right$\cdots$ Keep doing that until only one person is in the line. $f(n)$ is the number of the last person left at the first count. Find the expression for $f(n)$ and find the value of $f(2022)$
Problem
Source: 2022 China Southeast Grade11 P3
Tags: combinatorics
a22886
02.08.2022 11:38
There are obvious recurrence relations $f(2k+1)=f(2k)$ and $f(2k)=2k+2-2f(k)$ If we let $g(k)=f(k)-\frac23$ then $$g(4k+3)=g(4k+2)=4g(k)+2$$$$g(4k+1)=g(4k)=4g(k)$$Now we let $n=\sum_{i=0}^{p-1}u_i4^i$, so $g(n)=4^{p-1}g(u_{p-1})+\sum_{i=0}^{p-2} h(u_i)4^i$ where $h(0)=h(1)=0,h(2)=h(3)=2$ The first values of $g$ are $g(1)=\frac13,g(2)=g(3)=\frac43$ And it will be "nice" to write $g(x)=\frac13+[\frac{2+x}4]~(x=1,2,3)$ and $h(x)=2[\frac{2+x}4]~(x=1,2,3,4)$ to get an expression for $f$ Note for $0\le i\le p-2, u_p=[\frac n{4^i}]-4[\frac n{4^{i+1}}]$ If we write it down we get $$f(n)=\frac23+4^{[\log_4{n}]}\left(\frac13+\left[\frac{2+\left[\frac n{4^{[\log_4 n]}}\right]}4\right]\right)+\sum_{i=0}^{[\log_4 n]-1}2^{2i+1}\left[\frac{2+[\frac{n}{4^i}]-4[\frac{n}{4^{i+1}}]}4\right]$$
$$2022=(1\textcolor{red}{332} \textcolor{blue}{1} \textcolor{red}{2} )_4$$$$\downarrow$$$$g(2022)=(\text{'}\frac13 \text{'}\textcolor{red}{222} \textcolor{blue}0 \textcolor{red}{2} )_4$$
to get $f(2022)=1016$