本帖最后由 abababa 于 2021-7-7 13:39 编辑
回复 45# abababa
终于弄出来了。
由于$p$是不小于$\frac{n}{n-k}$的最小偶数，因此：当$(n-k)\mid n$时，若$\frac{n}{n-k}$为偶数则$p=\frac{n}{n-k}<\frac{n}{n-k}+2$，若$\frac{n}{n-k}$为奇数则$p=\frac{n}{n-k}+1<\frac{n}{n-k}+2$(*)。当$(n-k)\nmid n$时，若$[\frac{n}{n-k}]$为偶数则$p=[\frac{n}{n-k}]+2<\frac{n}{n-k}+2$，若$[\frac{n}{n-k}]$为奇数则$p=[\frac{n}{n-k}]+1<\frac{n}{n-k}+2$(**)。由(*)(**)可以得到总有$p<\frac{n}{n-k}+2$(***)。
先证明$(p-3)(n-k)+1\le n$和$(p-3)(n-k)+1\le k$。为证明$(p-3)(n-k)+1\le n$，结合(***)，只要证明$(\frac{n}{n-k}+2-3)(n-k)+1<n$，只要证明$k<n-1$，这是已知的。结合(***)有$(p-3)(n-k)+1<(\frac{n}{n-k}+2-3)(n-k)+1=k+1$，而由整数知总有$(p-3)(n-k)+1\le k$。
先翻转$(p-2)$次：第一次从$a_1$开始翻转$k$个，第二次从$a_1$开始跳过$n-k$个，然后再翻转$k$个，如此继续，第$(p-2)$次从$a_1$开始跳过$(p-3)(n-k)$个，然后再翻转$k$个。每次翻转到$a_n$后如果翻转数量不足$k$个，则循环从$a_1$开始继续翻转直到翻满$k$个：
\[
\begin{cases}
a_1,\cdots,a_k\\
{\color{red}{a_{(n-k)+1},\cdots,a_n}}\\
{\color{red}{a_{2(n-k)+1},\cdots,a_n}}, {\color{blue}{a_1,\cdots,a_{n-k}}}\\
{\color{red}{a_{3(n-k)+1},\cdots,a_n}}, {\color{blue}{a_1,\cdots,a_{2(n-k)}}}\\
\cdots\\
{\color{red}{a_{(p-2)(n-k)+1},\cdots,a_n}}, {\color{blue}{a_1,\cdots,a_{(p-1)(n-k)}}}\\
a_{(p-3)(n-k)+1},\cdots,a_n, {\color{blue}{a_1,\cdots,a_{(p-2)(n-k)}}}
\end{cases}
\]
由于$(p-3)(n-k)+1\le n$，因此第$p-2$次翻转能做到。相邻两次中，前次的红色和后次的蓝色部分恰好构成完整的硬币序列，而蓝色部分被翻转了$p-2$次，是偶数，所以带颜色的部分共经过$p-2$次翻转，此时它们仍然正面向上。还余下$a_1,\cdots,a_k$和$a_{(p-3)(n-k)+1},\cdots,a_n$需要翻转，由于$(p-3)(n-k)+1\le k$，因此这两部分除了构成完整的硬币序列外，还有一部分重叠，完整硬币序列被翻转一次，反面向上，而重叠部分有$k-((p-3)(n-k)+1)+1=k-(p-3)(n-k)$个，被翻转两次，正面向上。所以经过$p-2$次翻转后，还剩下$k-(p-3)(n-k)$个正面向上的硬币。显然$k-(p-3)(n-k)$是偶数，设$2s=k-(p-3)(n-k)$，调整硬币顺序，不妨设此时$a_1,\cdots,a_t$是反面向上，$b_1,\cdots,b_{2s}$是正面向上。
先证明$2s\le 2k$，只要证明$k+(p-3)(n-k)\ge 0$，只要证明$p\ge 3$。因为$\frac{n}{2}<k<n-1$，所以只操作$2$次无法完成，从而$p>2$，但$p$是偶数，因此$p\ge 4$，所以$p\ge 3$，于是有$2s\le 2k$。
第$(p-1)$次翻转$b_1,\cdots,b_s$和$a_1,\cdots,a_{k-s}$这$k$个，因为$s<k$所以这能做到。此时正面向上的硬币还有$b_{s+1},\cdots,b_{2s}$和$a_1,\cdots,a_{k-s}$这$k$个，第$p$次翻转就使所有硬币反面向上。 |
新浪微博
QQ空间
人人网
腾讯微博
Facebook
Google+
Plurk
Twitter
Line
发表于 2021-7-4 16:42
|