有$n$个杯子口朝上，每次翻$m$个，几次能全都口朝下

realnumber

回复 20# abababa


    17楼n偶数举了两个例子,没发现有错,
n=10,k=4,翻一次4个,要么加2个反面,要么加4个反面(0,-2,-4不在考虑内),又第一和最后一次一定要加4个,那么10=4+2+4一共3次,最少的
n=10,k=3,翻一次3个,要么加1要么加3,10=3+1+3+3也4次
n=8,k=3,8=3+1+1+3也4次
n=14,k=6,14=6+2+6,3次
n=16,k=6,16=6+4+6,3次

abababa

回复 21# realnumber

n=14, k=4的情况要怎么做？这也满足$k<\frac{n}{2}$且为偶数，但按帖子里说的，只要翻转4次（不小于n/k的最小整数）就能完成，我怎么操作也没做出来。

abababa

回复 22# abababa

我先假设$k\nmid n$的情况，因为$k\mid n$是平凡情况，只要依次翻转就能做到。以下$[x]$表示不超过x的最大整数。

然后我猜测在$k\nmid n$的情况下，若$k<\frac{n}{2}$且$k$为偶数，则$[\frac{n}{k}]+1\le p\le [\frac{n}{k}]+2$。
左半部分容易证明：显然对翻转次数$p$必有$p\ge\frac{n}{k}$，但由于$k\nmid n$，因此$p>\frac{n}{k}$，但$p$又是整数，因此$p\ge[\frac{n}{k}]+1$，这是必要的。

