当前在线人数13955
首页 - 分类讨论区 - 情感杂想 - 肚皮舞运动版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
奥数题求助
[版面:肚皮舞运动][首篇作者:weierstrass] , 2021年05月04日09:07:23 ,585次阅读,10次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
weierstrass
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: weierstrass (没昵称), 信区: Joke
标  题: 奥数题求助
发信站: BBS 未名空间站 (Tue May  4 09:07:23 2021, 美东)

同学在群里发的,被小朋友的奥数题难住了

你被蒙住了双眼,什么都看不见。你的正前方有一张方桌,桌子的四个角上各有一枚硬
币。有一个机器人根据你的指令操作硬币。你可以发出指令让机器人翻转任何你指定位
置的硬币。例如:翻转左上和右下两枚硬币;翻转全部四枚硬币。机器人每次按你的指
令操作完成后,桌子会随机顺时针或逆时针旋转90、180、270、360度,然后等待你下
一次指令。当四枚硬币全部正面朝上时,机器人立即发出声音通知你(其他任何时候它
不会发声),游戏结束。
问题:你可以通过有限次指令保证使得游戏结束吗?若能,请给出你的指令步骤。若不
能,请证明。


--
☆ 发自 iPhone 买买提 1.24.11
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 47.]

 
SLE
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: SLE (嗯,就这样定了。), 信区: Joke
标  题: Re: 奥数题求助
发信站: BBS 未名空间站 (Tue May  4 10:21:33 2021, 美东)

想起这道题怎么做了。

如果硬币对角状态相同,三步以内结束。

如果没有声音:
第一步,全部翻转。
如果没有声音:
第二步:左上和右下翻转。
如果没有声音:
第三步:全部翻转

如果三步以内没有结束,那么就先翻转左上,然后重复上面的三步。

如果过了三步还是没有结束,那就翻转左上和右上,然后重复那三步。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
weierstrass
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: weierstrass (没昵称), 信区: Joke
标  题: Re: 奥数题求助
发信站: BBS 未名空间站 (Tue May  4 10:31:34 2021, 美东)

多谢,我转给朋友研究下


【 在 SLE (嗯,就这样定了。) 的大作中提到: 】
: 想起这道题怎么做了。
: 如果硬币对角状态相同,三步以内结束。
: 如果没有声音:
: 第一步,全部翻转。
: 如果没有声音:
: 第二步:左上和右下翻转。
: 如果没有声音:
: 第三步:全部翻转
: 如果三步以内没有结束,那么就先翻转左上,然后重复上面的三步。
: 如果过了三步还是没有结束,那就翻转左上和右上,然后重复那三步。




--
☆ 发自 iPhone 买买提 1.24.11
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 47.]

 
Huangchong
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: Huangchong (净坛使者), 信区: Joke
标  题: Re: 奥数题求助
发信站: BBS 未名空间站 (Tue May  4 10:56:54 2021, 美东)

部分解:

初始情况 (1 )有两个相邻朝下  另两个朝上

发出如下指令可以保证达到四个全朝上
翻相邻两个
翻对角两个
翻四个
翻对角两个 
翻四个


如果到这里没胜利 说明初始状态 不是两个相邻的朝下

而且  此时的状态  等于起始状态翻了相邻两个



如果起始状态是(2)对角两个朝上  那翻了任意两个相邻棋子之后  会变成相邻两个
棋子朝上  

所以重复上面五条指令一次  肯定可以达到四个朝上 

这样  只要开始是2上2下  10条指令可解











--
☆ 发自 iPhone 买买提 1.24.11
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 142.]

 
Huangchong
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: Huangchong (净坛使者), 信区: Joke
标  题: Re: 奥数题求助
发信站: BBS 未名空间站 (Tue May  4 11:03:52 2021, 美东)


如果这时还没成功  说明开始是3对1  而这时相当于随机翻了其中两个  三对一  随机
翻两个  结果还是三对一  所以这时随机翻一个  会产生四比0或者2比2  那就再先全
翻一次  没成功的话  重复上面两个5个指令序列   应该就可以了

(补充修改 : 开始也可能是全朝下  所以在所有指令之前加一步全翻即可)


【 在 Huangchong (净坛使者) 的大作中提到: 】
: 部分解:
: 初始情况 (1 )有两个相邻朝下  另两个朝上
: 发出如下指令可以保证达到四个全朝上
: 翻相邻两个
: 翻对角两个
: 翻四个
: 翻对角两个 
: 翻四个
: 如果到这里没胜利 说明初始状态 不是两个相邻的朝下
: 而且  此时的状态  等于起始状态翻了相邻两个
: ...................





