Yamagishi Complexity Torus Lab山岸勇輝ラボ

【論文614】一人おきに除く輪で最後に残る席は、人数を二進法で書いて先頭の 1 を末尾へ回した数である

要旨

$n$ 人が $1$ から $n$ の番号順に輪になって座り、$1$ 番から数えて $k$ 人目ごとに輪から外れていく。最後に残る席は何番か(ヨセフスの問題)。一人おき($k=2$)と二人おき($k=3$)で、輪を実際に回した結果と式を突き合わせる。新しい定理も法則も主張しない。

第一に、一人おきなら、残る席は二進法の回転で決まる。$n$ を二進法で書き、先頭の $1$ を末尾へ回した数が、最後に残る席である。$n=1$ から $1024$ のすべてで、輪を回した結果と一致した。$41$ 人なら $101001$ が $10011$ になって $19$ 番、$100$ 人なら $73$ 番、$1000$ 人なら $977$ 番である(第2節)。

第二に、一人おきでは、残る席はいつも奇数である。回した数の末尾はいつも $1$ だからで、$1024$ 通りすべてで奇数だった。人数が $2$ の冪なら、回しても $1$ に戻り、$1$ 番が残る(第2節)。

第三に、これが本稿の芯である。一人おきの輪は、一周ごとに人数を半分にする二進法の操作である。$n=2^m+L$ のとき、$L$ 人を外した時点で残りは $2^m$ 人になり、次に数え始める席 $2L+1$ がそのまま最後に残る。$2^m$ 人の輪では、一周ごとに半分が外れて最初の席が生き残り続けるからである(第3節)。

第四に、分離子は、何人おきに除くかである。二人おき($k=3$)では、二進法の回転のような短い形は無く、一人ずつ減らす漸化式か、定数を使う閉じた式で出す。$n=1$ から $1000$ のすべてで、輪を回した結果と漸化式が一致し、$41$ 人では最後の二人が $16$ 番と $31$ 番だった。残る席が偶数になる人数は $1000$ のうち $500$ で、奇数の偏りは消える(第4節)。

キーワード:ヨセフスの問題、二進法、漸化式、除去の輪、再帰。

射程(何を示さないか)

新しい定理も法則も主張しない。一人おきの場合の二進法の式と、一般の $k$ の漸化式は、いずれも既知である(グラハム、クヌース、パタシュニクの本、ボールとコクセターの本などにある)。一般の $k$ の漸近式は扱わない。$k=2$ と $k=3$ の二つだけを数える。伝承の史実は論じない。$41$ 人と $k=3$ の組は、数を確かめる例として使うだけである。既刊との関係:論文602 はニムの勝ち負けを繰り上がりのない足し算で、論文608 はパスカルの三角形の奇数を二進法の $1$ の数で示した。本稿でも答は二進法の桁で決まり、先頭の $1$ を末尾へ回すという別の操作として現れる。加えたのは、$1024$ 人までで輪を回した結果と式を突き合わせたこと、回転の式がなぜ成り立つかを、$2^m$ 人に減った時点で説明したこと、分離子を「何人おきか」に置き、$k=3$ では二進法の回転のような短い形が無く偶奇の偏りも消えることを数で示したことである。

1. 記法と問い

設定:$n$ 人が番号 $1$ から $n$ の順に輪になる。$1$ 番から数えて $k$ 人目を輪から外し、次の人から数え直すことを、一人になるまで続ける。最後に残る番号を $J_k(n)$ と書く。

問い:$J_2(n)$ に式はあるか。なぜその式になるか。$k=3$ では何が変わるか。

2. 一人おき

計算 2.1:$n=1$ から $1024$ まで、輪を実際に回して一人ずつ外し、最後に残る番号を求めた。それを、$n$ の二進法の先頭の $1$ を末尾へ回した数と比べると、すべて一致した。

人数 $n$ 二進法 残る席 残る席の二進法
$5$ $101$ $3$ $11$
$6$ $110$ $5$ $101$
$7$ $111$ $7$ $111$
$8$ $1000$ $1$ $1$
$41$ $101001$ $19$ $10011$
$100$ $1100100$ $73$ $1001001$
$1000$ $1111101000$ $977$ $1111010001$
$1024$ $10000000000$ $1$ $1$

観察 2.2 一人おきでは、残る席はいつも奇数である。先頭の $1$ を末尾へ回すので、回した数の末尾はいつも $1$ になる。$1024$ 通りすべてで奇数だった。偶数の席の人は、一周目で必ず外れる。

