パズル・ロワイアル答え合わせ

• パズル・ロワイアル

　全員で生還する確率を上げたければ、皆が何かしらの意味で協調した行動を取らなければならない。それなのに、挑戦中にも挑戦後に一切情報をやりとりできない。この一見取り付く島もなさそうなルールの裏をかくにはどうしたらいいか。

　情報をやりとりすることはできなくても、新しく全員が得ることができる情報がひとつだけある。というか、ひとつしかない。名前の書かれた紙である。突破口があるとしたらこれしかない。

　考えやすくするためにまず用語の準備をしよう。

　生徒には出席番号がついているものとして以後数字で考える。ついていなければどんな基準でもジャンケンでもくじ引きでもいいので適当に決める。以後生徒1〜42と呼ぶ。生徒nの名前の書かれた紙を紙nと呼ぶ。

　ロッカーにも番号を振る。たとえばロッカーに番号や記号がついていたら辞書順あるいは小さい順に、仮に番号がついてなかったとしても、左上が1でその右が2など事前に決めておいた何らかの規則性に基づいて、やはり1〜42と番号を振る。以後ロッカー1〜42と呼ぶ。

　さらに便宜的に同じ状態の42部屋で全員が同時に挑戦しているとして考え、生徒1が案内される部屋を教室1と呼ぶことにする。同様にして仮想の別々の教室をそれぞれ教室1〜42と呼ぶことにする。

　このゲームでは、生き残るために必要なのは自分の名前の紙だけである。仮に他人の名前の紙が入っていると分かっているロッカーがあるとしたら、そこを開けるのは避けるべきである。これが基本方針である。

　それを知る手段がないから困ってるんだろーが！　と思ってしまいそうだが、もう少し待て。

　まず最初に開けるロッカーは全員別々にすると決めよう。あえて違う選択をする理由はないのでわかりやすさのため、生徒nはロッカーnを開けることにする。

　仮に自分が生徒13だとして、ロッカー13を開ける。もし幸運にも紙13が出てきたら、それでクリアだ。あとは他人の幸運を祈るのみである。しかし、そんなことは1/42の確率でしか起きないので、大抵は外れる。

　出てきたのが紙4だったとする。生徒13は「ああ外れた」と嘆き悲しむ。しかし、死にたくないので嘆いてばかりいないで2個目のロッカーを選ばなければならない。2個目はもう当てずっぽうで選ぶしかないだろうか？　そんなことはない。

　実はこのとき、生徒13は、絶対に手に入らないと思われた他の部屋の情報を、知ることができている。

• 教室4で生徒4が、紙4以外の紙を引き「ああ外れた」と嘆き悲しんでいるということ

　がわかるのだ。なぜなら、紙4はロッカー13に入っているのだから。ロッカー4を開けることになっている生徒4が紙4を引いたということは、ありえない。

　ということは、生徒13が次に選ぶべきは？　ロッカー4である。なぜか？　この時点で生徒13が何らかの情報を持っているのは教室4に関してのみである。たとえば教室7でロッカー7を開けた生徒7が紙7を引いている可能性は、僅かながらある。

　もちろん、生徒13が自分の生き残りだけ考えた場合、ロッカー4もロッカー7も「紙13が入っているかもしれない」ことにおいては何も変わることはない。

　しかし、全員で生き残りたいと考えている場合には、すでに他の生徒の正解と決定している（かもしれない）ロッカーを避けることには意味がある。

　よって生徒13は2個目にロッカー4を開ける。出てきたのが仮に紙9だったとする。このとき、生徒13には新たに2つのことがわかる。

