\section*{5. For ALL APPLICANTS.}
Alice is participating in a TV game show where $n$ distinct items are placed behind $n$ closed doors. The game proceeds as follows. Alice picks a door $i$ which is opened and the item behind it is revealed. Then the door is shut again and the host secretly swaps the item behind door $i$ with the item behind one of the neighbouring doors, $i - 1$ or $i + 1$. If Alice picks door 1, the host has to then swap the item with the one behind door 2; similarly, if Alice picks door $n$, the host has to swap the item with the one behind door $n - 1$. Alice then gets to pick any door again, and the process repeats for a certain fixed number of rounds. At the end of the game, Alice wins all the items that were revealed to her.

As a concrete example, suppose $n = 3$, and if the original items behind the three doors were ( $a _ { 1 } , a _ { 2 } , a _ { 3 }$ ), then if first Alice picks door 2 , the arrangement after the host has swapped items could be either $\left( a _ { 2 } , a _ { 1 } , a _ { 3 } \right)$ or $\left( a _ { 1 } , a _ { 3 } , a _ { 2 } \right)$. So if Alice was allowed to pick twice, had she chosen door 2 followed by door 1, in the former case she would only get the item $a _ { 2 }$, whereas in the latter she would get items $a _ { 2 }$ and $a _ { 1 }$. Alice's aim is to find a sequence of door choices that guarantee her winning a large number of items, no matter how the swaps were performed.\\
(i) For $n = 13$, give an increasing sequence of length 7 of distinct doors that Alice can pick that guarantees she wins 7 items.\\
(ii) For any $n$ of the form $2 k + 1$, give a strategy to pick an increasing sequence of $k + 1$ distinct doors that Alice can use to guarantee that she wins $k + 1$ items. Briefly justify your answer.\\
(iii) For $n = 13$, give a sequence of length 10 of doors that Alice can pick that guarantees she wins 10 items.\\
(iv) For any $n$ of the form $3 k + 1$, give a strategy to pick a sequence of $2 k + 2$ doors that Alice can use to guarantee that she wins $2 k + 2$ items. Briefly justify your answer.\\
(v) (a) For $n = 3$, give a sequence of length 3 of doors that Alice can pick that guarantees she wins all 3 items.\\
(b) For $n = 5$, give a sequence of length 5 of doors that Alice can pick that guarantees she wins all 5 items.\\
(vi) For $n = 13$, give a sequence of length 11 of doors that Alice can pick that guarantees she wins 11 items.\\
(vii) For any $n$ of the form $4 k + 1$, give a strategy to pick a sequence of $3 k + 2$ doors that Alice can use to guarantee that she wins $3 k + 2$ items. Briefly justify your answer.\\
(viii) For $n = 6$, is there a sequence of any length of doors that Alice can choose that will guarantee that she wins all 6 items? Justify your answer.



This page has been intentionally left blank