2021 Pascal Problem 23

Suppose that k \ge 2 is a positive integer. An *in-shuffle* is performed on a list with 2k items to produce a new list of 2k items in the following way:

- The first k items from the original are placed in the odd positions of the new list in the same order as they appeared in the original list. - The remaining k items from the original are placed in the even positions of the new list, in the same order as they appeared in the original list.

For example, an in-shuffle performed on the list P\ Q\ R\ S\ T\ U gives the new list P\ S\ Q\ T\ R\ U. A second in-shuffle now gives the list P\ T\ S\ R\ Q\ U. Ping has a list of the 66 integers from 1 to 66, arranged in increasing order. He performs 1000 in-shuffles on this list, recording the new list each time. In how many of these 1001 lists is the number 47 in the 24th position?

\textbf{(A)}\ 90\quad \textbf{(B)}\ 71\quad \textbf{(C)}\ 83\quad \textbf{(D)}\ 72\quad \textbf{(E)}\ 84

If there are no answer choices shown, enter a numerical answer.

Full credit to this problem is given to the CEMC, you may view all Pascal contests here.