秤の問題
　　　　　　　　　　　　　　　　　　           　　2000.09.06 deepgreen　

高橋謙一郎さんのＨＰ（掲示板）の話題となったものです｡(2000.06.05)

ｎ個の中に１つだけ重さの違うものがある（重いか軽いかは不明）とき
秤を何回使えばよいか？というものです。１３個の場合、３回の測定で
確定できます。一般解は、（３＾ｎ−１）／２とのことです。
この具体的な手順を見つけることが問題です。

□用語の定義

？ｎ　：ｎ個の中に１つだけ重さの違うものがある（重いか軽いかは不明）
？？ｎ：ｎ個の中に１つだけ重さの違うものがあるかもしれない
Ｓｎ　：ｎ個はすべて同じ重さ（標準の）である
＋ｎ　：ｎ個の中に１つだけ重いものがあるかもしれない（不確定）
−ｎ　：ｎ個の中に１つだけ軽いものがあるかもしれない（不確定）
＋＋ｎ：ｎ個の中に１つだけ重いものがある（確定）
−−ｎ：ｎ個の中に１つだけ軽いものがある（確定）

□比較のパターン（秤の使い方）

［ｒｕｌｅ１」
　　？ｎからｍ個を２組取り出して比較する。
　　　　＝のとき　：２ｍ個はすべて同じ重さであり
　　　　　　　　　　違う重さのものは残りのｎ−２ｍ個の中にある
　　　　≠のとき　：どちらかのｍ個に異なる重さのものがある
　　　　　　　　　　残りのｎ−２ｍ個は同じ重さである

　　これを以下のように記述する
　　？ｎ　−＞　？ｍ　ｖｓ　？ｍ
　　　　　　　　　　　＝　：？（ｎ−２ｍ），Ｓ２ｍ
　　　　　　　　　　　≠　：＋ｍ，−ｍ，Ｓ（ｎ−２ｍ）

［ｒｕｌｅ２」
　　？ｎからｍ個を取り出し、Ｓｍと比較する（すでに、Ｓｍが確定しているとき）
　　　　＝のとき　：ｍ個はすべて同じ重さであり
　　　　　　　　　　違う重さのものは残りのｎ−ｍ個の中にある
　　　　＜のとき　：ｍ個に軽いものがある。よって、−−ｍ
　　　　　　　　　　残りのｎ−ｍ個は同じ重さである
　　　　＞のとき　：ｍ個に重いものがある。よって、＋＋ｍ
　　　　　　　　　　残りのｎ−ｍ個は同じ重さである

　　これを以下のように記述する
　　？ｎ　−＞　？ｍ　ｖｓ　Ｓｍ
　　　　　　　　　　　＝　：？（ｎ−ｍ），Ｓ２ｍ
　　　　　　　　　　　＜　：−−ｍ，Ｓ（ｍ＋ｎ）
　　　　　　　　　　　＞　：＋＋ｍ，Ｓ（ｍ＋ｎ）
　　　　　　　　
［ｒｕｌｅ３］
　　＋＋ｎから（ｎ＋２）／３個を２組取り出して比較する
　　　　＝のとき　：２組の（ｎ＋２）／３個はすべて同じ重さであり
　　　　　　　　　　違う重さのものは残りのｎ−（ｎ＋２）／３＊２個の中にある
　　　　≠のとき　：重い方の（ｎ＋２）／３個に異なる重さのものがある
　　　　　　　　　　残りのｎ−（ｎ＋２）／３個は同じ重さである

　　これを以下のように記述する
　　＋＋ｎ　−＞　＋（ｎ＋２）／３　ｖｓ　＋（ｎ＋２）／３
　　　　　　　　　　　＝　：＋＋(n-(n+2)/3*2)，Ｓ（(n-(ｎ+2)/3)*2）
　　　　　　　　　　　≠　：＋＋（ｎ＋２）／３，Ｓ（ｎ−（ｎ＋２）／３）
　　同様に、−−ｎも定義する　　　　　　
　　−−ｎ　−＞　−（ｎ＋２）／３　ｖｓ　−（ｎ＋２）／３
　　　　　　　　　　　＝　：−−(n-(n+2)/3*2)，Ｓ（(n-(ｎ+2)/3)*2）
　　　　　　　　　　　≠　：−−（ｎ＋２）／３，Ｓ（ｎ−（ｎ＋２）／３）

　　☆これによって、＋＋９は２回、＋＋２７は３回の測定で済むことがわかる

［ｒｕｌｅ４］
　　＋ｎ，−ｎ，Ｓｍのとき、＋ｎ，−ｎからそれぞれｋ個、Ｓｍから２ｋ個とりだして比較する
　　　　＝のとき　：比較対象の４ｋ個はすべて同じ重さであり
　　　　　　　　　　違う重さのものは＋（ｎ−ｋ），−（ｎ−ｋ）のいずれかにある
　　　　≠のとき　：＋ｋ，−ｋのいずれかに異なる重さのものがある
　　　　　　　　　　残りの２組の（ｎ−ｋ）個は同じ重さである

