不清楚什么是约瑟夫环，按笨办法试证明一下

A "card" is a half-card. A "whole card" is what is torn into two half cards.

Denote each card with a name. The pile of 8 cards is: ABCDabcd, where Aa is a pair that used to form a whole card. So are Bb, Cc, Dd. The distance of any pair is 4. Take operations below as suggested by Magician Liu.

Op1: shift by N times in a circle. For example, shfiting twice results in: CDabcdAB. Shifting doesn't change the distance of any pair. Later, all we care is to keep a card and find its counterpart, so we can actually still denote the shifted pile as ABCDabcd.

op2: take top 3 cards and insert them anywhere in the middle: DaABCbcd. Now, top card D and bottom card d form a pair. This is important.

op3: Remove top card, which is "D", and hide it. The queue becomes: aABCbcd. What we care is card "d". So, simply denote all other cards as "x". The queue is: xxxxxxd, or to make it easier to read: Queue=123456d

op4: Take top 1~3 cards and insert it in the middle. This doesn't change anything. Q=123456d.

op5: Remove top 1 or 2 cards. Q = xxxxxd or xxxxd. From now on, there are two cases in every step below.

op6: Shift 7 times: Q= xxxxdx or xxdxx

op7: shift 1 and remove top card. Q= xxdxx or dxxx

op8: repeat op7: Q=dxxx or xxd

op9: repeat op7: Q=xxd or dx

op10: repeat op7: Q=dx, or d (This is done by now)

op11: repeat op8: Q=d

Now that "d" remains in queue, it matches the originally saved card "D".

From op7 to op11, it repeats the same operations: shift 1 and remove top card. This seems to preserve certain card in the queue, and eventually only that card remains in queue. Not sure why.

所有跟帖： 

• 推广证明一下最后几步，可能就是大家说的约瑟夫环的特例 -monseigneur- ♂ (1784 bytes) () 02/11/2024 postreply 11:48:07