对于整数 $n≥4$,求出最小的整数 $f(n)$,使得对于任何正整数 $m$,集合 $\{m,m + 1,…,m + n – 1\}$ 的任一个 $f(n)$ 元子集中,均有至少 $3$ 个两两互素的元素.
【难度】
【出处】
无
【标注】
【答案】
略
【解析】
当 $n\geqslant 4$ 时,考察集合 $M=\left\{ m,m+1,m+2, \cdots, m+n-1 \right\}$.
若 $2\mid m$,则 $m+1$、$m+2$、$m+3$ 两两互素;
若 $2\nmid m$,则 $m$、$m+1$、$m+2$ 两两互素.
于是,$M$ 的所有 $n$ 元子集中,均有至少 $\text{3}$ 个两两互素的元素.因此,$f\left( n \right)$ 存在,且 $f\left( n \right)\leqslant n$.……10分
设 ${{T}_{n}}=\left\{ t\left| t\leqslant n+1\right. \right.$ 且 $2\mid t$ 或 $\left. 3\mid t \right\}$,则 ${{T}_{n}}$ 为 $\left\{ 2 3 \cdot \cdot\cdot n+1 \right\}$ 的子集,但 ${{T}_{n}}$ 中任 $\text{3}$ 个元素均不能两两互素,因此,$f\left( n \right)\geqslant \left| {{T}_{n}} \right|+1$.
由容斥原理知
$\left| {{T}_{n}} \right|=\left[ \dfrac{n+1}{2}\right]+\left[ \dfrac{n+1}{3} \right]-\left[ \dfrac{n+1}{6} \right]$,
从而必有
$f\left( n \right)\geqslant \left[ \dfrac{n+1}{2}\right]+\left[ \dfrac{n+1}{3} \right]-\left[ \dfrac{n+1}{6} \right]+1$.① …20分
因此 $f\left(4 \right)\geqslant 4$,$f\left( 5\right)\geqslant 5$,$f\left( 6\right)\geqslant 5$,
$f\left( 7 \right)\geqslant 6$,$f\left( 8 \right)\geqslant 7$,$f\left( 9 \right)\geqslant 8$.
以下证明 $f\left( 6 \right)=5$.
设 ${{x}_{1}}$、${{x}_{2}}$、${{x}_{3}}$、${{x}_{4}}$、${{x}_{5}}$ 为 $\left\{ m m+1 \cdot\cdot \cdot m+5 \right\}$ 中的 $\text{5}$ 个数.若这 $\text{5}$ 个数中有 $\text{3}$ 个奇数,则它们两两互素;若这 $\text{5}$ 个数中有 $\text{2}$ 个奇数,则必有 $\text{3}$ 个偶数,不妨设 ${{x}_{1}}$、${{x}_{2}}$、${{x}_{3}}$ 为偶数,${{x}_{4}}$、${{x}_{5}}$ 为奇数,当 $1\leqslant i<j\leqslant 3$ 时,$\left| {{x}_{i}}-{{x}_{j}} \right|\in \left\{ 2 4 \right\}$,所以 ${{x}_{1}}$、${{x}_{2}}$、${{x}_{3}}$ 中至多一个被 $\text{3}$ 整除,至多一个被 $\text{5}$ 整除,从而至少有一个既不被 $\text{3}$ 整除也不被 $\text{5}$ 整除,不妨设 $3\nmid {{x}_{3}}$,$5\nmid {{x}_{3}}$,则 ${{x}_{3}}$、${{x}_{4}}$、${{x}_{5}}$ 两两互素,这就是说这 $\text{5}$ 个数中有 $\text{3}$ 个两两互素,即 $f\left( 6 \right)=5$.……30分
又由 $\left\{ m,m+1, \cdot\cdot \cdot m+n \right\}=\left\{ m,m+1, \cdot \cdot \cdot ,m+n-1 \right\}\bigcup \left\{ m+n \right\}$ 知
$f\left( n+1 \right)\leqslant f\left( n \right)+1$.
因为 $f\left( 6 \right)=5$,所以
$f\left(4 \right)=4$,$f\left( 5\right)=5$,$f\left( 7\right)=6$,$f\left( 8\right)=7$,$f\left( 9\right)=8$.
因此,当 $4\leqslant n\leqslant 9$ 时
$f\left(n \right)=\left[ \dfrac{n+1}{2} \right]+\left[ \dfrac{n+1}{3} \right]-\left[ \dfrac{n+1}{6}\right]+1$.② ……40分
以下用归纳法证明 ② 对所有 $n$ 都成立:
假设 $n\leqslant k\left( k\geqslant 9 \right)$ 时 ② 式都成立.
当 $n=k+1$ 时,由于
$\left\{m m+1 \cdot \cdot \cdot m+k \right\}=\left\{ m m+1 \\cdot \cdot \cdot m+k-6 \right\}\bigcup $
$\left\{m+k-5 m+k-4 m+k-3 m+k-2 m+k-1 m+k \right\}$
且由归纳假设 $n=6$,$n=k-5$ 时,② 式成立,所以
$f\left(k+1 \right)\leqslant f\left( k-5 \right)+f\left( 6 \right)-1$
$=\left[\dfrac{k+2}{2} \right]+\left[ \dfrac{k+2}{3} \right]-\left[ \dfrac{k+2}{6}\right]+1$.③
由 ①、③ 式知,对于 $n=k+1$,② 式成立.
所以,对于任意 $n\geqslant 4$,有
$f\left( n \right)=\left[ \dfrac{n+1}{2} \right]+\left[\dfrac{n+1}{3} \right]-\left[ \dfrac{n+1}{6} \right]+1$.……50分
若 $2\mid m$,则 $m+1$、$m+2$、$m+3$ 两两互素;
若 $2\nmid m$,则 $m$、$m+1$、$m+2$ 两两互素.
于是,$M$ 的所有 $n$ 元子集中,均有至少 $\text{3}$ 个两两互素的元素.因此,$f\left( n \right)$ 存在,且 $f\left( n \right)\leqslant n$.……10分
设 ${{T}_{n}}=\left\{ t\left| t\leqslant n+1\right. \right.$ 且 $2\mid t$ 或 $\left. 3\mid t \right\}$,则 ${{T}_{n}}$ 为 $\left\{ 2 3 \cdot \cdot\cdot n+1 \right\}$ 的子集,但 ${{T}_{n}}$ 中任 $\text{3}$ 个元素均不能两两互素,因此,$f\left( n \right)\geqslant \left| {{T}_{n}} \right|+1$.
由容斥原理知
$\left| {{T}_{n}} \right|=\left[ \dfrac{n+1}{2}\right]+\left[ \dfrac{n+1}{3} \right]-\left[ \dfrac{n+1}{6} \right]$,
从而必有
$f\left( n \right)\geqslant \left[ \dfrac{n+1}{2}\right]+\left[ \dfrac{n+1}{3} \right]-\left[ \dfrac{n+1}{6} \right]+1$.① …20分
因此 $f\left(4 \right)\geqslant 4$,$f\left( 5\right)\geqslant 5$,$f\left( 6\right)\geqslant 5$,
$f\left( 7 \right)\geqslant 6$,$f\left( 8 \right)\geqslant 7$,$f\left( 9 \right)\geqslant 8$.
以下证明 $f\left( 6 \right)=5$.
设 ${{x}_{1}}$、${{x}_{2}}$、${{x}_{3}}$、${{x}_{4}}$、${{x}_{5}}$ 为 $\left\{ m m+1 \cdot\cdot \cdot m+5 \right\}$ 中的 $\text{5}$ 个数.若这 $\text{5}$ 个数中有 $\text{3}$ 个奇数,则它们两两互素;若这 $\text{5}$ 个数中有 $\text{2}$ 个奇数,则必有 $\text{3}$ 个偶数,不妨设 ${{x}_{1}}$、${{x}_{2}}$、${{x}_{3}}$ 为偶数,${{x}_{4}}$、${{x}_{5}}$ 为奇数,当 $1\leqslant i<j\leqslant 3$ 时,$\left| {{x}_{i}}-{{x}_{j}} \right|\in \left\{ 2 4 \right\}$,所以 ${{x}_{1}}$、${{x}_{2}}$、${{x}_{3}}$ 中至多一个被 $\text{3}$ 整除,至多一个被 $\text{5}$ 整除,从而至少有一个既不被 $\text{3}$ 整除也不被 $\text{5}$ 整除,不妨设 $3\nmid {{x}_{3}}$,$5\nmid {{x}_{3}}$,则 ${{x}_{3}}$、${{x}_{4}}$、${{x}_{5}}$ 两两互素,这就是说这 $\text{5}$ 个数中有 $\text{3}$ 个两两互素,即 $f\left( 6 \right)=5$.……30分
又由 $\left\{ m,m+1, \cdot\cdot \cdot m+n \right\}=\left\{ m,m+1, \cdot \cdot \cdot ,m+n-1 \right\}\bigcup \left\{ m+n \right\}$ 知
$f\left( n+1 \right)\leqslant f\left( n \right)+1$.
因为 $f\left( 6 \right)=5$,所以
$f\left(4 \right)=4$,$f\left( 5\right)=5$,$f\left( 7\right)=6$,$f\left( 8\right)=7$,$f\left( 9\right)=8$.
因此,当 $4\leqslant n\leqslant 9$ 时
$f\left(n \right)=\left[ \dfrac{n+1}{2} \right]+\left[ \dfrac{n+1}{3} \right]-\left[ \dfrac{n+1}{6}\right]+1$.② ……40分
以下用归纳法证明 ② 对所有 $n$ 都成立:
假设 $n\leqslant k\left( k\geqslant 9 \right)$ 时 ② 式都成立.
当 $n=k+1$ 时,由于
$\left\{m m+1 \cdot \cdot \cdot m+k \right\}=\left\{ m m+1 \\cdot \cdot \cdot m+k-6 \right\}\bigcup $
$\left\{m+k-5 m+k-4 m+k-3 m+k-2 m+k-1 m+k \right\}$
且由归纳假设 $n=6$,$n=k-5$ 时,② 式成立,所以
$f\left(k+1 \right)\leqslant f\left( k-5 \right)+f\left( 6 \right)-1$
$=\left[\dfrac{k+2}{2} \right]+\left[ \dfrac{k+2}{3} \right]-\left[ \dfrac{k+2}{6}\right]+1$.③
由 ①、③ 式知,对于 $n=k+1$,② 式成立.
所以,对于任意 $n\geqslant 4$,有
$f\left( n \right)=\left[ \dfrac{n+1}{2} \right]+\left[\dfrac{n+1}{3} \right]-\left[ \dfrac{n+1}{6} \right]+1$.……50分
答案
解析
备注