>>13 で触れられていた問題をあらためて書き直しこちらに記載するとともに、その詳解をコンパクトにまとめておきたく思います。
■問題
コインが 18 枚あり、たがいに見分けがつきません。
このうち 9 枚についてはそれぞれの重さが 10 グラム、残りの 9 枚についてはそれぞれの重さが 11 グラムであるとわかっています。
18 枚中の特定の 1 枚の重さを X とします。残りの 17 枚の重さを A B C D E F G H I J K L M N O P Q とします。
天秤を３回使って X が 10 グラムなのか 11 グラムなのかを判定してください。ただし、天秤にのせるものとしては、 18 枚のコイン以外に、重りなどは使わないでください。
■解答
weighing:(XABC)vs(DEFG)
case:(<)
| weighing:(X)vs(A)
| case:(<)
| | {X is 10g}
| case:(>)
| | {X is 11g}
| case:(=)
| | weighing:(XA)vs(BC)
| | case:(<)
| | | {X is 10g}
| | case:(>)
| | | {X is 11g}
| | case:(=)
| | | {X is 10g}
| | endweighing:
| endweighing:
case:(>)
| weighing:(X)vs(A)
| case:(<)
| | {X is 10g}
| case:(>)
| | {X is 11g}
| case:(=)
| | weighing:(XA)vs(BC)
| | case:(<)
| | | {X is 10g}
| | case:(>)
| | | {X is 11g}
| | case:(=)
| | | {X is 11g}
| | endweighing:
| endweighing:
case:(=)
| weighing:(XDEFG)vs(ABCHI)
| case:(<)
| | {X is 10g}
| case:(>)
| | {X is 11g}
| case:(=)
| | weighing:(XHI)vs(ABC)
| | case:(<)
| | | {X is 10g}
| | case:(>)
| | | {X is 11g}
| | case:(=)
| | | *impossible*
| | | because of {X=A=B=C=D=E=F=G=H=I}
| | endweighing:
| endweighing:
endweighing:
注１:
weighing:(ホニャ)vs(ララ)
は、天秤の左の皿に「ホニャ」、右の皿に「ララ」を乗せて計量することを意味しています。
また、case:() は、直前の weighing: の結果により手続きが分岐することを意味しています。case:(<) は左の皿が軽い、case:(>) は右の皿が軽い、case:(=) は釣り合うことを意味しています。
endweighing:は、分岐について全て記述しおわったとのマークです。
使用例
9 枚のメダル中、軽い 1 枚をみつけだしたい。メダルを A B C D E F G H I とする。
１回目に ABC を左に乗せ、 DEF を右に乗せるときには
weighing:(ABC)vs(DEF)
case:(<)
| 左が軽いときの手続きをここに書く
case:(>)
| 右が軽いときの手続きをここに書く
case:(=)
| 釣り合うときの手続きをここに書く
endweighing:
と書くことにします。
それぞれの分岐ごとに、天秤計測を更に入れ子にして書くことができます。
weighing:(ABC)vs(DEF)
case:(<)
| weighing:(A)vs(B)
| case:(<)
| | {A が軽い}
| case:(>)
| | {B が軽い}
| case:(=)
| | {C が軽い}
| endweighing:
case:(>)
| [ 今回は省略 ]
case:(=)
| [ 今回は省略 ]
endweighing:
使用例終わり。
注2
| | | *impossible*
| | | because of {X=A=B=C=D=E=F=G=H=I}
とありました。
weighing:(XABC)vs(DEFG)
で釣り合い、
weighing:(XDEFG)vs(ABCHI)
で釣り合い、
weighing:(XHI)vs(ABC)
で釣り合うことはありえません。
このときには
{X=A=B=C=D=E=F=G=H=I}
となりますが、10枚のコインが同じ重さになることは問題の設定上ありえないからです。同じ重さは 9 枚までです。
注3
weighing:(XABC)vs(DEFG)
で釣り合ったもとでの
weighing:(XDEFG)vs(ABCHI)
の意味は
weighing:(XX)vs(HI)
と等価です。
これより、Xの重さが判定できます。
(XDEFG)は、(XXABC)と等しく、これと(ABCHI)とを比べているからです。
また、
weighing:(XABC)vs(DEFG)
で釣り合い、
weighing:(XDEFG)vs(ABCHI)
で釣り合ったもとでの
weighing:(XHI)vs(ABC)
は
weighing:(XXX)vs(ABC)
と同じ意味です。
これより、Xの重さが判定できます。
>>13 で触れられていた問題をあらためて書き直しこちらに記載するとともに、その詳解をコンパクトにまとめておきたく思います。
■問題
コインが 18 枚あり、たがいに見分けがつきません。
このうち 9 枚についてはそれぞれの重さが 10 グラム、残りの 9 枚についてはそれぞれの重さが 11 グラムであるとわかっています。
18 枚中の特定の 1 枚の重さを X とします。残りの 17 枚の重さを A B C D E F G H I J K L M N O P Q とします。
天秤を３回使って X が 10 グラムなのか 11 グラムなのかを判定してください。ただし、天秤にのせるものとしては、 18 枚のコイン以外に、重りなどは使わないでください。
■解答
weighing:(XABC)vs(DEFG)
case:(<)
| weighing:(X)vs(A)
| case:(<)
| | {X is 10g}
| case:(>)
| | {X is 11g}
| case:(=)
| | weighing:(XA)vs(BC)
| | case:(<)
| | | {X is 10g}
| | case:(>)
| | | {X is 11g}
| | case:(=)
| | | {X is 10g}
| | endweighing:
| endweighing:
case:(>)
| weighing:(X)vs(A)
| case:(<)
| | {X is 10g}
| case:(>)
| | {X is 11g}
| case:(=)
| | weighing:(XA)vs(BC)
| | case:(<)
| | | {X is 10g}
| | case:(>)
| | | {X is 11g}
| | case:(=)
| | | {X is 11g}
| | endweighing:
| endweighing:
case:(=)
| weighing:(XDEFG)vs(ABCHI)
| case:(<)
| | {X is 10g}
| case:(>)
| | {X is 11g}
| case:(=)
| | weighing:(XHI)vs(ABC)
| | case:(<)
| | | {X is 10g}
| | case:(>)
| | | {X is 11g}
| | case:(=)
| | | *impossible*
| | | because of {X=A=B=C=D=E=F=G=H=I}
| | endweighing:
| endweighing:
endweighing:
注１:
weighing:(ホニャ)vs(ララ)
は、天秤の左の皿に「ホニャ」、右の皿に「ララ」を乗せて計量することを意味しています。
また、case:() は、直前の weighing: の結果により手続きが分岐することを意味しています。case:(<) は左の皿が軽い、case:(>) は右の皿が軽い、case:(=) は釣り合うことを意味しています。
endweighing:は、分岐について全て記述しおわったとのマークです。
使用例
9 枚のメダル中、軽い 1 枚をみつけだしたい。メダルを A B C D E F G H I とする。
１回目に ABC を左に乗せ、 DEF を右に乗せるときには
weighing:(ABC)vs(DEF)
case:(<)
| 左が軽いときの手続きをここに書く
case:(>)
| 右が軽いときの手続きをここに書く
case:(=)
| 釣り合うときの手続きをここに書く
endweighing:
と書くことにします。
それぞれの分岐ごとに、天秤計測を更に入れ子にして書くことができます。
weighing:(ABC)vs(DEF)
case:(<)
| weighing:(A)vs(B)
| case:(<)
| | {A が軽い}
| case:(>)
| | {B が軽い}
| case:(=)
| | {C が軽い}
| endweighing:
case:(>)
| [ 今回は省略 ]
case:(=)
| [ 今回は省略 ]
endweighing:
使用例終わり。
注2
| | | *impossible*
| | | because of {X=A=B=C=D=E=F=G=H=I}
とありました。
weighing:(XABC)vs(DEFG)
で釣り合い、
weighing:(XDEFG)vs(ABCHI)
で釣り合い、
weighing:(XHI)vs(ABC)
で釣り合うことはありえません。
このときには
{X=A=B=C=D=E=F=G=H=I}
となりますが、10枚のコインが同じ重さになることは問題の設定上ありえないからです。同じ重さは 9 枚までです。
注3
weighing:(XABC)vs(DEFG)
で釣り合ったもとでの
weighing:(XDEFG)vs(ABCHI)
の意味は
weighing:(XX)vs(HI)
と等価です。
これより、Xの重さが判定できます。
(XDEFG)は、(XXABC)と等しく、これと(ABCHI)とを比べているからです。
また、
weighing:(XABC)vs(DEFG)
で釣り合い、
weighing:(XDEFG)vs(ABCHI)
で釣り合ったもとでの
weighing:(XHI)vs(ABC)
は
weighing:(XXX)vs(ABC)
と同じ意味です。
これより、Xの重さが判定できます。