--
☆ 发自 iPhone 买买提 1.24.11
--
※ 修改:·Huangchong 於 May  4 11:12:22 2021 修改本文·[FROM: 142.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 142.]

 
Huangchong
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: Huangchong (净坛使者), 信区: Joke
标  题: Re: 奥数题求助
发信站: BBS 未名空间站 (Tue May  4 11:06:38 2021, 美东)

这个解法好 

【 在 SLE (嗯,就这样定了。) 的大作中提到: 】
: 想起这道题怎么做了。
: 如果硬币对角状态相同,三步以内结束。
: 如果没有声音:
: 第一步,全部翻转。
: 如果没有声音:
: 第二步:左上和右下翻转。
: 如果没有声音:
: 第三步:全部翻转
: 如果三步以内没有结束,那么就先翻转左上,然后重复上面的三步。
: 如果过了三步还是没有结束,那就翻转左上和右上,然后重复那三步。




--
☆ 发自 iPhone 买买提 1.24.11
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 142.]

 
SLE
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: SLE (嗯,就这样定了。), 信区: Joke
标  题: Re: 奥数题求助
发信站: BBS 未名空间站 (Tue May  4 11:18:39 2021, 美东)

好像后两种情况的讨论有一些纰漏。修改一下。
开始三步不变。
如果没有结束,就翻转左上和右上,然后重复那三步。
如果还是没有结束,就翻转任何一个,再重复开始三步。
如果还是没有结束,就翻转左上和右上,然后重复开始三步。

【 在 SLE (嗯,就这样定了。) 的大作中提到: 】
: 想起这道题怎么做了。
: 如果硬币对角状态相同,三步以内结束。
: 如果没有声音:
: 第一步,全部翻转。
: 如果没有声音:
: 第二步:左上和右下翻转。
: 如果没有声音:
: 第三步:全部翻转
: 如果三步以内没有结束,那么就先翻转左上,然后重复上面的三步。
: 如果过了三步还是没有结束,那就翻转左上和右上,然后重复那三步。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
frozensea
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: frozensea (冰冻之海), 信区: Joke
标  题: Re: 奥数题求助
发信站: BBS 未名空间站 (Wed May  5 08:32:48 2021, 美东)

这道题有些意思,稍微想了一下。
本质上,是一个有穷自动机的问题。在信息不完备的情况下,如何能够到达特定的状态。

一、如何定义状态。
4个硬币是16状态,如果考虑旋转那么一共是64状态。一开始我想以64状态分析,后来
发现没有必要。
现将硬币从左上开始,按顺时针顺序,构成状态,显见有0000-1111共16状态。

二、状态转移
我方的操作其实可以在任意子【两种状态间转移。但因为自身状态未知,这块不好入手
。所以先从不可控的机器随机操作开始。
机器的所有操作是旋转,对应的比特状态变化是循环移位操作。

以图的方式来构建,那么将机器操作作为节点间的连接(图中红线),那么整个状态图
可以分为几个子图

S0: 1111
S1: 0000
S2: 1010, 0101
S3: 1100, 1001, 0011, 0110
S4.1: 0001, 0010, 0100, 1000
S4.2: 1110, 1101, 1011, 0111

三、策略分析
感谢SLE大佬的分析,非常有启发。本来我的策略是尝试构建子操作集,在特定子集中
可以保证跃迁,从而能确保遍历,实现1111状态。看到SLE关于对角的分析后觉得很有
道理,想归纳出策略,就继续再走了几步,大致就走通了。

引理1:机器操作可且仅可跃迁至当前子图中的任一状态。例如当前处于1001,那么机
器操作后,可能是S3中的任一状态,但不会是S3以外的状态

由此可见,用户操作(蓝线表示)以实现子图间跃迁,机器操作(红线表示)实现子图
内跃迁。我们需要寻找最有共性的操作,以确保路径可控。

易知:
S1 -> S0:
通过操作1111(全翻转实现)

S2 -> S0:
1010操作可以使S1跃迁至S1或S0
所以,综合操作步骤为:1010 -> 1111

(S1 + S2) -> S0:
1111操作使S2依然保持在S2状态,因此
步骤为:1111 -> 1010 -> 1111

S3 -> S0:
在S3时选择1100操作,必然跃迁至S0/S1/S2
所以易知,步骤为:
1100 -> 1111 -> 1010 -> 1111

