正整数 $a_{1}, a_{2}, \cdots, a_{2006}$（可以有相同的）使得 $\dfrac{a_{1}}{a_{2}}, \dfrac{a_{2}}{a_{3}}, \cdots,\dfrac{a_{2005} }{a_{2006} }$ 两两不相等．问：$a_{1}, a_{2}, \cdots, a_{2006}$ 中最少有多少个不同的数？
【难度】
【出处】
2006第21届CMO试题
【标注】
【答案】
略
【解析】
$a_{1}, a_{2}, \cdots, a_{2 006}$ 中最少有 $46$ 个互不相同的数．
由于 $45$ 个互不相同的正整数两两比值至多有 $45\times 44 + 1 = 1 981$ 个，故 $a_{1}, a_{2}, \cdots, a_{2006}$ 中互不相同的数大于 $45$．
下面构造一个例子，说明 $46$ 是可以取到的．
设 $p_{1}, p_{2}, \cdots, p_{46}$ 为 $46$ 个互不相同的素数，构造 $a_{1}, a_{2}, \cdots, a_{2006}$ 如下
$p_{1}, p_{1}, p_{2}, p_{1}, p_{3}, p_{2}, p_{3}, p_{1}, p_{4}, p_{3}, p_{4}, p_{2}, p_{4}, p_{1}, \cdots,$
$p_{1}, p_{k}, p_{k-1}, p_{k}, p_{k-2}, p_{k}, \cdots, p_{k}, p_{2}, p_{k}, p_{1}, \cdots$
$p_{1}, p_{45}, p_{44}, p_{45}, p_{43}, p_{45}, \cdots, p_{45}, p_{2}, p_{45}, p_{1}$
$p_{46}, p_{45}, p_{46}, p_{44}, p_{46}, \cdots, p_{46}, p_{22}, p_{46}$
这 $2 006$ 个正整数满足要求．
所以 $a_{1}, a_{2}, \cdots, a_{2006}$ 中最少有 $46$ 个互不相同的数．
由于 $45$ 个互不相同的正整数两两比值至多有 $45\times 44 + 1 = 1 981$ 个，故 $a_{1}, a_{2}, \cdots, a_{2006}$ 中互不相同的数大于 $45$．
下面构造一个例子，说明 $46$ 是可以取到的．
设 $p_{1}, p_{2}, \cdots, p_{46}$ 为 $46$ 个互不相同的素数，构造 $a_{1}, a_{2}, \cdots, a_{2006}$ 如下
$p_{1}, p_{1}, p_{2}, p_{1}, p_{3}, p_{2}, p_{3}, p_{1}, p_{4}, p_{3}, p_{4}, p_{2}, p_{4}, p_{1}, \cdots,$
$p_{1}, p_{k}, p_{k-1}, p_{k}, p_{k-2}, p_{k}, \cdots, p_{k}, p_{2}, p_{k}, p_{1}, \cdots$
$p_{1}, p_{45}, p_{44}, p_{45}, p_{43}, p_{45}, \cdots, p_{45}, p_{2}, p_{45}, p_{1}$
$p_{46}, p_{45}, p_{46}, p_{44}, p_{46}, \cdots, p_{46}, p_{22}, p_{46}$
这 $2 006$ 个正整数满足要求．
所以 $a_{1}, a_{2}, \cdots, a_{2006}$ 中最少有 $46$ 个互不相同的数．
答案
解析
备注
