每周一题 by 万精油: 桌面上的牌

fzy

桌面上的牌

Difficulty: +++ to ++++

桌子上放着三张牌面朝上的牌：ＡＣＥ，ＫＩＮＧ，ＱＵＥＥＮ。它们的位置可以是左中右三个位置的任何一个。也可能两张牌或三张牌都放在同一个位置。这种时候你只能看见上面那张牌，看不见下面的牌（根本不知道下面有没有牌）。你每次可以把一张牌移到另一个位置（放在一个空位或另一张牌上面都可以）。如果三张牌以ＡＫＱ的顺序放在最左面的位置上，某一盏灯就会亮，也就是说你过关了。唯一的问题是，你完全失去了短期记忆。记不得上次的牌的位置或任何以前的操作过程。你的所有信息只能从你现在能看见的牌得到。我们的问题是让你设计一套操作程序，使得不管初始是什么情况（三张牌在什么位置），你都能过关。 www.ddhw.com

把这个问题推广到任意多牌，如果有Ｎ张牌放在桌子上左中右三个位置，上面有Ｎ个不同的数，你是否能把它们按从小到大的顺序放在最左面的位置上?

We may also consider it as a prisoners' problem. Prisoners are randomly called into the room to move one card. He can only see the top cards. Once all cards are ordered correctly on the left stack, they will be released. Furthermore, we may assume each prizoner is called only once. (Suppose there are enough prizoners, thousands.)

www.ddhw.com

 

fzy

This is my solution. There are should be others. Assuming the final order is smallest on top.www.ddhw.com 1. When there are no empty stacks: If the middle card is the biggest, move the second biggest card to the middle stack. Otherwise move middle to cover the smaller card. 2. When the left stack is empty and middle is not: If middle is bigger than right or right is empty, move the middle card to right. Otherwise move middle to left. www.ddhw.com 3. When the middle stack is empty and right is not: If right is smaller than left or left is empty, move right to left. Otherwise move right to middle. 4. When the right stack is empty and left is not: If left is bigger than middle or middle is empty, move left to middle. Otherwise move left to right. www.ddhw.com The basic idea is to set the middle stack to the correct order. When done, dump it to the right stack in reversed order, and then dump it back to left in the correct order. If failed in any step, start the next round with the middle stack again. In each round, the "orderliness" is better than the previous round. So in finite steps we will achieve total orderliness. It is a very slow process, taking O(N^2) steps or more. www.ddhw.com I never formally proved that the approach always works, although I think it can be proved by induction. I tried to find a simple proof such as assigning an orderliness value to each state, but was not successful.  (I did simulate it in my computer for a few thousand times with 100 cards, and that should be good enough ) So anybody is still welcomed to prove it or to provide another method.www.ddhw.com