一道算算算的数学竞赛题(滑稽)

昨晚lyj大佬扔给我一题(其实是他的某位学数竞的朋友扔给他的

题目是这样的:

若\( n \in \mathbb { N }\),证明\( (n+1)^4+n^5\)可以构成无穷多个合数。

一开始想偏了,暴力展开发现好像前面有个\(1\)变一下奇偶性后面只要为偶数就行了这不就证玩了吗傻逼题,后来发现是自己傻逼了,从原式子可以直接得出它一定是个奇数。

然后就开始想构造,事实上这个就很好办了:

我们设\(f(n)= (n+1)^4+n^5\),然后考虑\( f( n + k \cdot f(n) ), k \in \mathbb{N}\)

把它直接写成代数表达式的形式,也就是\(\left(k \left(n^5+(n+1)^4\right)+n\right)^5+\left(k \left(n^5+(n+1)^4\right)+n+1\right)^4\)

然后展开(Crazy!),得到\( k^5 n^{25}+5 k^5 n^{24}+30 k^5 n^{23}+120 k^5 n^{22}+425 k^5 n^{21}+1306 k^5 n^{20}+3520 k^5 n^{19}+8500 k^5 n^{18}+18440 k^5 n^{17}+36005 k^5 n^{16}+\\63474 k^5 n^{15}+100910 k^5 n^{14}+144070 k^5 n^{13}+183830 k^5 n^{12}+208120 k^5 n^{11}+206606 k^5 n^{10}+177060 k^5 n^9+128770 k^5 n^8+\\78120 k^5 n^7+38840 k^5 n^6+15509 k^5 n^5+4845 k^5 n^4+1140 k^5 n^3+190 k^5 n^2+20 k^5 n+k^5+5 k^4 n^{21}+21 k^4 n^{20}+\\114 k^4 n^{19}+402 k^4 n^{18}+1241 k^4 n^{17}+3333 k^4 n^{16}+7720 k^4 n^{15}+15800 k^4 n^{14}+28656 k^4 n^{13}+45716 k^4 n^{12}+64022 k^4 n^{11}+\\78282 k^4 n^{10}+82170 k^4 n^9+72270 k^4 n^8+51984 k^4 n^7+29916 k^4 n^6+13472 k^4 n^5+4620 k^4 n^4+1160 k^4 n^3+200 k^4 n^2+21 k^4 n+k^4+\\10 k^3 n^{17}+34 k^3 n^{16}+166 k^3 n^{15}+502 k^3 n^{14}+1312 k^3 n^{13}+2974 k^3 n^{12}+5680 k^3 n^{11}+9298 k^3 n^{10}+13132 k^3 n^9+15636 k^3 n^8+15246 k^3 n^7+11922 k^3 n^6+\\7360 k^3 n^5+3520 k^3 n^4+1264 k^3 n^3+322 k^3 n^2+52 k^3 n+4 k^3+10 k^2 n^{13}+26 k^2 n^{12}+114 k^2 n^{11}+284 k^2 n^{10}+600 k^2 n^9+\\1090 k^2 n^8+1600 k^2 n^7+1892 k^2 n^6+1804 k^2 n^5+1340 k^2 n^4+730 k^2 n^3+270 k^2 n^2+60 k^2 n+6 k^2+\\5 k n^9+9 k n^8+36 k n^7+70 k n^6+108 k n^5+145 k n^4+140 k n^3+84 k n^2+28 k n+4 k+n^5+n^4+4 n^3+6 n^2+4 n+1\)

然后怎么办!我们要证它可能是个合数,当然是给它除上一个东西…有经验的选手一看就知道是除以\(f(n)\)

于是我们得到了:

\(
\dfrac{f( n + k \cdot f(n) )}{f(n)} = k^5 n^{20}+4 k^5 n^{19}+22 k^5 n^{18}+76 k^5 n^{17}+233 k^5 n^{16}+620 k^5 n^{15}+1420 k^5 n^{14}+2876 k^5 n^{13}+\\5156 k^5 n^{12}+8112 k^5 n^{11}+11182 k^5 n^{10}+13420 k^5 n^9+13750 k^5 n^8+11704 k^5 n^7+8056 k^5 n^6+4372 k^5 n^5+\\1820 k^5 n^4+560 k^5 n^3+120 k^5 n^2+16 k^5 n+k^5+5 k^4 n^{16}+16 k^4 n^{15}+78 k^4 n^{14}+230 k^4 n^{13}+583 k^4 n^{12}+\\1293 k^4 n^{11}+2387 k^4 n^{10}+3745 k^4 n^9+5043 k^4 n^8+5616 k^4 n^7+4923 k^4 n^6+3270 k^4 n^5+1595 k^4 n^4+\\550 k^4 n^3+126 k^4 n^2+17 k^4 n+k^4+10 k^3 n^{12}+24 k^3 n^{11}+102 k^3 n^{10}+244 k^3 n^9+\\476 k^3 n^8+804 k^3 n^7+1076 k^3 n^6+1072 k^3 n^5+784 k^3 n^4+416 k^3 n^3+154 k^3 n^2+36 k^3 n+4 k^3+10 k^2 n^8+16 k^2 n^7+\\58 k^2 n^6+102 k^2 n^5+130 k^2 n^4+130 k^2 n^3+90 k^2 n^2+36 k^2 n+6 k^2+5 k n^4+4 k n^3+12 k n^2+12 k n+4 k+1
\)
希望你还没去世。我们已经得到了正确答案!

注意到这个结果里没有分式出现,所以把\(n,k\)的任意值代入结果都应为整数。于是就证明了\(f(n)\)是\( f( n + k \cdot f(n) )\)的一个因子,又由于\(f(n)\)单调递增,所以我们就可以按这个方法构造出无穷多个合数辣!!!

我觉得你真心需要一个Mathematica

1+

测试推莫反&打LaTeX的速度

无聊,不看论文和博客我能否手推莫比乌斯反演公式?

计时开始13:34

Möbius function:
\[
\mu(n) = \left\{\begin{matrix}0 & \mathrm{if} \: n \: \mathrm{is \: NOT \: square free.}\\ (-1)^{\omega (n)} & \mathrm{if} \: n \: \mathrm{is \: square \: free.} \end{matrix}\right.
\]

To Prove:
\[
\displaystyle{F(n) = \sum_{d|n} f(d)} \Rightarrow \displaystyle{f(n) = \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right)}
\]

Proof:
\[
\begin{align} \quad \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right ) &= \sum_{d|n} \mu(d) \sum_{d|n} f \left ( \frac{n}{d} \right ) \\ &= \sum_{d|n} \mu(d) \sum_{e|\frac{n}{d}} f(e) \\ &= \sum_{d|n} \sum_{e|\frac{n}{d}} \mu(d) f(e) \end{align}
\]
From \( e | \frac{n}{d} \Rightarrow d | \frac{n}{e}\) and \( \mu \circ \mathit{1} = \iota \)we deduce that
\[
\begin{align} \quad \sum_{e|n} \mu (d) F \left ( \frac{n}{d} \right ) &= \sum_{e|n} \sum_{d|\frac{n}{e}} \mu(d) f(e) \\ &= \sum_{e|n} \left ( f(e) \cdot \sum_{d|\frac{n}{e}} \mu(d) \right ) \\ &= \sum_{e|n} f(e) \iota \left ( \frac{n}{e} \right ) \\ &= \sum_{e|n} f(e) \cdot \left\{\begin{matrix} 0 & \mathrm{if} \: e \neq n \\ 1 & \mathrm{if} \: e = n \end{matrix}\right. \\ &= f(n) \end{align}
\]

Hence \(\begin{align} \quad f(n) = \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right ) \quad \blacksquare \end{align}\)

计时结束13:47

13分钟打完以上内容

1+

Tarjan求有向图强连通分量【模板】

0