順番に取り除き最後に残るカード

質問

1 から n の番号がそれぞれ書かれた n 枚のカードがある。
このカードを昇順に並べ、小さい方から t 番目のカードを順に取り除くことを考える。
t は n を超えてもよい。
1回目は t 番目のカードを取り除き、2回目以降は、その前に選ばれたカードから t 番目のカードを取り除く。
最大数のカードの次は、最小数のカードに戻る。

取り除くカード : #
既に取り除いたカード : -

▼ t = 1 のとき
1 2 3 4 5 6 7 8
# 2 3 4 5 6 7 8
- # 3 4 5 6 7 8
- - # 4 5 6 7 8
- - - # 5 6 7 8
- - - - # 6 7 8
- - - - - # 7 8
- - - - - - # 8
- - - - - - - 8
最後に残ったカードは 8

▼ t = 2 のとき
1 2 3 4 5 6 7 8
1 # 3 4 5 6 7 8
1 - 3 # 5 6 7 8
1 - 3 - 5 # 7 8
1 - 3 - 5 - 7 #
1 - # - 5 - 7 -
1 - - - 5 - # -
1 - - - # - - -
1 - - - - - - -
最後に残ったカードは 1

▼ t = 3 のとき
1 2 3 4 5 6 7 8
1 2 # 4 5 6 7 8
1 2 - 4 5 # 7 8
# 2 - 4 5 - 7 8
- 2 - 4 # - 7 8
- # - 4 - - 7 8
- - - 4 - - 7 #
- - - # - - 7 -
- - - - - - 7 -
最後に残ったカードは 7

▼ t = 4 のとき
1 2 3 4 5 6 7 8
1 2 3 # 5 6 7 8
1 2 3 - 5 6 7 #
1 2 3 - # 6 7 -
1 # 3 - - 6 7 -
# - 3 - - 6 7 -
- - # - - 6 7 -
- - - - - 6 # -
- - - - - 6 - -
最後に残ったカードは 6

自然数 n, x(≦n) が与えられたとき、最後に残るカードが x となるような t を求めるにはどのように考えればよいのでしょうか…？
また、題意を満たす t のうち、最小の t を求める導出式は考えられるのでしょうか…？
ご教示いただければ幸いです。

回答No.2

lick6 · ベストアンサー

/≡ は ≠ みたいに捉えてください

t = f(N,x) とでもすると

N = 2 で x = 1 のとき t は偶数 ⇔ t /≡ 1 (mod 2)
　　　　 x = 2 のとき t は奇数 ⇔ t /≡ 0 (mod 2)

何らかの周期性みたいなのはあるかもしれないけど、具体的に N,x で表せるかは解らない

N = 3 で x = 1 のとき t は少なくとも 3m or 3m+2 ⇔ t /≡ 1 (mod 3)
このとき t = f(2,1) の状態になる
∴ t /≡ 1 (mod 3) かつ t /≡ 1 (mod 2)

N = 3 で x = 2 のとき t は少なくとも 3m or 3m+1 ⇔ t /≡ 2 (mod 3)
ここで t ≡ 0,1 (mod 3) で f(2,1) か f(2,2) かの場合分け

N = 3 で x = 3 のとき t は少なくとも 3m+1 or 3m+2 ⇔ t /≡ 0 (mod 3)
このとき t = f(2,2) の状態になる

・・・おそらく最後に残る x が何番目かが重要になってくるとおもいます。
例えば全部で８個のとき、３番目が選ばれるのは t = 3 , 11 , 19 , 27 , … , 75 , …
ところが次に７個のとき、５番目が選ばれるのは t = 5 , 12 , 19 , 26 , … , 75 , …
当然一定の周期でどちらも満たす t の値が現れます。
x が端ならば多少考えやすいかもしれませんが、真中にあった場合それこそ何億何兆周期で現れてくるので t は ○○ で割り切れる 等といった程度が限界だと思います。

お礼

回答ありがとうございます。
示していただいたように小さなNで実際に追跡して考えると題意を満たす t を絞ることができますが、
N, x に対する t を直接的に導出することは限りなく不可能ですよね…。
N, t に対する x すら漸化式でしか表現できていないのに、その逆を行うことは巨大数の素因数分解と同様に困難なのかもしれません。

頂いた回答、参考になりました。
できる限り研究してみたいと思いますが…難しそうです。
ありがとうございました。

回答No.1

mis_take

これは「ままこだて」というものです。
「ままこだて」で検索するとよいでしょう。

お礼

回答ありがとうございます。
継子立てについては N, t が与えられたときに x を導出する方法はいくつかのページで紹介されていましたが、
t が 3 以上のときは、漸化式で再帰的に x を求めるものでした。
t=2 に関しては、N から x を簡単に導けますが、
N, x が与えられたときに x を最後に残すような t を求める方法について考えております。

N, x から t を導出することは自然数分割問題と同様に容易ではなさそうですが…
これについての一般化は、N, t に対する漸化式止まりなのでしょうか…？