大学入試数学に置けるヨセフス問題

入試問題で,
Josephus1.jpg
と言う漸化式が与えられる事が有りますが,これはヨセフス問題と言います(問題集では人名が書かれてい無い事が多いが点数に結び付か無いからか著者が無知だからかは不明).人名が付いている程の有名問題で日大,一橋大,鳥取大等で出題された事が有ります.本来は,

番号の付いた n個の碁石を円形に並べ,2, 4, 6, ・・・ と順に取り除いて行く時,最後に f(n)番目の碁石が取り除かれる.JosephusFig.jpg

から漸化式を導きます.碁石は別に右回りに並べても構いません.多角形の頂点に番号を付ける時は左回りなので左回りに並べましたが色々な文献では右回りに並べている物ばかりですね.
Wikipedia -> https://ja.wikipedia.org/wiki/%E3%83%A8%E3%82%BB%E3%83%95%E3%82%B9%E3%81%AE%E5%95%8F%E9%A1%8C
等に詳しく書かれていますが,今回は大学入試に必要な知識や考え方に限ってまとめて見ようと思いますが何だか長く成ってしまいました.初見だと難しい問題だと思いますが,ここに書いて有る事位はマスターして置けば的中した時にラッキーですね.

n を書き換えて,
Josephus2.jpg
としている問題も有りますが同じ事です.

[プロローグ] n が小さい f(n) を求める.
これは初見では実験すべきですが,
 f(1)=1,
 f(2)=1, f(3)=3,
 f(4)=1, f(5)=3, f(6)=5, f(7)=7
 f(8)=1, f(9)=3, f(10)=5, f(11)=7, f(12)=9, f(13)=11, f(14)=13, f(15)=15,
 f(16)=1, ・・・
 ・・・

と n が 2 の冪毎に 1 にリセットされる奇数列でその直前は不動点で有る事を押さえて置きましょう.

[第1章] 漸化式の導出
i) n = 2n の時,
初めに,2, 4, ・・・, 2n と n個の碁石を除くと,残った碁石は n個で 3 から除く事に成る.
JosephusEven.jpg
表の上の行は,1, 2, ・・・, n の n個を 2 から除く時,i番目の碁石は i.最後は f(n)番目が除かれる事を表す.
表の下の行は,1, 3, ・・・, 2n-1 の n個を 3 から除く時,i番目の碁石は 2i-1.従って最後は f(n)番目の碁石である 2f(n)-1 が除かれる.
f(2n) = 2f(n) -1.
ii) n = 2n+1 の時,
初めに,2, 4, ・・・, 2n, 1 と (n+1)個の碁石を除くと,残った碁石は n個で 5 から除く事に成る.
JosephusOdd.jpg
表の上の行は,1, 2, ・・・, n の n個を 2 から除く時,i番目の碁石は i.最後は f(n)番目が除かれる事を表す.
表の下の行は,3, 5, ・・・, 2n+1 の n個を 5 から除く時,i番目の碁石は 2i+1.従って最後は f(n)番目の碁石である 2f(n)+1 が除かれる.
f(2n+1) = 2f(n)+1.

[第2章] f(n) の 1般項の証明
m, r ∊ ℤ,
n = 2m+r, 0≤m, 0≤r≤2m-1 として,f(n) = 2r+1.

です.これは m に付いての r を偶奇に分けた数学的帰納法に依り示されます.初見で難しいのは,まず 1般項を自分で文字を使って設定する事,その文字の範囲の設定でしょう.この問題に限りませんが文字の範囲は(特に端の値を)自分で代入してチェックするのが確実です.1≤m としても良いです(その場合,m -> (m-1) と成るから表記も微妙に変わる).好みの問題です.
m = 0, 1 では成立.有る m で成立すると仮定すると m+1 では,
i) r = 2q (0≤q≤2m-1) の時,
 f(2m+1+2q)
= f(2(2m+q))
= 2f(2m+q)-1 (∵ 漸化式)
= 2(2q+1)-1 (∵ m での仮定)
= 2r+1.
ii) r = 2q+1 (0≤q≤2m-1) の時,
 f(2m+1+2q+1)
= f(2(2m+q)+1)
= 2f(2m+q)+1 (∵ 漸化式)
= 2(2q+1)+1 (∵ m での仮定)
= 2r+1.
∴ 数学的帰納法は完結.

[第3章] 数値計算
漸化式ないし 1般項を利用して具体的な数値計算をさせる事が有りますが,その殆どが,
 f(2m) = 1, f(2m-1) = 2m-1
を利用する物ばかりです.覚えて置きましょう.証明は n = 2m, 2m-1 を漸化式の右辺に代入すれば帰納的に明らかです.実は,am = f(2m), bm = f(2m-1) 等と置く事に依り漸化式を解く事も可能です.
気を付けるべきは上向きの帰納法で証明した場合や漸化式で求めた場合,不動点の 1意性が言え無い事でしょう.不動点の 1意性を言う為には漸化式から不動点は奇数かつ 2進法表示して下向きの帰納法で言うか,[第2章] の帰納法の後,2m+r = 2r+1 ⇔ r = 2m-1 を言う.
 f(1+2+22+・・・+2m)
= f(2m+1-1)
= 2m+1-1
も良くさせられる計算です.1+2+22+・・・+2m は等比数列の和公式でも良いのですが,2進法表示を利用すると,
2m.jpg

他,予想問題として今年は 2017年なので,
 f(2017)
= f(1024+993)
= 2・993+1
= 1987.
です.

[エピローグ]
除くのが 1個置きでは無い場合も考え方の基本は変わら無いと思います.又碁石を取り除か無いと言う設定で全ての番号の碁石を選べるかどうかは,gcd(a, b) = 1 の時,b, 2b, ・・・, ab を a で割った余りは全て異なり,{ 0, 1, 2, ・・・, a-1 } と集合として 1致すると言う有名事項と成ります.
ヨセフス問題はその場で考えるべき問題にカテゴライズしている人もいるかも知れませんが人名が付いている程の有名問題なのでマスターして置くべきです.

Post a comment

Private comment

プロフィール

A6033x

Author:A6033x
数検1級取得しました.
個人的な連絡は,hermitvseinsiedler@_@gmail.com
まで(@_@は@に置換すること).
あまり見ないかも知れないのでその場合は twitter の方へ.
twitter:https://twitter.com/A603zw
そもそもネット接続自体減らして行く事になりますが...

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR