Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

プログラミングがわからない彼に、すこしだけプログラミングがわかっている自分が言えること

今日の風景

f:id:nisemono_san:20160921151048j:plain

こういう記事を書いてドヤ顔をするような人間は、大抵本人が思っているより能力にたけているわけでは無いという法則が、どこかの民族の諺としてあるとかないとか。

はじめに

石田祐希というブロガーの方が、起業をしたのはいいけれども、プログラミングがわからなくて、書籍が欲しいというエントリを書いている。

この一件に関しては、自分は特に言うこともなく(自分もレールから外れたが、文才の無い自分がその経路を書いても凡庸になるだけだと思って書いていない)、ただ傍観していただけだが、プログラミングのことだったら、自分の知識が無くても教えられることがあるだろう、とは思ったので、彼自身がこれを参考にするかどうかは兎も角として、せっかくなので書いてみようと思う。

ちなみに、記事の性質上、Web系に偏っていることをお断りしておく。

読みたい記事

まず最初に、プログラミングとは何だろうということを考えたときに参考にしたいのは、Qiitaにあがっているズンドコキヨシを見かけた男子中学生がプログラミングを勉強していく話 第1話だと思う。

実際、多くの入門と名を打つプログラミングサイトでは、やはり自分を含めて経験者が多いので、例えば「エラーメッセージが出たら、そのメッセージをコピペして調べてみる」といったような、そういうあたり前のことは説明しない傾向にある(そして、この習慣はとても大切だ)。この記事自体を熟読する必要はないと思うけれども、プログラミングとは何か、ということを知るのにはとてもいいと思う。

無料であるチュートリアル

さて、プログラミングとは何か、というところでやはり実際のアプリケーションを作ってみたい、特にWebアプリケーションであるならば、Railsチュートリアルがインターネットに公開されている、のはいいのだけれども、起業文化でRailsから入るという人は多いと思うのだけれども、実際のところは、結構厳しい。それはどうしてかというと、「データベース」とか、そのあたりの知識が必要になってくるからだ(はずかしいことに、自分も最初はまったく理解できなかった)。本来なら身近に知人がいて、逐一おしえてくれる人がいると良いと思う。

このあたりのチュートリアルに関して、問題集になるのだが、確実に力がつくものがある。言語処理100本ノックだ。いちおう言語処理ということになってはいるが、しかし、言語処理に限らず、プログラミングの初歩的な部分からはじまって、だんだんと高度になっていくので、やるとプログラミング力がつくと思う。ちなみに、著者はこれをやっていないので、まったく力がついていない。

また、Python3に関してならばPython チュートリアルがあるので、これを読もう。どうも知人がとあるプログラマー志望の子に、プログラミングのセンスを教えるために、この教材をすすめることを結論したらしい。Python自体の仕事は機械学習などの、ちょっと数学的なセンスが必要になるものが多いので、仕事には直結しないと思うが、言語自体のクセは特には無く、最初の言語のとっかかりとしては丁度いいかもしれない。

で、やりたいことがサーバーサイドであるならば、上のチュートリアルをやりながら、RubyおよびPythonについて勉強するといいと思う。あれ、JavaScriptとPHPはどうなるんだろう? 正直言うと、この両者については、自分は適切な教材を提示することができない。書籍であるならば、いくつかいいのが出ているけれども、自信はない。ただ、PHPで簡単な掲示板を作成するというのもチュートリアルとしていいと思うのでやってみるといいと思う。

ちなみに、PHPに関してはオライリーのほうはあまりいい印象がなかったので、『パーフェクトPHP』のほうをおすすめする。無料があくまでもよければ、いまはドットインストールがあるので、それを毎日聞きながしながら、起業準備をすればいいと思う。そうそう、なんでオライリーのほうを薦めないかというと、Ruby、 JavaScript、PHPに関しては、私見によれば、パーフェクトシリーズのほうがいい気がしている。

パーフェクトPHP (PERFECT SERIES 3)

パーフェクトPHP (PERFECT SERIES 3)

パーフェクトJavaScript (PERFECT SERIES 4)

パーフェクトJavaScript (PERFECT SERIES 4)

さて、JavaScriptについてなんだけど、jQueryだけだと、やはりちょっと辛いので、無責任にVue.jsのチュートリアルをおすすめしておく。ほかのものでもいいんだけど、たぶん個人的に触ってみて感触がよかったのがこれだったので、ドットインストールでJavaScriptについて基礎的なことを学んだら挑戦してみるといいと思う。ちなみに、JavaScriptを勉強する上でおすすめになるアプリは「TODOアプリ」の作成で、だいたいそういうサンプルをやることが多い(やることをリストにして、終わったら消すアレ)。

プログラミングに関するエッセイ

プログラミングに関するエッセイについては二人の巨頭がいて、それはポール・グレアムと、ジョエル・スポルスキだろう。

いや、異論は認めるけれども、「プログラミングをしてスタートアップを立ちあげでやっていきたい」という人は、必ず通る道であると思う。ポール・グレアムは「Y Combinator」を立ちあげ、スタートアップ支援をしたりしているくらいだから、読んでおいて損はないのではないかと思う。

ついでにアフィリエイト乞食

とはいえ、自分は起業していなくても、お金がないので適当にこのあたりの書籍が必要になるであろう、というものをピックアップしておく。とはいえ、これはプログラミングよりの書籍が多く、起業となると、また別問題が発生すると思われるので、あまりのめりこみすぎず、適度なところで身をひいて、少なくとも一緒に今後やっていくエンジニアの話はできるようにするくらいのことは重要だろう。

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

  • 作者: Dustin Boswell,Trevor Foucher,須藤功平,角征典
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2012/06/23
  • メディア: 単行本(ソフトカバー)
  • 購入: 68人 クリック: 1,802回
  • この商品を含むブログ (135件) を見る

プログラムがわからないという考え方には二つの方向がある。まず一つに、そのロジックがわからないということと、もう一つに、「ちゃんとしたコードをどうかくか」がわからない、ということがある。で、その後者を埋めるのがこの本である。大抵のプログラマがこの本を名著とあげるので、いまさらという感じもしないことはないのだが、プログラミングを始めて慣れてきたら、勢いで買うべき本だと思う。

SQL 第2版 ゼロからはじめるデータベース操作 (プログラミング学習シリーズ)

SQL 第2版 ゼロからはじめるデータベース操作 (プログラミング学習シリーズ)

SQLといえばミック氏による書籍。とくにMySQLやPostgreSQLなどのリレーショナルデータベースを扱うさいに使われる言語である。直接いじる機会は、おそらくフレームワームを使えばそれほどないけれども、理解があるのとないとでは大違いなので、基礎教養として知っておく必要がある。実際使う場面もあるしね。

体系的に学ぶ 安全なWebアプリケーションの作り方 脆弱性が生まれる原理と対策の実践

体系的に学ぶ 安全なWebアプリケーションの作り方 脆弱性が生まれる原理と対策の実践

もはや定番となってしまったアプリケーションのセキュリティー本。Webッサービスを作るということは、当然のことながら、そのサービスに対して責任を持つということになるので、是非一読しておきたい一冊。

