给定正整数 $n(n > 2)$,将若干个互异的正整数排在一个圆周上,使得相邻两数之积小于 $n$,问圆周上最多有多少个数?
【难度】
【出处】
无
【标注】
【答案】
略
【解析】
如果 $a(a+1)<n$,则称 $a$ 为小数,否则称其为大数。当 $k(k+1)<n\leqslant (k+1)(k+2)$ 时,由于圆周上任意两个大数不相邻,且小数至多有 $k$ 个,故圆周上至多 $2k$ 个数。
当 $k(k+1)<n\leqslant k(k+2)$ 时,若能放 $2k$ 个数,则 $k$ 的两侧必然都是大数,必有一个数 $p\geqslant k+2$,而此时 $kp>n$,矛盾,故此式最大值 $\leqslant 2k-1$
用 $f$ 表示圆周上最多放的数的数目。
当 $k(k+1)<n\leqslant k(k+2)$ 时,$f=2k-1$
先将 $1,2,3,\cdots ,k-1,k$ 依次排成一条直线,然后再形成的 $k-1$ 个空中依次插入 $2k-1,2k-2,2k-3,\cdots ,k+1$,得到 $1,2k-1,2,2k-2,3,2k-3,\cdots ,k-1,k+1,k$ 。再将次序列依次排列在圆周上即可,此时最大的相邻两数之积为 $k(k+1)<n$ 。
当 $k(k+2)<n\leqslant (k+1)(k+2)$ 时,$f=2k$ 。
先将 $1,2,3,\cdots ,k-1,k$ 依次排成一条直线,然后再形成的 $k$ 个空(包括末尾一个空)中依次插入 $2k,2k-1,2k-2,\cdots ,k+1$,得到 $1,2k,2,2k-1,3,2k-2,\cdots,k-1,k+2,k,k+1$ 。再将次序列依次排列在圆周上即可,此时最大的相邻两数之积为 $k(k+2)<n$ 。
综上所述,当 $k(k+1)<n\leqslant k(k+2)$ 时,$f=2k-1$,当 $k(k+2)<n\leqslant (k+1)(k+2)$ 时,$f=2k$ 。
当 $k(k+1)<n\leqslant k(k+2)$ 时,若能放 $2k$ 个数,则 $k$ 的两侧必然都是大数,必有一个数 $p\geqslant k+2$,而此时 $kp>n$,矛盾,故此式最大值 $\leqslant 2k-1$
用 $f$ 表示圆周上最多放的数的数目。
当 $k(k+1)<n\leqslant k(k+2)$ 时,$f=2k-1$
先将 $1,2,3,\cdots ,k-1,k$ 依次排成一条直线,然后再形成的 $k-1$ 个空中依次插入 $2k-1,2k-2,2k-3,\cdots ,k+1$,得到 $1,2k-1,2,2k-2,3,2k-3,\cdots ,k-1,k+1,k$ 。再将次序列依次排列在圆周上即可,此时最大的相邻两数之积为 $k(k+1)<n$ 。
当 $k(k+2)<n\leqslant (k+1)(k+2)$ 时,$f=2k$ 。
先将 $1,2,3,\cdots ,k-1,k$ 依次排成一条直线,然后再形成的 $k$ 个空(包括末尾一个空)中依次插入 $2k,2k-1,2k-2,\cdots ,k+1$,得到 $1,2k,2,2k-1,3,2k-2,\cdots,k-1,k+2,k,k+1$ 。再将次序列依次排列在圆周上即可,此时最大的相邻两数之积为 $k(k+2)<n$ 。
综上所述,当 $k(k+1)<n\leqslant k(k+2)$ 时,$f=2k-1$,当 $k(k+2)<n\leqslant (k+1)(k+2)$ 时,$f=2k$ 。
答案
解析
备注