カードトリック問題について
こんにちは。カードについて書いてあることはわかるのですが、内容がよくわかりません。アドバイスお願いします＞＜
The card trick
Consider the following card trick. The trickster has 21 cards in a pack; the audience chooses one card (leaving it in the pack) and the pack is shuffled. The trickster deals out the cards face up in a row of three, then in a second row of three, and so on, the cards finally making an array of seven rows of three cards each(or three columns of seven cards each). The audience states which column the chosen card is in, the trickster collects up the columns to reform the pack ensuring that the chosen column is placed between the other two. This process (which we call a round) is repeated twice more. The trickster can now tell the audience which card was chosen, for it will be the card in the centre of the pack with ten cards before it and ten cards after it. Of course, the trickster can add the usual embellishments to deflect the audience's attention from the crucial issues.
Why does this trick work? What will happen if we take a different size pack? We shall analyse the trick for a pack of any size, explain why it works, and show how many rounds are needed. Unexpectedly perhaps(but only at first), we shall see that if the trick were to be carried out with an array of, for example, 999×999 cards, the chosen card would find its way to the centre of the pack in just two rounds.
The convergence of the process
We consider a pack with PQ cards which will be arranged in an array of P columns, each of Q cards or, equivalently, Q rows, each of P cards. The case described above is with P=3 and Q=7. We shall only analyse the case when P and Q are odd and greater than 1 (leaving the other cases to the interested reader), and we write P=2p+1 and Q=2q+1, where p>=1 and q>=1. We are interested in the central card in the pack; this has exactly 1/2(P×Q-1) cards above and below it and, labelling the cards 1,2,3,... from the top of the pack, the central card is labelled C, where
C=1/2(P×Q+1)=p×Q+q+1=q×P+p+1.
Suppose now that the chosen card lies in the Xn th position in the pack after n rounds have been played. During the play in the next round the first Xn cards will be spread out over the first few rows, and the chosen card will occur in the r th row, where r is the smallest integer greater than or equal to Xn/P. We write <Y> for the smallest integer m satisfying m>=Y. It follows that, after reforming the pack by ensuring that the column containing the chosen card is the
central column, the position Xn+1 of the chosen card will satisfy the recurrence relation
Xn+1=pQ+<Xn/P>.
This is a recurrence relation, but it is non-linear, and we do not know the initial value X0 of the chosen card in the pack; all we know is that 1=<X0=<PQ. Nevertheless, this information is sufficient to give us a complete solution of our problem, and we shall see that the dynamics of the trick is reminiscent of the convergence of iterates of a function towards an attracting fixed point of the function.
We begin by noting that there is a symmetry in the process, so that we may confine our attention to those cases where the chosen card lies in the top half of the pack; thus we may assume that 1=<X0=<C. An induction argument now shows that, for all n, Xn=<C. For suppose that Xn=<C; then
Xn+1=pQ+<Xn/P>=<pQ+<C/P>
=pQ+<(qP+p+1)/P>
=pQ+q+1=C
This argument also shows that if Xn=C, then Xn+1=C.
Observe next that X1>pQ. We shall now show that there is some integer N with
pO<X1<X2<....<Xn-1<Xn=C=Xn+1=Xn+2=.... ・・・(1)
