翻硬币与青蛙跳
IMO的翻硬币今（2019）年的国际数学奥林匹亚数学竞赛（InternationalMathematicalOlympiad,IMO）甫于7月在英国巴斯（Bath）举办。IMO每队6人，只考6题，每题7分，其中第五题是相当有趣的翻硬币问题。
问题：小明把n枚硬币由左至右排成一列，如果恰有k枚正面（head, H）朝上的硬币，他就把从左边数来第k枚硬币翻面过来。一直这样翻下去，直到所有的硬币都是背面（tail, T）朝上为止，例如从THT会这样翻：
THT→HHT→HTT→TTT
亦即翻3次后停止。
（1）请证明不管一开始硬币正反如何，一定能翻到全部背朝上。
（2）求出所有2n种硬币状态所需要翻的次数平均。
例如说，3个硬币有23=8种初始状态，把每一种都试一
试，会有以下的结果：HHH→HHT→HTT→TTT（3次）
HHT→HTT→TTT（2次）
HTH→HHH→HHT→HTT→TTT（4次）
HTT→TTT（1次）
THH→TTH→HTH→HHH→HHT→HTT→TTT（6次）
THT→HHT→HTT→TTT（3次）
TTH→HTH→HHH→HHT→HTT→TTT（5次）
TTT（0次）
的确，不管初始状态如何，最后都可以翻成全部反面朝上。而且，平均需要翻
3+2+4+1+6+3+5+0/8=3（次）
一般来说，n个硬币时平均要几次呢？答案公布在最后，读者可以先阖上杂誌试试看。......
问题：小明把n枚硬币由左至右排成一列，如果恰有k枚正面（head, H）朝上的硬币，他就把从左边数来第k枚硬币翻面过来。一直这样翻下去，直到所有的硬币都是背面（tail, T）朝上为止，例如从THT会这样翻：
THT→HHT→HTT→TTT
亦即翻3次后停止。
（1）请证明不管一开始硬币正反如何，一定能翻到全部背朝上。
（2）求出所有2n种硬币状态所需要翻的次数平均。
例如说，3个硬币有23=8种初始状态，把每一种都试一
试，会有以下的结果：HHH→HHT→HTT→TTT（3次）
HHT→HTT→TTT（2次）
HTH→HHH→HHT→HTT→TTT（4次）
HTT→TTT（1次）
THH→TTH→HTH→HHH→HHT→HTT→TTT（6次）
THT→HHT→HTT→TTT（3次）
TTH→HTH→HHH→HHT→HTT→TTT（5次）
TTT（0次）
的确，不管初始状态如何，最后都可以翻成全部反面朝上。而且，平均需要翻
3+2+4+1+6+3+5+0/8=3（次）
一般来说，n个硬币时平均要几次呢？答案公布在最后，读者可以先阖上杂誌试试看。......
上一篇：翻盖隔层小手包製作教程
下一篇：翻糖蛋糕世界夺冠 技职教育扬威
热门专题
-
08
07月
带你睇澳门游戏博览带你睇澳门游戏博览
今日编辑Jack过咗去澳门，并冇去大三巴观音像同妈阁庙睇优美景致，更唔係去玩两手，而係去咗「澳门游戏
-
08
07月
带你破解最常见的 4 大性爱迷思：根本没 G 点这回事，男人
关于性爱的话题是怎幺聊都聊不完，特别是那些特别有争议的性爱迷思。但是很多的性爱迷思是能够透过医学来解
-
08
07月
带你穿梭丹麦、德国、瑞典「日常美学」，最吸引人的是满额送巴黎
一年一度玛黑生日活动「玛黑週年盛宴」于 8/29 正式展开，选在在夏天的尾巴，玛黑家居丝毫不减热情，
-
08
07月
带你观星及体验星空拍摄︰请即报名参加 「夜摄初夏星流迹」摄影活动！
夏天是适合观星、拍摄银河的季节，天空的微粒较少、能见度较高，可以较容易拍摄到银河及其他星系。 与女子
-
08
07月
带你解析脸红心跳的「春梦」，其实暗示你很多事情
你是否曾从春梦中醒来，发现自己在梦里不是和另一半做爱，竟是跟别人做爱，而心生内疚吗？「现在，你可以大
-
08
07月
带你解锁兔子手工的100种做法，收藏起来慢慢看！
毛线小白兔然鹅，这样可爱的DIY小白兔玩偶，你见过吗？轻松易学不复杂，只要一团毛线、剪刀、胶水等工具