　　これを以下のように記述する
　　＋ｎ，−ｎ，Ｓｍ　−＞　（＋ｋ，−ｋ）　ｖｓ　Ｓ２ｋ
　　　　　　　　　　　＝　：＋（ｎ−ｋ），−（ｎ−ｋ），Ｓ（ｍ＋２ｋ)
　　　　　　　　　　　≠　：＋ｋ，−ｋ，Ｓ（ｍ＋（ｎ−ｋ）＊２））

［ｒｕｌｅ５］　　このルールが見つけにくかった！！！
　　＋ｎ，−ｎ，Ｓｍのとき、ｎ＝ａ＋ｂとなるａ，ｂの２つにわけ、以下の２組を比較する
　　　　（＋ａ，−ｂ）　と　（−ａ，Ｓｂ）　　残りは、＋ｂ，Ｓ（ｍ−ｂ）
　　　　＝のとき　：比較対象の（＋ａ，−ｂ）と（−ａ，Ｓｂ）はすべて同じ重さであり
　　　　　　　　　　違う重さのものは＋ｂにある。故に、＋＋ｂとなる
　　　　＜のとき　：−ｂに軽いものがある。故に、−−ｂとなる
　　　　　　　　　　（右側の−ａに重いものはないので、左側は軽くなければならない）
　　　　＞のとき　：＋ａ，−ａのいずれかに違う重さのものがある

　　これを以下のように記述する
　　＋ｎ，−ｎ，Ｓｍ　−＞　（＋ａ，−ｂ）　ｖｓ　（−ａ，Ｓｂ）　ただし、ｎ＝ａ＋ｂ
　　　　　　　　　　　＝　：＋＋ｂ，Ｓ（ｍ＋２ｎ−ｂ）
　　　　　　　　　　　＜　：−−ｂ，Ｓ（ｍ＋２ｎ−ｂ）
　　　　　　　　　　　＞　：＋ａ，−ａ，Ｓ（ｍ＋２ｂ）

いよいよ、本題です。

□？４０は、何回で秤れるか？

　�@４０＝１３＋１３＋１４に分解し、
　　？４０　−＞　？１３　ｖｓ　？１３
　　　　　　　　　　　　　＝　：　？１４，Ｓ２６　　　　　　　�A−１
　　　　　　　　　　　　　≠　：　＋１３，−１３，Ｓ１４　　　�A−２

　�A−１　１４＝９＋５に分解し、
　　？１４　−＞　？９　ｖｓ　Ｓ９
　　　　　　　　　　　　＝　：　？５，Ｓ１８　　　　　　　　　�B−１
　　　　　　　　　　　　＜　：　−−９，Ｓ１４　　　　　　　　�B−２　　
　　　　　　　　　　　　＞　：　＋＋９，Ｓ１４　　　　　　　　�B−３
　　�B−１　？５は、あと２回で測定できる（簡単なので省略）
　　�B−２，�B−３は、あと２回の測定で確定できる。（ｒｕｌｅ３）

　　よって、この場合は、４回の測定で確定できることになる。

　�A−２　ｒｕｌｅ５で、ａ＝４，ｂ＝９とする（ｎ＝１３）と
　　　＋１３，−１３，Ｓ１４　−＞　（＋４、＋９）　ｖｓ　（−４，Ｓ９）
　　　　　　　　　　　　＝　：　＋＋９，Ｓ３１　　　　　　　　�B−４
　　　　　　　　　　　　＜　：　−−９，Ｓ３１　　　　　　　　�B−５
　　　　　　　　　　　　＞　：　＋４，−４，Ｓ３２　　　　　　�B−６
　　�B−４，�B−５は、あと２回の測定で確定できる。（ｒｕｌｅ３）
　　　　
　�B−６　ｒｕｌｅ４を適用する
　　　＋４，−４，Ｓ３２　−＞　（＋３、−３）　ｖｓ　Ｓ６
　　　　　　　　　　　　＝　：　＋１，−１，Ｓ３８　　　　　　�C−１
　　　　　　　　　　　　＜　：　−−３，Ｓ３７　　　　　　　　�C−２
　　　　　　　　　　　　＞　：　＋＋３，Ｓ３７　　　　　　　　�C−３
　　�C−１は、あと１回の測定で確定できる。（ｒｕｌｅ３）
　　�C−２，�C−３は、あと１回の測定で確定できる。（ｒｕｌｅ３）

　　よって、この場合も、４回の測定で確定できる。

　以上により、？４０は、４回の測定で確定できる。


□？？３８は、何回で秤れるか？

