パズル神は細部に宿り給う

2008 7/18

2人で世界を征服する方法

まず誰か1人でいいので、自分と志を同じくするか、自分の言いなりになる人間を連れてくる。*1
その2人を含む3人で、多数決で全てを決する1つ目の秘密結社を作る。
その3人を含む5人で、多数決で全てを決する2つ目の秘密結社を作る。
その5人を含む9人で、多数決で全てを決する3つ目の秘密結社を作る。
n番目の秘密結社は2^n+1人を支配できる。

　世界の総人口はいまちょっとググったところでは約67億人。

2^10 = 1024 ≒ 10^3
2^33 ≒ 8*10^9 > 67*10^8

　だから、33段階の秘密結社を通じて全人類を支配することができる。めでたしめでたし……という話が何の役に立つだろうか？

　世界で最も大きな組織には何段階の階級が存在するでしょうか？

　というフェルミ推定の問題が出されたときに役に立つかも知れない。

　実際には全人類は1つの組織に統一されていないし、各階層が単純多数決というもっとも効率が悪い*2と思われる意志決定方法であってこの数なので、現実の組織に必要な階層数はこの推計よりかなり少ないと思ってよいだろう。

　たとえばアメリカ合衆国大統領からイラクのどこかで哨戒中の二等兵に何か命令を伝える必要が生じたとする*3。途中で何回命令を受け渡す必要があるだろうか？

　直接つまり1ということはなさそうだというのは常識でわかるが、上限について何か推定できることがあるだろうか。ここで33より多くなることは絶対にありえないと断言してよさそうである。

DSI 米軍階級

　答え合わせにちょっとググってみる。概ね妥当と言ってよさそうである。

*1：ここがクリアできない人は世界征服などという大それた野望は諦めよう！
*2：全構成員数に占める意志決定に必要な人数の割合が多いという意味で。社会的政治的な価値とはなんの関係もない。
*3：実在する巨大組織の例として最初に思いついたのが米軍だっただけなので自衛隊でも人民解放軍でもマイクロソフトでも好きなように置き換えてもらって構わない。

おまけ

<a href="http://www.nicovideo.jp/watch/sm820860">【ニコニコ動画】某国に世界を征服された</a>

by 木戸孝紀 tags:パズルフェルミ推定社会数学

2008 3/29

ルービックマジックが復刻されている

ゲーム森羅万象 0 コメント »

ルービックキューブは25手で完成可能、米研究者が新解法の証明に成功 – Technobahn

　上のニュースを見てルービックキューブで検索していたら、昔持っていたこれが復刻されているのを発見した。

　もっとも、様々な点でルービックキューブに比べると遥かに劣る。一番の問題は繋ぎの部分がテグスのせいで耐久性がなくて、ちょっと力の入れ方を間違えたり古くなったりするとすぐ壊れるところで、昔もかなり短い時間で壊れたような記憶がある。

　今考えるとそこまで面白いとも思えないのだが、かなり懐かしい。買ってみようかな。

おまけ

　これと同じ作者とか。多芸だなあ。
<a href="http://www.nicovideo.jp/watch/sm2531465">【ニコニコ動画】【Phun】ニコニコスイッチ☆アイランド総集編</a>

by 木戸孝紀 tags:おもちゃパズル買い物

2007 11/23

数学パズルペプシ算

WEB情報通信 0 コメント »

清涼飲料水のキャップのオマケとして、10 種類の清涼飲料水マンのキャップがついてくるキャンペーンがありました。そこで、豪気な凛さんは 24 本の箱買いを実行しました。24 本も買えば、10 種類そろっていそうな感じですが、実際には（以下省略）そこで、そろわない場合の確率はどのくらいになるのか？　果たして凛さんは、全部の種類の清涼飲料水マンのキャップを持っているのだろうか？

（サンプル: "多倍長計算のサンプル(ペプシ算)"）

