機械Xと互い重さの違う重り1〜nがあるとする
また「1&2」「1&3」…「1&n」「2&3」…「2&n」…「n-1&n」とn(n-1)/2個の項目がある
パンチカードが何枚かあるとする
機械Xは例えば「1&2」「2&5」「2&3」の項目に穴を開けられたカードを読み取れば
まず重り1と2を比べ、次に2と5を比べ、最後に2と3を比べその結果を
「1<2」「2>5」「2<3」という風に出力することが出来るとする

パンチカードがm枚しか無かったとき
重りを比べる操作をk回以上行わせないと、どの重りが一番重いか分からないとき
k=f(n,m)とおくことで関数f:N×N→Nを定義する

例えばn=3の場合を考える
1枚目のパンチカードは「1&2」の項目にだけ穴をあけ機械に読み取らせ
出力が「1<2」なら「2&3」、出力が「1>2」なら「1&3」と
2枚目のパンチカードの項目に穴をあけて読み取らせば
機械に2回重りを比べる操作をさせるだけで重り1,2,3のどれが一番重いか分かる
しかしパンチカードが1枚だけしか無いなら「1&2」「1&3」「2&3」に穴をあけて読み取らせ
機械に3回重りを比べる操作をさせないとどれが一番重いか分からない
このように考えてけばf(3,1)=3 f(3,2)=f(3,3)=f(3,4)...=2だと分かる

(1) f(n,1)は幾つ？
(2) mが十分大きいならf(n,m)は幾つ？
(3) f(n,2)は幾つ？