コードには、多分問題にぶちあたればぶちあたるほど、そのプログラミングに対しての幅が広がる筈だろう。いまは、実際に問題を解かせる転職サイトなんかもあるし。実際に、競技プログラミング的な部分が実務に役に立つのかどうかは、俺にはわからない。ただ、プログラミングの幅は確実に広がると思う。

Linuxのことを知る

あとはLinuxに関する本があればいいのだけれども、ぱっと思いつかなかった(本当はここにとある書籍が紹介されていたんだけど、未読の書籍を紹介のは問題なんじゃないかというご指摘をうけて削除しました)。ただ、他の方からムック本みたいな形で本が出ていることを教えて貰いました。

ちなみに、Linux技術者認定試験のLPICでは下の教科書が配られている。

またコメント欄で、THE DEBIAN ADMINISTRATOR'S HANDBOOKの存在を教えて頂きました。ありがとうございます。

ただ、上記2つ、無料で配られているマニュアルと教科書を全部読むと、インフラエンジニアになるぞというやっていく気持ちがない限り、心が折れると思うので、適当に気を追わずに読んでいくといいと思う。

標準的な設計について知る

ブコメに、「設計の話もしたほうが良い」という全うなご指摘を頂いたので、その本も紹介。とある方から頂いたもので感謝している。

下の本は、ちょっと受託開発よりになるとは思うし、個人的にはここまで固くやる必要かあるのか、という疑問はあるけれども、手難くやるという意味で、設計とかの話の概要を知っておくにこしたことはない。全部のことを真に受けないにしろ、どういうことが必要になってくるか、というのを見ておく意図として、下の本は便利だ。

システム設計の謎を解く 強いSEになるための、機能設計/入出力設計の極意

システム設計の謎を解く 強いSEになるための、機能設計/入出力設計の極意

上記にいった通り、自分でサービスを作ったり、実際に係った経験からすると、ここまでキチッとやる必要はないが、しかし、こういう風なものがあるというのを知っておくのは、多分武器になる。

読まなくてもいいもの

あと、個人的な趣味として、下の本を薦めておく。これは買わなくてもいい。

素数夜曲―女王陛下のLISP

素数夜曲―女王陛下のLISP

この本はわからなくても良い。

最後に

おれはレールから外れたので、山谷で無職をしている。特に、今後どうするかという予定もない。なので、もしこのリストで一発サービスが当ったら、いろいろと助けてくれることを期待している。

蛇足

他にこんなのがあるよと、はてなブックマークで教えてくれれば、追記しますのでよろしくお願いします。

表か裏のどちらかが3連続出るかどうか賭けをしたゲームの場合、何回投げたら公平なのだろうか

今日の風景

f:id:nisemono_san:20160917145522j:plain

端的に説明すると、これは暴力革命を再現したものです。

はじめに

世の中には、直観に反して「ありえそうもないこと」が案外「ありえそう」であることがある。例えば、このブログで以前に紹介した誕生日のパラドックスがそれに当たる。その詳細は上のリンクから飛んでもらうとして、他にも、その類のものがある。

コインを投げて表か裏かのどちらかが、3連続出るかどうかを賭けるゲームを考えてみよう。このとき、何回にしたら公平だろうか。直感的には、3連続というのはなかなかありえそうにもない数であるので、公平なゲームにするためには、7回くらい必要なのではないか、と思う人もいるかもしれない。しかし、7回にした場合、確率的に67.1%の可能性で、3回連続で同じ面が出る。なので、もし7回投げるとした場合、3回連続出るとして賭けるほうが有利なのだ。

組みあわせを考える

しかし、この結論では釈然としない。そこで、ちゃんと組みあわせを考えてみることにする。とはいえ、最初に7回から数えると、投げたときに起こりうる組みあわせの総数は128種類になる。128種類なら、数えられないことは無いけれども、やはり少ない回数から考えていったほうがいいと思う。

まず最初に3回投げたときの場合を考えてみよう。3回の場合、2の3乗なので、8通りの組みあわせが考えられる。このとき、表と裏のどちらかが3連続で出る確率は、3回とも同じ面が出ればいいわけだから、2通り。とすると、2/8、つまり1/4の確率で3連続出ると考えることができる。

同じく4回の場合を考えてみよう。とりあえず3連続出る場合のパターンを数えあげてみると、次のようになるはずだ。ちなみに、一々裏と表と書くのは面倒なので、0と1で表記してある。

[0, 0, 0, 0]
[1, 1, 1, 1]
[0, 0, 0, 1]
[1, 0, 0, 0]
[1, 1, 1, 0]
[0, 1, 1, 1]

この6通りが考えられる。当然、4回の場合には16通りなので、6/16、つまり3/8が考えられる。

フィボナッチみたいに計算する

とはいえ、このように数えあげていくのは、あまりにも非効率的であることは間違いない。実は、3連続にならない組みあわせの数はある公式によって導きだすことができる。

まず、最初にコインを投げる回数をNとする。このとき、3連続ではない組みあわせのことをg_Nとした場合、下の式で算出することができる。

 { g_N = g_{N-1} + g_{N-2} }

この式はフィボナッチ数を求める数と非常に良く似ている。念のため、フィボナッチ数を求める公式は次のようになる(このとき、任意の順番のフィボナッチ数をiとしよう)。

 i_n = i_{n-1} + i_{n-2}

ただし、フィボナッチ数の場合、nが1と2の場合は、n-2に該当するものが存在しないので、1ということになるわけだが、ではこのコイン投げの場合においてはどうなるのかを考えないといけない。

そこで、愚直に1回投げたときに、コインで3回同じ面が出る場合を考えてみよう。とはいえ、書いていて馬鹿馬鹿しいというか、あたりまえだが、そんな組みあわせは存在しない(どうやって1回投げて3回の面を出すというのか)。なので、この場合は2つの組みあわせが、3回連続しない組みあわせとなる。さて、同様に2回投げる場合も同じようにすると4つの組みあわせが、3回連続しない組みあわせとなる。

さて、賢明な読者であるならば、気がついているように、この1回目の2通りと、2回目の4通りを組みあわせると、3回目の6通り(8 - 2)が導きだせる。念のため、4回目も考えてみると、4 + 6 = 16 - 6となる。この具体的 な証明は、実際のところ不明なので、知っている人がいれば教えて頂ければ、と思う。

コードで検証してみる

とはいえ、実際にそういう風になっていると言われても、実際に確率を求めるのがいいだろう、というわけで、さっそく確率を求めるようなコードを書くことにした。

class CoinTossGame
  attr_accessor :win

  def initialize(times)
    @memory_toss = nil
    @win = false
    @succession = 1
    @times = times
  end

  def toss
    result = Random.rand(0..1)
    if result != @memory_toss
      @memory_toss = result
      @succession = 1
    else
      @succession += 1
    end

    if @succession > 2
      @win = true
    end
  end

  def run
    1.upto(@times) do
      toss
    end
  end
end

3.upto(10) do |times| 
  point = 0
  1.upto(10000) do
    game = CoinTossGame.new(times)
    game.run
    point += 1 if game.win
  end
  puts "#{times} TOSS GAME POINT: #{point}"
end

ログは以下の通りである:

3 TOSS GAME POINT: 2493
4 TOSS GAME POINT: 3752
5 TOSS GAME POINT: 5067
6 TOSS GAME POINT: 5872
7 TOSS GAME POINT: 6755
8 TOSS GAME POINT: 7304
9 TOSS GAME POINT: 7836
10 TOSS GAME POINT: 8276

だいたい、推測していた確率になっている。

まとめ

というわけで、だいたい公平になるのは5回投げるのが、賭けとしては一番いいということになる。もし、賭けに有利にしたければ、6回以上を提案すればいいということになる。

数字の国のミステリー (新潮文庫)

数字の国のミステリー (新潮文庫)

「任意の数からスタートして、偶数なら2を割る、奇数ならnをかけて1を足す過程で、1に収束するか」をいろいろな数でやってみる

今日の風景

f:id:nisemono_san:20160916152021j:plain

寿司によってベルリンの壁が崩壊したことは、ドイツの歴史において重要な発見の一つとなっています。

はじめに

数学において、未解決問題というのはいろいろあるのだけれども、その一つにコラッツ問題(角谷問題とも言う) がある。大抵の数論の教科書だったりすると、このトピックは取りあげられるので、その方面に詳しい人なら「ああ、あの問題ね」というのはピンとくるはずだ。

そのあたりに明くない人に解説すると、コラッツ問題とは「任意の数からスタートして、偶数なら2を割る、奇数なら3をかけて1を足す過程を繰りかえすと、全ての数は最終的に1になるか」というものである。これが不思議なもので、ステップ数は、始める数によって違うのだけれども、最終的には1に収束する。とりあえずはデータを集めようということで、この計算結果を集めてみようというサイトがあるくらいである。

さて、そんな簡単にして、いざ解こうとなると、難問のように立ち塞がるコラッツ問題なのだが、『数学を生み出す魔法のるつぼ』という本をペラペラと読んでみると、下のような記述にぶちあたった。

3を5に代えて「5n + 1」規則にするとどうなるでしょうか。3n + 1予想がどうしたら間違いとなるか自らに問うでみましょう。予想が間違いとなるには、数列が発散するか無限ループに陥いるかのどちらかになる数が存在しなければなりません。5n + 1規則では多くのものが無限ループになります。

この一文を読んでみたときに、ふと思ったのは、「では最も1に収束しないような規則というのは存在するのだろうか」ということだった。思いたったら吉日なので、さっそくコードを書いてみることにした。

コード

今回は何故かElixirが書きたいなと思ったので、Elixirで実装している:

defmodule Collaz do
  def calc(n, m, count) do
    cond do
      n == 1 -> exit(0)
      count > 1000 -> :ok
      rem(n, 2) == 1 -> calc(m * n + 1, m, count + 1)
      true -> div(n, 2) |> (&(calc(&1, m, count + 1))).()
    end
  end

  def forprint(x, y) do
    for y <- (
          Stream.iterate(3, &(&1 + 2))
          |> Enum.take(y)
          |> Enum.to_list ) do
      IO.puts "\n===="
      for i <- 3..x do
        try do
          calc(i, y, 0)
        catch
          :exit, _ -> :io.format("~B ", [i])
        end
      end
      IO.puts("\n---------")
      :io.format("~B ", [y])
    end
  end
end

Collaz.forprint(1000, 10)

実行すると、次のようなログが吐きだされる筈だ。

3 4 6 8 12 15 16 19 24 30 32 38 48 51 60 64 65 76 96 97 102 120 128 130 137 152 
155 163 175 192 194 204 219 240 243 256 260 274 304 307 310 326 343 350 384 388 
397 408 417 429 438 480 486 491 512 520 548 608 614 620 635 652 655 667 686 700 
768 776 794 816 819 834 858 876 941 960 972 982 993 
---------
5 
====
4 5 8 9 10 16 18 20 32 36 40 41 64 72 73 80 82 128 144 146 160 164 167 256 288 292 320 328 329 334 512 576 584 585 640 656 658 668 
---------
7 
====
3 4 6 7 8 12 14 16 24 28 32 48 56 64 96 101 112 128 192 199 202 224 256 319 359 384 398 404 448 455 512 567 638 718 768 796 808 896 910 
---------
9 
====
4 8 16 32 64 93 128 186 256 372 512 541 744 
---------
11 
====
4 8 16 32 64 128 256 315 512 630 
---------
13 
====
4 8 9 16 17 18 32 34 36 64 68 72 128 136 144 145 256 272 273 288 290 512 544 546 576 580 
---------
15 
====
4 7 8 14 15 16 28 30 32 56 60 64 112 120 128 224 240 256 448 480 512 896 907 960 
---------
17 
====
4 8 16 32 64 128 256 512 
---------
19 
====
3 4 6 8 12 16 24 32 48 64 96 128 192 195 256 384 390 512 768 780 
---------
21

ちなみに、3は自明なので、このログの中では飛ばしてある。また、実装の関係上、無限に発散する、あるいは無限ループに陥いるような判定のコードを書く手間をおしむため、ある一定のステップに達した場合、それは無限ループであるという風に決めうちをしている。

また、掛けあわせる数を奇数に制限している理由としては、考えてみれば当然なのだが、奇数に1を足すと必ず偶数になる。偶数において掛け算するという規則なわけだから、無限ループに陥いって、発散することになる。この問題の妙は、偶数と奇数をいったり来たりしながら、なぜか1に収束するということなわけだから、規則に奇数を使わなければならない。

結果を見ると

さて、ここで気になることが一つある。例えば、この中で特徴的な解決を見せている「17を掛けて1を足す」という規則である。上記では、2の乗算でできる数でしかループが終わらないようになっている。これには理由があって、Twitterで示唆してもらったところによると、2の乗数でできる数は、何度割っても偶数になるため、1になるまで常に偶数となる。そのため、偶数のループによって、必ず終了することが保証されることになる。

このように、2の乗算だけしかループが完了しないものは、17の他に25, 27, 29となるわけだが、では23以上だったらそのような規則になるのか、といえばそうはならず、例えば31の場合、「17」でも、先にループは終了するため、ぱっと見、「この数ならば、2の乗数のみしかループが終了しない」という法則は無いように思える(もしかしたらあるのかもしれない。そのような法則を知っている人がいたら教えて欲しい)。このような規則は無数にあるので、興味がある人は試してみるといいかもしれない。

まとめ

確かにコラッツの問題自体は良く知っていたけれども、その中の規則を変化させると、どのようになるかまでには思い至らなかった。このように、既存の良く知っている問題について、規則を変更すると、どのような結論になるのかということを確認するのは楽しかった。月並みな結論だけれども、何か他の問題でそのような規則について見つけることができたら試してみたい、と思ったりした。

数学を生み出す魔法のるつぼ ―実験数学への招待 (O’Reilly math series)

数学を生み出す魔法のるつぼ ―実験数学への招待 (O’Reilly math series)

お金の総体が変わらない市場でやりとりしたら、貧富の差が生まれるか?

今日の風景

f:id:nisemono_san:20160914151326j:plain

貧乏人に再分配された(半額になった)寿司の風景です

はじめに