　ペプシ算ファイナル – 永字八法で知って、久々にパズル欲を触発されたのでやってみた。我ながらなかなかエレガント。大元ページの再帰的な計算法では手も足も出ない数になっても瞬殺。rubyのBignumが許す限り。

pepsi.rb


class Integer
  def factorial
    (1..self).inject(1){|r, i| r * i}
  end
  def combination(n)
    self.factorial / (n.factorial * (self - n).factorial)
  end
end
def pepsi(m, n)
  result = (0..m).inject(0){|r, i| r + (-1)**i * m.combination(i) * (m - i)**n}
  (result * 10000000000000000 / m**n).to_f / 10000000000000000
end
puts pepsi(ARGV[0].to_i, ARGV[1].to_i)

　下のように実行するとm種類のおまけ付きのペプシn本入りを箱買いしたときにコンプできている確率を返してくれます。


ruby pepsi.rb m n

　たとえば例題の通りなら、


ruby pepsi.rb 10 24

ね。それだけ。

11/27追記

　combinationも整数のメソッドにしてみたりちょっと表現を整理。ロジックはまったく一緒。それと、30 300程度で計算できなくなるのは、よく見たらBignumに入りきらないって言ってるんじゃなくてFloatで表現できないと言ってるだけだった。道理で少なすぎると思った。整数だけで最後の割り算をするようにしたらもっとでかい数でもいけるようになった。


ruby pepsi.rb 365 2287
0.500370783936947

　つまり誕生日が均等に分布していると仮定して2月29日を無視した場合、人口2287人以上の街では「毎日誰かしらは誕生日を迎えている」確率5割以上。へー。

おまけ

<a href="http://www.nicovideo.jp/watch/sm88000">【ニコニコ動画】マイヤヒー２</a>

by 木戸孝紀 tags:Ruby パズルプログラミング数学

2006 10/7

嘘つき天秤答え合わせ

科学技術哲学 2 コメント »

　見た目も大きさも同じ8個の重りがあります。7個は重さも同じですが1つは他よりわずかに軽いニセモノです。天秤を使ってニセモノを確実に特定するには何回天秤を使う必要があるでしょうか。ただしこの天秤はただの天秤ではなく嘘つき天秤で、1回だけ嘘をつく（左に傾く・右に傾く・釣り合うの中から間違った結果を出す）可能性があります。

　まず私の解答を書きます。正解は4回です。4回で確実に特定する手順は以下の通り。

１２３
４５６
７８９

　重りを上のような3×3の行列風に並べます（９はダミー）。

　4回の各測定で、横・縦・右斜め・左斜めの列ごとに3個ずつをそれぞれグループとし、９が入っていない2グループを天秤に載せます。

　釣り合った場合は皿に載っている6個を、傾いたら上がった皿に載っている以外の6個に白判定回数を+1します。

　4回目が終わった時各重りの白判定回数が1以下のものが1つだけ残ります。それがニセモノです。

　次に3回以下ではできないことを示します。結果的にニセモノを特定できた時、同時に天秤が何回目にどんな嘘をついたか、あるいは嘘をつかなかったかも全て特定されます。

　天秤を3回使う時、天秤の嘘のつき方は1-3回目でそれぞれ2通りの嘘をつく、あるいは全くつかないの7通りがありえます。さらにニセの重りがどれかで8通りの場合があるので、問題全体の場合の数は 7 * 8 = 56 通りです。

　対して天秤から得られる情報は最高でも 3 ^ 3 = 27 通りしかありません。3回で確実にニセモノを特定できるということは、27通りの結果を見ただけで56通りの問題のどれかひとつを確実に言い当てられることを意味し、これは明らかに不合理です。

　よって3回では特定できません。

解説

　元となった有名な金貨8枚の問題（ビルゲイツの面接試験にももちろん載ってる）に適当に条件を付け加えてみたら意外にもすごく面白い問題に化けてしまいました。

　一見答え方も元の問題と同じに見えます。元の問題は2回で特定できます。それを応用すれば、各測定を2回繰り返し、嘘が出て割れた場合だけもう一回必要なので答えは5回……と言いたくなります。