観察 2.3 人数が $2$ の冪なら、$1$ 番が残る。$2^m$ は二進法で $1$ のあとに $0$ が並ぶので、先頭の $1$ を末尾へ回すと $1$ になる。$n=1$ から $1024$ までの $2$ の冪、$11$ 通りすべてで $1$ 番が残った。

3. なぜ回転になるか

観察 3.1 これが本稿の芯である。一人おきの輪は、一周ごとに人数を半分にする二進法の操作である。$2^m$ 人の輪では、一周で偶数の席の半分が外れて $2^{m-1}$ 人が残り、次の周も $1$ 番から数え始める。これを繰り返すと $1$ 番が最後に残る。$n=2^m+L$($0\le L<2^m$)なら、$2,4,\dots,2L$ 番の $L$ 人を外した時点で残りは $2^m$ 人になり、次に数え始めるのは $2L+1$ 番である。そこから先は $2^m$ 人の輪と同じなので、$J_2(n)=2L+1$ になる。

観察 3.2 $2L+1$ が「先頭の $1$ を末尾へ回した数」である。$n=2^m+L$ の二進法は、先頭の $1$ のあとに $L$ の $m$ 桁が並ぶ。先頭の $1$ を取り去ると $L$、それを一桁左へずらして末尾に $1$ を置くと $2L+1$ である。$41=32+9$ なら $2\times9+1=19$ で、$101001$ から $10011$ への回転に一致する。

4. 分離子

計算 4.1:二人おき($k=3$)で、$n=1$ から $1000$ まで輪を実際に回した結果と、一人ずつ減らす漸化式 $J_3(n)=((J_3(n-1)-1+3)\bmod n)+1$ を比べると、すべて一致した。

人数 $n$ 残る席($k=3$)
$5$ $4$
$6$ $1$
$7$ $4$
$8$ $7$
$41$ $31$
$100$ $91$
$1000$ $604$

$41$ 人・$k=3$ で最後に残る二人は $16$ 番と $31$ 番で、伝承でヨセフスとその友が座ったとされる席に一致する。

観察 4.2 分離子は、何人おきに除くかである。$k=2$ では一周ごとに人数が半分になり、二進法の桁がそのまま答になる。$k=3$ では一周で三分の一が外れるが、$3$ 進法の回転のような短い形にはならず、一人ずつ減らす漸化式か、定数を使う閉じた式で出す。残る席が偶数になる人数は、$k=3$ では $1000$ のうち $500$ で、$k=2$ の「いつも奇数」という偏りは消える。

第2版の補足:$k=3$ にも閉じた式はある。Halbeisen と Hungerbühler(1997)の式は定数 $\alpha\approx0.8111$ を使い、$R=\mathrm{round}(\alpha(3/2)^{m})$ が $n$ 以下で最大になる $m$ から席が決まる。手元で確かめると、折り返す人数は $31$、$47$、$70$ と比が $3/2$ に近づき、折り返しのあいだは席が $3$ ずつ増え、$n=5$ から $2000000$ まで「$3(n-R)$+折り返しの席」と全部一致した。無いのは、二進法の回転のように短い形である。

観察 4.3 論文602・608 と並べる。602 はニムの勝ち負けを繰り上がりのない足し算で、608 はパスカルの三角形の奇数を二進法の $1$ の数で示した。本稿でも二進法の桁が答を決めるが、今度は足し算でも数でもなく、先頭の $1$ を末尾へ回すという並べ替えとして現れる。

観察 4.4 言わないこと。一般の $k$ の漸近式は扱わない。伝承の史実も論じない。示したのは、$k=2$ の式と $k=3$ の漸化式を輪を回した結果と突き合わせたこと、そして何人おきかで答の形が変わることである。

5. 点呼と結び

  1. 一人おきの残る席は、二進法の回転(計算 2.1):$1024$ 人まで一致。
  2. $41$ 人で $19$ 番、$1000$ 人で $977$ 番(計算 2.1):$101001$ から $10011$。
  3. 残る席はいつも奇数(観察 2.2):偶数の席は一周目で外れる。
  4. $2$ の冪なら $1$ 番(観察 2.3):$11$ 通りすべて。
  5. 一周ごとに人数を半分にする(観察 3.1):本稿の芯。
  6. $L$ 人外すと $2^m$ 人、次は $2L+1$ 番(観察 3.1):それが残る。
  7. $2L+1$ が先頭の $1$ を末尾へ回した数(観察 3.2):$41=32+9$ で $19$。
  8. 二人おきは漸化式で $1000$ 人まで一致(計算 4.1):$1000$ 人で $604$ 番。
  9. $41$ 人・$k=3$ の最後の二人は $16$ 番と $31$ 番(計算 4.1):伝承の席。
  10. $k=3$ では偶数の席が $500/1000$(観察 4.2):分離子は何人おきか。