『ベットルームで群論を』という、みすず書房から出ている本の中に、「富が一定である閉鎖的なマーケットの中で、平等に富を持ったプレイヤーに対し、ランダムに得する人と損する人を決めていき、ある一定のステップを踏んだ結果、少数の金持ちと、多数の貧民の格差に分かれることになる」という話を載せていた。

この話に興味を持ったので、実際に、そういうモデルを作って、実際に閉鎖的なマーケットで各種のプレイヤーが損と得を繰り返していった結果、貧富の差が生まれるかどうかを実際に簡単なコードでシミュレーションしたいと思う。当然、このモデルは、実際の経済市場とは乖離したものであることは認めざるを得ないが、極端なモデルにも、何らかの示唆は、多分あると思う。

ルール

とはいえ、ざっくりとこのようなことを書いたとして、そもそものルールが如何なるものかを考えないといけないだろう。

ルールとしては、まず市場に存在するプレイヤーは、それぞれ同じお金を所持しているものとする。そして、各プレイヤーのお金の総体は、増減しない。つまり、プレイヤーの所持する金額のお金を合計すると、いつも同じ所持金になるということである。そして、そのプレイヤーでとりひきするときに、損するプレイヤーと、得するプレイヤーをランタムに決める。このモデルにおいては、借金は認められないので、得するプレイヤーは、損するプレイヤーの所持金を越えない範囲においてのみ得することができる。また、損得の率については、これまたランダムで決定されることにする。

直観的には、損するプレイヤーと、得するプレイヤーの決定がランダムであるならば、おそらくプレイヤー同士の金額はそれほど変わらず、ある時は金持ちになったり、あるいはある時は貧乏になったり、を繰りかえすであろうということが予測される。神の見えざる手はそれほど残酷では無いように思える。

実装と実行

というわけで、このモデルを実装した結果としては下のようになる:

class Market
  def initialize(players)
    @players = players
  end

  def players_print
    puts "================================================================"
    @players.each_with_index { |player, i| print "#{i}: #{player.money}  "}
    puts ""
  end

  def money_flow
    win = player_choice
    lose = player_choice
    until define_player? win, lose
      win = player_choice
      lose = player_choice
    end

    if lose.money < win.money
      pay_money = (lose.money * (Random.rand(1..3) * 0.1)).to_i
    else
      pay_money = (win.money * (Random.rand(1..3) * 0.1)).to_i
    end

    lose.money -= pay_money
    win.money += pay_money
  end

  private
  def define_player? win, lose
    !(win.eql? lose) 
  end


  def player_choice
    @players[Random.rand(@players.size)]
  end
end


class Player
  attr_accessor :money
  def initialize
    @money = 10000
  end
end

players = Array.new(6) { Player.new }
market = Market.new players
market.players_print
1.upto(1000) do |x|
  market.money_flow
  if x % 10 == 0
    market.players_print
  end
end

これを実行した結果、次のようなログが得られる。

================================================================
0: 10000  1: 10000  2: 10000  3: 10000  4: 10000  5: 10000  
================================================================
0: 5923  1: 10756  2: 22849  3: 8422  4: 756  5: 11294  
================================================================
0: 3599  1: 18123  2: 6177  3: 17843  4: 255  5: 14003  
================================================================
0: 9336  1: 12062  2: 2571  3: 24749  4: 586  5: 10696  
================================================================
0: 1300  1: 8344  2: 2839  3: 30751  4: 260  5: 16506  
================================================================
0: 367  1: 5699  2: 3338  3: 35885  4: 308  5: 14403  
================================================================
0: 230  1: 2834  2: 9082  3: 42119  4: 69  5: 5666  
================================================================
0: 135  1: 2315  2: 8237  3: 44967  4: 67  5: 4279  
================================================================
0: 120  1: 1830  2: 6367  3: 45974  4: 6  5: 5703  
================================================================
0: 274  1: 542  2: 5036  3: 52045  4: 3  5: 2100  
================================================================
0: 163  1: 609  2: 3204  3: 53927  4: 3  5: 2094  
================================================================
0: 22  1: 363  2: 1518  3: 56812  4: 3  5: 1282  
================================================================
0: 18  1: 483  2: 1090  3: 57799  4: 3  5: 607  
================================================================
0: 10  1: 1278  2: 1909  3: 56636  4: 3  5: 164  
================================================================
0: 3  1: 1454  2: 1912  3: 56468  4: 3  5: 160  
================================================================
0: 3  1: 1697  2: 805  3: 57339  4: 3  5: 153  
================================================================
0: 3  1: 727  2: 802  3: 58381  4: 3  5: 84  
================================================================
0: 3  1: 229  2: 844  3: 58789  4: 3  5: 132  
================================================================
0: 3  1: 160  2: 741  3: 59023  4: 3  5: 70  
================================================================
0: 3  1: 40  2: 2131  3: 57702  4: 3  5: 121  
================================================================
0: 3  1: 91  2: 2434  3: 57244  4: 3  5: 225

繰りかえした結果、ある一定の閾値を越えると、途端に富の偏りが出てくるようで、この場合であるならば、3に集中していることがわかる。

考察

上記のモデルにおいては、お金のフローは硬直していく傾向にある。元ネタの『ベッドルームで群論を』にも書いてある通り、確かに金持ちはより金持ちになっていくわけだが、その分、金持ちは誰とも売買することのできない硬直した市場があり、その一方で、貧乏人同士で些細なお金のやりとりをしあうような世界になることが示唆されている。もちろん、このような特殊な市場というのは存在はしていない。

しかし、このような硬直に向かいつつある市場を、上手く修正する方法は一つある。上のモデルだと、金を持っているプレイヤーが、金を持っていないプレイヤー以上にお金を出さない、とする、ある意味では理知なプレイヤーのモデルである。そこで、もうすこしルールを単純にして、「与える側」と「貰う側」にしてしまう。つまり、ランダムに選ばれたプレイヤーはお互いの所持しているお金とは関係なく、一定率の金額を渡さなければならない、としてみよう。この修正は簡単で:

  def money_flow
    win = player_choice
    lose = player_choice
    until define_player? win, lose
      win = player_choice
      lose = player_choice
    end

    pay_money = (lose.money * (Random.rand(1..3) * 0.1)).to_i
    lose.money -= pay_money
    win.money += pay_money
  end

といったように、分岐の部分を無くせば良い。このログは以下のようになる。