　しかし！　正解は4回でした。4回でできる方法があったんです。面白いですね。最初は元の問題の先入観から「まず１２３と４５６番の重りを天秤に載せて、釣り合った場合……」という風にニセモノを特定する方向で考え始めたので、ややこしすぎてハマりました。

人力検索はてな – 論理パズル「嘘つき天秤」

　で答えてもらったDanielさんの解答を見るとそれでできないわけではないですが。

　解法を見つけるには元の問題に立ち返って、そもそも天秤で何をしているのか、そして特定できたと言うためには最後にどのような状態になっていなければならないかをちゃんと原理から見直さないといけませんでした。

　まず天秤が釣り合うということは皿に載っている全ての重りが白だということです。天秤が傾くということは上がった方の皿に載っているもの以外の全ての重りが白だということです。

　そして3/3/2個に分けるのは、天秤の1回で3通りを識別できる特性を最大現生かすためです。

　そしてここからがポイントですが、今回の天秤が1回だけ嘘をつくかもしれない中で、ニセモノを特定できたと言える条件は他の7個の重り全てが2回以上白判定を受けていることです。

　2回以上白判定を受けていれば最低でもどちらかは真実、すなわちその重りは本物です。逆に言えばその条件を満たせなければ失敗です。

　条件を満たすには、もっとも運が悪い場合でも確実に白判定の数が0や1の重りを追いつめ、その数を減らすことができるようにグループ分けしなければなりません。

　それを可能にする方法は、ある時点でもっとも白判定回数の少ないものが最大限別々になるような3グループに分けて計り続ける方法です。ここまで来てようやく行列風のグループ分けに思いいたりました。

具体例

　ニセモノは3、2回目に嘘が出て釣り合うはずが左に傾く場合。ただし3*3の数字は、

１２３
４５６
７８９

　と同じ位置にある番号の重りの白判定回数。

１回目：１２３・４５６・７８９がグループ

０００
１１１
１１１

２回目：１４７・２５８・３６９がグループ

１０１
２１２
２１２

３回目：１５９・２６７・３４８がグループ

２１１
２２３
３１３

４回目：１６８・２４９・３５７がグループ

３２１
３２４
３２４

結論：1回しか白判定されていない３がニセモノ。

　3回でできないことを示した方法はもっと一般的にできます。k回天秤を使い、重りがn個の時、


n(2k+1) > 3^k

　ならば特定不可能です。問題は n=8 k=4 だったので 72 <= 81 なので特定できたのは不思議ではありません。

　というか私が諦めずに4回でできる方法を探したのは先にこっちの式でできないと決まったわけではないとあたりをつけていたからです。

　また、この式から重りが9個でも、81 = 81 なのでできるかもしれないことが分かります。現に上の解答の手順でダミーを本物と区別しないだけでできます。

　天秤を3回しか使わない場合、できるのは3個までということも分かります。4個になると28 > 27 なのでできません。

　しかし、適当に考えた割には本当に面白い問題でした。付き合っていただいた方々ありがとうございます。

by 木戸孝紀 tags:クイズパズル解答論理

2006 10/3

頭の体操第3回嘘つき天秤

科学技術哲学 10 コメント »

　見た目も大きさも同じ8個の重りがあります。7個は重さも同じですが1つは他よりわずかに軽いニセモノです。天秤を使ってニセモノを確実に特定するには何回天秤を使う必要があるでしょう。ただしこの天秤はただの天秤ではなく嘘つき天秤で、1回だけ嘘をつく（載せたものとは何の関係もなく左右に傾いたり釣り合ったりする）可能性があります。

　前の問題のコメント欄で話しているときに思いついた問題。思いついたばかりなので実は私もまだ答えを知らない。解答熱烈募集中。

　とりあえず元ネタの有名な問題の解法を単純に拡張すれば5回でできることは確実。4回以下でできる方法があればその方法を見つけ、同時にさらにそれ以下の回数ではできないことの証明もつけられればパーフェクトだと思う。