カードトリック問題の意味について

質問

こんにちは。前に質問させてもらい、
内容として
「21 枚のカードがあり、絵が見えるように上にして、三枚ずつ七行に並べていく。七行・三列の配列で考える。
そして、観客に一枚を選ばせ、三列のうちのどの列なのか言わせる。カードは手渡さないで、指示された列が真ん
中になるよう各列のカードを集めたあと、また繰り返す。このイカサマを 3ラウンド繰り返せば、イカサマ師は観
客の選んだ札を言い当てられる。」
ということで、理解できました。そして、そのあとの英文のないようで、数式が出てきているのですが、
どのような意味なのかが、読みとれません＞＜
その内容は、
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)

いつも質問させてもらい、本当に助かってます。時間がある方、アドバイスお願いします＞＜

回答No.1

noname#101087 · ベストアンサー

Good xxxxx !
よくできたトリックのようです。手際が良くないとバレそうですけど。
P*Q 枚の札を P 列(columns)、Q 行(rows)に配列した場合(前記例では、P=3 and Q=7)を解析してます。
-------------------------------------------------------------
P, Q が奇数の場合、P=2p+1 および Q=2q+1 (p>=1 and q>=1)とする。(前記例では、p=1 and q=3)
重ねた札のテッペンから順番に 1, 2, 3, ... と番号付けすると、真ん中の札の上下には (P*Q-1)/2 枚ずつあり、(前記例では10枚ずつ)
真ん中の札の番号(C)は C = (P*Q+1)/2 = p*Q+q+1 = q*P+p+1 である。(前記例では C=11)

トリック・プレイ第 n ラウンドの直後、選ばれた札が重ね札のテッペンから X(n) 番目だったとしよう。
次の(n+1)ラウンドでそれが第 r 行に現れるとすれば、その r は X(n)/P 以上の整数で最小の値のものである。
m>=Y の最小整数を <Y> と書けば、選ばれた札が真ん中の列になるよう札を重ねなおしたあと、選ばれた札の番号 X(n+1) は次のような関係を満たす。
　X(n+1) = p*Q+<X(n)/P>

この回帰関係は非線形で、初期値 X(0) も不明である。
だが、この情報は問題の完全解を得るのに充分なもので、このトリックの動きは、関数の繰り返し適用が不動点へ引きつけて収束することのヒントになる。
問題の対称性から、選ばれた札が重ね札の上半分にあるだけに注目すれば良い。
そこで 1=<X(0)=<C と想定してみる。上記の帰納法により、すべての n について X(n)=<C である。そうすると、
　X(n+1) = p*Q+<X(n)/P> = <p*Q+<C/P> = p*Q+<(q*P+p+1)/P> = p*Q+q+1=C
同様にして、Xn=C のとき X(n+1) = C である。

また X(1)>p*Q の場合は、
　pO<X(1)<X(2)<....<X(N-1)<X(N)=C=X(N+1)=X(N+2)=....(不動点 !)
となる整数 N があることを示せる。

(前記例では、第3ラウンドで札を行列に配列したとき、選ばれた札は必ず第4行にあり、観客にどの列にあるかを指示させたとたんに、どの札かがわかる。もう一度札を重ねて行列に配りなおせば、選ばれた札はど真ん中へ。もっと繰り返すと、いつもど真ん中なのでネタばれしそう)
-------------------------------------------------------------
バナッハ(Banach)の不動点定理 (縮小写像は唯一つの不動点を持つ) もどきの説明です。
もっとも、「札師」はそんな定理なんぞ知らなくてもやれてます。