================================================================
0: 10000  1: 10000  2: 10000  3: 10000  4: 10000  5: 10000  
================================================================
0: 6969  1: 10320  2: 12290  3: 5745  4: 13080  5: 11596  
================================================================
0: 7164  1: 3748  2: 16601  3: 8685  4: 8224  5: 15578  
================================================================
0: 7406  1: 15377  2: 9058  3: 5122  4: 5063  5: 17974  
================================================================
0: 3734  1: 10490  2: 14153  3: 16212  4: 4864  5: 10547  
================================================================
0: 13148  1: 9684  2: 15894  3: 8781  4: 8608  5: 3885  
================================================================
0: 7805  1: 10750  2: 14149  3: 11574  4: 8861  5: 6861  
================================================================
0: 6703  1: 15829  2: 2977  3: 21076  4: 5230  5: 8185  
================================================================
0: 13891  1: 15145  2: 7964  3: 8959  4: 5049  5: 8992  
================================================================
0: 8533  1: 7824  2: 18422  3: 12643  4: 9779  5: 2799  
================================================================
0: 10555  1: 16868  2: 9294  3: 6705  4: 2611  5: 13967  
================================================================
0: 12567  1: 10251  2: 8030  3: 11520  4: 4077  5: 13555  
================================================================
0: 10842  1: 4568  2: 3893  3: 5262  4: 28368  5: 7067  
================================================================
0: 7995  1: 4610  2: 6152  3: 11740  4: 15761  5: 13742  
================================================================
0: 10156  1: 7349  2: 8515  3: 19949  4: 5052  5: 8979  
================================================================
0: 19181  1: 8281  2: 11931  3: 13179  4: 1447  5: 5981  
================================================================
0: 1148  1: 18653  2: 16047  3: 4865  4: 9887  5: 9400  
================================================================
0: 21972  1: 10682  2: 4554  3: 3439  4: 9466  5: 9887  
================================================================
0: 2751  1: 13354  2: 15472  3: 7961  4: 7018  5: 13444  
================================================================
0: 22601  1: 11600  2: 5940  3: 10826  4: 2973  5: 6060  
================================================================
0: 11854  1: 21281  2: 10629  3: 6394  4: 4587  5: 5255  

といったように、若干偏りはあるものの、先ほどのような、酷い偏りではない結果が生まれることになった。元の本では、この経済モデルのことを「盗みと詐欺のモデル」としている。なぜなら、金持ちはできるだけ豊かになるように行動するはずだ。この場合、圧倒的に金持ちのほうが、貧乏人より、このモデル上では不利だからだ。(最も、経済学的に考えれば、このモデルは再配分がうまくいっているモデルとは言えるかもしれない)

まとめ

このモデルは単純化しすぎているので、経済学的な市場モデルを即ち反映しているとはとても言いがたいのは間違いない。しかし、単純化したところによって、いわゆる「売り買い」、あるいは「与える・貰う」という結論がどのような結果に収束するのか、あるいはしないのかを見てみるのは非常に面白かった。

今回、利用した『ベッドルームで群論を』では、このようなプログラミング的なトピックを扱った、硬すぎず、かといって簡単すぎるでもない、非常にほどよいエッセイが収められていて、読んでいてとても面白かった。もしかしたら、また幾つかトピックを紹介するかもしれないが、もし興味のある人がいれば、読んでみて欲しい。

ベッドルームで群論を――数学的思考の愉しみ方

ベッドルームで群論を――数学的思考の愉しみ方

世にも奇妙な素数の生成方法、PRIMEGAMEを理解するために、分数で足し算と掛け算をする

今日の風景

f:id:nisemono_san:20160913072039j:plain

破壊される予定の壁です。破壊されない壁などなく、皆さんもまた破壊ですか?

はじめにーーPRIMEGAMEとは何か

コンウェイという人は本当に色々な、気の狂ったようなことを考えていて、その中で最も有名なものの一つにライフゲームがある。しかし、ライフゲームだけではなく、計算機で遊ぶということには、彼の右に出るものは殆どいなく、例えば、任意の分数表が素数のリストを作り出すことができるということを発明したのも、彼であり、それはプライムゲーム(PRIMEGAME)と呼ばれている。

PRIMEGAMEの骨格はこうだ。以下の分数表に対して、2を先頭から掛けていく。もし、ある分数の掛けあわせた結果が整数になった場合、その整数を分数表の先頭から掛けていく。これを繰り返していくと、奇妙なことに、2の乗で表すことのできる整数の指数は、全て整数になっているという。

説明が下手なのは、このブログの得意技であるので、実際にコードを見てもらうほうが早いだろう:

PRIMEGAME = [Rational(17, 91),
             Rational(78, 85),
             Rational(19, 51),
             Rational(23, 38),
             Rational(29, 33),
             Rational(77, 29),
             Rational(95, 23),
             Rational(77, 19),
             Rational(1, 17),
             Rational(11, 13),
             Rational(13, 11),
             Rational(15, 2),
             Rational(1, 7),
             Rational(55, 1)]

class Rational
  def int?
    self.to_i == self
  end
end

class PrimeGame
  def initialize n
    @i = n
  end

  def until_integer
    result = @i
    PRIMEGAME.each do |e|
      result = @i
      result *= e
      return result.to_i if result.int?
    end
  end

  def exponent? n
    m = 0
    while n > 1
      return false if n % 2 == 1
      n /= 2
      m += 1
    end
    puts "2 * #{m} = "
    true
  end

  def times n
    n.times do |i|
      @i = until_integer
      puts(@i) if exponent?(@i)
    end
  end
end

prime = PrimeGame.new 2
prime.times 1000000

これを動かしてみると、下のような出力が得られる:

...

2 * 43 = 
8796093022208
2 * 47 = 
140737488355328
2 * 53 = 
9007199254740992
2 * 59 = 
576460752303423488
2 * 61 = 
2305843009213693952
2 * 67 = 
147573952589676412928
2 * 71 = 
2361183241434822606848
2 * 73 = 
9444732965739290427392
2 * 79 = 
604462909807314587353088
2 * 83 = 
9671406556917033397649408
2 * 89 = 
618970019642690137449562112
...

確かに指数によって素数が出てくるのか不思議な結果だと思う。そこで、借りに、この分数表をいわばプログラミング言語であると見なし(実際、本書の中ではFACTRANという呼び名がついている)、分数表を使って足し算と掛け算を実現する方法を解説し、なぜ素数リストを作ることができるのか考察してみるのが、この記事の目的となる。

余談

RubyのRational(つまり分数クラス)から、その分数が整数になるかどうかを取得する方法がわからなかったため、聞いてみたところ、このような解答を頂きました。助言してくださった方々、ありがとうございました。

FACTRANのルール

とりあえず、不正確ではあるものの、ここで利用するFACTRANの定義を行なっておこう。

ルールは以下の通りだ。インプットされる整数に対して、分数表の先頭から、その分数を掛けていく。もし、何らかの分数で掛けたとしても、整数の場合、その整数を採用し、また分数表の最初から掛けていく。もし、最後まで分数表に整数が現われなかった場合、その整数が最終出力として採用される。先のRubyのコードに書いてある分数表は、最後が55/1のため、必ず整数となり、無限ループになる。

単純なカウンターを作る

こういうのを理解するためには、まず単純なループから作ってみるのが一番いいだろう。ということで、本書に習い、一つの分数でできだ分数表、{ 5/6 }を用意し、この最初の数を648とし、このループを廻してみると、375で止まることがわかる。ここで何が起きているかを紙に書きだしてみると:

  645 * 5 / 6 
= 540 * 5 / 6
= 450 * 5 / 6
= 375

となる。なぜこうなるのか、といえば、5/65 / (3 * 2)として表記できるわけで、さらに言うと、648は、2^3 * 3^4だからだ。5/6で割ったとき、23の指数はそれぞれマイナスされ、そのかわり、5の指数が増える。実際:

  (2 ^ 3) * (3 ^ 4) * 5 / 6