然后以下的充分性说明只要$p\le [\frac{n}{k}]+2$，就必定能完成操作。
先对前面几个依次翻转，先做$(p-3)$次翻转，此时正面向上的硬币还有$n'=n-(p-3)k$个，因为
\[n'=n-(p-3)k\ge n-([\frac{n}{k}]+2-3)k=n-[\frac{n}{k}]k+k\ge n-n+k>0\]
因此做完$p-3$次翻转后，剩余的正面向上的硬币$n'$是正数。

只要能证明$\frac{n'}{2}<k<n-1$，就说明做完$p-3$次翻转后，局面变成了$\frac{n}{2}<k<n-1$的情况，而这种情况按帖子里说的，只要做$3$次翻转就可以完成，所以总共就做了$(p-3)+3=p$次翻转，就能证明了。

我以下只能证明$p = [\frac{n}{k}]+2$的情况。对于$p=[\frac{n}{k}]+1$的情况，$\frac{n'}{2}<k$的部分我没能证明出来。

为证明$\frac{n'}{2} < k$，只要证明$n-(p-3)k = n' < 2k$，只要证明$p > \frac{n}{k}+1$，即要证明$[\frac{n}{k}]+2>\frac{n}{k}+1$，这显然成立(*)。为证明$k<n'-1=n-(p-3)k-1$，只要证明$pk<n+2k-1$，只要证明$p<\frac{n}{k}+2-\frac{1}{k}$，而$p\le [\frac{n}{k}]+2$，因此只要证明$[\frac{n}{k}]+2<\frac{n}{k}+2-\frac{1}{k}$，即要证明$[\frac{n}{k}]<\frac{n-1}{k}$，即要证明$k[\frac{n}{k}]<n-1$。设$n = sk+t$，其中$0\le t<k$，但由于$k\nmid n$，因此$t\neq 0$(**)。注意$n,k$都是偶数，因此$n \bmod k$也是偶数，也就是$t$为偶数(***)。由(**)(***)就知道有$2\le t<k$。因为只要证明$k[\frac{sk+t}{k}]<n-1$，即要证明$ks<n-1$，但$ks=n-t$，因此只要证明$n-t<n-1$，即要证明$1<t$，这由$t\ge 2$可知成立。

abababa

回复 23# abababa

但这里依据的帖子中$\frac{n}{2}<k<n-1$，且$k$为偶数的情况，只需要$3$次翻转，这个我没仔细证明，也不知道对不对，感觉也不太好证。

realnumber

回复 22# abababa


   
k=4时，一次操作，
若翻四个正，则增加4个反（记为+4）；若翻3个正一个反，则增加2个反（记为+2），（不可能出现+1，+3，-1，-3，至于-2，-4只会增加操作次数）

n=14,k=4,这样来，14=4+2+4+4（或14=4+4+2+4，没有别的了）,也就是4次

realnumber

回复 24# abababa

也许你还没想到，其实都简单的

比如n=14,k=8
那么14=8+x+8,x=-2,也就是第一次+8，第二次-2，第三次+8，第一次，最后一次一定为+k

abababa

回复 25# realnumber
谢谢，14硬币每次翻转4个的我已经想明白怎么翻转了：
1-1-1-1-1-1-1-1-1-1-1-1-1-1
0-0-0-0-1-1-1-1-1-1-1-1-1-1
0-0-0-1-0-0-0-1-1-1-1-1-1-1
0-0-0-0-0-0-0-0-0-0-1-1-1-1
0-0-0-0-0-0-0-0-0-0-0-0-0-0

但这种翻转方式，并不是帖子里所说的：当$k<\frac{n}{k}$且为偶数时，对前面$\frac{pk-n}{2}$个翻转$3$次，对后面$\frac{3n-pk}{2}$个翻转$1$次的操作方式。是不是帖子里的翻转方式说得有问题，还是我哪里没理解清楚？

我的证明存在的问题就是，它不能依次连续翻转前k个，最后留下尾部的几个再去翻转，而是在中间就需要借助已经翻转的再翻过来。但具体的证明还不知道要怎么写。
回复 26# realnumber
这个翻转3次的，对于实际的具体的数字，我都能操作出来，就是证明不知道怎么写，我是想像n为奇数时，有那种具体的数学化的证明过程，这样才放心。就比如对n是奇数，n/3<=k<n-2的情况，我整理的证明如下：
当$\frac{n}{3}\le k< n-2$时有$0\le\frac{3k-n}{2}<n$，因此$\frac{3n-3k}{2}=n-\frac{3k-n}{2}>0$，即$\frac{3k-n}{2}$和$\frac{3n-3k}{2}$都是非负数。

只要让前面$\frac{3k-n}{2}$个硬币翻转$3$次，后面的$\frac{3n-3k}{2}$个硬币翻转$1$次，做法：
第一次翻转前面$a_1,\cdots,a_{\frac{3k-n}{2}}$个，再带上后面硬币中正面向上的$k-\frac{3k-n}{2}=\frac{n-k}{2}$个；
第二次仍翻转前面$a_1,\cdots,a_{\frac{3k-n}{2}}$个，再带上后面硬币中正面向上的$\frac{n-k}{2}$个；
第三次再翻转前面$a_1,\cdots,a_{\frac{3k-n}{2}}$个，并带上后面硬币中正面向上的$\frac{n-k}{2}$个。

此时前面的$a_1,\cdots,a_{\frac{3k-n}{2}}$个经过$3$次翻转，变为反面向上，后面硬币每次都将正面向上的$\frac{n-k}{2}$个翻转，共翻转了$3\cdot\frac{n-k}{2}=\frac{3n-3k}{2}$个，这样就完成了整个翻转。

realnumber

可能没理解你的要求，17楼的结论每条结论应该利用这个性质，可以快速得到
性质：操作一次，可以增加±k,或±（k-2）或±（k-3）...个反面，
其中第一次操作因为都是正面，一定是+k,最后一次要全部翻为反面也是+k；
中间某次操作，有一个反重新变为正，其他k-1个正变为反，那么就是+(k-2)个反面，余者类似


象n偶数,k偶数，且0.5n<k<n-1,就这样n=+k+x+k,解得x=n-2k=-(2k-n)<0
也即是第一次操作把k个正面转为反面，第二次操作有$\frac{n-k}{2}$个正，$\frac{3k-n}{2}$个反，这k个反一下，就是-(2k-n),最后一次就是第三次，把k个正面反一下，就全反了 。

abababa

回复 28# realnumber
当n是偶数时，若n/2<k<n-1且k是偶数时，只要操作3次，这个我能理解，跟n是奇数时是一样的证明方式，我所说的就是像我在27楼里那种数学化的证明方式。
但后面那个若n/2<k<n-1且k是奇数时，只要操作4次，要怎么证明？因为按帖子里说的，把前面$\frac{4k-n}{2}$个翻转3次，后面$\frac{3n-4k}{2}$个翻转1次，那我首先得证明$\frac{4k-n}{2}$是一个正数，并且小于n才行，这样才能操作下去，但这个我证明不出来。因为如果n=14,k=11，就满足n/2<k<n-1且k是奇数，但这时$\frac{4k-n}{2}=15$，总共只有14个硬币，怎么能翻动15个呢？

realnumber

回复 29# abababa


   帖子里 具体办法我其实没看,结论应该对的,k=11时,不能是14=+11-8+11,-8是偶数,最小只能是14=+11-5-3+11四次了,中间的负偶数拆成两个奇数就可以

abababa

回复 27# abababa

当$n$是偶数，$k$是偶数，且$k\nmid n$时：

若$k<\frac{n}{2}$且$k$为偶数，则$p=[\frac{n}{k}]+1$。

必要性：显然对翻转次数$p$必有$p\ge \frac{n}{k}$，但由于$k\nmid n$，因此$p>\frac{n}{k}$，但$p$为整数，因此$p\ge [\frac{n}{k}]+1$，以下的充分性说明只要$p=[\frac{n}{k}]+1$必能完成操作。

充分性：先对前面几个依次翻转，共做$(p-2)$次翻转，此时正面向上的硬币还有$n'=n-(p-2)k$个，先证明$0<n'<2k$。

为证明$0<n'$，只要证明$0<n-(p-2)k$，只要证明$p-2<\frac{n}{k}$，只要证明$[\frac{n}{k}]+1-2<\frac{n}{k}$，只要证明$[\frac{n}{k}]<\frac{n}{k}+1$，这是显然的(*)。为证明$n'<2k$，只要证明$n-(p-2)k<2k$，只要证明$n-pk<0$，只要证明$\frac{n}{k}<p$，只要证明$\frac{n}{k}<[\frac{n}{k}]+1$，这也是显然的(**)。由(*)(**)即有$0<n'<2k$。因此操作$(p-2)$次后，前面$a_1,\cdots,a_{(p-2)k}$个是反面向上，后面$b_1,\cdots,b_s$个是正面向上，其中$s<2k$。而且还有$n=(p-2)k+s$，因为$(p-2)k$是偶数，因此$s$也是偶数。

下面翻转编号是$b_1,\cdots,b_{\frac{s}{2}}$和$a_1,\cdots,a_{k-\frac{s}{2}}$的硬币，由于$s$是偶数且$s<2k$，因此这能做到。此时正面向上的硬币只有$b_{\frac{s}{2}+1},\cdots,b_s$和$a_1,\cdots,a_{k-\frac{s}{2}}$，共$\frac{s}{2}+(k-\frac{s}{2})=k$个，再做一次翻转就使所有硬币反面向上。

因此共做了$(p-2)+1+1=p$次翻转。

abababa

回复 31# abababa

关键的就是倒数第二次那个回头翻转$a$序列里的硬币，这点我之前没想明白。

现在还剩下$n$是偶数$k$是奇数的情况了，还是希望有数学化的证明。

abababa

回复 30# realnumber

请问n=14,k=11的情况，第二次要怎么翻动，才能让背面向上的有5个？初始和第一次应该就这样翻动吧，第二次翻动要怎么做呢？
初始：1-1-1-1-1-1-1-1-1-1-1-1-1-1
一次：0-0-0-0-0-0-0-0-0-0-0-1-1-1
二次：
三次：0-0-0-1-1-1-1-1-1-1-1-1-1-1
四次：0-0-0-0-0-0-0-0-0-0-0-0-0-0

abababa

回复 31# abababa

仿照这个证明，当$n$是偶数$k$是奇数，且$k\nmid n$的情况：
若$k<\frac{n}{2}$且$k$为奇数，则$p$为不小于$[\frac{n}{k}]+1$的最小偶数。

必要性：显然对翻转次数$p$必有$p\ge \frac{n}{k}$，但由于$k\nmid n$，因此$p>\frac{n}{k}$，但$p$为整数，因此$p\ge [\frac{n}{k}]+1$。由于$k$为奇数，若$p$为奇数，则所有硬币总共翻转次数为奇数，但由$n$为偶数知总共翻转次数必为偶数，矛盾，因此$p$为偶数，所以$p$是不小于$[\frac{n}{k}]+1$的偶数。以下的充分性说明只要$p$是不小于$[\frac{n}{k}]+1$的偶数必能完成操作。

充分性：先对前面几个依次翻转，共做$(p-2)$次翻转，此时正面向上的硬币还有$n'=n-(p-2)k$个，先证明$0<n'<2k$。因为$p$是不小于$[\frac{n}{k}]+1$的最小偶数，当$[\frac{n}{k}]$是奇数时$p=[\frac{n}{k}]+1$，当$[\frac{n}{k}]$是偶数时$p=[\frac{n}{k}]+2$。因此总有$[\frac{n}{k}]+1 \le p \le [\frac{n}{k}]+2$。

为证明$0<n'$，只要证明$0<n-(p-2)k$，只要证明$p-2<\frac{n}{k}$，而$p\le [\frac{n}{k}]+2$，因此只要证明$[\frac{n}{k}]+2-2<\frac{n}{k}$，这是显然的(*)。为证明$n'<2k$，只要证明$n-(p-2)k<2k$，只要证明$n-pk<0$，只要证明$\frac{n}{k}<p$，只要证明$\frac{n}{k}<[\frac{n}{k}]+1$，这也是显然的(**)。由(*)(**)就得到$0<n'<2k$。

因此操作$(p-2)$次后，前面$a_1,\cdots,a_{(p-2)k}$个是反面向上，后面$b_1,\cdots,b_s$个是正面向上，其中$s<2k$，且$n=(p-2)k+s$。由于$p$是偶数因此$(p-2)k$也是偶数，而$n$是偶数，从而$s$是偶数。

下面翻转$b_1,\cdots,b_{\frac{s}{2}}$和$a_1,\cdots,a_{k-\frac{s}{2}}$这$k$个，由于$s$是偶数且$s<2k$，因此这能做到。此时正面向上的硬币只有$b_{\frac{s}{2}+1},\cdots,b_s$和$a_1,\cdots,a_{k-\frac{s}{2}}$，共$\frac{s}{2}+(k-\frac{s}{2})=k$个，再做一次翻转就使所有硬币反面向上。

因此共做了$(p-2)+1+1=p$次翻转。

realnumber

请问n=14,k=11的情况，第二次要怎么翻动，才能让背面向上的有5个？初始和第一次应该就这样翻动吧，第二次翻动要怎么做呢？
初始：1-1-1-1-1-1-1-1-1-1-1-1-1-1
一次：0-0-0-0-0-0-0-0-0-0-0-1-1-1 对应+11
二次：0-0-0-0-0-0-1-1-1-1-1-1-1-1  对应-5  意思是把上面蓝色部分翻一下
三次：0-0-0-1-1-1-1-1-1-1-1-1-1-1   对应-3,我发现我翻不出,除非蓝色翻1次,红色翻2次,一共11
四次：0-0-0-0-0-0-0-0-0-0-0-0-0-0   对应+11

14=+11-5-3+11

abababa

回复 35# realnumber
如果允许在一次翻转里对某个硬币翻转多次，那就容易了吧，n=14,k=11时，第一次翻11个，第二次翻转3个，就已经全是反面向上了，但这时还余下11-3=8次没翻转，那就对最后一个连着翻转8次就好了，8是偶数，结果还是反面向上。那这样的话只要翻转两次就完成了啊，应该不能这样做吧，单次操作中翻转的硬币应该不允许相同。

abababa

回复 35# realnumber
这种对n=14,k=11的，只做4次应该是做不到的，我证明如下：
因为$n$是偶数，因此当所有硬币反面向上时，对所有硬币的翻转总次数必定是偶数，但单次翻转的$k$为奇数，因此翻转次数$p$必为偶数。但每个硬币都必翻转奇数次才能达到反面向上，因此每个硬币都至少在某一次操作中没被翻转（否则存在一个硬币在所有操作中都被翻转，则此硬币被翻转了偶数$p$次，这与每个硬币都必翻转奇数次矛盾），因此所有硬币总共没被翻转的次数至少为$n$。

设所有硬币总共没被翻转的次数为$m$，则有$m\ge n$。而每次操作都有$n-k$个硬币没被翻转，因此$p=\frac{m}{n-k}\ge\frac{n}{n-k}$，然而$p$是偶数，因此$p$是不小于$\frac{n}{n-k}$的偶数。

换到这里，$p$就是不小于$\frac{14}{14-11}=4.7$的偶数，所以$p$至少是$6$，而不可能是$4$。但6次能不能翻转出来，我还没有找到方案，对于一般的情况也没有思路。

realnumber

回复 37# abababa


   n=14,k=11
1-1-1-1-1-1-1-1-1-1-1-1-1-1
1-1-1-0-0-0-0-0-0-0-0-0-0-0
0-0-0-0-0-0-1-1-1-1-1-1-1-1
1-1-1-1-1-1-1-1-1-0-0-0-0-0
0-0-0-0-0-0-0-0-0-0-0-0-1-1
1-1-1-1-1-1-1-1-1-1-0-0-1-0
0-0-0-0-0-0-0-0-0-0-0-0-0-0
14=+11-5-1+7-9+11

这个其实这样想出来的,象"补码",把n=14,k=3改动一下,
1-1-1-1-1-1-1-1-1-1-1-1-1-1
0-0-0-1-1-1-1-1-1-1-1-1-1-1  上面k=11时,蓝色不翻,翻其它11个,后面都如此
0-0-0-0-0-0-1-1-1-1-1-1-1-1
0-0-0-0-0-0-0-0-0-1-1-1-1-1
0-0-0-0-0-0-0-0-0-0-0-0-1-1
0-0-0-0-0-0-0-0-0-0-1-1-0-1
0-0-0-0-0-0-0-0-0-0-0-0-0-0
14=+3+3+3+3-1+3  试了下n=8,k=5,也可以如此改自"n=8,k=3"
6次操作,每个硬币翻奇数次$t_i$,那"补码"时,每个硬币翻$6-t_i$次,也是奇数次,所以都翻过来了

realnumber

假设有更少次数，那么“补码”也有更少次数，看来上面n=14,k=11,6次是最少了

青青子衿

回复  realnumber
如果允许在一次翻转里对某个硬币翻转多次，那就容易了吧，n=14,k=11时，第一次翻11个， ...
abababa 发表于 2021-7-3 20:05

感觉应该在主贴补充说明一下