부산대학교 도서관

Summary: ``Let $n$ and $q$ be positive integers, with $n\ge3$, and let $N=nq$. As input, we are to be given an arbitrary ordered $n$-sequence $x_1,x_2,\dots,x_n$, where $1\le x_i\le N$ for all $i$. We are to be presented with this sequence one entry at a time. As each entry is received, it must be placed into one of the positions $1,2,\dots,n$, where it must remain. A natural way to do this, in an attempt to sort the input sequence, is as follows. For any integer $x\in\{1,\dots,N\}$ we let $s(x)$ denote the unique integer $s$ for which $(s-1)q+1\le x\le sq$. When we receive the entry $x_i$ we consider those positions still unoccupied after having placed the previous $i-1$ entries, and we place $x_i$ into the one which is closest to $s(x_i)$. In the event of a tie for closest, we choose the higher of the two positions. We refer to this procedure as {\it the placement algorithm}. Regarding this algorithm, we consider the following question: for how many input sequences will the last two positions filled be positions 1 and $n$? We show that this number is $(n-1)^{n-3}n^2q^n$.''