= (2 ^ 2) * (3 ^ 3) * 5 * 5 / 6
= (2 ^ 1) * (3 ^ 2) * (5 ^ 2) / 6

となり、2の指数がなくなってしまった時点で、5/6は分数となってしまって、そこでストップしてしまうことになる。

足し算をする

さて、これらの指数を疑似的にカウンダーだと考えてみよう。今度は(2 ^ 1) * (3 ^ 2) = 2 * 9 = 18に対して、10 / 3を掛け続け、整数でなくなるまでにしてみよう。この場合:

  18 * 10 / 3
= 60 * 10 / 3
= 200

となる。この時、200を因数分解してみれば、(5 * 5) * (2 * 2 * 2)となり、2の指数は、最初の指数を足しあわせたものと一致する。ちなみに、5に関しては、10が2 * 5であるため、5の指数がストックされる形となっている。

これらは分数で行なっているから不思議に思うものの、これを素朴なコードに直してみれば、やっていることは次のコードとたいして変わらなかったりする。

a = 1
b = 2
c = 0
while b > 0
  b -= 1
  a += 1
  c += 1
end

puts a + c

もちろん、先の分数による計算も実装できる。

class Rational
  def integer?
    self.to_i == self
  end
end

a = 3
b = 4

aa = (2 ** a) * (3 ** b)

while (aa * 10/3r).integer?
  aa = aa * 10/3r
end

aa = aa / (5 ** b)
count = 0
until aa == 1
  aa = aa / 2
  count += 1
end

puts count

掛け算の実装(不完全な方法)

同様に分数の掛け算も実装することが可能である。愚直にループだけで掛け算を実装することを考えた場合、次のように実装することが可能である:

r2 = 0
r3 = b = 9
r7 = 6

while r7 > 0
  while r3 > 0
    r2 += 1
    r3 -= 1
  end
  r3 = b
  r7 -= 1
end

puts r2

変数名から推測できるかもしれないが、素朴な方法としては、1/710/33/5で実装することが可能だ。足し算の実装のさいに、5の指数をスタックしておいたのだけれども、これを3/5でさしもどすための伏線である。

ただし、この方法は不完全である。なぜなら、愚直にループしたい回数ならびに、そのループのさいにカウントしたい回数、例えばこの場合で言うならば、7の指数がループ回数で、3の指数がループ内でカウントされる回数と見なすことができるわけなんだけども、頭から分数を割っていって、整数が出てきたら、最初からやりなおすというルールの場合、考えても見ればわかるように、7の指数は最初に消化されてしまうので、このままだと動かない。

とはいえ、基本的な発想はわかったので、取りあえずこのバージョンのものを書いてみよう。

class Rational
  def integer?
    self.to_i == self
  end
end

r2 = 0
r3 = n = 11
r7 = 23

aa = (3 ** r3) * (7 ** r7)
puts aa
while (aa * 1/7r).integer?
  aa *= 1/7r
  while (aa * 10/3r).integer?
    aa *= 10/3r
  end
  while ( aa * 3/5r ).integer?
    aa *= 3/5r
  end
end

aa = aa / (3 ** n)

count = 0
while aa > 1
  aa = aa / 2
  count += 1
end

puts count

ちなみに、2で割る前に、元の3の乗で割っているのは、ループ抜けるさいの3/5で上がった指数が残っているからである。それはともかくとして、上のコードを見てみればわかるように、問題は「1/7のループに入るまえ」と「入ったあと」を区別するような制御が必要になる。

掛け算を改良する

そこで、何らかの方法で掛け算におけるループをフラグとして持たせ、もしループに入っている状態であるならば、「1/7を採用しない」とする方法を考えるといい。そこで、分数表の「1/7」に、別の素数をフラグとして持たせることによって、その組みあわせでなかったとするならば、既にループの中に入っていると認定し、そのままループするようにすればいいのではないだろうか。

……と書いていても、恐らく理解できない。というより書いている本人がそもそも理解ができないので、具体的 にその分数表を出すと次のようになる:

13/77, 170/39, 13/17, 19/13,
69/95, 19/23, 11/19

さて、これらをいきなり見せられても、どまどうと思うので、この分数表を因数分解したものを見せる。

13/(7 * 11)
(2 * 5 * 17) / (3 * 13)
13/17
19/13
(3 * 23) / (5 * 19)
19/23
11/19

ここで重要なのは、先も伸べたように、単純なカウンターを作ったときの例を考えてみればわかるように、5/6というのは、ある数を因数分解した際に、2と3が入っていないといけなかった。それを応用して、11が入っている場合にはループに入っていないと見做し、11と7の指数を下げ、13のフラグを立てる。

そしてその後、3の指数があるならば、それをカウントし続ける。3のカウントが無くなれば、延々とループの回数をカウントしている2と、3の回数を計算している5が出てくる。3のループは脱出したわけだから、一度13のフラグは削除し、今度は3の指数を元に戻し、次のループに供えるためのループが出てくる。最後に、まだループが続く可能性を考慮し、11を掛ける。もし、これでまだ7の指数が残っているならば、最初の分数表に引っかかる筈だ。

概要はわかった。問題は、これがちゃんと動くかだ。コードに書きなおすと、次のようになる。

class Rational
  def integer?
    self.to_i == self
  end
end

RATIONAL_LIST = [
  13/77r,
  170/39r,
  13/17r,
  19/13r,
  69/95r,
  19/23r,
  11/19r
]

r2  = 0
r3  = b = 11
r5  = 0
r7  = 13
n = ((3 ** r3) * (7 ** r7) * 11) * 1/1r

loop_flag = true
while loop_flag
  RATIONAL_LIST.each do |x|
    if (n * x).integer?
      n *= x
      loop_flag = true
      break
    end
    loop_flag = false
  end
end

n = n / 11
n = n / (3 ** b)

count = 0
while n > 1
  n = n / 2
  count += 1
end

puts count

当然、最後にフラグとして利用した11と3は残ってしまうため、あらかじめ割っておく。このようにして、分数表によって、足し算と掛け算が実装できるようになる。

まとめ

ざっくりと、分数表を使った足し算と掛け算の方法について解説をしてみた。今回の元の本になっているものでは、フィボナッチ数を算出するための分数表や、あるいは円周率の桁を出すための分数表が載っている。今回の説明がとてもいいとは、自分でも思っていないので、興味のある人は、下の本を読んで理解を深めるといいと思う。

反直観の数学パズル―あなたの数学的思考力を試す14の難問

反直観の数学パズル―あなたの数学的思考力を試す14の難問

ジャンケンみたいに三すくみになるサイコロについて

今日の風景

f:id:nisemono_san:20160810152435j:plain

mograg garage【ART SPACE /GALLERY】の展示で買った郡司侑祐という方の作品です。

はじめに

普通、サイコロと言うと、1から6までの数字が書いてあるものだ。イカサマのサイコロでは無い限り、お互いの出た目を比較すると、だいたい半々の確率になる筈だろう。しかし、これではゲーム性があまりにもない。そこで、サイコロの目を改造し、あるサイコロAと、あるサイコロB、あるサイコロCの出目がそれぞれジャンケンのように、三すくみになるようなサイコロが作れるという話が実はある。