• 少し前、教室4で生徒4が1個目に開けたロッカー4から出たのは紙9だったこと
• 現在、教室4で生徒4がロッカー9を開けて紙x(4,9以外の何か）を見ていること
• 現在、教室9で生徒9はロッカーxを開けて紙yを見ているがyは9ではないこと

　最初の2つは当然として、紙yが紙9ではないというのはなぜわかるのか？

　紙yが紙9だとすると、紙9はロッカー4に入っているのだから、生徒9は2回目にロッカー4を開けたことになり、ひいては1回目に紙4の入ったロッカー13を開けたことになる。作戦上1回目にロッカー13を開けるのは生徒13である自分なのだから、生徒9が作戦に逆らったことになる。作戦に逆らう生徒はいないことになっているので矛盾である。よってyは9ではない。

　こうして2個目のロッカーを開けた時点で、生徒13は部屋を一歩も出ずして、生徒4と生徒9がいまだクリアしていないことがわかる。

　生徒13が3個目に開けるべきロッカーは？　先と同様の論理で9だ。なぜなら紙13が入っているかもしれない点では他と変わらず、かつ、すでに他の生徒の正解として確定してしまっている可能性がないロッカーだからだ。

　ここで、なんと！　ロッカー9から紙13が出てきたとしよう。生徒13はもちろんクリアの喜びで雀躍する。だが、同時に生徒4と生徒9もクリアの喜びで雀躍していることがわかる。

　というのは、少し前、生徒4が開けたロッカー9に入っていた紙xが紙13だったというのなら、今現在、生徒4はロッカー13を開けて紙4を発見したところだからだ。生徒9に関しても同様。

　では、肝心のその作戦で全員生き残れる確率はいくらかぐらいになるのか？　とりあえず10万回試行させてみたところ、なんと約32%もある。こんな怖ろしいゲームに巻き込まれて笑い話で済む可能性が1/3近くもあるなんて、約4兆4千億分の1とか言ってたのに比べると夢のような話ではないか。

　ただし、いくら同様に続けても紙13が発見できず、今だクリアしていないと分かっている生徒が増えていくだけの可能性もある。21個目のロッカーを開けても紙13が発見できなかった場合。生徒13は死ぬ。

　そして同時に、これまで紙の上に名前を見てきた4,9をはじめとする他の21人も同時に死ぬということがわかってしまう。なぜなら、すでに自分とその21人のクリアはかならず同時になることがわかっているからだ。自分が助かっていない以上みんな死ぬ。

　要するに、例の場合4,9,13の3つのロッカーが13→4→9→13というループを形成していたことになる。すべての番号は必ず1以上42以下の長さのループに所属することになる。ルール上そうならないことは不可能である。

　22以上の長さのループが存在しさえしなければ、全員が、確実にクリアできる。逆に22以上の長さのループが存在してしまうと、そのループにつかまった生徒は一人残らず死ぬ。

　ループの長さがいくつになるパターンがいくつあるかをちゃんと計算すれば厳密な確率も求まるはず……だが、その方法は自分も思い出せない*1ので発展課題にしておく。

試行に使ったRubyスクリプト

#!/usr/local/bin/ruby
#-*- coding: Windows-31J -*-

TIMES = 10000
NUM = 42
max = NUM / 2

all = 0
win = 0

live_sum = 0
dead_sum = 0

TIMES.times do
  all += 1
  
  arr = (0...NUM).to_a
  arr = arr.sort_by{|i| rand}
  
  live = 0
  dead = 0
  
  (0...NUM).to_a.each do |i|
    cnt = 0
    box = i
    loop do
      cnt += 1
      if cnt > max
        dead += 1
        break
      end
      if arr[box] == i
        live += 1
        break
      else
        box = arr[box]
      end
    end
  end
  
  live_sum += live
  dead_sum += dead
  
  win += 1 if live == NUM
  puts "#{win}/#{all}回目の試行：#{live}人生存・#{dead}人死亡"
end

puts "個人が助かる確率：#{live_sum.to_f / (live_sum + dead_sum).to_f}"
puts "全員助かる確率：#{win.to_f / all.to_f}"

追記 8/5

　HandDrumさんのコメントを元に、厳密解の求め方をコードにしたもの。これでよさそう。

#!/usr/local/bin/ruby
#-*- coding: Windows-31J -*-

class Integer
  def factorial
    (1..self).inject(1){|r, i| r * i}
  end
  def permutation(n)
    self.factorial / (self - n).factorial
  end
end

NUM = 42
puts 1 - (0...(NUM/2)).inject(0) {|r, n| r + NUM.permutation(NUM - n) / (NUM - n) * n.factorial}.to_f / NUM.factorial

おまけ

　死にゲーつながり。選曲と天丼が秀逸。（釣り・微ビックリ注意）