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

abababa

如题。这个问题的一般解法是什么？单次翻转（翻转m个）当中只允许对同一个杯子翻转1次。

realnumber

3个杯子口向上，每次翻2个，做不到口都向下.
这是可以的$m\mid n$,还有其它吗？不会这么简单吧....

abababa

回复 2# realnumber

是有的情况做不到，做不到也算在解法里。当整除时是平凡情况，也算在解法里。
一般的像10个杯子每次翻4个，3次就能完成。8个杯子每次翻3个，4次能完成。但一般情况，脱离这个具体的数字，还是不知道要怎么表达。

青青子衿

回复 3# abababa
很有趣的问题
之前看过一个类似的：
有10枚硬币正面朝上，规定操作A每次只能将7枚硬币翻面，要使得这10枚硬币全部背面朝上，最少需要进行多少次操作A。
（之前找到一种较少步骤的方法）
11111 11111
↓
11100 00000
↓
00011 11000
↓
11100 11110
↓
00000 00000

realnumber

也特殊到一般,积累些经验n≥m
当m=2时，n为偶数可以成立，n为奇数不成立
m=3时，都成立
m=4时，$n \mod m=1,3$时不成立，$n \mod n=0,2$时成立
m=5时，除n=6，其余都成立

1.当m为奇数，n稍微大点，一般都成立，记$n\mod m=r>0$
     ①若r为偶数r=2k,翻[$\frac{n}{m}$]次后有r个开口朝上，只需把（k个开头朝上的）和（m-k开口朝上的）翻转一下，再翻转一次就OK了，次数是[$\frac{n}{m}$]+2.
     ②若r为奇数，翻[$\frac{n}{m}$]次后有r个开口朝上，这r个和m-r个开头向下的再来一次，得到m-r个（偶数个）开口向上的，再模仿①.合计[$\frac{n}{m}$]+3次
2.当m为偶数时，r为偶数，同上；r为奇数，无法完成，开口向上总是奇数个.

abababa

回复 5# realnumber

谢谢，这个操作很明了。不过如何证明$[\frac{n}{m}]+1,2$次无法完成操作呢？

realnumber

回复 6# abababa


    不能，不一定最小步骤，3楼的n=10,m=4最少3次
但按5楼办法是4次

realnumber

n足够大的话，比如n>2m,最小猜是[n/m]+1或[n/m]+2

Infinity

$n$为奇数，$m$为偶数时，不可能办到（其他其他情形都可以）。

abababa

回复 9# Infinity

觉得这里是不是和二进制码有什么关联，比如一次允许改变$m$个位，最少几次把全$1$变成全$0$。证明$n$为奇数$m$为偶数不能办到容易，但是像$n=6,m=5$这样情况的证明，感觉不那么明显。

Infinity

回复 10# abababa
对于这种问题，最少的翻动方法不是唯一的。
比如 `n=6,m=5` 的情况，最少次数是6次，一种方法是：将杯子进行编号，第$k$次翻动中除了第$k$号保持不翻动，其他都翻动，这样翻动6次就能使全部杯子朝下。
当然还有其他的方法，只要保证每次剩下未翻动杯子能在6个杯子中遍历一次，不必像上面一样一定要第$k$次保证第$k$号不翻动这种方式。

Infinity

上述方法对于一般情形也成立，也就是说，对于n个杯子（不一定都朝一个方向，可以各自向上或向下），若每次翻动n-1个，那么至少n次就可将所有杯子的朝向与最初相反（称为反转）。使用的方法方法仍然和11#一样。

abababa

回复 11# Infinity

谢谢，这个存在性的证明我理解了，但这仍然无法证明这是最少操作步数。并且我还有一个问题，如果把任意开口方向相同的杯子视为同一个，在这个意义下，最少操作步数是不是唯一的？

Infinity

回复 13# abababa
其实，$m\geqslant \lceil n/2\rceil$的情况与其对立面是互为对偶问题。比如$m=n-1$与$m=1$是对偶问题，前者每次翻动过程可以等价为先全部翻转，然后再翻转其中1个。显然$m=1$时最少次数为$n$，所以$m=n-1$时最少翻动次数也是$n$.
11#中我说的是最少的翻动方法（途径）不唯一，而不是步数。