結び:$n$ 人の輪から一人おきに外していくと、最後に残る席は、$n$ を二進法で書いて先頭の $1$ を末尾へ回した番号である。$1024$ 人まで、輪を実際に回した結果とすべて一致した。$41$ 人なら $19$ 番、$1000$ 人なら $977$ 番で、残る席はいつも奇数、人数が $2$ の冪なら $1$ 番である。一人おきの輪は、一周ごとに人数を半分にする二進法の操作である。$n=2^m+L$ なら、$L$ 人外した時点で $2^m$ 人になり、次に数え始める $2L+1$ 番が最後まで残る。分離子は、何人おきに除くかである。二人おきでは二進法の回転のような短い形が無く、漸化式は $1000$ 人まで一致した。残る席の偶奇の偏りも消え、$1000$ のうち $500$ が偶数だった。既刊との位置:論文602・608 と同じく二進法の桁が答を決めるが、ここでは並べ替えとして現れる。正直に言えば、一般の $k$ の漸近式にも伝承の史実にも入らず、$k=2$ と $3$ を数えただけである。

改訂記録

第2版(2026年10月):第1版の「二人おきに除くと式は無い」「漸化式でしか出せない」は言いすぎであった。Halbeisen と Hungerbühler(1997)の閉じた式があり(英語版ウィキペディアの Josephus problem の節による・原論文は読んでいない)、$n=5$ から $2000000$ まで手元で確かめた。副題・要旨の第四・射程注記・観察 4.2・結びを「二進法の回転のような短い形は無い」に直し、第4節に補足を足した。数の表は変わらない。

第3版(2026年10月):本文の区切りに使っていた横棒を句読点に改め、副題を短くした。主張・数・参考文献は変えていない。

参考文献

  1. Ball, W. W. R., & Coxeter, H. S. M. (1987). Mathematical Recreations and Essays (13th ed.). Dover Publications.
  2. Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley.
  3. 山岸勇輝 (2026). 『ニムの勝ち負けは、繰り上がりのない足し算で決まる』[論文602]. Zenodo. 10.5281/zenodo.22805951
  4. 山岸勇輝 (2026). 『パスカルの三角形の奇数は、行の番号を二進法で書いたときの 1 の数で決まる』[論文608]. Zenodo. 10.5281/zenodo.23014462

作成にあたって:本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI(大規模言語モデル)の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝(2026)「一人おきに除く輪で最後に残る席は、人数を二進法で書いて先頭の 1 を末尾へ回した数である」[論文614]. Zenodo.
DOI: 10.5281/zenodo.23014482

YOI 614第3版・2026年10月ビットコインに記録済み

日付の証拠(OpenTimestamps):日本語版の .ots・英語版の .ots・SHA256SUMS

住所:https://www.yamagishiyuuki.com/yoi/614・DOI 10.5281/zenodo.23014482・CC BY 4.0・プレプリント(査読を経ていません)・ORCID 0009-0006-8587-3450

引用するとき

山岸勇輝 (2026). 一人おきに除く輪で最後に残る席は、人数を二進法で書いて先頭の 1 を末尾へ回した数である [論文614]. YOI: https://www.yamagishiyuuki.com/yoi/614 ・ DOI: 10.5281/zenodo.23014482

Yamagishi, Y. (2026). In a Circle Where Every Second Person Leaves, the Last Seat Is the Head Count with Its Leading Binary 1 Moved to the End [Paper 614]. YOI: https://www.yamagishiyuuki.com/yoi/614; DOI: 10.5281/zenodo.23014482

@misc{yamagishi2026yoi614,
  author = {Yamagishi, Yuuki},
  title = {In a Circle Where Every Second Person Leaves, the Last Seat Is the Head Count with Its Leading Binary 1 Moved to the End},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/614},
  doi = {10.5281/zenodo.23014482},
  note = {Preprint, edition 3}
}
指紋(SHA-256)と確かめ方
131860de3021f587ba2c4f1390f8658ec141e3fcbf3eba7539f5966c9c19a9fa yamagishi_yoi614_v3_jp.pdf
15c5d248da97ff73e27ef8d7f53ac0abf93f2863b42651203f4ace9efa0c79b6 yamagishi_yoi614_v3_en.pdf

PDF と .ots を同じ場所に保存し、opentimestamps.org に .ots、続けて PDF を落とすと、記録された日時が表示されます。PDF が 1 バイトでも変わっていれば通りません。