免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 有$n$个杯子口朝上,每次翻$m$个,几次能全都口朝下

本帖最后由 abababa 于 2021-7-4 16:36 编辑

如题。这个问题的一般解法是什么?单次翻转(翻转m个)当中只允许对同一个杯子翻转1次。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

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

TOP

回复 2# realnumber

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

TOP

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

11100 00000

00011 11000

11100 11110

00000 00000

TOP

本帖最后由 realnumber 于 2019-5-19 19:32 编辑

也特殊到一般,积累些经验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为奇数,无法完成,开口向上总是奇数个.

TOP

回复 5# realnumber

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

TOP

回复 6# abababa


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

TOP

本帖最后由 realnumber 于 2019-5-20 09:47 编辑

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

TOP

$n$为奇数,$m$为偶数时,不可能办到(其他其他情形都可以)。

TOP

回复 9# Infinity

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

TOP

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

TOP

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

TOP

回复 11# Infinity

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

TOP

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

TOP

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

TOP

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

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

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

TOP

TOP

本帖最后由 abababa 于 2021-6-28 13:27 编辑

回复 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})$才行,这能做到吗?

TOP

本帖最后由 abababa 于 2021-6-29 03:53 编辑

回复 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。

TOP

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

TOP

返回列表 回复 发帖