abababa

回复 14# Infinity
哦，我有点明白了，这里是不是专指$m=n-1$这种情况？我理解的是一般情况的最少步数。
这个最少操作步数是唯一的，我在13楼里写错了，我的意思是：如果把开口方向相同的杯子视为无差别的，就是说每次翻转后，可以把所有开口向上的都放左边，向下的都放右边，不区分口向相同的杯子，在这个意义下，翻动方法是不是唯一的？

Infinity

一般情况的翻动方法也不是唯一的。比如n=10（杯子编号1到10），m=2，每次翻动的可以是连续相邻的两个编号杯子，也是随便挑选的（比如偶数），总之顺序和位置都不一定，只要遍历完就行。

如果把开口方向相同的杯子视为无差别的，就是说每次翻转后，可以把所有开口向上的都放左边，向下的都放右边，不区分口向相同的杯子，在这个意义下，翻动方法是不是唯一的？

因为次数一样，每次翻动更新的状态信息是一样的，那么不同只能在于顺序不同，所以很有可能是唯一的，但我没法严格证明。

青青子衿

翻硬币游戏(Coin Turning Game)
blog.csdn.net/qq_34374664/article/details/74892646
blog.sina.com.cn/s/blog_8f06da99010125ol.html

abababa

回复 17# 青青子衿
谢谢，只看到：$n$是奇数，$k$为奇数，且$k<\frac{n}{3}$的情况，这个情况我还没看明白。就是怎么推出的$pk<3n$，还有后面翻转前$s=\frac{pk-n}{2}$个三次，后$\ell=\frac{3n-pk}{2}$个一次，这两个数之和不就是$n$吗，也就是可以看成$a_1,\cdots,a_s$和$b_1,\cdots,b_{\ell}$这样组成的两个序列，$s+\ell=n$，然后$a$的那串就翻转三次变成背面向上，$b$的那串里，每次只取出一小段来翻转，每段不重叠，最后所有的$b$序列里都翻转一次。但这样的话，因为每次翻转$k$个，所以每次把$a$翻转完，还需要翻转$k-s=\frac{2k-pk+n}{2}$个$b$序列里的，而$b$序列里有$\ell=\frac{3n-pk}{2}$个，那应该有$(\frac{2k-pk+n}{2}) \mid (\frac{3n-pk}{2})$才行，这能做到吗？

abababa

回复 18# abababa
我觉得原帖里对n是奇数时，最后一种情况的说明是错的，比如我用n=11,k=3来做验证，就不是帖中所说的那样操作。
下面我说一下我的想法，还有一个地方没能完成证明：
只要先对前面几个依次翻转，共做$p-3$次翻转，就能变成第二种情况：$\frac{n}{3}\le k<n-2$的情况。而第二种情况只要翻转3次，所以这时共需翻转p次。

这样翻转前面几个，共翻转了$(p-3)k$个，还剩下$n'=n-(p-3)k$个，只要证明它满足第二种情况的条件，也就是证明$\frac{n'}{3} \le k < n'-2$
因为$n\le pk$，所以$n-pk+3k\le 3k$，也就是$n-(p-3k)\le 3k$，也就是$n'\le 3k$，这就证明了左边。
对于右边，如果能证明$(p-2)k+2<n$，就有$2<n-pk+2k$，两边加$k$就有$2+k<n-(p-3)k=n'$，也就是$k<n'-2$。

现在就差红色的没能证明了。
对于红色的地方，我想到这样的方法：因为$p,k,n$都是奇数，还有$(p-2)k<n\le pk$，这样就能说明红色成立了吧。因为相邻奇数间隔是2。

abababa

n是奇数的情况，现在我已经完全弄明白了。原帖里对n是偶数的情况，最后两个怎么是一样的操作呢？而且还在括号里注明了$\frac{pk-n}{2}$和$\frac{3n-pk}{2}$不是整数，这个情况不对吧。