Ireland

Suppose a list $L=(n_i{)}_{i=1}^N$ is made up only of numbers selected from the (possibly much shorter) list of distinct numbers $(m_i{)}_{i=1}^k$, and that the products $n_i{n}_{i+1}$, $1\le i\le 2010$, are all distinct. We write down the indices of the numbers $m_i$ occurring in $L$ as another list $M$ also of length $N$, e.g. if $L$ begins $m_3,m_7,m_1,m_9,m_7,\dots$, then $M$ begins $3,7,1,9,7,\dots$. If $n_i=m_a$ and $n_{i+1}=m_b$, the product $n_i{n}_{i+1}$ is determined by the set $\{a,b\}$. Hence, any two (not necessarily distinct) numbers $a,b$ from $\{1,2,\dots ,k\}$ can appear as neighbours in the list $M$ at most once. As $M$ contains $2011$ elements, there must exist at least $2010$ different subsets of $\{1,2,\dots ,k\}$ with one or two elements. Note that, by usual conventions of set theory, $\{a,a\}=\{a\}$ contains only one element. The number of such subsets is equal to $k(k+1)/2$ and so we need to have $k(k+1)/2\ge 2010$, i.e. $k\ge 63$. That $k=63$ is indeed sufficient follows from the construction of a sequence $M$ given below. We will in fact construct for each odd number $k\ge 3$ a 'cycle' of numbers such that each subset of $\{1,2,\dots ,k\}$ with one or two elements appears exactly once as a set of neighbours in the cycle. A 'cycle' of numbers is simply a list in which the first and last element coincide. Two such 'cycles' of length $T+1$ are said to be equivalent iff we obtain the same result, up to rotation, if their numbers are cyclically written at the vertices of a regular $T$-gon, whereby the first and last element of the list are written on the same vertex. To prove the existence of such a cycle, we first form the set $\mathcal{T}$ of all subsets of $\{1,2,\dots ,k\}$ with one or two elements. Note that each number appears $k-1$ times in a two-element subset and once in a singleton. We start the sequence with $1,2,3,\dots ,k$ and remove from $\mathcal{T}$ the sets $\{1,2\},\{2,3\},\dots ,\{k-1,k\}$ which appear as neighbours already. We repeatedly do now the following: If $a$ is the last element of our list and there is a set in $\mathcal{T}$ which contains $a$, we pick such a set, remove it from $\mathcal{T}$ and append $a$ (if the set was a singleton) or the second element of this set (if it was a two-element set) to the list. Because $k-1$ is even, if $\mathcal{T}$ is not empty but does not contain a set which contains the last element of our list, then the last element of our list must coincide with the first element of our list, i.e. the list is a cycle. In this case, we replace it by an equivalent cycle which has an element as its first and last element which appears in one of the sets in $\mathcal{T}$. This is possible because we started our list in such a way that it contains all numbers $1,\dots ,k$ at least once. After replacing the cycle by an appropriate equivalent one, we continue as above appending elements to the list. This process can be continued until all elements of $\mathcal{T}$ are used. The result is a list which contains all possible neighbour-subsets exactly once. If $k=63$, the list will have length $63\cdot 64/2+1=2017$. By discarding the last $6$ elements we obtain a list $M$ with $2011$ elements. Let $M=({\mu }_i{)}_{i=1}^{2011}$ be this list and let $m_i$ be the $i$-th prime number. Defining $n_i=m_{{\mu }_i}$ we obtain a list $L=(n_i{)}_{i=1}^{2011}$ which satisfies the conditions of the problem.