翻譯

令 $m>n>1$ 為正整數. 一個集合含有 $m$ 個給定的實數. 我們從中選取任意 $n$ 個數, 記作 $a_1$, $a_2$, $\dotsc$, $a_n$, 并提問: 是否 $a_1<a_2<\dotsb < a_n$ 正確? 證明: 我們可以最多問 $n!-n^2+2n-2+m(n-1)(1+\lfloor \log_{n} m \rfloor)-m$ 個問題，將所有的 $m$ 個數排序.

We can find the order of the first $n$ numbers $n!-1$ questions,
looking at all possible orderings but one.

我們可通過查看除$1$以外的所有可能的順序,找出前$n$個數$n!-1$個問題的順序.

Suppose we have found the relative order of the first $k$ numbers
and let us find the relative order of first $k+1$ numbers.

假設我們已找到前$k$個數的相對順序,讓我們來找出前$k+1$個數的相對順序.

Suppose we have $a_1<a_2<\dotsb<a_k$
and let us find where $a_{k+1}$ fits.

假設有$a_1<a_2<\dotsb<a_k$,讓我們找出$a_{k+1}$應該放在哪里.

We use the following {\it binary search}:
pick $n-1$ numbers among $1,2,\dotsc,k$ that divide the interval $[1,k]$
most equally.

利用下面的\textbf{二分法搜索(binary search)}:在$1,2,\dotsc,k$之間選取$n-1$個數等分區間$[1,k]$.

(This is achieved by taking the numbers
$a_{\left\lfloor \frac{k}{n}\right\rfloor},a_{\left\lfloor \frac{2k}{n}\right\rfloor},\ldots ,
a_{\left\lfloor \frac{(n-1)k}{n}\right\rfloor}$).

(這可通過取數字
$a_{\left\lfloor \frac{k}{n}\right\rfloor},a_{\left\lfloor \frac{2k}{n}\right\rfloor},\ldots ,
a_{\left\lfloor \frac{(n-1)k}{n}\right\rfloor}$來實現).

We can find the relative order of $a_{k+1}$ and these numbers by at most $n-1$ questions.

我們最多可通過$n-1$次提問找出$a_{k+1}$和這些數的相對順序.

Indeed, for $1\leqslant j\leqslant n-1$, let $q_i$ be ``Is it true that
$a_{\left\lfloor \frac{k}{n}\right\rfloor}<\ldots <aa_{\left\lfloor \frac{ik}{n}\right\rfloor}
<a_{k+1}<a_{\left\lfloor \frac{(i+1)k}{n}\right\rfloor}<\ldots <a_{\left\lfloor \frac{(n-1)k}{n}\right\rfloor}$?''

實際上, 對于$1\leqslant j\leqslant n-1$, 令$q_i$為``
$a_{\left\lfloor \frac{k}{n}\right\rfloor}<\ldots <aa_{\left\lfloor \frac{ik}{n}\right\rfloor}
<a_{k+1}<a_{\left\lfloor \frac{(i+1)k}{n}\right\rfloor}<\ldots <a_{\left\lfloor \frac{(n-1)k}{n}\right\rfloor}$成立么?''

Then we find an $i$ such that
$a_{\left\lfloor \frac{ik}{n}\right\rfloor}<a_{k+1}<a_{\left\lfloor \frac{(i+1)k}{n}\right\rfloor}$.

那么我們找到 $i$使得
$a_{\left\lfloor \frac{ik}{n}\right\rfloor}<a_{k+1}<a_{\left\lfloor \frac{(i+1)k}{n}\right\rfloor}$.

Therefore, by at most $n-1$ questions we reduce the length of the interval of searching
from $k$ to at most $\left\lceil \frac{k}{n}\right\rceil$, where $\lceil x\rceil$
is the least integer number not less than $x$.

因此,我們最多可通過$n-1$個問題,使搜索的區間長度從$k$減小到最多是$\left\lceil \frac{k}{n}\right\rceil$,其中$\lceil x\rceil$為不小于$x$的最小整數.

We repeat this binary search until we find exactly the position of $a_{k+1}$
(that is, the interval of searching is 1 or 0).

我們重復這個二分法搜索,直到找出$a_{k+1}$的確切位置.
(即搜索間隔為$1$或$0$).

Now if $k\leqslant n^j$, then after $i$ steps the interval will be at most $n^{j-i}$,
so we need at most $j=\lceil \log _n k\rceil$ steps to insert $a_{k+1}$ into the sequence.

現在，如果$k\leqslant n^j$,那么在$i$步之后,間隔最多為$n^{j-i}$,因此我們最多需要$j=\lceil \log _n k\rceil$步來將$a_{k+1}$插入數列中.

Therefore, the number of questions needed is at most
$n!-1+(n-1)(\lceil \log_n(n+1)\rceil+\ldots +\lceil \log_n(m-1)\rceil)$.

因此,所需的提問次數最多為
$n!-1+(n-1)(\lceil \log_n(n+1)\rceil+\ldots +\lceil \log_n(m-1)\rceil)$.

All we need to do is to evaluate this number:
suppose that
$n^k\leqslant m<n^{k+1}$.
Then there are $n^2-n$ numbers $r$ for which
$\lceil \log_n r\rceil=2$, $n^3-n^2$ numbers for which
$\lceil \log_n r\rceil=3$, and so on until we have $m-1-n^k$ numbers $r$ for which
$\lceil \log_n r\rceil=k+1$.

我們需要做的就是計算這個數字:設
$n^k\leqslant m<n^{k+1}$.
那么有$n^2-n$個數$r$滿足$\lceil \log_n r\rceil=2$, 有$n^3-n^2$個數滿足$\lceil \log_n r\rceil=3$等等,直到我們有$m-1-n^k$個數$r$滿足
$\lceil \log_n r\rceil=k+1$.

Therefore the sum is
\begin{align*}
n!-1+(n-1)(2(n^2-n)+3(n^3-n^2)+\dotsb +k(n^k-n^{k-1})+(k+1)(m-1-n^k)) \\
=n!-1+(n-1)((k+1)(m-1)-n^k-n^{k-1}-\dotsb -n^2-2n).
\end{align*}
Because $n^{k+1}>m$,
\[ n^k+n^{k-1}+\dotsb +n^2+2n=\frac{n^{k+1}-1}{n-1}+n-1
\geqslant \frac{m}{n-1}+n-1. \]
Hence our sum is at most
\begin{align*}
n!-1+(n-1)\left((k+1)(m-1)-\frac{m}{n-1}-n+1\right) \\
= n!-n^2+2n-2+(n-1)(\lfloor \log_n m\rfloor+1)m-m,
\end{align*}
as desired.

因此和為
\begin{align*}
n!-1+(n-1)(2(n^2-n)+3(n^3-n^2)+\dotsb +k(n^k-n^{k-1})+(k+1)(m-1-n^k)) \\
=n!-1+(n-1)((k+1)(m-1)-n^k-n^{k-1}-\dotsb -n^2-2n).
\end{align*}
由于$n^{k+1}>m$,
\[ n^k+n^{k-1}+\dotsb +n^2+2n=\frac{n^{k+1}-1}{n-1}+n-1
\geqslant \frac{m}{n-1}+n-1. \]
因此我們的和最多為
\begin{align*}
n!-1+(n-1)\left((k+1)(m-1)-\frac{m}{n-1}-n+1\right) \\
= n!-n^2+2n-2+(n-1)(\lfloor \log_n m\rfloor+1)m-m,
\end{align*}
得證.