　�@３８＝１３＋１３＋１２に分解し、
　　？？３８　−＞　？？１３　ｖｓ　？？１３
　　　　　　　　　　　　　＝　：　？？１２，Ｓ２６　　　　　　�A−１
　　　　　　　　　　　　　≠　：　＋１３，−１３，Ｓ１４　　　�A−２
　　�A−２は？４０と同じなので、あと３回で測定できる。（合計は４回）
　
　�A−１　１２＝９＋５に分解し、
　　？？１２　−＞　？９　ｖｓ　Ｓ９
　　　　　　　　　　　　＝　：　？？３，Ｓ１８　　　　　　　　�B−１
　　　　　　　　　　　　＜　：　−−９，Ｓ１４　　　　　　　　�B−２　　
　　　　　　　　　　　　＞　：　＋＋９，Ｓ１４　　　　　　　　�B−３
　　�B−１　？？３は、あと２回で測定できる（簡単なので省略）
　　�B−２，�B−３は、あと２回の測定で確定できる。（ｒｕｌｅ３）

　　よって、この場合は、４回の測定で確定できることになる。

　以上より、？？３８は、４回の測定で確定できる。


□？タイプのとき、ｎ回の測定で確定できる数は、（３＾ｎ−１）／２
　
　以下の関数ｆ（ｎ）を定義する。
　　ｆ（ｎ＋１）＝　３ｆ（ｎ）＋１　　　　　　　　　　　（１）式
　　ｆ（１）　　＝　２
　これを解くと、
　　　　ｆ（ｎ）＝　（３＾ｎ−１）／２　
　　　　ｆ（ｎ）＝　ｆ（ｎ−１）＋ｇ（ｎ−１）　　　　　（２）式　　
　　　　　　　　　　　　　ただし、ｇ（ｎ）＝　３＾ｎ
　となる。

　？ｆ（ｎ＋１）を考える。

　�@（１）式の関係により、ｆ（ｎ＋１）を f(n), f(n), f(n)+1 に分解する。
　　？ｆ（ｎ＋１）−＞　？ｆ（ｎ）　ｖｓ　？ｆ（ｎ）
　　　　　　　　　　　　＝　：？（ｆ（ｎ）＋１），Ｓ（ｆ（ｎ）＊２）　　　　�A−１　
　　　　　　　　　　　　≠　：＋ｆ（ｎ），−ｆ（ｎ），Ｓ（ｆ（ｎ）＋１）　　�A−２
　　　　　　　　　　　　　　　
　�A−１　？（ｆ（ｎ）＋１）は、（２）式により、f(n-1)＋ｇ(n-1)＋１と変形すると、
　　　？（ｆ（ｎ）＋１）−＞　？ｇ(nｰ1)　ｖｓ　Ｓ（ｇ(nｰ1)）
　　　　　　　　　　　　＝　：？（ｆ（ｎ−１）＋１），Ｓ（ｇ(n-1)）　　　　 �B−１　
　　　　　　　　　　　　＜　：−−g(n-1), Ｓ（f(n-1)+1）        　        　�B−２
　　　　　　　　　　　　＞　：＋＋g(n-1), Ｓ（f(n-1)+1）        　        　�B−３
　　�B−２，�B−３は、ｎ−１回で確定できる（ｒｕｌｅ３）
　　�B−１は、�A−１と同様の繰り返しができる。

　�A−２　＋ｆ（ｎ），−ｆ（ｎ）も（２）式により、f(n-1)+g(n-1)に分解する。
　　ｒｕｌｅ５で、a=f(n-1), b=g(n-1) とすると
      + f(n),- f(n), S(f(n)+1) -> (+f(n-1),-g(n-1)) vs (-f(n-1),S(g(n-1))
                        ＝　：　＋＋ｇ（ｎー１），．．．　　　　　　　　　　�B−４
                        ＜　：　−−ｇ（ｎ−１），．．．　　　　　　　　　　�B−５
　　　　　　　　　　　　＞　：　＋ｆ（ｎ−１），−ｆ（ｎ−１），．．．　　　�B−６
　　�B−４，�B−５は、ｎ−１回で確定できる（ｒｕｌｅ３）
　　�B−６は、�A−２と同様の繰り返しができる。

　以上より、？タイプのｆ（ｎ＋１）個の識別はｎ＋１回の測定でできる。
　（概略説明でした）

★なお、ｆ（ｎ）が上限である説明は私には思いつきません。どなたかご存知のかたは
　教えてください。

　？？タイプの場合、ｆ（ｎ）のかわりに以下の再帰関数となる。

　　　ｈ（ｎ＋１）＝　３ｈ（ｎ）−１　　　　　　　　　（３）式
　　　ｈ（２）　　＝　３
　これより、
　　　ｈ（ｎ）＝　（３＾ｎ−３）／２
　　　ｈ（ｎ）＝　ｈ（ｎ−１）＋ｇ（ｎ−１）　　　　　（４）式
　　　　　　　　　　　　ただし、ｇ（ｎ）＝３＾ｎ

　（３）式，（４）式により、？？３８の手順を再帰的に書き直すことができる。