(S1 + S2 + S3) -> S0:
需要注意1100同样会让S1/S2跃迁至S3
1111、1010操作让S3仍然保持S3:
所以一个简单的策略就是叠加(也许不是最优):
1111 -> 1010 -> 1111 -> 1100 -> 1111 -> 1010 -> 1111
前3条指令解决S1/S2,如果是S3的话,保持在S3
第4条指令跃迁至S0/S1/S2

合并S4.1/S4.2为S4
S4 -> S0:
指令1000可让S4跃迁至S0/S1/S2/S3

(S1 + S2 + S3 + S4) -> S0:
指令1111、1010、1100让S4仍然保持S4
所以依然可采用叠加策略。

综上,最终依次执行指令集如下
1)0000              S0的情况
2)1111              S1的情况
3)1010 -> 1111      S2的情况
4)1100 -> 1111 -> 1010 -> 1111 S3的情况
5)1000 -> 1111 -> 1010 -> 1111 -> 1100 -> 1111 -> 1010 -> 1111

显见,无唯一解。给出的解可能不是最少步骤的最优解,但满足题目要求。以上。

【 在 weierstrass (没昵称) 的大作中提到: 】
: 同学在群里发的,被小朋友的奥数题难住了
: 你被蒙住了双眼,什么都看不见。你的正前方有一张方桌,桌子的四个角上各有一枚硬
: 币。有一个机器人根据你的指令操作硬币。你可以发出指令让机器人翻转任何你指定位
: 置的硬币。例如:翻转左上和右下两枚硬币;翻转全部四枚硬币。机器人每次按你的指
: 令操作完成后,桌子会随机顺时针或逆时针旋转90、180、270、360度,然后等待你下
: 一次指令。当四枚硬币全部正面朝上时,机器人立即发出声音通知你(其他任何时候它
: 不会发声),游戏结束。
: 问题:你可以通过有限次指令保证使得游戏结束吗?若能,请给出你的指令步骤。若不
: 能,请证明。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 138.]


此主题相关图片如下:

[删除]

 
llaalways
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: llaalways (熊大), 信区: Joke
标  题: Re: 奥数题求助
发信站: BBS 未名空间站 (Wed May  5 16:15:42 2021, 美东)

这个是对的。

两对对角线的就只有3种状态。
case 1. 两对对角线都同状态, 第1个3步内成功。
case 2. 两对对角线都不同状态,翻转相邻两个,变成case 1 .

case 3. 一对相同,一对不同,翻转任何一个, 变成,case 1或case 2。

最多15次必定成功


【 在 SLE (嗯,就这样定了。) 的大作中提到: 】
: 好像后两种情况的讨论有一些纰漏。修改一下。
: 开始三步不变。
: 如果没有结束,就翻转左上和右上,然后重复那三步。
: 如果还是没有结束,就翻转任何一个,再重复开始三步。
: 如果还是没有结束,就翻转左上和右上,然后重复开始三步。
--
🥧💌llaalways
※ 修改:·llaalways 於 May  6 08:11:35 2021 修改本文·[FROM: 2607:fb90:25dd:d]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 107.]

 
llaalways
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: llaalways (熊大), 信区: Joke
标  题: Re: 奥数题求助
发信站: BBS 未名空间站 (Thu May  6 08:29:31 2021, 美东)

如果初始状态是全部朝上,而机器人不提醒。
那就要在开始时加一次保持原状你指令。
这样最多16个指令完成

【 在 llaalways (熊大) 的大作中提到: 】
: 这个是对的。
:
: 两对对角线的就只有3种状态。
: case 1. 两对对角线都同状态, 第1个3步内成功。
: case 2. 两对对角线都不同状态,翻转相邻两个,变成case 1 .
:
: case 3. 一对相同,一对不同,翻转任何一个, 变成,case 1或case 2。
:
: 最多15次必定成功
:

: 【 在 SLE (嗯,就这样定了。) 的大作中提到: 】
: : 好像后两种情况的讨论有一些纰漏。修改一下。
: : 开始三步不变。
: : 如果没有结束,就翻转左上和右上,然后重复那三步。
: : 如果还是没有结束,就翻转任何一个,再重复开始三步。
: : 如果还是没有结束,就翻转左上和右上,然后重复开始三步。
--
☆ 发自 Android 大灌 20.11.08
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 107.]

[分页:1 ]
[快速返回] [ 进入肚皮舞运动讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996