オンライン上では、英語になるけれども、この記事で概要を知ることができる。また、実物は海外だとグランド・イリュージョン社が販売している。

f:id:nisemono_san:20160810225508j:plain

側面が二つ2のサイコロと、見えている側面全部が4であるサイコロが見える。

さて、このサイコロを実際に自分達の手で作ってみることは非常に楽しいことであるのは間違いないけれども、プログラマーなんだから、簡単にこの手のダイズについてシミュレーションしてみるのが楽しいだろう。

ジャンケンみたいなサイコロの組みあわせ

まず、最初にこの「ジャンケンみたいなサイコロ」の定義から始める。まず、任意の目を持つサイコロが三種類あり、それぞれのサイコロに対して、A、B、Cと名づける。このとき、AはBより勝率が高く、AはCより勝率が低い。同様に、BはCより勝率が高い。当然、CはAより勝率が高い……というようにくりかえされる。

さて、まず気になる出目に関してだが、3つ見つかっている。

  • {3, 3, 5, 5, 7, 7}, {2, 2, 4, 4, 9, 9}, {1, 1, 6, 6, 8, 8}
  • {1, 1, 1, 13, 13, 13}, {0, 3, 3, 12, 12, 12}, {2, 2, 2, 11, 11, 14}
  • {1, 4, 4, 4, 4, 4}, {3, 3, 3, 3, 3, 6}, {2, 2, 2, 5, 5, 5}

元記事によれは、最初の3組は、下の魔方陣から取られている。

|8|1|6|
|3|5|7|
|4|9|2|

それぞれの横の列が、そのままこのジャンケンみたいなサイコロの出目となっている。

実際に勝負させてみる

というわけで、実際に勝負させてみよう。これは簡単なプログラムなので、Lisp系であるところのRacketを使って書き下してみよう:

(define dice-a '(3 3 7 7 5 5))
(define dice-b '(2 2 9 9 4 4))
(define dice-c '(1 1 8 8 6 6))

(define (winner? a b)
  (> (car (shuffle a)) (car (shuffle b))))

(define (win a b)
  (printf "勝利数: ~a\n"
   (count (lambda(x) x)
          (build-list 100000 (lambda (x) (winner? a b))))))

特徴としては、build-listが、第2引数の回数だけ、第三引数の関数の結果をリスト化している。さて、まずdice-adice-bを5回セットさせてみると、以下のようになる。

> (for ([i 5]) (win dice-a dice-b))
勝利数: 55763
勝利数: 55565
勝利数: 55306
勝利数: 55609
勝利数: 55500

だいたい、5.5割の確率で勝利する。同様にAとCの場合:

> (for ([i 5]) (win dice-a dice-c))
勝利数: 44678
勝利数: 44407
勝利数: 44390
勝利数: 44805
勝利数: 44593

となる。つまり、0.5割ほど有利だということになる。次に、dice-bdice-cを組みあわせた場合

> (for ([i 5]) (win dice-b dice-c))
勝利数: 55475
勝利数: 55514
勝利数: 55418
勝利数: 55576
勝利数: 55436

となり、若干有利である。

2回振ると逆転するようなサイコロ

さて、次は{1, 4, 4, 4, 4, 4}, {6, 3, 3, 3, 3, 3}, {2, 2, 2, 5, 5, 5}なのだが、これには不思議な特徴があるらしい。その特徴というのが、なんでも二回振った合計の数だと、勝率が逆転してしまうというものらしい。なので、下のようにリファクタする

#lang racket
(define dice-a '(1 4 4 4 4 4))
(define dice-b '(6 3 3 3 3 3))
(define dice-c '(2 2 2 5 5 5))

(define (throw a) (car (shuffle a)))

(define (winner? a b)
  (> (throw a) (throw b)))

(define (winner-two? a b)
  (> (+ (throw a) (throw a))
     (+ (throw b) (throw b)))) 

(define (win a b)
  (printf "1回だけの勝利数: ~a\n"
   (count (lambda(x) x)
          (build-list 100000 (lambda (x) (winner? a b))))))

(define (win-two a b)
  (printf "2回の勝利数: ~a\n"
   (count (lambda(x) x)
          (build-list 100000 (lambda (x) (winner-two? a b))))))```

一度だけ振ってみる

まず、dice-adice-bの勝率から:

> (for ([i 5]) (win dice-a dice-b))
1回だけの勝利数: 69428
1回だけの勝利数: 69579
1回だけの勝利数: 69485
1回だけの勝利数: 69529
1回だけの勝利数: 69625

次に、dice-adice-cの勝率:

1回だけの勝利数: 41912
1回だけの勝利数: 41687
1回だけの勝利数: 41898
1回だけの勝利数: 41521
1回だけの勝利数: 41748

最後に、dice-bdice-cの勝率:

1回だけの勝利数: 58290
1回だけの勝利数: 58308
1回だけの勝利数: 58267
1回だけの勝利数: 58166
1回だけの勝利数: 58587

若干ばらつきはあるものの、AとBが対決した場合は、Aは7割勝利し、AとCが対決した場合はAは4割勝利し、BとCの場合は5.8割となる。ゲームとしてはともかく、定義的にはあっている。

次に二回振ってみる

そこで、次に二回振ってみることにする。dice-aおよびdice-bの場合だとすると:

> (for ([i 5]) (win-two dice-a dice-b))
2回の勝利数: 48276
2回の勝利数: 47996
2回の勝利数: 48410
2回の勝利数: 48008
2回の勝利数: 48136

ということになり、dice-adice-cだと

> (for ([i 5]) (win-two dice-a dice-c))
2回の勝利数: 59055
2回の勝利数: 59072
2回の勝利数: 59139
2回の勝利数: 59035
2回の勝利数: 59024

ということになる。そこで、さらにdice-bdice-cを比較すると:

(for ([i 5]) (win-two dice-b dice-c))
2回の勝利数: 40914
2回の勝利数: 40884
2回の勝利数: 40908
2回の勝利数: 41044
2回の勝利数: 41082

となるので、見事有利なサイコロが逆転した

まとめ

これが数学に属するのかどうかはよくわからないけれども、このように三すくみのサイコロができるという観点は面白かった。このサイコロはちょっと欲しい気もするけれども、作るとなると、オーダーメイドになるよなーという感じではある。それはともかくとして、「サイコロにはこういう観点から見ることもできるのだな」と思ったので、とてもわかりがあってとても面白かった。

反直観の数学パズル―あなたの数学的思考力を試す14の難問

反直観の数学パズル―あなたの数学的思考力を試す14の難問

数学のおもちゃ箱 下

数学のおもちゃ箱 下

シャッフルしたカードを順番にならべていったら、その並び順と同じ数が出てこない確率はどれくらいだろうか

今日の料理

f:id:nisemono_san:20160808113612j:plain

メンチカツサンドを汚なく作る方法。

トレーズというゲーム、そしてその問題

トレーズ(treize)というゲームがある。このゲームの名前はフランス語で13を表している。このゲームは、ジョーカーを抜いた52枚のトランプを使って遊ぶ。

まず、トランプを良くシャッフルする。そのトランプのカードに1から順番を付けながらめくっていく。このとき、順番と同じ番号が出た場合は勝利し、次のプレイヤーに残りのトランプを渡す。当然ながら、順番とカードの数が一致しないときもある。このとき、プレイヤーは負けということになる。

そこで、このカードゲームにならって、我々は13枚のカードを用意することにしよう。そして、このカードを順番を付けながらめくっていった場合、果して順番と一致しない数しか出ない確率はどれほどになるだろうか。さらに、もしこのカードの枚数を2倍に増やした場合、勝つ確率は上がるだろうか。それとも下るだろうか。

相対確率を調べる

上記の問題は、『反直感の数学パズル』から引用したものである。ちなみに相対確率(試行から当てはまったものを使う方法)では、次のようにして調べることができる。

def treize n
  card = [*0..(n - 1)].shuffle
  card.each_with_index do |k, i|
    return true if k == i
  end
  return false
end

TIMES = 100000

2.upto(52) do |n|
  win = 0
  1.upto(TIMES) do
    win += 1 if treize n
  end
  puts "#{n}枚の当たった回数は#{win}, 確率は#{win.to_f / TIMES}"
end

このようにして出力した結果は下のようになる。

13枚の当たった回数は63272, 確率は0.63272
26枚の当たった回数は63277, 確率は0.63277
39枚の当たった回数は63165, 確率は0.63165
52枚の当たった回数は63187, 確率は0.63187

本書には、13枚で1枚以上当たる確率と、52枚一枚以上当たる確率は、理論上「0.632121」まで一致すると伸べている。

完全順列

先ほどの、任意のカードをシャッフルして、順番と一致しないということを言いかえると、{1, 2, 3, ... , n}の順列とそれがシャッフルしてできた順列({a1, a2, a3, .. , an}と表記する)を照らしあわせると、それぞれの位置において同じ要素が現れない、という風に説明できる。これを完全順列と言うらしい。

さて、もしこのゲームにおいて外れる確率を計算したいとするならば、完全順列の総数を、順列の総数で割ればいいということになる。そこで、本書で紹介されているベルヌーイの方法を利用することにする。

包除原理を使う

包除原理とは、例えばAとBという集合があるとし、nをそこに属する要素を求める関数であると定義した場合、n(A \cup B)に属する要素を求めるにはどうすればいいか、ということである。

もちろん、AとBが独立している場合(つまり、要素の重複が存在しない場合)、n(A) + n(B)とすることで計算ができる。とはいえ、あらかじめ、AとBが独立しているかどうかがわからない場合、n(A) + n(B) - n(A \cap B)とする。理由は、Aを数え、かつBを数えた場合、AとBに属している数は2度数えられているという計算になるからだ。

さて、集合が2つの場合はわかった。今度は3つの集合であるA, B, Cの場合を考えてみよう。最初同様に、n(A) + n(B) + n(C)を計算する。当然ながら、n(A \cap B)n(A \cap C)n(B \cap C)の場合は前出同様、2重に数えられているわけだから、これを消す。

しかし、ちょっと考えてみよう。n(A \cap B \cap C)は、この段階でどれだけ含まれているか。まず、n(A) + n(B) + n(C)の段階で3回数えられている。そのあとn(A \cap B)n(A \cap C)n(B \cap C)で3回除去されているので、実質計算されていないことになる。これではまずいので、n(A \cap B \cap C)を足しあわせることにする。

ここで、ある法則性が理解できる。先ほどの集合の名前A, B, CをA1, A2, A3と表現した場合、まず最初にそれぞれの総数をとりあえず求め、そのあとに、2組の重複、つまりは偶数組は引き算をおこない、そして、3組の重複 、つまりは奇数組は足すとよい。これは集合が4つある場合もそうであるので、もし手元に手軽なノートがあるならば、各自で確認して欲しい。

完全順序と包除原理

さて、そこで完全順序の求めかたを考えてみよう。そこで、わかりやすいように、順列が{1, 2, 3}の場合を考えてみよう。

まず最初にこの順列をシャッフルして取りうる全ての数を計算する。そのリストを上げると下のようになる。

{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}

この程度なら個数は数えあげられるのだけれど、今はロジックを確認するためのものだから勘弁して欲しい。

まずそれぞれの順列に対して{a1, a2, a3}という名前を付ける。まず最初のケースとして{a1 = 1}, {a2 = 2}, {a3 = 3} という場合を取りあげる(今後、このように完全順序にならないものを「固定した」と表現する)。このとき、元の順列と、上記の事例は完全順序ではないので排除される。

{2, 3, 1}
{3, 1, 2}

実際、ここで既に要素は出ているのだが、あくまで包除原理にもとづいて計算を進める。先に言うと、奇数回で消さなければならない要素は{1, 2, 3}である。そこで、偶数回である今回は、{a1 = 1, a2 = 2}, {a2 = 2, a3 = 3} といった配列を足すことにする。とはいえ、これに当てはまるのは {1, 2, 3}だけなので、{1, 2, 3}を足すことになる。

{1, 2, 3}
{2, 3, 1}
{3, 1, 2}

で、これを改めて消すと、元の組みあわせが出てくる。

この説明を元に公式を作ると、次のようになる。まずa_nはn個が固定された(つまり、完全順序数とならない)組みあわせ数だと考えて欲しい。

 n! - a_1(n - 1)! + a_2(n - 2)! - a_3(n - 3)! + ... 1

そこで、{a1}や{a1, a2}の組み合わせの総数が必要となる。これは箱の中にボールが入っていて、そこから取りだすときの組みあわせと考えるとわかりやすい。

先の例であるならば、固定された要素数は1個である。その1個をボールから取り出す可能性は3つある。なので、3になり、そして残りの順序を計算する。これは_nC_r = \frac{n!}{r!(n - r)!}という公式があるので、これを利用し、変形すると、次のようになる。

 n! - \frac{n!}{1!(n - 1)!}(n! - 1)! + \frac{n!}{2!(n - 2)!}(n - 2)! - \frac{n!}{3!(n - 3)(n - 3)!} + ... 1

ということになる。良く見れば、分母は削ることができる。なので、さらに簡略化して

 n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + ... 1

とでき、さらに共通のn!をまとめれば、次の公式が出てくる。

 n!(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} ... + (-1)^{n}\frac{1}{n!}

実際にこれを利用して3を計算すると、次のようになる。

 6(\frac{2}{6})

また、5を計算すると、44となり、本書と一致する。そして、確率を計算する場合、完全順序の総数を順序の総数で割れば良い。なので、実質:

 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} ... + (-1)^{n}\frac{1}{n!}

ということになる。そして、この式からわかるように影響する分子はどんどん大きくなっていくため、枚数をいくら増やしても、その確率にほぼ影響は無い(興味がある人は実際にコードを書いて検証してみるといいかもしれない)。

まとめ

だいたい、エントリを書く前にノートに草稿を書くという律儀なことをしているのだけれど、このエントリを書くためにノートを4ページくらい使った。とはいえ、それを使うだけの納得感は味わえたので、非常によかった。数学の良さがわかるように、一歩くらいは前進したのかもしれない。

反直観の数学パズル―あなたの数学的思考力を試す14の難問

反直観の数学パズル―あなたの数学的思考力を試す14の難問