文档章节

第60届IMO 第5题

o
 osc_g8254g7s
发布于 2019/08/19 23:16
字数 511
阅读 5
收藏 0

精选30+云产品,助力企业轻松上云!>>>


题目
 
巴斯银行发行的硬币在一面上铸有H,在另一面上铸有T,哈利有枚这样的硬币并将这些硬币从左至
右排成一行,他反复地进行如下操作:如果恰有k(>0)枚硬币H面朝上,则他将从左至右的第k枚硬币
翻转;如果所有硬币都是T面朝上则停止操作,例如:当n=3,并且初始状态是THT,则操作过程为
THT→HHT→HTT→TTT,总共进行了三次操作后停止

证明:对每个初始状态,哈利总在有限次操作后停止

解答
 
将问题转化为:H的个数总会在有限次操作后-1
设最右端的H坐标为x,易知x>=k
当x=k时,前x个全为H,后面全为T,易知经过x次操作后,变为全T
当x>k时,分为两种情况
1)当第k个为H时,H翻转变为T,H个数-1
2)当第k个为T时,T翻转变为H,H个数+1,向右走,因为第k到第x(包含x)必然有H,设第k个右侧第一个H坐标为k+a,则k到k+a全是T,因为只要是T就会翻转变为H,又会往右走,所以会一直向右走,直到遇见右侧第一个H(坐标k+a),之后H变为T,H的个数-1,向左走,又因为此时从k到k+a-1,全已经翻转变为了H,所以当K+a的H变为T之后向左走又会导致左边的H变为T,H的个数又减少,又会向左走,直到回到坐标k,又由于k为H,所以H-1,H的个数变为k-1
 
综上所述,任何情况都会经过有限步使H个数-1,所以任何情况都会经过有限步使H个数变为0即全为T,即总会经过有限次操作后停止。
 
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

unity的UGUI之中锚点(Anchors)和中心点(Pivot)、Shift和Alt键功能

在UGUI的控件属性之中,最上方的Rect Transform一栏可以看到锚点和中心点: 锚点Anchors 控件用于定位自身的基准点 可以点击左上角的方框,在其中选择锚点的不同方式: 注意图中,黄色的小点...

路过暴风
46分钟前
7
0
如何将div放置在其容器的底部? - How can I position my div at the bottom of its container?

问题: Given the following HTML: 鉴于以下HTML: <div id="container"> <!-- Other elements here --> <div id="copyright"> Copyright Foo web designs </div> </div> I would like #cop......

富含淀粉
今天
10
0
Distinct()与lambda? - Distinct() with lambda?

问题: Right, so I have an enumerable and wish to get distinct values from it. 是的,所以我有一个可枚举的,并希望从中获得不同的值。 Using System.Linq , there's of course an ext......

法国红酒甜
今天
16
0
学习编写编译器[关闭] - Learning to write a compiler [closed]

问题: Preferred languages : C/C++, Java, and Ruby. 首选语言 :C / C ++,Java和Ruby。 I am looking for some helpful books/tutorials on how to write your own compiler simply for......

技术盛宴
今天
17
0
OSChina 周一乱弹 —— 毛巾又怎么样?!我在乎的是大姐姐温柔的怀抱!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《雨 因你而下,于你而止》- Seto 手机党少年们想听歌,请使劲儿戳(这里) @Dan...

小小编辑
今天
48
2

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部