The False Coin                     戻る

 1945年American Mathematical Monthly 1月号に「8枚の硬貨の中の1枚の贋金」
というタイトルでE.D.Schellによって発表されたパズルは、瞬く間に広く知れ渡り、日本にも
第二次世界大戦後間もないころ、雑誌Reader’s Digest の日本語版(昭和22年5月号)で
紹介された。

 この雑誌は、欧米のいろいろな話題の書を紹介するもので、戦中欧米文化が禁制された反
動からか、爆発的な売れ行きを示したそうだ。昭和40年代半ばのころ、姉の愛読書であった
この雑誌を、よく姉から借り受けて読んだものだ。文庫本サイズで、日本の文化とは違う匂い
を持ち、とても魅力的な本だった。特に私のお気に入りは、パズルと付録であった。

 日本語版では、次のような形で問題が紹介された。

 見かけ上全く同じ硬貨が8枚ある。その中の1枚は他の硬貨より少し目方が重い。
そのものを天秤を用いて見つけよ。


 天秤は左右の重い軽いを判断するための道具として用いられる。

 8枚の硬貨から1枚の贋金を見つけるための天秤の操作は、実は、わずか2回で済む。
次のようにすればよい。ただし、重さが等しい場合は「=」で表し、重い>軽いの場合は「>」
で表すことにする。

 8枚の硬貨K1,K2,K3,K4,K5,K6,K7,K8を3つのグループA,B,Cに分ける。
A:K1,K2,K3   B:K4,K5,K6   C:K7,K8

第1回 第2回 贋金
A=B K7>K8 K7
K7<K8 K8
A>B K1=K2 K3
K1>K2 K1
K1<K2 K2
A<B K4=K5 K6
K4>K5 K4
K4<K5 K5

 但し、贋金の軽重が分かっていない時は、3回の操作が必要である。

 外見上区別のつかない12枚の硬貨がある。そのうちの1枚は贋金で、本物と目方が少し違
う。重いか軽いかは分からない。このとき、贋金1枚を見つけるための天秤の操作は、やはり、
3回で、贋金の軽重も分かる方法が知られている。

 回数は少ないが、硬貨の組み合わせ方が巧妙なので、その手順をまとめておこう。

第1回 第2回 第3回 贋金
1,2,3,4=5,6,7,8 9,10=11,1 12>1 12重
12<1 12軽
9,10>11,1 9=10 11軽
9>10 9重
9<10 10重
1,2,3,4>5,6,7,8 1,2,5=3,6,12 7=8 4重
7>8 8軽
7<8 7軽
1,2,5>3,6,12 1=2 6軽
1>2 1重
1<2 2重
1,2,5<3,6,12 5=12 3重
5<12 5軽
1,2,3,4<5,6,7,8 1,2,5=3,6,12 7=8 4軽
7>8 7重
7<8 8重
1,2,5>3,6,12 5=12 3軽
5>12 5重
1,2,5<3,6,12 1=2 6重
1>2 2軽
1<2 1軽

 因みに、上記のような問題設定の場合、硬貨の枚数が5〜13の間は、天秤の操作は3回で
済み、14〜40の間は、4回かかることが知られている。皆さん、実験してみてください。


(追記)  最近、『木村俊一 著 算数の奥義教えます(講談社)』を読んでいたら、上記のよ
     うな問題に対しては、3進数が有効であるということが述べられていた。 

 実際に、冒頭の問題:「見かけ上全く同じ硬貨が8枚ある。その中の1枚は他の硬貨より少
し目方が重い。そのものを天秤を用いて見つけよ。」に対して、適用してみよう。

 いま、8枚の硬貨に対して、3進数で、01、02、10、11、12、20、21、22 と名前を
つけて、互いを区別する。

 天秤は左右の重い軽いを判断するための道具として用いられる。

第1回 第2回 贋金
*1=*2 10>20 10
10<20 20
*1>*2 01=11 21
01>11 01
01<11 11
*1<*2 02=12 22
02>12 02
02<12 12

 冒頭の解法と基本的には同じである。しかし、冒頭の解法では、天秤を用いる回数の理由
付けが難しいが、このように3進数を用いると、3進数の各位を決定するための数と考えれば
よいということに気がつく。

 実際に、8枚の場合は、名前が、「**」 の形なので、天秤を用いる回数は、2回である。
81枚の場合は、名前が、「****」 の形なので、天秤を用いる回数は、4回である。


(追記) 平成24年9月3日付け

 当HPの掲示板「出会いの泉」に当HPがいつもお世話になっているHN「GAI」さんが、「天
秤コインパズルの拡張」と題して、平成24年8月31日付けで書き込まれた。

 パズルで12個のコインがあり、この中で一つだけ重さの違うコインがまぎれている。
天秤を3回使うことで、その異なるコインを探す方法は?ただし、そのコインは他より
重いか、軽いかは事前には解らないものとする。


という、パズル好きな人なら一度は見たことがあると思います。そこでふと、では天秤を4回
まで使うことの条件に変えると、何枚までのコインで見分けることが出来るのだろうと疑問が
湧きました。これに対して、挑戦された方は情報を下さい。これって、n回の天秤使用で挑戦
できる最大コイン数を求める式は出来るのでしょうか?


 らすかるさんからのコメントです。(平成24年8月31日付け)

 実際の方法は考えていませんが、

  4回ならば、(34−1)/2 枚まで

  n回ならば、(3−1)/2 枚まで

となりそうな気がします。

 ...と考えた後、検索してみたらありました。(→ 参考:「★ 13枚の金貨★」)


 空舟さんからのコメントです。(平成24年8月31日付け)

 オンライン整数列大辞典(A003462)にもありますね。


(コメント) 「★ 13枚の金貨★」では難しく証明されていますが、3進数の各位を決定するた
      めの数と考えて、贋金の軽重が分かっている時、n回の操作で判明できる硬貨の
      枚数は、3−1 枚まで可能。贋金の軽重が分かっていない時は、もう一手間必
      要なので、n回の操作で判明できる硬貨の枚数は、(3−1)/2 枚までと単純に
      考えてはいけないんですかね?

 上記の公式を用いると、贋金の軽重が分かっていない時に5回の操作で判明できる硬貨
の枚数は121枚までとなるんですね!


(追記) 平成25年1月19日付け

 当HPの掲示板「出会いの泉」に当HP読者のHN「りらひい」さんが、平成25年1月18日
付けで、創作問題を書き込まれた。

 私は天秤パズルが大大大好きです。あまり数学的な話題とは言えないかもしれませんが、
少しお話します。

 この手のパズルには、次の二つの手法があります。

手法A:それまでの測定結果によってその次の回のはかり方を決める方法
手法B:最初にすべての回のはかり方を決め、全結果から答えを出す方法

 手法Bの方が条件がきつくなっています。(手法Bで解くことができる問題なら当然手法Aで
も解けますが、手法Aで解くことができて手法Bで解くことができない問題もあります。)

 パズルの問題文に何も書かれていなければ通常は手法Aで答えればいいでしょう。手法B
で解けるならその方がスマートでかっこいい気がします。

 手法Bで解ける問題として、次のようなものがあります。

問題1 n≧1とする。3n枚[もしくは、3n−1枚]のコインの中に、本物より少し軽い偽物が
     1枚混じっている。天秤をn回使って偽物を見つけよ。

問題2 n≧2とする。(3n−1)/2枚[もしくは(3n−3)/2枚]のコインの中に、本物と少し重さ
     の違う偽物が1枚混じっている。天秤をn回使って偽物を見つけよ。

     [(3n−3)/2枚のときには、偽物が重いか軽いかも判定可能]

 前置きはこれくらいにして、ここからが本題です。これらの問題に刺激されて、わたしも手
法Bで解くパズルを自作しました。

(1) ここに、見た目では区別できない5枚のコインがあります。このうち3枚は本物のコイン
  で同じ重さですが、残りの2枚は本物と違う重さの偽物です。2枚の偽物のうち、1枚は本
  物より少しだけ軽く、もう1枚は本物より少しだけ重いです。また、この偽物コイン2枚の
  重さの合計は本物2枚の重さの合計と同じであることがわかっています。

   このとき、天秤を3回だけ使って軽い偽物と重い偽物を両方特定することは可能でしょ
  うか?

   ただし、コインの乗せ方はあらかじめ3回分すべて決めておかなければならないとしま
  す。(つまり、1回目の結果によって2回目以降の乗せ方を変えることなどはできないとい
  うことです。)

 答えは「可能」となりますが、その乗せ方の一例を示してください。

 (解答例) コインに1,2,3,4,5と名前を付ける。

  例1
1  <=> 2
3  <=> 4
12 <=> 34
  例2
12 <=> 34
13 <=> 24
14 <=> 23

(2) ここに、見た目では区別できない9枚のコインがあります。このうち7枚は本物のコイン
  で同じ重さですが、残りの2枚は本物と違う重さの偽物です。2枚の偽物のうち、1枚は
  本物より少しだけ軽く、もう1枚は本物より少しだけ重いです。また、この偽物コイン2枚
  の重さの合計は本物2枚の重さの合計と同じであることがわかっています。

   このとき、天秤を4回だけ使って軽い偽物と重い偽物を両方特定することは可能でしょ
  うか?

   ただし、コインの乗せ方はあらかじめ4回分すべて決めておかなければならないとしま
  す。(つまり、1回目の結果によって2回目以降の乗せ方を変えることなどはできないとい
  うことです。)

 答えは「可能」となりますが、その乗せ方の一例を示してください。

 (解答例) コインに1,2,3,4,5,6,7,8,9と名前を付ける。

  例1
12  <=> 34
56  <=> 78
135 <=> 246
147 <=> 238
  例2
1234 <=> 5678
1256 <=> 3478
135  <=> 246
367  <=> 458

 (2)が頭で解ける人は天才だと思います。パズルと言いながら、コンピュータに解かせる問
題だと思います。


(コメント) 問題を提供していただいて、りらひいさんに感謝します。


 当HPがいつもお世話になっているHN「GAI」さんがりらひいさんの問題を考察されました。
                                      (平成25年1月19日付け)

 5枚のコインをA,B,C,D,E と表して天秤にのせる組合せを下記のように組む。

  2枚(左の皿へ)-2枚(右の皿へ)-1枚(のせない)

  第1回目:AB−CE−D
  第2回目:AC−BE−D
  第3回目:AE−BCーD

 この時の天秤の動きを記録しておき、下の表から判断する。

  +:他のコインより少し重い。
  −:他のコインより少し軽い。
  ◎:本物のコイン。
      0:天秤が釣り合っている。
    h:左が下がっている。
    m:右が下がっている。
  
( A, B, C, D, E) ←→ 秤の状態(1回目,2回目,3回目)
(+,−,◎,◎,◎) ←→ (0,h,h)
(−,+,◎,◎,◎) ←→ (0,m,m)
(+,◎,−,◎,◎) ←→ (h,0,h)
(−,◎,+,◎,◎) ←→ (m,0,m)
(+,◎,◎,−,◎) ←→ (h,h,h)
(−,◎,◎,+,◎) ←→ (m,m,m)
(+,◎,◎,◎,−) ←→ (h,h,0)
(−,◎,◎,◎,+) ←→ (m,m,0)
(◎,+,−,◎,◎) ←→ (0,m,0)
(◎,−,+,◎,◎) ←→ (0,h,0)
(◎,+,◎,−,◎) ←→ (h,m,m)
(◎,−,◎,+,◎) ←→ (m,h,h)
(◎,+,◎,◎,−) ←→ (h,0,m)
(◎,−,◎,◎,+) ←→ (m,0,h)
(◎,◎,+,−,◎) ←→ (m,h,m)
(◎,◎,−,+,◎) ←→ (h,m,h)
(◎,◎,+,◎,−) ←→ (0,h,m)
(◎,◎,−,◎,+) ←→ (0,m,h)
(◎,◎,◎,+,−) ←→ (h,h,m)
(◎,◎,◎,−,+) ←→ (m,m,h)

 初めは一枚残すコインをいろいろ変えて、残りの4つをあれこれ組合せを変えながら調査
していきました。(誰しもそう試みることで始めると思う。)

 このダブりの数が組合せ方で微妙に変化していったので、いつかは達成出来るものだと
思いこんで作業していました。しかし何度試みても必ず天秤の状態がダブルことが起きてし
まい上手く行きませんでした。<3時間位この方針で調査していた。>

 次は、最後は3回目の計り方で一個ずつのせてみることで調査してみました。しかし、こ
れも上手くいきませんでした。

 途方に暮れながら、残すコインが重複してしまうがまだ試みてなかったので、2、3回目の
天秤にしかたなく残すコインをダブらせて調べていきました。すると予想に反し何とダブりの
数が減り残り2セットまで減ってしまった。これで新たなルートが発見できたこととなり、さら
にいっそ残すコインは皆同じにしてしまうという当初は思ってもない試みをすることになって
いきました。

 ついに全パターンが全て異なる組合せが見つかりました。

 (2)の問題はまだ全く手を付けていませんが、機会があれば(長期に渡り考え続ける体力
と時間が確保できたら・・・)挑戦してみようと思っています。


 りらひいさんからのコメントです。(平成25年1月19日付け)

 さっそく解いてくださりありがとうございます。

 (1)は5枚のうち4枚の(軽重含めた)真偽がわかれば残りの1枚も自動的に確定します。そ
のため1回も天秤にかけないコインが1枚あっても、すべてを特定できる可能性があります。
私の解答例2つはどちらものせないコインが1枚あるものです。

 同様にして・・・、

 (2)は9枚のうち8枚の(軽重含めた)真偽がわかれば残りの1枚も自動的に確定します。そ
のため1回も天秤にかけないコインが1枚あっても、すべてを特定できる可能性があります。
私の解答例2つはどちらものせないコインが1枚あるものです。

 (1)は手探りでも解けなくはありませんが、(2)はコンピュータプログラムを組まないと厳しい
ように私は思います。


 りらひいさんから、投稿した内容に、一部修正したいところが見つかったとの報告がありま
した。(平成25年1月28日付け)

手法A:それまでの測定結果によってその次の回のはかり方を決める方法
手法B:最初にすべての回のはかり方を決め、全結果から答えを出す方法

 手法Bで解ける問題として、次のようなものがあります。

問題1 n≧1とする。3n枚[もしくは、3n−1枚]のコインの中に、本物より少し軽い偽物が
     1枚混じっている。天秤をn回使って偽物を見つけよ。

問題2 n≧2とする。(3n−1)/2枚[もしくは(3n−3)/2枚]のコインの中に、本物と少し重さ
     の違う偽物が1枚混じっている。天秤をn回使って偽物を見つけよ。

     [(3n−3)/2枚のときには、偽物が重いか軽いかも判定可能]


について、訂正というか補足です。特定の枚数でなくても手法Bで解くことができるので、問
題を次のように変えます。

問題1 n≧1、3n-1+1≦k≦3n とする。k枚のコインの中に、本物より少し軽い偽物が1
    枚混じっている。天秤をn回使って偽物を見つけよ。

問題2 n≧2、(3n-2−1)/2+1≦m≦(3n-1−1)/2 とする。3m+1枚[もしくは3m枚]
    のコインの中に、本物と少し重さの違う偽物が1枚混じっている。天秤をn回使って偽
    物を見つけよ。

     [3m枚のときには、偽物が重いか軽いかも判定可能]

 問題2について、

   3m−1枚のときに偽物を見つける方法があるかどうかは未確認。
   3m+1枚のときに偽物の軽重判定こみの方法があるかどうかは未確認。

です。もしこのことに関してわかる方がいましたら教えてください。

 3[{3n-2−1}/2+1]−1={3n-1+1}/2枚のときに偽物を見つけられることはわかるんで
すけどね。コイン11枚で天秤3回使用とか、8枚で3回とかは、手法Bで偽物を見つけることが
可能なのだろうか?

 重いか軽いかわからない偽物が1枚ある場合で、天秤の使用回数が3回、コインの枚数が
5〜12枚のとき、偽物の軽重まで判定して偽物を特定する方法があるかどうかをコンピュー
タで調べました。

 結果は、5〜12枚のすべてで方法が見つかりました。

 天秤の使用回数が4回以上のものは調べていませんのでわかりませんが、ひょっとすると、
全ての枚数で天秤使用回数が適正な偽物特定方法があるかもしれませんし、(3n−1)/2枚
を除くすべての枚数で軽重判定まで含めた偽物特定方法があるのかもしれません。

 ただ、あくまでも、あるかもしれないという推測です。3m枚の場合は軽重判定込の方法を
きちんと提示できるのですが、3m+1枚で軽重判定込の場合と3m−1枚の場合は私はま
だわかりません。また何かわかったら書き込もうと思います。

 ちなみに、(3n−1)/2枚で、n回の場合は偽物特定はできても軽重判定が完全にはできな
いことが証明できます。


(追記) 平成25年6月28日付け

 当HPの掲示板「出会いの泉」に、HN「moonlight」さんから書き込みがあった。

 The False Coin について、

「見かけ上全く同じ硬貨が8枚ある。その中の1枚は他の硬貨より少し目方が重い。
そのものを天秤を用いて見つけよ。」

は、9枚あっても2回で見出せるのではないでしょうか?



(コメント) moonlight さん、書き込みありがとうございます。上記の問題1からも分かるよう
      に、9枚でも天秤2回で見分けることができます。

 いま、9枚の硬貨に対して、3進数で、00、01、02、10、11、12、20、21、22 と
名前をつけて、互いを区別する。天秤は左右の重い軽いを判断するための道具として用い
られる。

第1回 第2回 贋金
*1=*2 10=20 00
10>20 10
10<20 20
*1>*2 01=11 21
01>11 01
01<11 11
*1<*2 02=12 22
02>12 02
02<12 12

(追記) 平成25年9月4日付け

 当HPの掲示板「出会いの泉」に、HN「エスタ」さんから書き込みがあった。

The Faise Coin について、

 他より重みがある金貨が複数ある場合、最小探索回数を求めることは可能でしょうか?

例 n枚の金貨のうち2枚・・・ など

 ご意見をお願いいたします。



(コメント) エスタさんの問題は、上記の、HN「りらひい」さんが平成25年1月18日付けで
      創作された問題をさらにレベルアップしたような雰囲気ですね!重みがある金貨
      の重みについて、何かしらの条件を設定しないと難しいような...予感!


(追記) HN「りらひい」さんからのコメントです。(平成25年10月6日付け)

 久々に来てみれば、呼ばれた気がしたので・・・、少々長くなりますが、ある程度いろいろと
書いておきます。

 天秤の問題では、1回の測定で「右が下がる」「左が下がる」「釣り合う」の3パターンがあり
ます。よって、k回測定をすると、最大で3k通りの識別ができます。つまり、重さの違いの場
合の数が3kを超えてしまったら、k回では識別不能ということになります。

 しかし、場合の数が3k以内ならk回で必ず可能かというと必ずしもそうではなく、実際にk
回で識別する具体的手順を示す必要があります。

 いくつか例を挙げて説明していきます。

<場合の数について>

(例1) 9枚(A,B,...,I)の中に1枚だけ重い偽物があるとき
   --> Aが偽物、Bが偽物、・・・、Iが偽物  9通り

(例2) 12枚(A,B,...,L)の中に1枚だけ偽物があり、偽物が本物より重いか軽いかわからない
   とき
   --> Aが重い偽物、Aが軽い偽物、Bが重い偽物、Bが軽い偽物、
                                  ・・・、Lが重い偽物、Lが軽い偽物
        12*2=24通り

(例3) 9枚(A,B,...,I)の中に1枚の重い偽物と1枚の軽い偽物があり、
    重偽物+軽偽物=本物+本物のとき
  --> 重A軽B、重A軽C、・・・、重I軽H  9*8=72通り

(例4) 7枚(A,B,...,G)の中に2枚だけ重い偽物があり、偽物2枚の重さは等しいとき
  --> AとBが偽物、AとCが偽物、・・・、FとGが偽物  72=21(通り)

(例5) 13枚(A,B,...,M)の中に2枚だけ重い偽物があり、偽物2枚の重さは等しいとき
  --> AとBが偽物、AとCが偽物、・・・、LとMが偽物  132=78(通り)

(例6) 8枚(A,B,...,H)あるが、実は重いタイプ4枚と軽いタイプ4枚が混ざっているとき
 --> 重ABCD軽EFGH、重ABCE軽DFGH、・・・、重EFGH軽ABCD  84=70(通り)

<手順について>・・・以前私が投稿した際に使った手法A、手法Bの語句を用います。

手法A:それまでの測定結果によってその次の回のはかり方を決める方法
手法B:最初にすべての回のはかり方を決め、全結果から答えを出す方法

(例1) 9通り≦32 なので、2回で特定できる可能性があります。そして実際に、手法A・手法
   Bともに2回で特定できる方法が存在します。

(例2) 24通り≦33 なので、3回で特定できる可能性があります。そして実際に、手法A・手
   法Bともに3回で特定できる方法が存在します。
      (ちなみに、13枚の場合は13*2≦33ですが、3回で軽重まで含めて特定することはでき
   ません。ただし、軽重がわからなくてもよければ特定できるとか、13枚のほかに本物が
   1枚余分にあれば特定可能だとか、派生問題がいろいろあります。)

(例3) 72通り≦34なので、4回で特定できる可能性があります。そして実際に、手法A・手法
   Bともに4回で特定できる方法が存在します。(わたしの以前の投稿参照)

(例4) 21通り≦33なので、3回で特定できる可能性があります。そして実際に、手法A・手法
   Bともに3回で特定できる方法が存在します。

(例5) 78通り≦34なので4回で特定できる可能性があります。そして実際に、手法Aの場合
   は4回で特定できる方法が存在します。しかし、この例の場合は、手法Bでは4回で特定
   することは不可能です。(わたし調べ)手法Bで解く場合は5回以上必要となります。
   (最低何回かは調べてません。)

(例6) 70通り≦34なので、4回で特定できる可能性があります。しかし、わたしはまだやり方
   を構築していないので、本当に4回で特定できるかはわかりません。
      (興味があったら調べてみてください。手法Bで4回はおそらく不可能だと思いますが。)

 エスタさんへの回答は、上の例4、5、6などが該当すると思います。n枚のうち2枚が重い偽
物(偽物同士は同じ重さ)の例としては、7枚と13枚の場合を例にしました。他の数ではどうで
しょうか。

 例えば、8枚中2枚とすると、82=28通りであり、3回では不可能で、少なくとも4回の測定が
必要となります。4回だと最大81通りまで識別できるので、かなり余裕があり、できる可能性
がとても高いです。
(本当に可能かどうかは手順を示す必要がありますが...。)

 わたしが7枚や13枚という例を挙げたのは、きわどいところをつくために、33や34を超えな
いなるべく大きな場合の数になるものを選んだからです。

 手法Aならば、13枚でも4回でできるので、8〜12枚の場合もおそらく4回でできると考えられ
ます。(本当に4回でいいかはそれぞれの場合で調べる必要があります。)

 さて、ここまでの話を踏まえて、最少探索回数を求めるにはどうすればいいかを書きます。

1.問題文の条件から、どれが偽物かという場合の数を求めます。
2.求めた場合の数が、3t-1より大きく3t以下となるような t を求めます。
  (この時点で、t-1回以下の測定では特定不可能だとわかります。)
3.t 回の測定で偽物特定できる手順を調べます。
4-1.手順があれば最少回数は、t 回です。おめでとう。
4-2.手順がなければ、t 回で識別不可能であることを証明します。そして、t+1 回の手順が
   あるか調べます。以下、繰り返し

 私は、今のところこんな感じだと思っています。しかし、一般的な枚数で手順を提示するこ
とができれば、一つずつ調べる必要はなくなります。もし一般の場合の手順を示すことに成
功した場合はぜひとも教えてください。よろしくお願いします。また、以上の説明でおかしなと
ころがあれば、指摘やフォローをしてください。


(コメント) いろいろな例示をしていただき、りらひいさんに感謝します。


(追記) The False Coin の未証明に関して、HN「悪食logical」さんより投稿頂きました。
                                       (平成27年2月8日付け)

 (3n+1)/2枚が出来ない事が数学的には未だ未証明だったと思うのですが、次の補題
を扱う事によって証明可能になるのではということを思いつきました。

 ここに一つの電子天秤がある。真ん中にボタンと液晶があり、ボタンを押すと天秤が動く
代わりに、液晶に、 左が重ければ「>」 、右が重ければ「<」 、釣り合えば「=」 が表示
されるというパズル用の天秤だ。

 ある時、遊びに来た友人が、私が席を外した間に液晶を改造してしまった。友人曰く、

 「>」「<」「=」の代わりに「パ」「ピ」「プ」を表示する。それぞれ「パ」「ピ」「プ」がどの結果に
対応しているかはわからない。「パ」「ピ」「プ」が、「>」「<」「=」の二種類以上の結果に重複
する事はない。他の場所はいじっていないので動作は正常である。

 友人はニヤニヤ笑いながらこんな問題を出してきた。

 ここに、x 枚のコインがあります。x 枚のコインの中に、一枚だけ重さが異なるコインが入っ
ていますが、他のものに比べて重いか軽いかはわかりません。上記の電子天秤を4回使い、
x 枚の中の重さが異なるコインを確実に探し出せる x の最大値は何枚でしょうか?


 これを、パズル雑誌社に解答と解説、未証明問題へのアプローチもつけて投稿してみたん
ですが、リアクションが無く・・・orz。未証明問題へのアプローチというのはともかく、パズルと
して非常に良い問題だと思いますので、ここで流行ったら嬉しいなと思います。


 DD++さんからのコメントです。(平成27年2月8日付け)

 挑んでみた感じ、なかなか面白いパズルの気配。あることに気づくと、13枚が可能なこと
は明らかですね。さて、14枚は可能かどうか……。


 悪食logical さんからのコメントです。(平成27年2月8日付け)

 素晴らしいです!そこがスタートラインです!自力で完全に解けたら、未証明に繋がる事も
すんなり理解して頂けると思います!


 りらひいさんからのコメントです。(平成27年2月8日付け)

 え・・・、「あること」には全然気づきません。が、14枚の手順は構築しました。(たぶん)


 悪食logical さんからのコメントです。(平成27年2月8日付け)

 手順聞かせて下さいね!ちなみに「あること」は気付かなくても解けますが、大体この位だ
ろうという当たりをつける上で、結構大事な感じです!某SNSで出題した所、答えが13枚か
14枚という事に思い当たらずに、パズルとして解こうと下から虱潰しで挫折した人が結構い
ますので・・・。


 DD++さんからのコメントです。(平成27年2月8日付け)

 14枚、できました。実際にやらされたら頭がこんがらがりそうですが。これ、「n枚は不可能
だけど、(n+1)枚は可能」がありえないとも言い切れないので、15枚が不可能だと示せても
安心できないですよね。その次の16が四乗数なので何か起こってもおかしくないですし。


 悪食logical さんからのコメントです。(平成27年2月8日付け)

 15枚以上が不可能な事はわりかし簡単に示せます。天秤4回の結果の組み合わせが、
4=81通り。天秤の結果の組み合わせが6通りなので(左右への傾きの組み合わせ2通り
があるので、重さが異なるコインが重いか軽いかで再度2で割る必要はないし、重さが異な
るコインが重いか軽いかは最後までわからない)、81/6=27/2 より、15枚以上はどう足掻
いても不可能です!良かったら手順を聞かせてくださいね!


 DD++さんからのコメントです。(平成27年2月8日付け)

 それで本当に証明したことになるでしょうか。この問題の難しさは、「実際の状況」と「測定
の結果」を必ずしも一対一に対応させる必要はない点にあると私は認識しています。

≪14枚のときの手順≫ 14枚に、AからNまで名前をつけます。

 1回目 左ABC 右DEF  2回目 左DEF 右GHI

 これらが異なる結果だった場合は、 3回目 左ABC 右GHI

 最初2回が同じ(パ→パとしてよい)
 1回目と3回目が同じ(パ→ピ→パとしてよい)
 2回目と3回目が同じ(パ→ピ→ピとしてよい)
 全部異なる(パ→ピ→プとしてよい)

のいずれかになります。

(1) パ→パ となった場合 3回目 左ABC 右JKL

 これでパなら、4回目 左A 右M  パならNが偽物、パ以外ならMが偽物

 これでパ以外(ピとする)なら、4回目 左J 右K
  パならLが偽物、ピならKが偽物、プならJが偽物

(2) パ→ピ→パ となった場合 4回目 左A 右B
   パならAが偽物、ピならCが偽物、プならBが偽物

(3) パ→ピ→ピ となった場合 4回目 左G 右H
   パならIが偽物、ピならHが偽物、プならGが偽物

(4) パ→ピ→プ となった場合 4回目 左D 右E
   パならEが偽物、ピならDが偽物、プならFが偽物

 これで行けてると思いますがいかがでしょう。


 りらひいさんからのコメントです。(平成27年2月8日付け)

 4回の結果の組み合わせが81通りもあるので、うまくはかり方を変えていけば15枚以上
でもできる可能性はあるんじゃないか?と思って今あれこれ考えてる途中です。

 悪食logicalさんの説明だけで、15枚以上の場合に不可能であることが本当にいえているの
かちょっとわからないので。

(ちなみに、私の以前の投稿で使った
手法A:それまでの測定結果によってその次の回のはかり方を決める方法
手法B:最初にすべての回のはかり方を決め、全結果から答えを出す方法
の用語を用いますと、
手法Bを採用する場合は最大枚数14枚は確定します。
手法Aの場合にどうなるかがわからないということです。)

 とりあえず私が組んだ14枚の手順を載せておきます。(ちなみに手法Bになっています。)

 14枚を a、…、n とおく。

  acejkmn <=> bdfghil 、acghl   <=> befik 、afhijl  <=> bdegmn 、acfgk   <=> dehjn

 とりあえず適当にひとつ作ったものなので、全然美しくありませんが。

 おっとすみません、対応表がないとわけわからないですよね。

 パ、ピ、プを文字と呼ぶとして、1回目に出た文字をxとする。2回目以降に出たxではない
最初の文字をyとする。残った3種類目の文字をzとする。

xxxx  a 、xxxy  b 、xxyx  c 、xyxx  d 、xyyy  e 、xxyy  f 、xyxy  g 、xyyx  h 、xxyz  i
xyxz  j 、xyzx  k 、xyyz  l 、xyzy  m 、xyzz  n

 たとえば、ピパパプなら、xyyz で、l が偽物となります。


 悪食logical さんからのコメントです。(平成27年2月8日付け)

 お二人とも手順はバッチリです!ちなみに1回目載せる枚数は2枚でも14枚でも可能で、
0枚の時だけ普通の天秤と同じになって13枚までしか出来ない、という事になります!

 15枚以上が不可能な事に関して、

 DD++さんの「実際の状況」と「測定の結果」を必ずしも一対一に対応させる必要はない
について、「実際の状況」と「測定の結果」は必ず一対一に対応しています。観測者が理解
するまで確定してない、という電子レンジの猫的な?
 ちなみに対応していないとすると、それはもう別の問題で、
1通りの結果しか表わさない天秤の場合、2通りの結果しか表わさない天秤の場合
が含まれてしまいますので、結果的に15枚以上は不可能になります。

 りらひぃさんの手法Aと手法Bに関して、

 まあ普通の天秤とコインのパズルもそうなんですが、少なくともこの問題において、AとBの
最大枚数は一致します。

 理由は、最終的に重さが異なるコインが見つかった時に、

・少なくとも1通りの天秤の結果がどれに該当しているか解ってしまう(3分の1)2通り解ると
 残りの一つも解るのでその場合は6分の1になる

 要は得られる情報は81通りで、結果的に天秤の結果の組み合わせが少なくとも一つは判
別してしまい(その分を強制的に割り算させられてしまう)、またそれなら27枚まで可能なんじゃ
ないか、という話ですけど、その場合は最初から2通りの結果しか出さない天秤、あるいは
1通りの結果しか出さない天秤と同値になってしまい、手法Aによる「3通りの結果が出る天
秤」という前提での「それまでの結果」が無意味になってしまう、という普通の天秤だと一度で
も天秤に乗ったコインが、重さが異なるコインであると判明すると強制的に重さが異なるコイ
ンが重いか軽いかわかってしまうのと基本的に同じです。

 コインの情報以外に得れてしまうものがあるので、積が81を上回れない、という事に帰着し
ます。


 DD++さんからのコメントです。(平成27年2月8日付け)

 「 要は得られる情報は81通りで、・・・が無意味になってしまう」という点に論理の欠陥があ
るように思います。おっしゃる主張をまとめると、

・天秤の表示と実態が6つのどれか判別できるなら情報量を考えて 6x≦81
・天秤の表示と実際の対応が完全にはわからないなら 3x≦16

ということと理解しましたが、実際は、「ある経路に入れば天秤の対応する表示が全て判明
するが、ある経路ではそれはわからない」ということが可能になります。
(一対一に対応させる必要はない、ということの意味です)

 りらひいさんがおっしゃっている内容もほぼ同じ意味と思います。

 というか、実際、x=14って既に、6x≦81を満たしてませんよね。


 悪食logical さんからのコメントです。(平成27年2月8日付け)

 上の式のxは問題のxと違う事が理解頂けますでしょうか?天秤の組み合わせが6つのど
れかが判別出来るコインは13枚、天秤の組み合わせが2通りに絞れるコインが1枚
 13×6 + 1×3=81
 また、下の式に関して1通りしか結果が出ない天秤だとコインの判別は不可能になります。
また、2通りしか結果が出ない天秤だと左辺の3が2になります。これに関しては「一対一に対
応させる必要がない」という事への私の勘違いが原因なので置いておいて

 ある経路に入れば天秤の対応する表示が全て判明する(6分の1)、ある経路ではそれは
わからない(3分の1)

 上記で述べた通り、13×6 + 1×3=81 で、ひらりいさんの手法Aについては、一回目の
結果の後、2回目以降の結果を選択する(3分の1を増やす事によって15枚以上から探し
出す)という事だと理解しましたが、それだと1回目から4回目まで全て同じ結果を出し続け
ないといけないので、2通り以上の判別が出来ません。また6分の1、3分の1という割当て
を変更するというのは、前のコメントで述べた
 結果が1通りしか出ない天秤 、結果が2通りしか出ない天秤
について考える(別の問題)という事になってしまいます。


 DD++さんからのコメントです。(平成27年2月8日付け)

 私は、xを問題と同じ意味で用いて誤りを指摘したつもりだったのですが、これが別のxと言
われてしまいわけがわからなくなりました。

 「2通りしか結果が出ない天秤だと左辺の3が2」というのもさっぱり意味がわからないので
私が何か勘違いしていた予感……?


 DD++さんからのコメントです。(平成27年2月9日付け)

 一対一対応の取り方を変えることで、単なる組み合わせの問題に落として簡潔に証明でき
ました。

≪14枚が最大数である証明≫

 何回目と何回目に同じ文字が出るか、の総数を考えます。
1種類しか文字が出ないとき、1通り 、2種類文字が出るとき、2^3-1=7通り
3種類文字が出るとき、4C2=6通り

よって、この電子天秤の判定で区別できる内容は最大14通りであるとわかります。つまり、コ
インの最大枚数は多くとも14枚で、実際に前述の14枚を判別する手順が存在するので、最大
枚数は14枚と示されました。

 この証明を参考に、電子天秤をn(≧3)回使えるときを考えます。

 結果表示の何回目と何回目に同じ文字が出るか、の総数を考えます。
1種類しか文字が出ないとき、1通り 、2種類文字が出るとき、(2^n-2)/2通り
3種類文字が出るとき、{3^n-3(2^n-2)-3}/6通り

よって、電子天秤の判定で区別できる内容は最大 {3n-1+1}/2通りであるとわかります。
つまり偽物判別可能なコインの最大枚数は多くとも {3n-1+1}/2枚です。

 逆に、{3n-1+1}/2枚のコインがあるとき、1回目は左右に3n-3枚ずつ乗せ、2回目は1回
目で右にあったものを左に移して右に新たな3n-3枚を乗せます。

 これらが異なる結果であれば、3回目は左を1回目と同じに、右を2回目と同じにします。

 1回目と同じ表示なら、今左に乗せた3n-3枚に偽物があり、2回目の表示が釣り合いを、1
回目と3回目の表示が左に偽物があることを、出ていない表示が右に偽物があることを示し
ます。よって「候補を3等分して、左、右、載せない、に分ける」ことを繰り返すと残りn-3回で
判別可能です。

 2回目と同じ表示なら、今右に乗せた3n-3枚に偽物があり、1回目の表示が釣り合いを、
2回目と3回目の表示が右に偽物があることを、出ていない表示が左に偽物があることを示
します。よって同様に残りn-3回で判別可能です。

 どちらとも異なる表示なら、2回目に左に乗せた3n-3枚に偽物があり、3回目の表示が釣
り合いを、1回目と2回目の表示がそれぞれ右と左に偽物があることを示します。よって同様
に残りn-3回で判別可能です。

 1回目と2回目が同じ結果であればそれが釣り合いの表示で、残り{3n-2+1}/2枚の中に
偽物があります。よって、このうち3n-3枚を左に乗せ、右には本物と判明している3n-3枚を
乗せ、釣り合いの表示なら残り{3n-3+1}/2枚で同様に繰り返し、釣り合わなければ左に偽
物がある表示が判明するので「候補を3等分して、左、右、載せない、に分ける」ことで、残り
n-2回で判別可能です。

 以上の手順で、{3n-1+1}/2枚のコインから偽物を見つける手順が実際に存在することが
確認できたので、天秤をn(≧3)回使える場合に偽物判別が可能な最大枚数は、
{3n-1+1}/2枚と示されました。

 さて、これが「普通の天秤n回で軽重不明な偽物を {3n-1+1}/2枚から見つけることは不
可能」にどう繋がるのかはまださっぱりですが、どうするんだろう。


 悪食logical さんからのコメントです。(平成27年2月9日付け)

 もう一度私のコメントをよく読んで下さい。xに6かけるのは間違いなので、DD++さんが書い
た 6x≦81 という式が間違ってます。15枚以上が不可能な事を示すのには十分ですが、そ
の場合は問題のxとは別のxになります。

 DD++さんが最初に仰った「実際の状況」と「測定の結果」が一対一に対応していないという
言葉自体が完全に別の問題になってしまい、多分ですけど、その間違ってるイメージを引っ
張っちゃってるのかと。その後の14枚が最大枚数であるという証明に穴が出来てます。

 りらひいさんの「手法Aなら15枚以上が不可能とは言い切れない」というのは、結果的に6通
りもしくは3通りの天秤の結果の組合せを得てしまう、という事を見落とした為に発生する偽の
仮定なんですが、それはりらひいさんも書いて頂いた、得られる文字の順列の対応表(xyzの
やつ、14通りでこれはDD++さんの証明と同義です)を示しても、偽の仮定が崩れません。

 81/6という結果的に6通り或いは3通りの天秤の結果の組合せを得てしまうという式が必
要になります。これが、「=x」でない事は私の前のコメントを読めば分かると思います。

 DD++さんの「一対一」というのは「実際の状況」と「測定の結果」ではなく(これも前に述べま
したが、そういう問題ではないので一対一で不変です)、「実際の状況」と「コインを分けれる
結果の組合せ」だと思いますが、それが一対一ではないのは当たり前で、最終的に判明す
る天秤の結果の組合せから6対1、或いは3対1であるということは既に述べました。


 りらひいさんからのコメントです。(平成27年2月9日付け)

 悪食logicalさんのおっしゃっていることがようやくわかりました。理解力が乏しくてすみませ
ん。自分なりに言っていることをまとめてみました。

 n枚のコインがあるとする。このとき、「実際の状態」のすべての場合の数は、

   重さの異なるコインの特定(n)×軽重の判別(2)×電子天秤の液晶表示方法(6)

で、12n通りとなる。また、「測定の結果」は3種類の文字(パ、ピ、プ)を4つ並べた重複順列
で、34=81通りである。

 測定方法を決定すると、すべての「実際の状態」(12n通り)に対して「測定の結果」の文字列
がひとつ決まる。このとき、コインを特定するという条件を満たすためには、コインが異なって
いる状態に同じ文字列が使われていてはならない。逆に言えば、同じコインを示す状態同士
ならば同じ文字列となってもよい。(同じコインを示す状態は軽重と液晶表示で2×6=12つず
つある。)

 このとき、以下の[A][B][補A]が言える。

[A]: (4回とも電子天秤に載せないコイン)または(4回とも電子天秤の同じ側の腕に載せ
   るコイン)の場合、

 測定結果は『パパパパ』、『ピピピピ』、『ププププ』のいずれかになり、12の状態に対してこ
の3つの文字列が4回ずつ対応される。すなわち、このとき、文字列は3つ使用される。

[B]: ([A]以外の乗せ方のコイン)の場合、

 測定結果の文字列は必ず2種類以上の文字を含む。12の状態を軽重の違いで分け6つ
ずつに分けて考えると、液晶表示方法の違いにより対応する文字列は6つとも異なるもの
になる。
(↑ここがちょっと自信ないけど、たぶんそうなんでしょう。どうなんだろ?)
すなわち、このとき、文字列は少なくとも6つ使用される。

[補A]: [A]に該当するコインは多くとも1枚だけでなければならない。

 なぜなら、2枚以上該当すると、コインの特定が不可能になるからである。

 以上のことをまとめる。

 別のコインの状態に同じ文字列は使用できないので、測定結果の文字列は少なくとも
3×1+6×(n-1)は必要である。4回測定の場合は文字列の数が81通りなので、
3×1+6×(n-1)≦81 よって、n≦14

 実際に14枚の測定方法が存在するので、最大値は14枚である。

 私なりの、「実際の状態」と「測定の結果」の解釈で説明してみました。

 測定方法(測定手順)とはすなわち「実際の状態」に「測定の結果」を対応させる写像である
という考え方です。今回のこの写像をf(コイン=x,軽重=w,液晶表示方法=d)とあらわすとすると、
写像fは単射ではありませんが、「f(x1,w1,d1)=f(x2,w2,d2) ⇒ x1=x2」が成り立っている必要が
あるということですね。さらに、f は自由に構成できるわけではなく、電子天秤を使って量った
結果でないといけないので、制限がたくさんかかるために今回のような上限となります。

 悪食logicalさんやDD++さんの解釈と違っていると思いますが、あくまで私はこう考えたとい
うことをお伝えできていればと思います。

 DD++さんへ: 昨日の私のコメントで、手法Bは14枚確定と述べた根拠はまさにこのような
ものです。しかしそのときに手法Aではわからないと言っていたのは、たとえば「パパピピ」と
「ピピププ」が別のコインを指し示すような手順の存在可能性が明確に否定される説明がな
いからです。感覚的にはなさそうな気もしますが、論理的に示されているわけではないので、
私は証明としては不十分な気がします。


 DD++さんからのコメントです。(平成27年2月9日付け)

 悪食logicalさんへ: 私の言う一対一対応についてもう一度丁寧に書いておきます。

 コイン5枚のうち軽重のわからない偽物1枚を探す問題を考えます。ただし、これらの他に
本物とわかっているコイン1枚を使用してよいとします。手順は最初にABとC本物を乗せて、
釣り合えばDと本物を、釣り合わなければAとBを乗せます。実際の状況は、

・Aが重い偽物である、・Aが軽い偽物である、・Bが重い偽物である、・Bが軽い偽物である
・Cが重い偽物である、・Cが軽い偽物である、・Dが重い偽物である、・Dが軽い偽物である
・Eが重い偽物である、・Eが軽い偽物である

の10通りあるのに対し、天秤は9通りしか発生しません。2回とも釣り合うという結果がEが重
い/Eが軽いの2つに対応していて、一対一対応が崩れているにも関わらず、どのコインが偽
物であるかだけなら判別できているという状況が発生するわけです。

 今回の電子天秤の場合、実際の状況が「コインの枚数×6(電子天秤)」だけあり、一方得
られる結果は、34=81通りです。
※コインの軽重は実は意味がないので×2は不要

 最初の貴殿の主張は「この積が81を超えることはない」というものでしたが、上の例に見ら
れるように実態と結果が一対一対応していると限らない場合にはこの2数を比べることに数
学的意味はありません。実際にx=14だと積は84となり81を超えますが偽物判別はできてい
るので、その論理には欠陥があります。
(ここまでが私が、2月8日のコメントまでで指摘した内容を詳細に書き直したものです。)

 それに対して、「6×13+3×1=81だから問題ない」と仰いましたが、もちろんこの式の意味せ
んところはわかりますが、これは最初の論には全くなかった内容です。つまり、これを認める
のならば最初の論が誤りであったとせざるを得ず、ならば15以上がなぜ不可能なのかの根
拠は完全に白紙に戻ります。ここまでご理解いただいた上で質問です。

(1) 最初の「天秤の結果の組み合わせが6通りなので、81/6=27/2 なので、15枚以上はどう
 足掻いても不可能です!
」は誤りないし内容が不十分であったという理解でいいですか?

(2) 6×13+3×1 を認めるのであれば、なぜ他の形で81以内にできないのかの議論が不足し
 ていると思います。一通りしか出なかった場合は×3の方になる、そのようなパターンは多
 くとも1通りである、までは述べられていますが、他に×3になるパターンがないかどうかは
 全く触れられていないと思います。

 ついでに、「左辺の3が2になる」の意味がわからないと言ったのは何についての話なのか
わからないという話は理解しました。パとピしか出ない別の問題の話をしているのですね。
私はピとプを「パ以外の何か」として利用する話として理解していたので、3xで書きました。
本筋ではないのでどうでもいい点でしたね。

 りらひいさんへ: あとから見直して二番煎じだったことに気づきました。n回の場合に一般
           化できた報告だということにしていただければ……。

 「手法Aではわからない〜明確に否定される説明がないからです。」は、確かに説明不足
でした。例えば、Aが偽物の場合に左左平平、Bが偽物の場合に平平右右 というのを利用
できないかということですよね?

 この場合、ピピププの表示を得たとして、
Aが偽物でパ=右、ピ=左、プ=平の可能性 、Bが偽物でパ=左、ピ=平、プ=右の可能性
のどちらも消えてくれません。

 途中で手順を変えるには「n回目はm(<n)回目と同じだったか異なったか」を基準にするしか
なく、そのような手順を取れば上記を利用するという目的を否定することになり、結局ダメで
す。どれが偽物か判別できるという前提の元ではこのような可能性を含む手順は排除されま
す。

 私が最初に気づいた「あること」というのがまさにこれなのです。普段の天秤でもコインの軽
重不明な場合は傾いた方向が右か左かというのは実は全く意味がなく、以前傾いたときと同
じ向きか逆向きかだけが重要です。つまり4回で13枚の場合は最初に何も乗せずに測って水
平だけ識別して、あとは普通の天秤3回で13枚の問題として解けばよかったわけです。

 14枚だともう少し工夫する必要がありますが、前と同じ結果かどうかしか情報価値を持た
ない性質は変わらないのです。


 りらひいさんからのコメントです。(平成27年2月9日付け)

 なるほど、理解しました。というか、私がすごい思い違いをしていました!私は分岐ルート
の違いで識別できないのかと思っていましたが、よく考えれば途中までにあらわれる文字が
同じになるんだから同じ分岐をたどるに決まっていますね。

 DD++さんと悪食logicalさんの『一対一対応』の解釈の違いについて、私は次のように感じま
した。私の写像の考え方で言いますと、DD++さんのいう『一対一対応ではない』というのは、
「写像が単射になるとは限らない」という意味であり、悪食logicalさんのいう『一対一対応して
いる』というのは、「状況を決めると結果が決まるのでこれは写像である」という意味であるよ
うに思われます。

 数学的には一対一対応は基本的に全単射を意味しますけど、パズルの文脈で使うといろ
いろ解釈できますからねぇ。


 DD++さんからのコメントです。(平成27年2月9日付け)

 納得いただけたようでよかったです。全単射になるとは限らない意味で書いたつもりでした
が、よく考えれば全射にならないところまで含めてしまってはまずいですね。「単射になるとは
限らない」と表現すべきでした。ご指摘感謝します。


 りらひいさんからのコメントです。(平成27年2月9日付け)

 私は意識して写像を定義しましたが、普通の(数学ではない)話の中では写像かどうかは
意識しませんし、特に終域と値域を区別したりもしないと思うので、一対一の対応という言葉
を使ってもおかしくはないですよ。

 今回の例だと、終域に相当する集合を測定4回の全結果表示法(81通り)とするのではなく、
その手順で測定してあらわれうる表示全体の集合(値域と同義)と考えれば、ちゃんと一対
一対応になりますしね。というか、ウィキペディアによれば「一対一対応」は全単射だが「一対
一」は単射の意味らしい・・・。言葉って難しいですね。

 先ほどは、「理解しました」なんて言いましたが、よくよく考えてみるとちゃんと理解してはい
ませんでした。まず、そもそも、

 「Aが偽物の場合に左左平平、Bが偽物の場合に平平右右 というのを利用できないかと
いうことですよね?」という問いかけに対して、「いいえ」でした。正しくは、

 例えば、Aが偽物(で、かつ特定の液晶表示法)の場合にパパピピ
      Bが偽物(で、かつ特定の液晶表示法)の場合にピピププ
というのを利用できないかということです。

 また、「途中で手順を変えるには「n回目はm(<n)回目と同じだったか異なったか」を基準に
するしかなく」ということについても、その限りではないように思います。

 n回目は、n−1回目までの表示結果に応じて手順を変えるという手法も考える必要がある
のではないかということです。(要は文字の変化だけを参照するのではなく、出た文字そのも
のを見て次の量り方を決めていく方法です。)

 極端に言ってしまえば、1回目にパが出たかピが出たかプが出たかにより2回目以降の手
順を変えるというような手順であっても、ダメであることが言えるのかというのがそもそも感じ
ていた疑問でした。


 悪食logical さんからのコメントです。(平成27年2月9日付け)

 お二人のお話を見てたら、DD++さんとの話の食い違いの内容がはっきりわかりました!
81/6が15枚以上が不可能であるという事を示してるという所にも関わっているので、枝葉の
どうでもいい部分は置いといて、大事な所だけ言いますね!

・「測定の結果」という言葉の解釈は「問題のパピプ」or「ひらりいさんのxyz」のどちらかで無
 意味な論争がおきてしまうので放置
・「実際の状況」という言葉の解釈について!が重要です。解釈の違いではなく、そこの理解
 がないと、本題に進めないので、ひらりいさんは一部自分と同じ意味で言葉を使われてま
 すが途中で交じってしまってます。また、DD++さんはひらりいさんの交じってしまった方の
 意味合いでしか読んでない為に、根本的に数字の見方がずれてしまってます(話が噛み
 合わないのはこのせいかと)。

 ひらりいさんの、自分と同じ意味の言葉を引用しますね!
★「実際の状態」の全ての場合の数は○○通りである
DD++さんのお使いになってる言葉を引用しますね!
★「実際の状態」は○○通りである

 「実際の状態」の全ての場合の数は○○通りであるというのは「実際の状態」は○○通り
の内の1通りである、と同義で、天秤を使わなくてもその状態は不変であり、天秤を4回使い
81通りの結果を得る事が出来る。81通りの結果を得られるが、得られる情報の積が81を超
える事が出来ないので、81/6で13.5

 15枚以上は不可能である(これは15枚以上が不可能である事を示す式であり、最大枚数
が○○枚である事を示す式ではありません)。

 対して、「実際の状態」は○○通りである、というのは「実際の状態」が○○通りあるので、
コインの枚数×6通り、14枚の場合は84通りですね!仰る通り、この84と81を比較する意
味はありません!自分の言っているのは得られる情報の積の話で、DD++さんの仰ってるの
は「実際の状態」の場合の数についていってるので話が噛み合わなくて当然です。

 なんでコインの枚数に6掛けるんだろうって思ってたら、実際の状態の場合の数について
言ってたんですね!ええと、結論から言うと、15枚以上が不可能である事を示すのに、DD++
さんの言ってる通り「実際の状況」の場合の数を計算する意味がありません。

 りらひいさんの今日のコメントで、「最大枚数が14枚である」事を示しています(内容につい
ては本質的な意味で全面的に同意します。12nを出す必要があったかどうかはお聞きしてみ
たい所です)。式を扱われているので、ご理解頂けたと思いますが、13×6 +1×3=81 は最
大枚数が14枚である事を示す式です

 私の最初の方のコメントで、「 天秤の結果の組み合わせが6通りなので、> 81/6=27/2
なので、15枚以上はどう足掻いても不可能です!


 まず、「最大枚数は14枚である」と「15枚以上は不可能である」という事がそもそも全く違
いますので・・・そこに加えて「実際の状況」と「実際の状況の場合の数」の認識の相違から
生まれたDD++さんの6x≦81という式に対するレスポンス(この時点で私はDD++さんがコイン
の枚数に得られる情報の積算として6を掛けていると思っている)として最大枚数は14枚で
ある事を示す式を提示しているので、話は全く噛み合いません。

 そもそもの得られる情報の積が81を上回れない事の式として、81/6=13.5だから15枚以上
が不可能である、というのは正しいです。十分かどうかは「なぜ他の形で81以内にできない
のか〜他に×3になるパターンがないかどうかは全く触れられていないと思います。
」の点は
一見考慮する必要があるように思えますので、

 連立式として出すと、 6a+3b≦81 、a+b=x 、b=1

で、b≠1の時、天秤の結果の組み合わせから、b=2の時はどの道無意味なので省きます。
b=3の場合、パパパパ、ピピピピ、ププププの3通りの結果で3通りの判別を出来るとすると
最初の一回目の判別の時、パ、ピ、プで3通りの判別が出来ている事になり一回目で3通り
の判別が出来ているなら81通りの判別が出来る事になってしまい・・・と考えるだけ悲しい気
持ちになるような背理法遊びになっちゃいます。

 最終的に理解して頂きたいのは
・「実際の状況」の場合の数をそのまま「実際の状況」として扱うとおかしな事になる
(場合の数はあくまで場合の数です。認識のズレが根本的に生じてしまいます)
・情報の積算としての式の正しさ
(上の項を理解頂けたら、自然と解ると思います。)

 十分か不十分かで言うと不十分だと思いますので、そこは謝ります。ごめんなさい!言い
訳はちゃんとあって、お二人が14枚の手順を提示する前でしたので、あんまり詳しく書きた
くなかったのです)

・無意味な否定ではなく、≪14枚が最大数である証明≫が証明になっていないという事。本
題である未証明へのアプローチを扱う前に、そこの認識の違いは訂正しないと本題に入れ
ません。

と、以上の3点になります。


 DD++さんからのコメントです。(平成27年2月9日付け)

 りらひいさんのコメントについて、「左左平平」と「平平右右」を表示の「パパピピ」「ピピププ」
で区別できないか、というのはどちら側から見ているかの違いだけの気がしますが、私もそち
ら側から見てご説明しましょう。

 表示パターンαでAが偽物の場合に、既定手順で「パパピピ」と表示されるとします。
 表示パターンαでBが偽物の場合に同一手順で「ピピププ」と表示されるとします。

 ここで、既定手順というのはそこまでの判定により分岐の仕方が決められていることも含み
ます。

 この時、偽物がAでもある表示パターンβでは同じ既定手順でピピププと表示されることに
なります。このとき、
・表示パターンαで偽物はB 、・表示パターンβで偽物はA
を区別するには、これらがどこかで異なる分岐へ入るようにするしかありませんが、そのため
には少なくともどちらかの結果が「ピピププ」から外れるような手順に変える必要があり、前提
が崩壊します。

 より厳密にやると、別のコインが偽物でn回目までの表示が対応の置換の自由度を除いて
一致する組が存在する場合に、n+1回目はそれらが対応の自由度を除いても異なる結果に
なるようにすると前提に反し、そうでない場合はどちらのパターンなのかこの回では判別が付
かず、云々と数学的帰納法にする必要がありますが。

悪食logicalさんのコメントについて、「お二人が14枚の手順を提示する前でしたので、あんま
り詳しく書きたくなかった」という気持ちは大変理解できます。ネタバレは面白くないですしね。

 しかし、次に進むために考え方を共有しようという場合にはただの障害にしかなりません。
手順も答えが出た今、詳しく書かない理由はなくなったと思うので、これまでに一度述べた内
容も含めて最初から順番に詳細に証明を書いていただけませんか。その方がきっとお互い
のためだと思いますので。

 私が理解できていない点を列挙しておきます。できれば、このあたり詳細に願います(証明
に含めていただければ、個々に答えていただく必要はありません)。

・そもそも「情報の積」とは何なのか。
「どのコインが偽物かという情報」と「天秤の仕様情報」の直積のことと理解していましたが、
どうも違うようなので。

・15はどこから出てきたのか。
27/2=13.5から「13以下は……」か「14以上は……」という帰結になるなら理解できますが、
「15以上は……」となると14と15は何を根拠に別扱いになったのかが不明です。

・×3は本当に1組限定?
りらひいさんも「どうなんだろ?」とおっしゃってる点ですが、私もここは「どうなんだろ?」です。
繰り返しになりますが、「パパパパとピピピピとププププは1組」は理解していて、疑問なのは
その3種1組以外に×3になるパターンは本当にないのか、という点ですので誤解なきよう願
います。もちろん私もおそらくないだろうと思っていますが、「全員がそうだと思っている」「確
かにそうである」は意味が全く違いますので。

 あと、私の証明は悪食logicalさんの用意されていた証明とは別手順なんでしょうけど、別証
にはなっていると思っています。証明になっていないというのであれば、どの点に誤りないし
不足があるのか具体的に指摘願います。


 悪食logical さんからのコメントです。(平成27年2月10日付け)

 証明は明日のお昼までに乗せますね♪式だけだと理解しがたいと思うので日本語による説
明を漏らさずつけるように頑張ります!ネタバレに関するお気持ち、とても嬉しいです(*´ω`*)
さくっと答えられる所だけ答えておきますね!

 「 情報の積とは何なのか。」について、「そのコインが偽物だと判明した時に判明する天秤
の仕様情報」です。一枚毎にかかります。「どのコインが偽物かという情報」と「天秤の仕様
情報」の直積は、「実際の状況」の場合の数です。

 「15はどこから出てきたのか。」について、6と3があることはご理解頂けてると思いますの
で、14枚が最大である事を示さずに15枚以上が不可能である事を示すのには、仮に全ての
コインで天秤の結果の組合せを一通りに特定出来ると仮定すると最大で13.5枚まで可能に
なる、で下の質問に対する答えに続きます。

 「×3は本当に1組限定?」について、天秤の結果の組合せは6通りである。二種類以上の
文字が出て重さが異なるコインが判明した時に重さが異なるコインが「右に乗っている」「左
に乗っている」「天秤に乗っていない」という3種類の結果の内、少なくとも2種類の対応する
文字の組合せが判明する。天秤の結果の組合せに重複が無い事は問題に明記されている
ので、2種類の対応する文字の組合せが判明したら残りの一つも判明する。故に同一の結
果が4回で続ける3通り(パパパパ、ピピピピ、ププププ)以外の78通で重さが異なるコインが
判明すると、必ず天秤の結果の組合せが1通りに絞れる。

 よって、(パパパパ、ピピピピ、ププププが一通りの判別しかできない事はご理解頂いてる
と思いますので)、全てのコインで天秤の結果の組合せが一通りに絞れると仮定した81/6=
13.5の内多くとも一枚(一通りの判別)は天秤の結果を2通りに絞れるだけなので、15枚以上
は不可能になる。

 「私の証明とは別手順なんでしょうけど、別証にはなっていると思っています。証明になって
いないというのであればどの点に誤りないし不足があるのか具体的に指摘願います。
」につ
いて、これは2月9日付けで既に指摘しましたのでコピペしておきます。

 その後の14枚が最大枚数であるという証明に穴が出来てます。りらひいさんの「手法Aなら
15枚以上が不可能とは言い切れない」というのは結果的に6通りもしくは3通りの天秤の結果
の組合せを得てしまう、という事を見落とした為に発生する偽の仮定なんですが、それはりら
ひいさんも書いて頂いた得られる文字の順列の対応表(xyzのやつ、14通りでこれはDD++さ
んの証明と同義です)を示しても、偽の仮定が崩れません。81/6という結果的に6通り或い
は3通りの天秤の結果の組合せを得てしまうという式が必要になります。


 DD++さんからのコメントです。(平成27年2月10日付け)

 もしかして、情報の"積"って情報の"和(というか合計)"の間違いで、13×6+1×3のあの式
を指してます?各場合ごとの情報量(ある時は6である時は3)を合計して81以下、というので
あれば非常に納得できますし、これまでの勘違いも解ける気がします。
(一部が異なるような数字群を全て加えるのを積とは言わないだろう、という一点を除いて)

 あー、そうか。仮に「パピパパ」と出たとして、ピが出た時にそれが何かその時にはわから
なくとも、偽物が必ず判別できる手順だという前提さえあれば3回目のパか4回目のパの時
に必ず遡ってピの中身が判明するんですね。そこに考えが至りませんでした。そういうことだ
としたら、「81/6を超えられない」ではなく「(81-3)/6+1を超えられない」というのが真におっしゃ
りたかった式でしょうか。だとしたら不可能な枚数に15が出てきたのは納得できます。

 そもそも私の証明(およびりらひいさんの証明)は天秤の表示81通りを
グループ1:パパパパ、ピピピピ、ププププ
グループ2:パパパピ、パパパプ、ピピピパ、ピピピプ、プププパ、プププパ
  ……
グループ14:パピプピ、パプピプ、ピパプパ、ピプパプ、プパピパ、プピパピ

と、コインの判別という観点からは同一視されるべきグループに全81通りを分類することから
始まっています。もちろんこの分類には重複も漏れもありません。つまり、各グループに何個
が属するか(これが実際は6か3なわけですが)を一切計算する必要なく、この14グループを
使い果たすということが全81パターンを使い尽くすこととイコールです。この点ご理解いただい
てますかね?


 悪食logical さんからのコメントです。(平成27年2月10日付け)

 理解はそれであってます!積の和が正しい表現なので、言葉足りずで申し訳ありませんで
した。その部分の理解が得られていれば問題はないので、謝ります!すいませんでした!
ちなみに、掛ける3は多くとも一通りである事は示した通り、6通りの判別が出来てしまうコイ
ンが13.5枚という事を示すのが、15以上が不可能だという事を示すのに十分かどうかは、不
十分という事にして、謝ります。ごめんなさい。また、DD++さんの書かれた証明は勿論理解し
ています。

 この問題についてのりらひいさんの書かれたコメントを全て読み直してください。さらに、こ
れを証明として認められるならそもそも本題の普通の天秤とコインの問題の(3n+1)/2枚が
不可能な事を示す、を未証明問題として扱う意味がなくなっちゃうんですよね。

 コインの判別という観点から同一視されるべきグループに全81通りを分類する

 これがそもそも数学的に有効ならば、普通の天秤とコインの一回目に奇数枚を乗せて得ら
れる結果はコインの判別という観点からは無意味な試行である事という事が示せるので、未
証明問題はとっくの昔に終わっています。

 りらひいさんの書かれたレスを全て読みなおして、それでも納得出来なかったら、何故、普
通の天秤とコインの問題の(3n+1)/2枚が不可能な事を示すのが未証明問題なのかを考え
てみてください。


 DD++さんからのコメントです。(平成27年2月10日付け)

 言っている意味がわかりません。同様の証明は成立して、最大枚数は多くとも(3n+1)/2
枚だという結果は得られます。これは古くからわかっている結果のはずです。要求されている
のはもう一つ厳しい結果なので別の手法が必要になるけれども、それが見つかっていないか
らですよね。

 一応悪食logicalさんの証明の言葉に直しておきます。

 偽物の軽重がわからない普通の天秤の問題は、釣り合いはわかるけれど傾いたときに「パ」
「ピ」という表示になる天秤で解いているのと等価です。全て釣り合ったときに判明するコイン
だけは情報量1ですが、他のコインは情報量2です。このとき、天秤3回(例えば)だと27通りの
表示結果があり、コインの枚数は (27-1)/2+1=14枚を超えることができません。ここまでは、
いろんな人がいろんな方法で証明しています。

 14枚そのものがなぜ未解決かといえば、「情報量合計は計算上足りているにもかかわらず
不可能である」ことの証明となると別のアプローチが必要だからですよね。

 ネット探してたら14年前の記事を見つけました。No.30 に証明があります。定理7の証明方
法を見て思わず膝を打ちました。天秤問題はFLTなどと同じくネットにけっこう「なんちゃって
証明」が転がってる問題ですが、この証明は信頼できそう。


 悪食logical さんからのコメントです。(平成27年2月10日付け)

 自分で見返したら、またもわかりにくいですね。ごめんなさい。実際にやってみましょうか。

≪初項(n=2)で5枚が不可能である証明≫

 5枚の中から重さが異なるコインを探し出す場合、一回目に有効な天秤の使い方が何通り
あるか、の総数を考えます。

  左皿2枚、右皿2枚、1枚乗せない 、左皿1枚、右皿1枚、3枚乗せない

の2通り有ります。

一回目 左皿2枚、右皿2枚、1枚乗せない で釣り合った時、残りの1枚だと特定できます。
釣り合わなかった時、左皿2枚、右皿2枚の計4枚の内どれか1枚ですが、残りの一回で区
別できるのは高々31通りなので特定出来ません。

一回目 左皿1枚、右皿1枚、3枚乗せない で傾いた時、左皿一枚、右皿一枚の計2枚の
どれか1枚です。残りの一回で特定できます。
釣り合った時、一回目に乗っていなかった3枚の内どれか1枚ですが、重さが異なるコイン
が重いか軽いかわかっていないので残りの一回で、天秤に乗っていなかった3枚から特定
する事は出来ません。

 故に、全ての場合において、2回で5枚のコインの中から重さが異なるコイン1枚を確実に
探し出すのは不可能という事が示されました。

 これ、言ってる事は間違っていないんですが、証明としては間違っているっていう典型的な
パターンですよね。

 よって、この電子天秤の判定で区別できる内容は最大14通りであるとわかります。

とか↑に適当に書いたのとかも同様に、観測者が理解出来る全ての場合分けを網羅しても
証明にはならないっていう事です。

 No.30 の証明は典型的ななんちゃって証明の良い例だと思うんですが・・・んー。これ以上
この場所でこの未証明問題について話すのはやめますね!お騒がせしました!


 DD++さんからのコメントです。(平成27年2月10日付け)

 そうですね。情報量が実態の総数を上回るまたは等しいとは限りませんからね。ただし、そ
の原因は「どのコインが偽物か」×「偽物の軽重」×「天秤仕様」→「表示結果」という写像が
単射とは限らないからです。一対一対応の相手である「実態」を「どのコインが偽物かだけ
(軽重や天秤の対応で分けていない)」で考えているので、複数の「実態」が入り混じってもコ
インが偽物かどうかわかるということは絶対になく、「どのコインが偽物か」→「表示結果(の
グループ)」は単射になっています。

 典型的なのは悪食logicalさんもご認識の通り、「考えられるもの全部試してだめだった」で
証明されていますが、この証明はそのやり方にならないように慎重に回避しているので、少
なくともその点については信頼できます。時間をかけてちゃんと読んだら他の重大な誤りが
あるかもしれないのでとりあえず信頼"できそう"にとどめてますが。


 悪食logical さんからのコメントです。(平成27年2月10日付け)

 ちょっと言葉が過ぎたかも...。すいません。ムキになっちゃってたので、多分自分の言っ
てる事は理解不能だったと思います。大変失礼致しました!とりあえず、いつか誰かの役に
立つかもしれないので、今回の補題を使った未証明問題へのアプローチを書いておきます。

 今回の補題で、一回目で天秤にコインを乗せないで計測した時に、普通の天秤とコインの
問題を同じになる事を示す(回数は一回分違う)。

 今回の補題で、一回目で天秤にコインを乗せないで計測した時に3n-1+1/2枚が出来な
くなる事を示す。

 概要は以下の通り。証明ではないので順序は滅茶苦茶です。

 一回目で天秤にコインを乗せないで計測した結果、計測結果の文字が釣り合うを意味する
文字である事、全てのコインが天秤に乗っていない事

 一回目の計測で得られた結果の情報量が、天秤一回の試行で得られる3通りと一致する

 その上で前に述べた、最大枚数を求めた積の和の式とそのコインが重さが異なるコインと
判明した時に得られてしまう天秤の結果の組み合わせの場合の数より、同一の結果がn回
連続ででた時に判別出来るコインは1通り(これは背理法で前に示しました)。

 つまり、そのコインが重さが異なるコインが判明した時に、1枚以外は少なくとも一度は天
秤に乗っていなければならない事が示せる。同様にして1回目・・・n-1回目まで同一の結果
で、n回目で異なる結果が出て重さが異なるコインであると判別出来るコインが最大1枚で
ある事を示す。1回目・・・n-a回目まで同一の結果で、n-a+1回目で異なる結果が出て重さ
が異なるコインであると判別出来るコインの枚数が最大で3a-1枚である事を示す(残りの
a-1回で得られる天秤の結果は3a-1枚であるため)。

 1回目が釣り合う結果で2回目で異なる結果が出て重さが異なると判別出来るコインの数
が最大で3n-2枚である事が示せる。

 手順が他に本当にないかは神様しかわからないので、それを使わないで、2回目に3n-2
(普通の天秤だと一回目に3n-1枚)を天秤に乗せなくてはならない事を示せますよ的な。(そ
こから先は解らないです...。)


 悪食logical さんからのコメントです。(平成27年2月11日付け)

 ちなみに、このアプローチが正しいかどうかとかは自分の脳味噌では全くわかりません。し
かし元の天秤とコインのパズルを数学的に取り扱う際に、本来は14枚まで出来るが、実際は
13枚までしか出来ないという事象を「重さが異ならない事が分かっているコインが一枚あれば」
っていう補題で扱うよりかは、一回目の図り方で同列に扱える今回の補題の方が、より本質
的な理解に近付けるのではないか?という事です。


 DD++さんからのコメントです。(平成27年2月11日付け)

 こちらも、この手の議論になると言葉がキツくなりがちで、すみませんでした。純粋なパズル
としても面白かったですし、天秤問題への見たことのないアプローチは興味深かったです。

 なるほど、私が最初に気づいた「あること(=1回目のカラ計量)」がここまで重要なカギだった
とは。このアプローチでうまくいくかどうか少し考えてみようと思います。


 悪食logical さんからのコメントです。(平成27年2月11日付け)

 ありがとうございます!パズルとして楽しんで頂けたのが本当に嬉しいです。DD++さんの書
かれたパズルの解答としての手順がすっごい美しくてカッコよかったです!アプローチが正し
いかどうかは解らないんですけど、この補題で一回目に仮に右皿だけにコインを乗せて計測
して得られる結果の情報が右が重いという結果がその文字に対応する、という天秤の結果の
3通りと一致する事からコインに対する情報を得られないというのが、観測者が理解出来るか
どうか関係なく示せるようになったのも良い感じかな、と思いました。


 りらひいさんからのコメントです。(平成27年2月11日付け)

 悪食logicalさん、DD++さん、途中からあまり参加ができなくてすみませんでした。

 得られる情報の観点から議論しているという大まかな流れまではわかっていますが、細か
い点まではまだまだ理解の追い付いていないところが多々あります。また、お二人はこう言っ
ているけれども実際はこうではないのかと思う点もあります。いろいろと新たに納得した事柄
もありますし、いくつかわからないことが残っていたりもします。けれども、まだわからない部
分は私の力不足ということで、ちょっとこの問題に関して私はいったんここまでにしようかな
と思います。これ以上何かを言うと、また引っ掻き回してしまいそうなので・・・。
(少なくとももうちょっと頭を整理して、何らかの確たる意見ができるまでは自粛。)

 問題を提示して別の観点を与えてくださった悪食logicalさん、議論を進め私の質問にも丁
寧に答えてくださったDD++さん、ありがとうございました。

 これからは「全情報の解明を要求する問題」のみを私は扱うことにしようかな。(写像の言葉
でいえば、単射であることが必要ってことです。)そうすれば、今回議論しようとした事柄は回
避できますよね?(典型的な場合分け網羅でも問題は生じませんよね?)


 悪食logical さんからのコメントです。(平成27年2月11日付け)

 色々ご迷惑をおかけいたしました!手法Aについての考え方、面白かったです!私も一度
ゆっくり色々考えなおします。最後に、問題としてコインの重さについて再設定が必要になり
ますが、この補題において、一回目0枚で計測した後(一回目0枚で計測した後じゃなくても
いいんですけど余計にややこしくなるのでここではこう言っときます)何回目でもいいんです
けど、天秤の左右に異なる枚数を乗せた時に「情報が得られない」←(数学的に証明不可
能?)のではなく「情報を得てしまう為に判別出来るコインの数が大幅に減る」事を示せたの
でのせておきます。

≪コインの重さに関しての再設定≫

 重さが異ならないコインの重さをsとする。重さが異なるコインの重さをtとする。この時、
  0<t 、0<s 、t≠s 、|s-t|<s
とする。

 重さが異なるコインと重さが異ならないコインの重さの差が重さが異ならないコインの重さ
より小さいという設定で、コインの枚数は整数枚なので、奇数枚を天秤に乗せようとすると左
皿と右皿の枚数が異なり、そして上記の重さに関する設定がある場合、枚数が多い方が重
いという事が解ります。

 補題の電子天秤に置いて奇数枚のコインを乗せると、乗っているコインの枚数が多い皿が
重い(乗っているコインの枚数が少ない皿が軽い)という結果がどの文字に該当しているかが
わかります。

 釣り合う結果がどの文字に該当しているかが1回目の試行で解っているので、天秤の結果
の組み合わせ6通りの内どれか1通りだと解ります。

 更に、一度でも天秤に乗って重さが異なるコインだと判明したコインは他のものに比べて重
いか軽いかわかるので、xの最大枚数は、 x=a+b 、12a+6b≦3^n 、
bは多くとも1枚なので(前に示しました)、x≦(3^n+6)/12

 なんでこんなヘンテコな数字になるかと言うと、奇数枚乗せる回をコインの判別に利用して
いる(人間には出来ないけど)且つ奇数枚乗せる回を3通りの結果が得られるとしている(人
間には出来ないけど、というかここは2通りとして右辺いじった方が良いのかもしれません。そ
の場合は綺麗な式になりますね!おそらくそちらの方がきっと正しいのだと思います。)ので
これより小さくなっても大きくなる事はありません。

 上の括弧の中の奇数枚乗せる回を2通りの結果しか得られないとした場合、
x=a+b 、12a+6b≦2・3^(n-1) 、bは多くとも一枚なので、x≦3^(n-2)+1 /2

 すごくわかりやすい式ですが、奇数枚乗せる回を2通りの結果しか得られないとするのが良
いものかどうなのか。釣り合う結果では確実にないから2通りって云うのが認められるかどう
かはもう自分には解らない。3通りの結果を得られるとしても判別出来るコインの最大枚数が
大幅に減る事は示せるので十分な気がします。

 人間がわかる事だけを使って奇数枚乗せる計測を一度行うと判別出来るコインの枚数が
大幅に減る事は示せました。

 奇数枚乗せる回を2通りの結果しか得られないとすると、一回損するという非常にわかりや
すい結果に。おそらくこれは証明としてちゃんと書けば確実に通るので、未証明の解決に一
歩近づいた気がします。

 意味不明な独り言になっちゃいましたね。重さの再設定を外せば良かった。

 =の時は問題の重りが重い事まで解るので最大枚数が無理になり、それ以外の結果なら
全てのコインが天秤の結果の組合せ6通りの内一通りである事が解るのでb=0になり最大枚
数が無理になるで良かった。


 悪食logical さんからのコメントです。(平成27年2月12日付け)

 皆様ありがとうございましたm(__)m。色々話すことで閃きが促進され、重さの再設定を外し
て、奇数枚を天秤に乗せて3通りの結果が得られる元の問題の場合でも、奇数枚を天秤に
乗せるという計測を行った場合、3通りの結果が得られるが最終的に判別出来るコインの枚
数が減るという事を理解し、示せたので後は証明にするだけです。

 度々の連投をお許し下さい。本当に色々ありがとうございました。また機会があればどこか
でお会いしましょう。


(追記) 「論理パズルの融合問題」と題して、DD++さんからご投稿いただきました。
                                      (平成29年1月29日付け)

 8枚のコインがあります。このうち7枚は本物ですが、1枚だけ偽物が混ざっています。本
物は全て同じ重さですが、偽物だけはわずかに重さが異なります。
(本物より重いか軽いかはわかりません)

 天秤を4回だけ使って、偽物を特定してください。ただし、天秤は目の前に2台あり、片方
は正直天秤、片方は嘘つき天秤で、見た目ではどちらが正直天秤か区別できません。

正直天秤:左右の皿に同じ枚数のコインを乗せると、「左が下がる」「釣り合う」「右が下がる」
      のうち正しい挙動をする。異なる枚数では動作しない。

嘘つき天秤:左右の皿に同じ枚数のコインを乗せると、「左が下がる」「釣り合う」「右が下が
       る」のうち誤った挙動2つのどちらかを無作為にする。異なる枚数では動作しない。

#当初、コインの枚数9枚で用意していた解答にミスがあったため、コインの枚数を8枚に
 変更しました。別手順で、9枚でも可能かもしれませんが。


 カルピスさんからのコメントです。(平成29年1月30日付け)

 8枚のコインにABCDEFGHと印を付ける。釣り合った場合「=」、釣り合わなかった場合
「≠」で表す。

【1回目】 ABCD=EFGH なら 嘘つき天秤、ABCD≠EFGH なら 正直天秤

 以後、正直天秤を使って

【2回目】 AB=CD なら ABCD は本物で、残りのEFGHの中に、偽物がある。

【3回目】 AB=EF なら EF も本物で、残りのGHの中に、偽物がある。

【4回目】 A=G なら Gは本物 だから Hが偽物(A≠H なら Hが偽物)
(ABの相手にGHを選んだとしても判断できる)

・・・・・・・・・・・・・・・・・・・

【2回目に、EFGHを選んだ場合】 EF≠GH なら 残りのABCD は本物。

【3回目】 AB=EF なら EF も本物で、残りのGHの中に、偽物がある。

【4回目】 A=G なら Gは本物 だから Hが偽物(A≠H なら Hが偽物)
(ABの相手にGHを選んだとしても判断できる)

PS 【1回目】で嘘つき天秤において、「私の解釈」が間違っていたら、その後の操作は、全
  て取り消しとします。


 らすかるさんからのコメントです。(平成29年1月30日付け)

 例えば、ABCD<EFGH の場合、嘘つき天秤は、ABCD=EFGH または ABCD>EFGH
のどちらかを答えるわけですから、「どちらの天秤でもABCD≠EFGH」となる可能性がありま
すね。


 カルピスさんからのコメントです。(平成29年1月30日付け)

 そうですね。やはり、「嘘つき天秤」の私の解釈が間違っていたようですね。このように解釈
しないと、私には解けませんでした。ただの「嘘つき天秤」ではなく「大嘘つき天秤」だったので
すね。


 DD++さんからのコメントです。(平成29年1月31日付け)

 既に指摘されていますが、嘘つき天秤でも逆に傾く可能性があるので、これでは不可能で
すね。

 普通の天秤の問題の場合、軽重不明な偽物に対して、n回で (3^n-1)/2 枚の中から特定
することが可能です。つまり、8枚の中からだとコイン特定に2.6回分くらい使えればよいので、
正直天秤の特定に1.4回分くらい使えます。2回目や3回目でどちらが正直天秤なのかはっき
りした時に過去の結果が有用な情報になるように乗せていくのがポイントになります。


 カルピスさんからのコメントです。(平成29年1月31日付け)

 ミスタードーナツで考えました。

【1回目】 天秤の左右にコインを、それぞれ2個づつ乗せる。(結果を記録)

【2回目】 今度は、1回目の左右を逆にして乗せてみる。逆にして、理屈が合ったら「正直天
      秤」・合わなかったら「嘘つき天秤」

 以後、「正直天秤」を使って、

【3回目】 1回目の結果で、釣り合った場合でも、釣り合わなかった場合でも、8個中、4個
は「本物」のコインを特定できる。残りの4個は、片側に「本物」2個を乗せて検討すれば、あ
と1回の測定で判断できる。これが【4回目】となり、その「偽物」が本物より軽いか、重いか
も分かる。

PS それぞれの場合に分けて書くのが大変だったので、簡略化して書きました。


 DD++さんからのコメントです。(平成29年1月31日付け)

 最初に左に重い偽物があったとして、嘘つき天秤が1回目は右が下がり2回目は左が下が
る可能性もありますね。あるいはもっと単純に2回とも釣り合うとか。

 使ったコインが全部本物でも嘘つき天秤が1回目と2回目で逆に傾く可能性はありますし。
毎回嘘をつくのでそれはそれで辻褄があってしまう可能性があるのがこの嘘つき天秤の恐
ろしさ。

 しかし、発想としては近い方向に向かっていると思います。


 カルピスさんからのコメントです。(平成29年1月31日付け)

 あれぇーー、「嘘つき天秤」の解釈も正しくしてミスタードーナツでは、辻褄がバッチリ合った
んだけどなぁ〜。ギブアップしまぁーす。らすかるさんにバトンタッチ!


 DD++さんからのコメントです。(平成29年2月8日付け)

 なかなか正解が出ないので、ヒントとして、天秤4回でコイン4枚の場合の手順の一例を示
します。コインを ABCD、天秤を αβ で表現します。

 最初の2回は以下のようにします。

1回目:天秤 α に AB-CD で乗せる
2回目:天秤 β に AC-BD で乗せる

これらの結果で3回目と4回目の手順を決定します。

(1) どちらかで釣り合った場合

 どちらも全てのコインを乗せているので、正直天秤が釣り合うことは絶対にありません。つ
まり、釣り合った方は嘘つき天秤で、もう片方が正直天秤です。このときは、以下のようにし
ます。

3回目:正直天秤に A-B で乗せる
4回目:正直天秤に A-C で乗せる

 両方傾けば A、3回目だけ傾けば B、4回目だけ傾けば C、どちらも釣り合えば D が偽物
です。

(2) どちらも傾いた場合

 例えば、どちらも左が下がった場合。

 2回とも下がった側に乗っていたコイン A について考えます。

 正直天秤を使ったとき(どちらの天秤だったのかはわかりませんが)に A 側が下がったと
いうことは、A は本物か重い偽物のどちらかです。

 一方、嘘つき天秤を使ったとき(やはりどちらの天秤だったのかはわかりませんが)に A
側が下がったということは、A は重い偽物ではありえません。つまり、A は本物です。

 同様に、2回とも上がった側に乗っていたコイン D も本物です。

3回目:天秤 α に A-D で乗せます。

どちらも本物なので、釣り合えば α が正直天秤、傾けば β が正直天秤とわかります。

4回目:正直天秤に A-B で乗せます。

傾けば B、釣り合えば C が偽物です。

 最初の傾き方がどうであっても全く同様に2枚は本物が確定するので、以後も同様の手順
で偽物を発見できます。

 4枚しかないので、手順にだいぶ余裕がありますね。さて、8枚の場合にはどのようにすれ
ばよいでしょうか。

 前半で有効なテクニックはこのあたりです。

・とりあえず全部乗せてみる
 (釣り合えば嘘つき確定、ただし偶数枚時限定)

・同じコインを両方の天秤に乗せてみる
 (両方で下がれば、あるいは両方で上がれば本物確定)

・同じコインを同じ天秤に2回乗せてみる
 (1回は下がって1回は上がれば本物確定)

・乗せるコインを全交換してみる
 (交換の前か後か少なくとも一方は本物しか乗せていない)

・本物確定したコイン2枚だけを乗せてみる
 (釣り合えば正直確定、傾けば嘘つき確定)

・両方の天秤を一度ずつ使う
 (両方傾けばどちらにも乗せていないコインは本物確定)


 ハンニバル・フォーチュンさんから問題をいただきました。(平成30年10月16日付け)

 あなたは盗賊団の支部のアジトの金庫番だ。

 支部の金庫には、重さがAグラムの金貨とBグラムの贋金貨とが多量に納められている。
ちなみに、安価な混ぜ物の入った贋金貨のほうが微妙に軽い。盗賊団のメンバーは全員
これらのことを知っている。

 ある日、あなたは盗賊団本部にいるボスから「支部の金庫から金貨と贋金貨とを21枚づ
つ取りだし、おのおの別々の袋に入れて持って来い。」との命令を受けた。

 さっそく用意をして、命令通りに本部に持参した。すると、ボスが言う。

 「金貨およびに贋金貨につき、命令通りの枚数があるかどうか、ここにある天秤を4回だけ
使って俺に証明しろ。(天秤には付属の分銅などの錘はない。)証明できなければ、お前に
は制裁を加える。俺たちの団に無能は要らないからな。」

 震え上がったあなただが、さていったいどうすればよいだろうか?

※持参した42枚のコインはくだんの金貨または贋金貨だけであることを、ボスも認識してい
 る。すなわち第3のコインはない。きちんと21枚づつ持参しているかどうかが問われてい
 る。また、ボスは、金貨が全て同じ重さであること、贋金貨もまた全て同じ重さであること、
 贋金貨のほうが金貨よりも軽いことを認識している。ボスは数理には強いので、あなたの
 証明を理解してくれる。

===

#以下のblogの記事に改変を加えて出題しております。15枚づつではなく21枚づつでOK
との改良を加えました。
●Another Cool Coin-Weighing Problem‖(Tanya Khovanova's Math Blog)

 一休さん的な頓知に気がつきました。

 あなたはボスに言う。

 「では、ボスが心から信頼している、本部の金庫番に命じて、本物の金貨を21枚、偽物の
金貨を21枚持ってくるように命じてください。私は天秤を2回だけ使って持参したコインの証
を立てましょう。」

 すると、ボスが言う。

 「本部の金庫番は昨日、お前に与えたのと同じ命令をだし、その証を天秤で示せと命じた
が失敗した。無能な者はテムズ川の魚のエサにならなければならぬ。そして今朝、そうなっ
たのだ。」


 DD++さんからのコメントです。(平成30年10月18日付け)

 やっとわかりました。思い込みが最大の敵でした。

 まず、金貨を7つのグループに分けます。

 両方の袋から6枚ずつ取り出してまとめ、このグループを X[12] とします。

 本物が入った袋の中身残り15枚を3枚4枚8枚で分けて、それぞれ A[3]、A[4]、A[8] としま
す。贋物が入った袋の中身残り15枚も3枚4枚8枚で分けて、それぞれ B[3]、B[4]、B[8] とし
ます。

 これらを、以下のように天秤に載せます。(不等号が開いている側が重い側)

A[3] + X[12]>B[3] + B[4] + A[8]
B[3] + B[4] + A[8]>A[3] + A[4] + B[8]
A[3] + A[4] + B[8]>B[3] + X[12]
A[4] + B[3]>A[3] + B[4]

 最初の3回の結果から、A[3] + X[12] は B[3] + X[12] より3枚以上多く本物が含まれてい
たことがわかり、X[12] は共通なので、A[3] は本物3枚組、B[3] は贋物3枚組であることが
確認されます。

 すると、4回目の結果から、A[4] は本物4枚組、B[4] は贋物4枚組であることが確認され、
さらに、2回目の結果から、A[8] は本物8枚組、B[8] は贋物8枚組であることが確認されます。

 最後に、X[12] ですが、1回目の結果からこの中に6枚以上本物があることがわかり、一方
で、3回目の結果から、この中に6枚以上贋物があることがわかるので、結局 X[12] は本物
6枚贋物6枚であることが確認されます。

 以上により、ここにある金貨42枚は、本物21枚、贋物21枚であることが示されました。

 ボスの要求は「命令通りの枚数があるかどうか」であり、袋に21枚ずつ分かれて入ってい
たかどうかは気にしていないので、これにて Q.E.D.


 らすかるさんからのコメントです。(平成30年10月18日付け)

 金貨と贋金貨とを21枚づつ取りだし、おのおの別々の袋に入れて持って来い

と書いてありますので、21枚ずつ分けて入れていないといけないのでは?


 DD++さんからのコメントです。(平成30年10月18日付け)

 「分けて持ってこい」とは言われていますが、「正しく分けて持ってきたことも天秤を使って
証明しろ」とは言われていません。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月18日付け)

 DD++さん、なるほどっ!!これは大変に失礼をいたしました。まったくの想定外でした。

 題意としては、blogの記事に準拠を狙いました。ただ、天秤の回数とコインの枚数に変更
があるのみです。件のblogのコメント欄が示唆するところでの「天秤4回では15個づつ」の
限界を突破してみませんか?とのお誘いです。翻案の際に、解釈上あいまいな点を増やし
てしまいました。申し訳ありません。

 今回のDD++さんの技法はおもしろく感じました。目から鱗が落ちます。この方向性でなら
ば、あるいは、21個づつよりも多くのコインを処理可能でしょうか?これはこれで大変に興
味深いお話となります。

 皆様、「天秤3回では7個づつ」が限界でしょうか?「天秤4回で27個づつ」は不可能でしょ
うか?21ではなく27です。27でできないかなあと思っていじくっていたら21の解がみつかり
ました。


 DD++さんからのコメントです。(平成30年10月18日付け)

 あ、やっぱり各金貨の真贋まで含めての題意でした?とりあえず、私は金庫番として制裁
を免れたとして、ボスの意図を改めて考えてみます。

 n≧3 のとき、真贋 3*2^(n-1)-4 枚ずつをそれぞれの真贋まで含めて証明する方法はすぐ
にわかったのですが、これに n=4 を代入しても20枚ずつなんですよね。どこかにあと1枚ねじ
込めるんだろうなあ……。

 個別の真贋まで含めての21枚ずつ、できました。最初の2枚の確定のさせ方、こんな手段
もあったんですね。

 まず、金貨を8つのグループに分けます。

 本物21枚を、2枚、3枚、6枚、10枚で分けて、それぞれ A[2]、A[3]、A[6]、A[10] とします。

 贋物21枚を、2枚、3枚、6枚、10枚で分けて、それぞれ B[2]、B[3]、B[6]、B[10] とします。

 これらを、以下のように天秤に載せます。(不等号が開いている側が重い側)

A[2] + A[3] + A[6] + B[10] > B[2] + B[3] + B[6] + A[10]
B[3] + B[6] + A[10] > A[3] + A[6] + B[10]
B[2] + A[3] > A[2] + B[3]
B[2] + B[3] + A[6] > A[2] + A[3] + B[6]

 最初の2回の結果から、A[2] は本物2枚組、B[2] は贋物2枚組であることが確認されます。

すると、3回目の結果から、A[3] は本物3枚組、B[3] は贋物3枚組であることが確認され、
さらに、4回目の結果から、A[6] は本物6枚組、B[6] は贋物6枚組であることが確認され、
最後に、2回目の結果から、A[10] は本物10枚組、B[10] は贋物10枚組であることが確認さ
れます。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月19日付け)

 最初の2枚の確定のさせ方、こんな手段もあったんですね。

 そうなのです。blogの記事のコメント欄では、軽いコイン1枚と重い金貨を1枚とがわかると
ころからスタートし、天秤の回数を増やすごとに、仕分けできる枚数がほぼ指数的に増えて
いく、そんな解の提案がありました。

 天秤の回数をnとすると、( 2^n - 1 )づつの金貨/贋金貨のボスへの証明ができるわけです。

 DD++さんも発見なさったように、スタートを〔軽いコイン2枚と重い金貨を2枚とがわかるとこ
ろから【2仮に】スタートし〕もって仕分け枚数の増加を加速しておいてから、天秤の回数が適
宜増えた時点で、後追いでスタートの本物2枚:偽物2枚の証明を仕込む、そのために天秤
1回分を犠牲にしてもなお、トータルで利益が上回る、そのような解法なのですね。

 なお、天秤3回では、金貨9枚、贋金貨9枚でボスへの証明が可能です。
( blogの記事では7枚:7枚でした。)

 念のため、天秤3回での解も記しておきます。以下、L(1)からL(9)までを贋金貨であるとボ
スに証明したいコインの重さとします。同様に、H(1)からH(9)までを本物の金貨であるとボス
に証明したいコインの重さとします。Hはヘビー、Lはライトから取りました。また、略記号とし
て、L(3:5) = L(3)+L(4)+L(5)などとします。

 ボスに示す不等式(1)から(3)までは以下の通りです。

(1) H[1:2]+L[3:5] < L[1:2]+H[3:5]

(2) H[3:5]+L[6:9] < L[3:5]+H[6:9]

(3) H[1:2]+H[3:5]+L[6:9] > L[1:2]+L[3:5]+H[6:9]

 (2)と(3)を比較して、以下が示されます。

 L(1) < H(1) 、L(2) < H(2)

※これらが種になります。これを増やすわけです。すなわち、重さが証明できる範囲を広げ
 ます。

 (1)により、以下がわかります。

 L(3) < H(3) 、L(4) < H(4) 、L(5) < H(5)

 更に(2)により、以下がわかります。

 L(6) < H(6) 、L(7) < H(7) 、L(8) < H(8) 、L(9) < H(9)

 これでおしまいです。

※(2)は次のように改善すれば証明できる枚数をより増やせそうですが、実はそうもいかな
 いのです。

(2') H[1:5]+L[6:11] < L[1:5]+H[6:11]

 (2)と(3)を比較して、以下を示す。

 L(1) < H(1) 、L(2) < H(2)

 そのために、(2')は採用できませんでした。

 天秤4回の解(DD++さんによるもの)でも、同様な理屈で、ボスへの証明のためのコストが
かかっています。

 天秤4回での解です。天秤3回の解と、是非、比べてみてください。

(1) H[1:2]+L[3:5] < L[1:2]+H[3:5]

(2) H[1:5]+L[6:11] < L[1:5]+H[6:11]

(3) H[3:11]+L[12:21] < L[3:11]+H[12:21]

(4) H[1:2]+H[3:11]+L[12:21] > L[1:2]+L[3:11]+H[12:21]

※(3)で1や2に触れない(A.K.A.22や23にも触れない)というコストがかかっています。


 DD++さんからのコメントです。(平成30年10月19日付け)

 このコストが消せれば27枚27枚でもイケソウな気がするのですが個人的に断念しました。

 その27枚というのは3回だと9枚というところから推測した数なのだろうと思いますが、もし仮
にそのコストが消せるなら、天秤3回の場合も9枚じゃなくなっちゃいますよね。

 ところで、4回で21枚ずつの別解。こちらの方針でも結局、天秤n回で 3*2^(n-1)-3 枚ずつ
というのが限度のようですが。

 まず、金貨を8つのグループに分けます。

 本物21枚を、2枚、4枚、7枚、8枚で分けて、それぞれ A[2]、A[4]、A[7]、A[8] とします。

 贋物21枚を、2枚、4枚、7枚、8枚で分けて、それぞれ B[2]、B[4]、B[7]、B[8] とします。

 これらを、以下のように天秤に載せます。(不等号が開いている側が重い側)

B[7] + A[8] > A[7] + B[8]
A[2] + A[7] + B[8] > B[2] + B[7] + A[8]
B[2] + A[4] + A[7] + B[8] > A[2] + B[4] + B[7] + A[8]
B[2] + B[4] + A[7] > A[2] + A[4] + B[7]

 最初の2回の結果から、A[2] は本物2枚組、B[2] は贋物2枚組であることが確認されます。
さらに最初と3回目の結果から、A[4] は本物4枚組、B[4] は贋物4枚組であることが確認さ
れます。
さらに、4回目の結果から、A[7] は本物7枚組、B[7] は贋物7枚組であることが確認され、
最後に、1回目の結果から、A[8] は本物8枚組、B[8] は贋物8枚組であることが確認されま
す。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月19日付け)

 DD++さん、確かにおっしゃる通りですね、参りました。よくぞ、このような形を発見なさいま
したね、脱帽いたしました。

H[7:13]+L[14:21]<L[7:13]+H[14:21]

L[1:2]+L[7:13]+H[14:21] < H[1:2]+H[7:13]+L[14:21]

H[1:2]+L[3:6]+L[7:13]+H[14:21] < L[1:2]+H[3:6]+H[7:13]+L[14:21]

L[1:2]+L[3:6]+H[7:13] > H[1:2]+H[3:6]+L[7:13]


 DD++さんからのコメントです。(平成30年10月20日付け)

 m, n は非負整数として、天秤 m+n+1 回で、真贋 (2^(m+1)-1)*(2^(n+1)-1) 枚ずつを、1枚
ごとの真贋まで含めて証明可能なようです。

 m と n がなるべく近い整数である方が金貨の枚数は増えるので、

 天秤1回:1*1=1枚ずつ
 天秤2回:1*3=3枚ずつ
 天秤3回:3*3=9枚ずつ
 天秤4回:3*7=21枚ずつ
 天秤5回:7*7=49枚ずつ
 天秤6回:7*15=105枚ずつ
 天秤7回:15*15=225枚ずつ

が可能ということになります。これが上限かはまだわかりません。


 らすかるさんからのコメントです。(平成30年10月20日付け)

 「A274230」に、1,3,9,21,49,105,225,…という数列がありますが、これは「紙をn+1回折って四
隅を切った時に出来る穴の数」だそうです。関連は全くなさそうですが。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月20日付け)

 <天秤5回:7*7=49枚ずつ> ギブアップしました(>∇<)

 よろしければ具体的な姿をご教示くださいませ。


 DD++さんからのコメントです。(平成30年10月20日付け)

 いきなり答えを書いても面白くないので、ヒント。

 49枚を、2枚、4枚、7枚、14枚、22枚にわけます。

 そこから先は、私が4回21枚ずつの解を2種類作ったそれぞれを参考にどうぞ。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月21日付け)

 DD++さん、ヒントを有り難うございます。

 7*7、15*15 の姿に、びびっておりまして難航しております。


 りらひいさんからのコメントです。(平成30年10月22日付け)

 DD++さんの解法を多分理解しました。途中で方針を切り替えるということですね。で、その
タイミングが真ん中のほうが枚数が増える。

 6回105枚のときは、2,4,7,14,28,50 または 2,4,8,15,30,46 に分け、7回225枚のときは、
2,4,8,15,30,60,106 に分ける。

 私は、DD++さんの二つの解ありきでわかりましたが、ゼロから思いついていくなんてさすが
ですね。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月24日付け)

 ヒントに従いまして以下のように考えました。

 贋金であることをボスに証明すべき49枚を、2枚、4枚、7枚、14枚、22枚にグループ化
して、おのおののグループの総重量を順に、a、b、c、d、e とします。

 本物であることをボスに証明すべき49枚を、2枚、4枚、7枚、14枚、22枚にグループ化
して、おのおののグループの総重量を順に、A、B、C、D、E とします。

 ボスには、天秤を5回使って、以下の5本の不等式を示します。

(1) A+B+c<a+b+C
(2) A+B+C+d<a+b+c+D
(3) C+D+e<c+d+E
(4) a+c+d+E<A+C+D+e
(5) A+b+c+d+E<a+B+C+D+e

 (3)と(4)とから、

 aは贋金2枚の重量の和であり、Aは本物2枚の重量の和である

と、ボスは知ります。

 (3)と(5)とから、

 bは贋金4枚の重量の和であり、Bは本物4枚の重量の和である

と、ボスは知ります。

 (1)から、

 cは贋金7枚の重量の和であり、Cは本物7枚の重量の和である

と、ボスは知ります。

 (2)から、

 dは贋金14枚の重量の和であり、Dは本物14枚の重量の和である

と、ボスは知ります。

 (3)から、

 eは贋金22枚の重量の和であり、Eは本物22枚の重量の和である

と、ボスは知ります。

※DD++さんによるアイデアはあらためて強力だと思いました。なお、りらひいさんのおっしゃ
 ることはまだ飲み込めておりませんが、天秤を7回を理解してからになりそうです。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月25日付け)

 私はこのテーマの言い出しっぺですのに早くも息切れです。天秤七回にて225枚づつを示
すことが出来ました。(やっとコツがわかってきました)

 贋金であることをボスに証明すべき225枚を、

  2枚、4枚、8枚、15枚、30枚、60枚、106枚

にグループ化して、おのおののグループの総重量を順に、a、b、c、d、e、f、g とします。

 本物の金であることをボスに証明すべき225枚を、

  2枚、4枚、8枚、15枚、30枚、60枚、106枚

にグループ化して、おのおののグループの総重量を順に、A、B、C、D、E、F、G とします。

 また、見やすさを考慮して、χ=D+E+F+g 、Χ=d+e+f+G と約束しておきます。

 ボスには、天秤を7回使って、以下の7本の不等式を示します。

(1) A+B+C+d<a+b+c+D
(2) A+B+C+D+e<a+b+c+d+E
(3) A+B+C+D+E+f<a+b+c+d+e+F
(4) D+E+F+g<d+e+f+G

 (4)と同じことですが、 (4') χ<Χ

(5) a+Χ<A+χ
(6) A+b+Χ<a+B+χ
(7) A+B+c+Χ<a+b+C+χ

 (4')と(5)とから、aは贋金2枚の重量の和であり、Aは本物2枚の重量の和であると、ボ
スは知ります。

 (4')と(6)とから、bは贋金4枚の重量の和であり、Bは本物4枚の重量の和であると、ボ
スは知ります。

 (4')と(7)とから、cは贋金8枚の重量の和であり、Cは本物8枚の重量の和であると、ボ
スは知ります。

 (1)から、dは贋金15枚の重量の和であり、Dは本物15枚の重量の和であると、ボスは
知ります。

 (2)から、eは贋金30枚の重量の和であり、Eは本物30枚の重量の和であると、ボスは
知ります。

 (3)から、fは贋金60枚の重量の和であり、Fは本物60枚の重量の和であると、ボスは知
ります。

 (4)から、gは贋金106枚の重量の和であり、Gは本物106枚の重量の和であると、ボス
は知ります。

※(4')ないし(4)がスタートとエンドになっているのですね。


 DD++さんからのコメントです。(平成30年10月28日付け)

 せっかく理解してくださったのを無に帰すようで申し訳ないのですが、偶発的に天秤4回真
贋23枚ずつ解を発見しました。

 本物23枚を、4枚、5枚、6枚、8枚で分けて、それぞれ A[4]、A[5]、A[6]、A[8] とします。

 贋物23枚を、4枚、5枚、6枚、8枚で分けて、それぞれ B[4]、B[5]、B[6]、B[8] とします。

 これらを、以下のように天秤に載せます。(不等号が開いている側が重い側)

B[4] + A[5] > A[4] + B[5]
B[5] + A[6] > A[5] + B[6]
A[4] + A[5] + B[8] > B[4] + B[5] + A[8]
A[4] + B[5] + B[6] + A[8] > B[4] + A[5] + A[6] + B[8]

 左の皿には延べ 9+11+17+23 = 60 枚載せています。その内訳は、A[4] と A[5] と B[5] が
2回ずつで残りが1回ずつです。

 右の皿にも延べ 60 枚載せています。その内訳は、B[4] と A[5] と B[5] が2回ずつで残り
が1回ずつです。

 さて、左の皿に載せた延べ60枚には、右の皿に載せた延べ60枚より、本物が4枚以上多く
含まれているはずです。つまり、A[4] は全て本物、B[4] は全て贋物です。

 あとは、1回目、2回目、4回目を順に見れば、全ての真贋が証明されていることがわかりま
す。

 さて、同様の手法で、24枚以上の解はあるでしょうか?また、天秤3回や5回では、同じ方法
で9枚や49枚を超えることができるでしょうか?


 りらひいさんからのコメントです。(平成30年10月28日付け)

 偶然ですがひとつできました。DD++さんの記法に従って書きます。(一部省略)

 本物、贋物各53枚を、5、6、8、12、22ずつに分ける。

B[5]+A[6] > A[5]+B[6]
B[5]+B[6]+A[12] > A[5]+A[6]+B[12]
A[5]+A[8]+B[12] > B[5]+B[8]+A[12]
A[5]+A[6]+A[12]+B[22] > B[5]+B[6]+B[12]+A[22]
A[5]+B[6]+B[8]+B[12]+A[22] > B[5]+A[6]+A[8]+A[12]+B[22]

 5回の結果を左辺同士、右辺同士で足し合わせると、A[5]とB[5]が確定します。あとは、
1回目、2回目、3回目、5回目を順に見れば、すべて確定することがわかります。


 DD++さんからのコメントです。(平成30年10月28日付け)

 4回で23枚ずつ、5回で59枚ずつ、6回で135枚ずつ、7回で317枚ずつ、が可能なことを確
認しました。3回はやっぱり9枚ずつが限界のようです。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月28日付け)

 DD++さんの「4回で23枚ずつ」、ここだけ漸く理解しました。

C[4]=A[4]-B[4] 、C[5]=A[5]-B[5] 、C[6]=A[6]-B[6] 、C[8]=A[8]-B[8]

とおくと、DD++さんによる4本の「不等式」は以下のようになります。

C[5]>C[4]
C[6]>C[5]
C[4]+C[5]>C[8]
C[4]+C[8]>C[5]+C[6]

 本物一枚の重さと偽物一枚の重さの差をεとします。さきの不等式は以下のようにかけま
す。

C[5]≧C[4]+ε
C[6]≧C[5]+ε
C[4]+C[5]≧C[8]+ε
C[4]+C[8]≧C[5]+C[6]+ε

 辺々足すと右辺と左辺とで相殺が起きて、C[4]≧4εを得ます。

A[4]-B[4]≧4εですから、A[4]は全て本物、B[4]は全て贋物、となるわけですね。

C[5]≧C[4]+ε
C[6]≧C[5]+ε

から、A[5]は全て本物、B[5]は全て贋物、A[6]は全て本物、B[6]は全て贋物、となり、

C[4]+C[8]≧C[5]+C[6]+ε

から、A[8]は全て本物、B[8]は全て贋物、を得るわけですか。いやあ、素晴らしいです。


 りらひいさんからのコメントです。(平成30年10月31日付け)

 今までの解の傾向から、条件を絞ってExcelさん(VBA)に探してもらったところ、次の解が見
つかりました。これが4式での最大かどうかはわかりません。

 前回と同じく、DD++さん流の記法で...。本物贋物各27枚を、3、6、8、10ずつに分ける。

A[3]+A[6]+B[8] > B[3]+B[6]+A[8]
A[3]+A[8]+B[10] > B[3]+B[8]+A[10]
B[3]+B[6]+A[10] > A[3]+A[6]+B[10]
B[3]+A[6]+A[8]+B[10] > A[3]+B[6]+B[8]+A[10]

 1つ目と2つ目と3つ目の式の左辺同士・右辺同士を足すと、A[3]とB[3]が確定する。
 1つ目と3つ目と4つ目の式の左辺同士・右辺同士を足して確定分を考慮すると、A[6]とB[6]
が確定する。
 2つ目と3つ目の式の左辺同士・右辺同士を足して確定分を考慮すると、A[8]とB[8]が確定
する。
 1つ目と3つ目の式の左辺同士・右辺同士を足して確定分を考慮すると、A[10]とB[10]が確
定する。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月31日付け)

 天秤4回で27個づつ、excellent です。仮に 3 6 8 10 だとヒントをもらっても、この4つの不
等式に気がつく自信は皆無です。不等式の本数をうまく使っている点が味噌なのでしょうか。
ひとつの不等式が何回も活躍している気がします。

 都度、(真の金貨マイナス偽の金貨の重量)×不等式本数だけ、稼いでいくわけですね。あ
まりよい喩えではありませんが...。いやあ、素晴らしいです。

※天秤4回で27個は、私が当初、根拠無しに目標としていただけに、感慨無量です。


 りらひいさんからのコメントです。(平成30年11月1日付け)

 5本の不等式になると、計算量が跳ね上がって、Excelさんが固まってしまいます。途中で
探索を中止しましたが、それまでの間に得られたものを書き込んでおきます。

 本物、贋物各95枚を、8、14、18、25、30ずつに分ける。

A[14]+B[18]+B[25]+A[30] > B[14]+A[18]+A[25]+B[30]
B[8]+B[14]+A[18]+B[25]+A[30] > A[8]+A[14]+B[18]+A[25]+B[30]
A[8]+A[18]+B[25] > B[8]+B[18]+A[25]
A[8]+B[14]+B[18]+A[25] > B[8]+A[14]+A[18]+B[25]
B[8]+A[14]+A[25]+B[30] > A[8]+B[14]+B[25]+A[30]

 本物1枚と贋物1枚の重さの差をeとする。

 C[k]=A[k]-B[k] とおく。(-k*e≦C[k]≦k*e に留意する。)

 先の5本の不等式はそれぞれ次のようになる。

C[14]+C[30]≧C[18]+C[25]+e       …(1)
C[18]+C[30]≧C[8]+C[14]+C[25]+e  …(2)
C[8]+C[18]≧C[25]+e              …(3)
C[8]+C[25]≧C[14]+C[18]+e        …(4)
C[14]+C[25]≧C[8]+C[30]+e        …(5)

 (1)+(2)より、2*C[30]≧C[8]+2*C[25]+2e  …(6)

 (3)+(4)+(5)より、C[8]+C[25]≧C[30]+3e  …(7)

 (6)+2*(7)より、C[8]≧8e なので、C[8]=8e が確定。

 (2)+(5)より、C[18]≧2*C[8]+2e=18e なので、C[18]=18e が確定。

 (1)+(5)より、2*C[14]≧C[8]+C[18]+2e=28e なので、C[14]=14e が確定。

 (4)より、C[25]≧C[14]+C[18]-C[8]+e=25e なので、C[25]=25e が確定。

 (1)より、C[30]≧C[18]+C[25]-C[14]+e=30e なので、C[30]=30eが確定。


 DD++さんからのコメントです。(平成30年11月1日付け)

 25枚解を見つけて報告に来たら、すでにそれより上が発見されていた……。なるほど4つ
の式だけで式の3つ組を2つ用意することが可能なのですね、これは驚き。

本物と贋物それぞれを同じように4つの組に分けて、同じ枚数の組は同じ不等式で逆の辺に
使用する制限で全探索をした感じですか?

 りらひいさんの記録と同じ、5回95枚の解の紹介。

「2からn(天秤の回数)までの自然数を、隣り合う自然数が隣接しないように一列に並べよ」
という問題の解を利用しているので、n≧5 でしか使えない手法ですが...。

 A-B=C とした記法を採用し、書き直したものだけ記載します。また、本物と贋物との重さの
差を1とします。

C[12] + C[15] ≧ C[26] + 1 ……(1)
C[22] + C[26] ≧ C[12] + C[15] + C[20] + 1 ……(2)
C[15] + C[20] ≧ C[12] + C[22] + 1 ……(3)
C[12] + C[26] ≧ C[15] + C[22] + 1 ……(4)
C[20] + C[22] ≧ C[15] + C[26] + 1 ……(5)

 (1)+(2) から、C[22] ≧ C[20] + 2 ……(6)

 (6)+(3) から、C[15] ≧ C[12] + 3 ……(7)

 (7)+(4) から、C[26] ≧ C[22] + 4 ……(8)

 (8)+(5) から、C[20] ≧ C[15] + 5 ……(9)

 (1)、(8)、(6)、(9) から、

 C[12] + C[15] ≧ C[26] + 1 ≧ C[22] + 5  ≧ C[20] + 7 ≧ C[15] + 12

 よって、 C[12] = 12

 あとは、(7)、(9)、(6)、(8) の順に見れば全て明らかです。


 りらひいさんからのコメントです。(平成30年11月1日付け)

 本物と贋物それぞれを同じように4つの組に分けて、同じ枚数の組は同じ不等式で逆の辺
に使用する制限で全探索をした感じですか?


 確かに、その制限は使用していますが、少し気づいたことを確認する延長で探索プログラ
ムを作ったので、変なアプローチになっています。

 なので、私のプログラムは全探索には程遠く、この制限よりもさらにきつい制限がかかっ
ていると思われます。
(ぎりぎりを狙うラインにおいては結果的に必要性が証明されて必要十分条件に変わる可
能性が……わずかにあるかも?ないかも?)

 ところで、ある解答がある条件を満たしていると、ペアとなる同一枚数の解が計算で導か
れます。
(ただし、導かれた解が結果として同じものになる場合もあります。たとえば、私が書き込ん
だ式4本・金貨各27枚の解のペアは同じ解になります。)

 私は、このペアが作れる条件(の中のさらに限定された条件)をもとにExcelさんに探して
もらいましたので、一つの出力で二つの解が得られます。

 先ほど確認しましたが、式5本・金貨各95枚の解で私が書き込んだもののペア相手は、
DD++さんが紹介してくださったものでした。私はコンピュータに頼りましたが、頭と手で出せ
るのはさすがですね。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年11月2日付け)

 りらひいさん、DD++さんの方法は、予想もできない驚くべき展開ですね。DD++さんによる、
天秤回数5回以上での新基軸は怒濤の展開ですし、りらひいさんによる姿形を絞っての探
索は、「双対」が同時にみつかるものであって、しかも、それがDD++さんにより見つけられた
解に一致する……。豊かな世界があったのですね。ため息をつくばかりです。

※81を遥かに越えての95、これにも驚きました。


 らすかるさんからのコメントです。(平成30年11月2日付け)

 「9、27、95」となると、「A148927」でしょうか。


 DD++さんからのコメントです。(平成30年11月2日付け)

 あ、なるほど。

 4回25枚の解

C[7] > C[6]
C[2] + C[6] > C[7]
C[10] > C[2] + C[7]
C[6] + C[7] > C[2] + C[10]

に対して、ペアの解

C[4] > C[3]
C[8] > C[3] + C[4]
C[3] + C[8] > C[10]
C[3] + C[10] > C[4] + C[8]

がある、という感じなわけですね。

 天秤3回9枚解も天秤4回27枚解も「対称」な解ということは、天秤5回も96枚以上の「対称」
解がありそうですね。


 りらひいさんからのコメントです。(平成30年11月3日付け)

 そうです。そうです。次の事実に基づきます。

 不等式の本数をnとする。n次正方行列P、Qが次の条件(ア)、(イ)、(ウ)を満たしているとき、
解のペアを得る。(行を使うor列を使う。)

(ア) PとQは互いに逆行列
(イ) Qの要素はすべて -1、0、+1 のいずれか
(ウ) Pの要素はすべて非負整数
 (↑(ウ)に関しては、「すべて非負かつ各行の和or各列の和が整数」でもOKかもしれません
  が、未検証です。)

  天秤3回9枚解も天秤4回27枚解も「対称」な解ということは、天秤5回も96枚以上の「対称」
解がありそうですね。


 これに関してはどうでしょうか。私が行った探索では、作れるQのパターンが有限なので、
そこからスタートして、Pの要素の合計が大きくなるものを探しています。探索総数を減らす
ために、

・Qの行や列の入れ替えで等価なものはできるだけ重複させない。
・Qの各行や各列は-1と+1を両方持つ。
・Qの行列式は±1に限る。

といった工夫をして、なんとか5次は数十分で探索しきって、max95を得ました。

 私のプログラムに不備があるかもしれませんし、そもそも探した範囲外に目的のものがあ
るかもしれませんので、わたしからはこれ以上何も言えません。そもそも、この行列のパタ
ーン以外の解がどうなっているかが全然想像つかないんですけどね……。


 DD++さんからのコメントです。(平成30年11月3日付け)

 へえ、その条件で96枚以上の解はないんですか。もうちょっと工夫の余地がありそうな手
応えでしたが……。

 じゃあ、次は6回を考えてみます。これまでの傾向からして、300ちょっとと予想されますね。

 らすかるさんの見つけて来た数列と関連があるのかも気になります。そもそもこれが何の
数列なのか読んでもよく理解できないわけですけども。


 GAI さんからのコメントです。(平成30年11月3日付け)

 らすかるさんを信じて挑戦してみました。

 天秤を6回使用して336枚ずつの真偽コインを確認する。

 本物、偽物コインをそれぞれ 46、51、53、57、63、66(枚)に分ける。

 記法をDD++さんのに習います。

5回分の測り方
C[51] + C[53] ≧ C[46] + C[57] + 1・・・・・・(1)
C[46] + C[63] ≧ C[51] + C[57] + 1・・・・・・(2)
C[53] + C[57] ≧ C[46] + C[63] + 1・・・・・・(3)
C[51] + C[66] ≧ C[53] + C[63] + 1・・・・・・(4)
C[57] + C[63] ≧ C[53] + C[66] + 1・・・・・・(5)

(1)+(2)+(3)+(4)+(5)から、 C[51] ≧ C[46] + 5・・・・・・(A)

(2)+(3)から、C[53] ≧ C[51] + 2

上と組み合わせて、 C[53] ≧ C[46] + 7・・・・・・(B)

(2)+(4)+(5)から、 C[46] + C[63] ≧ 2*C[53] + 3≧ 2*(C[46] + 7) + 3

 これより、 C[63] ≧ C[46] + 17・・・・・(C)

(2)+(3)+(4)から、 C[66] ≧ C[63] + 3≧ C[46] + 17 + 3

 よって、 C[66] ≧ C[46] + 20・・・・・(D)

(3)+(5)から、 2*C[57] ≧ C[46] + C[66] + 2≧ C[46] + C[46] + 20 + 2

 よって、 C[57] ≧ C[46] + 11・・・・・(E)

 そこで、6回目の天秤で、 C[46]>0 即ち、A[46] > B[46] を確認する。


 DD++さんからのコメントです。(平成30年11月3日付け)

 その流れでいくと、最後で必要なのは、 C[46]≧46、つまり、「A[46] の46枚組のなかに、
B[46] の46枚組よりも本物が46枚以上多く含まれている」ことですね。

 C[46]>0 では、「A[46] の46枚組のなかに B[46] の46枚組よりも本物が多く含まれている」
であり、それぞれ全て本物/贋物であることは証明できません。


 GAI さんからのコメントです。(平成30年11月3日付け)

 そうか!何か変だけど、とは感じていたんですが、逆に、C[46]≧46を取り出せるための第
6の式が全然分からなくて・・・


 DD++さんからのコメントです。(平成30年11月3日付け)

 5回のときの方法にさらに小細工で嵩増しして、6回で「300枚ちょっと」の305枚解ができま
した。まだまだ改善の余地はありそうな感触ですが、さて。

 とりあえずの305枚解

C[38] + C[41] + C[50] > C[61] + C[67] ……(1)
C[61] + C[67] > C[38] + C[41] + C[48] ……(2)
C[41] + C[48] > C[38] + C[50] ……(3)
C[38] + C[48] + C[67] > C[41] + C[50] + C[61] ……(4)
C[48] + C[61] > C[41] + C[67] ……(5)
C[38] + C[61] > C[48] + C[50] ……(6)

 全て「左辺≧右辺+1」と書き換えてから、

(1)+(2) より、 C[50] ≧ C[48] + 2 ……(7)
(7)+(3) より、 C[41] ≧ C[38] + 3 ……(8)
(7)+(8)+(4) より、 C[67] ≧ C[61] + 6 ……(9)
(9)+(5) より、 C[48] ≧ C[41] + 7 ……(10)
(8)+(10)+(6) より、 C[61] ≧ C[50] + 11 ……(11)

 (1)、(9)、(11)、(7)、(10) より、

C[38] + C[41] + C[50]≧ C[61] + C[67] + 1≧ 2*C[61] + 7≧ 2*C[50] + 29
             ≧ C[48] + C[50] + 31≧ C[41] + C[50] + 38

なので、 C[38] ≧ 38 つまり、 C[38] = 38

 あとは、(8)、(10)、(7)、(11)、(9) を順に見て明らか。


 GAIさんからのコメントです。(平成30年11月6日付け)

 驚くべき構成を見て、何とか305枚を超える構成をと考え、307枚に挑戦してみたんですが、
DD++さんのヒントとして、307を6つに分けるのも、(38、42、48、50、61、68)に対し、異なる
3つずつの和が1違い (6)、2つでの最大の和と3つでの和の最小値とでの1つ違い (4)、(5)、
などを利用し全部で6個の不等式がただ一つ

C[38] + C(61) > C[48] + C[50] ……(1)
C[42] + C[68] > C[48] + C[61] ……(2)
C[50] + C[61] > C[42] + C[68] ……(3)
C[61] + C[68] > C[38] + C[42] + C[48] ……(4)
C[38] + C[42] + C[50] > C[61] + C[68] ……(5)
C[38] + C[48] + C[68] > C[42] + C[50] + C[61] ……(6)

とはできるんですが、これから、C[38] ≧ 38 つまり C[38] = 38 を導ける方法はどうしても
見つけられない。またいろいろ試していて、なんとなくnの枚数は偶数では無理な気がしまし
た。

 やってみて、如何に305の分解を 38、41、48、50、61、67 とされているのが微妙なもので
あることが実感できました。


(追記) 「とある天秤パズル」と題して、HN「Dengan kesaktian Indukmu」さんより、ご投稿い
    ただきました。(令和3年1月31日付け)

 こんなパズルは如何でしょうか。

 以下、本物のコインの重さが x グラム、偽物のコインの重さが y グラムとします。 x と y と
の関係は、 x≠y だけが与えられています。 x>y であるのかそれとも x<y であるのかにつ
いては未知とします。

《初級編》

 グループAとして3枚のコインがあります。グループBとして3枚のコインがあります。両グル
ープともに本物のコインが2枚含まれ、偽物のコインが1枚含まれます。

 上皿天秤を使って確実に偽コインを全て特定してください。ただし、天秤を使用可能な回数
は4回までとします。


《中級編》

 グループAとして4枚のコインがあります。グループBとして4枚のコインがあります。両グル
ープともに本物のコインが3枚含まれ、偽物のコインが1枚含まれます。

 上皿天秤を使って確実に偽コインを全て特定してください。ただし、天秤を使用可能な回数
は4回までとします。


《上級編》

 グループAとして5枚のコインがあります。グループBとして5枚のコインがあります。両グル
ープともに本物のコインが4枚含まれ、偽物のコインが1枚含まれます。

 上皿天秤を使って確実に偽コインを全て特定してください。ただし、天秤を使用可能な回数
は4回までとします。


 初級編は三秒でできることかと存じます。

 中級編は慣れているひとならば五秒でできることかと存じます。

 上級編については時間がかかるかもしれません。

 お楽しみ頂ければ幸いです。


(コメント) 3秒で出来るという《初級編》に挑戦してみました。

 グループA: a1、a2、a3 、グループB: b1、b2、b3 とする。
(A、Bともに本物2枚、偽物1枚で、天秤の使用回数は4回まで)

(天秤1回目) (a1、a2)と(b1、b2)を比較する。

 (a1、a2)=(b1、b2)のとき、2つとも本物か、偽物が1枚ずつの何れか。

  (天秤2回目) a1とa2を比較する。

    a1=a2 ならば、 a1、a2、b1、b2 は本物で、偽物は、 a3 と b3
                            (本物・偽物の軽重には天秤をあと1回必要)

    a1≠a2 ならば、どちらかが偽物で、a3、b3 は本物となる。

    (天秤3回目) a1とa3を比較する。

      a1=a3 ならば、a1は本物で、a2が偽物(a1≠a2から本物・偽物の軽重が分かる)

      a1≠a3 ならば、a1は偽物で、a2が本物(a1≠a2から本物・偽物の軽重が分かる)

    (天秤4回目) b1とb3を比較する。

      b1=b3 ならば、b1は本物で、b2が偽物
             (本物・偽物の軽重には天秤をあと1回必要?・・・4回をオーバーか?)

      b1≠b3 ならば、b1は偽物で、b2が本物(b1≠b3から本物・偽物の軽重が分かる)

 (a1、a2)≠(b1、b2)のとき、片方は本物のみで、もう片方には偽物が1枚入っている。

  (天秤2回目) a1とa2を比較する。

    a1=a2 ならば、a1、a2、b3は本物で、偽物は、a3
                             (本物・偽物の軽重には天秤をあと1回必要)

    (天秤3回目) b1とb3を比較する。

      b1=b3 ならば、b1は本物で、b2が偽物(本物・偽物の軽重には天秤をあと1回必要)

      b1≠b3 ならば、b1は偽物で、b2が本物(b1≠b3から本物・偽物の軽重が分かる)

    a1≠a2 ならば、b1、b2、a3は本物で、偽物は、b3
                              (本物・偽物の軽重には天秤をあと1回必要)

    (天秤3回目) a1とa3を比較する。

      a1=a3 ならば、a1は本物で、a2が偽物(a1≠a2から本物・偽物の軽重が分かる)

      a1≠a3 ならば、a1は偽物で、a2が本物(a1≠a2から本物・偽物の軽重が分かる)


#3秒で出来るとのことですが、とても3秒では出来ませんでした!


 DD++さんからのコメントです。(令和3年1月31日付け)

 偽物同士はどちらもyグラムで、等しい重さということですよね。それならば、各グループ6枚
(本物5枚、偽物1枚)でも可能そうな気がしますが、いかがでしょう。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年1月31日付け)

 はい、おっしゃる通り、「偽物同士はどちらもyグラムで等しい重さ」です。

 「各グループ6枚(本物5枚、偽物1枚)でも可能そうな気がしますが...」については、力不
足でしょうか、私には肯定も否定も確言できません。

※直感的にはかなり厳しいかもしれないとは存じます。もしも、おっしゃる問題に解があるの
であれば、私にとって《超上級編》です。先程から取り組んでおります。じっくりと考えたいと思
います。コメントを有り難うございました。


 DD++さんからのコメントです。(令和3年1月31日付け)

 認識があっていたようでよかったです。ならば、各グループ6枚ずつは可能ですね。なんなら、
私には各グループ5枚ずつの方が難しかったです。5が素数なのでいろいろやりにくい……。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年1月31日付け)

 有り難うございました。おおいに参考になりました。

 手元でも確認いたしました。偽物コインが本物コインと比べて重さが軽いのか重いのかに
ついて最後まで未定のまま2枚の偽物コインが4回の天秤で特定される場合がありうる、そ
のような解です。

 【度肝を抜かれました】全くの想定外です。

 私には各グループ5枚ずつの方が難しかったです。 5が素数なのでいろいろやりにくい…。

 《上級編》の手元の解では、偽物コインが本物コインに比して軽いか重いのかについて確実
に判定できる解となっております。 こうした軽重の判定には 5 が便利だ…という側面もありま
して、当方にとっては違和感がございませんでした。

例:n を正の整数とします。 5*n 枚のコインがあり、うち 2 枚は偽物、残りの (5*n-2) 枚は本
  物とします。本物の重さを x 、偽物の重さを y とします。

 x ≠ y だけがわかっているときに、天秤を 3 回使えば x > y なのか否かについて判定でき
ます。

 この例についての変種をいろいろとあらぬ方向へと探っているうちに、今回ご提示いたしま
した《上級編》が生まれました。いらぬ舞台裏を申しました。失礼いたしました。


 DD++さんからのコメントです。(令和3年1月31日付け)

 私の手元の「6枚ずつの解」は、偽物の軽重まで判別可能です。厳密には軽重未定のまま
偽物が特定できるパターンが1つありますが、その場合は天秤3回で特定が完了しているの
で、4回目で軽重を決めるだけのために使う余裕がある、という感じです。

 5枚というのにはそういう事情があったのですか。用意されていた5枚組手順もその軽重判
別の解と関係する手順なんですかね?


 DD++さんからのコメントです。(令和3年2月1日付け)

 同じ軽重判定問題、6*n 枚中 2 枚でもできました。この解法で、私が 6 枚だとやりやすい
と思っている理由も伝わるかなと思います。

 n を正の整数とします。 6*n 枚のコインがあり、うち 2 枚は偽物、残りの (6*n-2) 枚は本
物とします。本物の重さを x 、偽物の重さを y とします。

 x ≠ y だけがわかっているときに、天秤を 3 回使えば x > y なのか否かについて判定で
きます。

方法: まず、2*n 枚ずつ 3 つのグループ P、Q、R に分けます。

1 回目に、P vs Q を比較します。

 1 回目が釣り合った場合、P, Q が全て本物であるか、P, Q に1枚ずつ偽物が混ざっている
か、です。

 よって、2 回目で P を n 枚ずつに分けて天秤に載せます。

 2 回目も釣り合った場合は、P, Q が全て本物なので、3 回目で R が P より軽いか重いか
を測れば終わりです。

 2 回目が釣り合わなかった場合は、R が全て本物なので、3回目で P が R より軽いか重い
かを測れば終わりです。

 1回目が釣り合わなかった場合、P, Q のうち片方は本物のみで、もう片方は 1 枚または 2
枚偽物が含まれています。

 よって、2 回目で R を n 枚ずつに分けて天秤に載せます。

 2 回目が釣り合った場合は、R が全て本物なので、3 回目で P が R と同じ重さかどうかを
測れば終わりです。

 2 回目も釣り合わなかった場合は、P または Q に含まれる偽物は 1 枚で R にもう 1 枚の
偽物が含まれているので、やはり 3 回目で P が R と同じ重さかどうかを測れば終わりです。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年2月2日付け)

 私の手元の6枚ずつの解は、偽物の軽重まで判別可能です。

⇒素晴らしいことです!!
(当方はいったん今までの先入観を全部捨てなければここまで到達できないと思いました。
持ち合わせていたのとは全く異なるアルゴリズムを思い付かなければならないことでしょう。)

 5枚というのにはそういう事情があったのですか。用意されていた5枚組手順もその軽重判
別の解と関係する手順なんですかね?


⇒第一版では5枚組手順で、軽重判別のアルゴリズムを適用後に、それまでの測定結果に
 よる副作用を利用して偽物コインをさらにトレースしていく手法を試みていたのですが、そ
 れですと天秤使用回数は4回よりも大になってしまっていました。回数面で結果に不満を感
 じまして作戦変更をいたしまして、第二版では天秤使用回数を4回にまで減らすことに成功
 しましたが…《先に(三回目までに)偽物軽重判定を行う》ことを放棄しなければなりません
 でした。それどころか【軽重判定は最後の天秤で確定する】ので、それまでは一切未定…と
 いう難儀な解を得るにいたりました。
――つまりこじらせてしまったわけです…5というマジックナンバーを早めに捨ててしかるべき
  でしたね、と今となっては思うところです。DD++さんからの御指摘がなければなかなか独
  力では気がつかなかったことでしょう。有難いことです。

  同じ軽重判定問題、6*n 枚中 2 枚でもできました。この解法で、私が 6 枚だとやりやすい
と思っている理由も伝わるかなと思います。


はい、伝わりました。有り難うございました。

 6*n で。私の先入観ですと、3グループにわけて天秤2回を使って、

  (A:2*n)≠(B:2*n)=(C:2*n)

をまず見つけ出してしまっていました。

@ B、Cに1枚ずつ偽物があるか、もしくは、A Aのみに2枚の偽物があるか、のどちらか
であると知ることになります。

 ついで、3回めの天秤では、Bの半分ずつ分けたものどうしを比較することで、@Aのどち
らであったのかを確定できます。
(その際に《副作用で》偽物が本物に比べて重いのか軽いのかも確定できてしまいます。)

 DD++さんによる軽重判定のアルゴリズムは本質的には上記記載のものと同じなのですけ
れども、多少手がこんでいます。このことが、DD++さんがおっしゃるところの

 【私の手元の6枚ずつの解は、偽物の軽重まで判別可能です。】

に結実しているのかと思いまして、昨夜からあれこれ試しております。

 色々と教えて頂きましてまことに有り難うございます。


 そろそろ私が用意していた《上級編》の解を書いておきたいと存じます。

■測定方法

 2つグループがありました。片方のグループのコインに A、B、C、D、Eと名付け、もう片方
のグループのコインに a、b、c、d、eと名付けます。

 天秤の左側の皿に乗せるコインがs、t、u、v、右側の皿に乗せるコインがw、x、y、zとする
ときには、その計測方法を stuv^wxyz と略記します。

 結果、左が重ければ"/"、右が重ければ"\"、釣り合えば"ー"と書くことにします。

 1回目から4回目までの測定方法は以下の通りです。

@ Aab^Ede
A DEa^ABe
B BDc^Cbd
C 3回目までの結果をみて随時に測定方法を定めます。

 早見表です。○は左、●は右に乗せます。

   A:○●−
B:−●○
C:−−●
D:−○○
E:●○−
  a:○○−
b:○−●
c:−−○
d:●−●
e:●●−

 @からBまでの測定結果にもとづき、以下の一覧を参照すれば、「偽物が本物よりも軽い
とき」にはUv、「偽物が本物よりも重いとき」にはWx、の組が偽物コインであると判明します。

   軽:@AB:重   軽:@AB:重     軽:@AB:重
   Da:\\\:Ce
Db:\\−:Bd
Ca:\\/:Be
Ba:\−\:Cd
Aa:\−−:Ee
Cb:\−/:De
Ac:\/\:Ed
Bb:\/−:Dd
Ab:\//:Ec
  Dc:−\\:Ad
Ea:−\−:Ae
Eb:−\/:Bc
Cc:−−−:Cc
Bc:−/\:Eb
Ae:−/−:Ea
Ad:−//:Dc
  Ec:/\\:Ab
Dd:/\−:Bb
Ed:/\/:Ac
De:/−\:Cb
Ee:/−−:Aa
Cd:/−/:Ba
Be://\:Ca
Bd://−:Db
Ce:///:Da

 4回めの天秤で、「偽物が本物よりも重いのか軽いのか」を確定できます。

 具体的には、

軽:@AB:重
Uv:???:Wx

と結果を得たときに、既に本物であると確定しているコインが少なくとも6枚あります。このうち
の1枚を Z としまして、U^Zを測定すれば良いわけです。

 以上、私が事前に用意していた解となります。別解がございましたならば、是非、ご教示を
お願い申し上げます。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年2月2日付け)

 DD++さんから御提示頂いた《超上級編》の問題を再掲しておきます。

超上級編問題

 本物のコインの重さが x グラム、偽物のコインの重さが y グラムとします。 x と y との関
係は、 x≠y だけが与えられています。 x>y であるのかそれとも x<y であるのかについ
ては未知とします。

 グループAとして6枚のコインがあります。グループBとして6枚のコインがあります。両グ
ループともに本物のコインが5枚含まれ、偽物のコインが1枚含まれます。

 上皿天秤を使って確実に偽コインを全て特定してください。ただし、天秤を使用可能な回
数は4回までとします。


■解についてわかっていること

 私が手元に持っている解では、4回の天秤による計測で、2枚の偽物コインを確実に特定
できますが、その際に、得られた偽物が本物に比べて重いのか軽いのかについて、わから
ないケースとわかるケースとの両方が出てしまいます。

 一方、DD++さんがお持ちのアルゴリズムでは、確実に2枚の偽コインを特定すると同時に、
確実に偽物が本物に比べて重いのか軽いのかをも確定できるとのことです。


 今日も暇さえあれば考えておりましたが、DD++さんによるアルゴリズムについて全く思い浮
かんでおりません。私にとっては、なかなかハードプロブレムです。


 DD++さんからのコメントです。(令和3年2月2日付け)

 なるほど、それを拝見して、Dengan さんが 5 枚が限度だと思われていた理由とその考え
で見落としている点がわかりました。

 天秤は各回ごとに 3 通りの結果を返します。つまり、3 回使えるならば 27 通り、4 回使用
できるならば 81 通りの結果があるわけです。

 Dengan さんの方式は 3 回目までに「偽物が重いならコレとコレ、軽いならコレとコレ」を確
定させてしまおうという方針ですよね。

 すると、偽物の番号が 25 種類あるのを天秤 3 回 27 通りの結果に収めなければならず、
なるほどこれはギリギリです。

 しかし、全部で 4 回使えるという観点からすると、この方針は 4 回目は必ずどちらかに傾
くことになるため、4 回目が釣り合うという 27 通りの結果を丸ごと空白にしている点に実は
非常に大きな無駄があるのです。

 仮に偽物の軽重まで完全に判別することを求めるとして、各グループのコインが n 枚ずつ
だとすると、判別すべき結果のパターンは 2*n^2 種類あり、これらは全て異なる天秤の結果
に割り当てられねばなりません。

 つまり、天秤 4 回なら n < √(81/2) = 6.36…… というのが必要条件。

 6 枚ずつというのは実はかなり余裕のある数字なんです。(この見積もりだけして、最初の
「可能そう」コメントを投稿しました)

 また、この考え方は、実際に手順構成をするときにも大きなヒントになってくれます。

 ところで、天秤 5 回で各グループ 11 枚(本物 10 枚、偽物 1 枚)、軽重まで判別を要求っ
て可能なんでしょうか。

 判別すべき結果は 242 種類、天秤の結果は 243 通り。しかも、5 回全て釣り合うという結
果は、偽物の軽重が判別できないので何も割り当てられないことが確定しています。

 もしこれが可能なら、これこそ正真正銘の「超々上級」だと思いますが、さてさて。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年2月3日付け)

 なるほどです。ふう。頑張ってみます。

 天秤 5 回で各グループ 11 枚(本物 10 枚、偽物 1 枚)、軽重まで判別を要求、って可能
なんでしょうか。


 お尋ねいたしたく、宜しくお願いいたします。以下での見積りはどうなりますでしょうか。

 天秤 4 回で各グループ 7 枚(本物 6 枚、偽物 1 枚)、軽重まで判別を要求。

 質問の動機を以下に申し上げます。

動機A:

 偽物の軽重が予め明らかのときには、天秤 3 回で 【1】グループ 7 枚(本物 5 枚、偽物 2
枚)にて偽物を特定可能です。しかも、 3 回の計測については入れ替え可能、別な表現をす
れば、3人の助手に1回分の計測の指示書を与え(指示書の内容は、たとえば、「aとbとを
【明日までに】計れ、結果は明日聞く」の形式で)、それぞれの助手は思い思い、手があいた
ときに計測します。どの助手が先に計測するかについては事前にはわかりません。また、助
手たちは互いに計測結果を他に教えません。明日になると3人の助手はそれぞれ計測結果
を報告してきます。報告結果から確実に偽物2枚を見つけ出す方法があります。

動機B:

 偽物の軽重が予め明らかのときには、天秤 4 回で 【1】グループ 11 枚(本物 9 枚、偽物 2
枚)にて偽物を特定可能です。しかも、 4 回の計測については入れ替え可能、別な表現をす
れば、4人の助手に1回分の計測の指示書を与え(指示書の内容は、たとえば、「aとbとを
【明日までに】計れ、結果は明日聞く」の形式で)、それぞれの助手は思い思い、手があいた
ときに計測します。どの助手が先に計測するかについては事前にはわかりません。また、助
手たちは互いに計測結果を他に教えません。明日になると4人の助手はそれぞれ計測結果
を報告してきます。報告結果から確実に偽物2枚を見つけ出す方法があります。

 この動機Bに登場する

 1グループ 11 枚(本物 9 枚、偽物 2 枚)を天秤4回で……… と、

 DD+さんによる提起であるところの、

 2グループ 11 枚ずつ、(各グループ本物 10 枚、偽物 1 枚)

とを比べて、《11枚》といるパラメーターが非常に気になるのです。

1グループから2グループに全体の枚数を増やすけれども偽物は2枚のまま、偽物の軽重
は未定、天秤使用回数は1回増やすだけ、これは厳しい設定だなあとため息をついており
ます。


 DD++さんからのコメントです。(令和3年2月3日付け)

 天秤 4 回で各グループ 7 枚(本物 6 枚、偽物 1 枚)、軽重まで判別を要求。

 偽物のパターンは 2*7^2 = 98 通りあります。一方で天秤の傾き方は 3^3 = 81 通りです。
よって偽物のパターンから天秤の傾き方への写像が単射にならないため、どうやっても確実
な特定は不可能です。

 動機A:

 偽物の軽重が予め明らかのときには、天秤 3 回で 【1】グループ 7 枚(本物 5 枚、偽物 2
枚)にて偽物を特定可能です。


 偽物のパターンは 7C2 = 21 通り、天秤の傾き方は 3^3 = 27 通り
よって、判別する手順が存在する可能性はあります。
(あくまで必要条件なので、存在する保証にはなりません)

 コインが 8 枚ある場合は、偽物のパターンが 8C2 = 28 通りとなるため、絶対に不可能です。

 動機B:

 偽物の軽重が予め明らかのときには、天秤 4 回で 【1】グループ 11 枚(本物 9 枚、偽物
2 枚)にて偽物を特定可能です。


 偽物のパターンは 11C2 = 55 通り、天秤傾き方は 3^4 = 81 通り
よって、判別する手順が存在する可能性はあります。

 こちらは、コイン 12 枚でも偽物のパターンが 12C2 = 66 通り、
コイン 13 枚でも 13C2 = 78 通りなので、最大 13 枚まで解が存在する可能性がありますね。

 13 はかなりキツそうですが、12 はかなり余裕がありそうな印象です。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年2月3日付け)

 分析の例示をまことに有り難うございました。こちらで考え始めたことに答え合わせができ
まして大変参考になりました。

 なお、以下は皆様のために御参考をと。

■偽物の軽重が予め明らかのとき、天秤 3 回で 【1】グループ 7 枚(本物 5 枚、偽物 2 枚)
にて偽物を特定可能です。

(10年ほど前に某サイトでこの問題を知り、インフル感染下で点滴を打たれながら暇すぎて
パズルに取り組んだベッド上で解答にたどりついたことが懐かしく思い出されます)

 この問題とこれへの解答とが記されているサイトの URLはこちら。このサイトの解答とは
異なる(点滴下で発見した)別解は以下となります。

 A から G までの 7 枚のコインから 2 枚の偽物(ただし、その軽重はあらかじめ判明)を
見つけます。

@ ABC^DEF
A BE^CD
B AE^BF

※ G については天秤に乗せなくてもオーケーです。
※@ABはどの順に天秤にかけても大丈夫です。
※上記手順は実はA から F までの 6 枚のコインから 1 枚もしくは 2 枚の偽物(ただし、その
 軽重はあらかじめ判明)を見つけます。

 偽物が 1 枚あるか 2 枚あるかについては、事前には未知である設定です。


■偽物の軽重が予め明らかのとき、天秤 4 回で 【1】グループ 13 枚(本物 11 枚、偽物 2 枚)
にて偽物を特定可能です。

 この問題とこれへの解答とが記されているサイトの URLはこちら

※私はこの問題の解をマスターしていません。理解不足なので1ヶ月もすると忘れてしまいます。
※1回目の計測で釣り合うときに、2回目に天秤に乗せる枚数が左の皿に 5 枚、右の皿に 5
 枚となっていまして、私には絶対に出てこない発想です。
(情報量を気にする余りです。)……10年前の当時に考えた理屈としては、1回目計測で5枚5
枚で計ると、もうその後の手数がどうにも足らなくなるからでして、(ここから誤解したのですが)
2回目以降の計測でも5枚5枚は悪手・禁手と強く感じていたのでした。

 以上、取り急ぎご報告まで。宜しくお願いいたします。


 DD++さんからのコメントです。(令和3年2月5日付け)

 超上級編問題の「6 枚ずつの解」(それぞれ本物5枚、偽物1枚)を提示しておきます。

1 回目:
 A グループ 6 枚を 2 枚ずつ 3 組に分け、天秤の左右に 1 組ずつ載せます。釣り合えば載
せた組は全て本物、釣り合わなければ載せていない組が全て本物です。

2 回目:
 B グループで同様に載せます。

3 回目:
 偽物の可能性がある全ての組から 1 枚ずつ選択し左の皿に載せます。右の皿には同枚
数の本物を載せます。

 3 回目が釣り合えば、そのときに載せたものは全て本物で、「偽物が重いならコレとコレ、
軽いならコレとコレ」という状態まで絞れます。よって、4 回目でそのうち 1 枚を本物と比べる
ことで全て判別できます。

 3 回目が釣り合わなければ、偽物の軽重が判明し、両グループとも偽物が含まれている
組が特定されます。その 2 つの組の 3 回目に皿に載せた 1 枚同士を 4 回目で比較する
と偽物が特定できます。

例: コインを A1 から A6 および B1 から B6 とします。

 1 回目に A1A2 vs A3A4 で左が下がり、2 回目に B1B2 vs B3B4 で釣り合ったとします。
この場合、A5A6B1B2B3B4 は本物と確定しますので、3 回目は A1A3B5 vs B1B2B3 で皿
に載せます。

 例えばこれで左が下がったとしたら、偽物は重いことが確定し、さらに偽物の組は A1A2 組
と B5B6 組に含まれていること、A1 と B5 の少なくとも片方は偽物であることが確定します。

 よって、 4 回目は A1 vs B5 で皿に載せ、例えばこれで右が下がったら偽物は A2B5 とわ
かりますし、例えばその 4 回目で釣り合ったら、偽物は A1B5 だとわかります。

#一見、5 枚ずつの場合も A6 と B6 の存在を無視すれば同じ手順で良さそうに見えますが、
 最初の 2 回が両方傾いた場合に本物と確定できるコインが 2 枚しかないために、3回目に
 右の皿に適切に載せられません。なので、5 枚ずつの場合は別手順が必要になります。


 りらひいさんからのコメントです。(令和3年2月6日付け)

 ところで、天秤 5 回で各グループ 11 枚(本物 10 枚、偽物 1 枚)、軽重まで判別を要求っ
て可能なんでしょうか。

 判別すべき結果は 242 種類、天秤の結果は 243 通り。しかも、5 回全て釣り合うという結
果は、偽物の軽重が判別できないので何も割り当てられないことが確定しています。

 もしこれが可能なら、これこそ正真正銘の「超々上級」だと思いますが、さてさて。


 上級や超上級はまだできていませんが、超々上級は解けました。とりあえず、できたやり方
を載せるので、自分で解きたい方は↓を見ないようにしてください。


グループAのコインを、Ap1,Ap2,Ap3,Aq1,Aq2,Aq3,Ar1,Ar2,Ar3,As,At と名付ける。
グループBのコインを、Bp1,Bp2,Bp3,Bq1,Bq2,Bq3,Br1,Br2,Br3,Bs,Bt と名付ける。
Ap1,Ap2,Ap3 をまとめて Ap123 のように書く。
本物と特定されたコインをGとし、Ap123が本物であることを G*3=Ap123 のように書き表す。

釣り合うことを「E」、左が重いことを「H」、左が軽いことを「L」と書き、「H or L」を一文字で「D」、
「E or H or L」を一文字で「A」と書く。
これらの文字を計測を行う順に左から並べて測定の途中経過や結果を表す。

[測定済み回数.測定の経過] {次測定で左に乗せるコイン}<=>{次測定で右に乗せるコイン}
のように書く。

[0.] {Ap123,Aq123,As,At} <=> {Ar123,Br123,Bs,Bt}
-[1.E] {Ap123,G*3} <=> {Aq123,Br123} // (G*9=Ar123,Bp123,Bq123)
--[2.EE] {Ap123,Br123} <=> {G*6}
---[3.EEE] {As,Bs} <=> {G*2}
----[4.EEEE] {At} <=> {G}
----[4.EEED] {As} <=> {Bs}
---[3.EED] {Ap1} <=> {Ap2}
----[4.EEDA] {Br1} <=> {Br2}
--[2.ED] {As,Bs} <=> {At,Bt}
---[3.EDE] {Aq1} <=> {Aq2}
----[4.EDEA] {Br1} <=> {Br2}
---[3.EDD] {Bs,Bt} <=> {G*2}
----[4.EDDE] {Br1} <=> {Br2}
----[4.EDDD(EHDH,ELDL)] {Ap1} <=> {Ap2}
----[4.EDDD(EHDL,ELDH)] {Aq1} <=> {Aq2}
-[1.D] {Ap123,Bp123,Bs} <=> {Aq123,Bq123,Bt}
--[2.DE] {Ap123,Bq123} <=> {Aq123,Bp123}
---[3.DEE] {Ar1} <=> {Ar2}
----[4.DEEA] {Br1} <=> {Br2}
---[3.DED(HEH,LEL)] {Ap1} <=> {Ap2}
----[4.DEDA(HEHA,LELA)] {Bq1} <=> {Bq2}
---[3.DED(HEL,LEH)] {Aq1} <=> {Aq2}
----[4.DEDA(HELA,LEHA)] {Bp1} <=> {Bp2}
--[2.DD(HH,LL)] {Ap123,Bp123,Bt,G} <=> {Ar123,Bq123,As,At} // (G*4=Aq123,Bs)
---[3.DDE(HHE,LLE)] {As} <=> {At}
----[4.DDEE(HHEE,LLEE)] {Ar1} <=> {Ar2}
----[4.DDED(HHED,LLED)] {Bp1} <=> {Bp2}
---[3.DDD(HHDH,LLDH)] {Ap1} <=> {Ap2}
----[4.DDDA(HHDHA,LLDHA)] {Bp1} <=> {Bp2}
---[3.DDD(HHDL,LLDL)] {Ar1} <=> {Ar2}
----[4.DDDA(HHDLA,LLDLA)] {Bq1} <=> {Bq2}
--[2.DD(HL,LH)] {Aq123,Bq123,Bs,G} <=> {Ar123,Bp123,As,At} // (G*4=Ap123,Bt)
---[3.DDE(HLE,LHE)] {As} <=> {At}
----[4.DDEE(HLEE,LHEE)] {Ar1} <=> {Ar2}
----[4.DDED(HLED,LHED)] {Bq1} <=> {Bq2}
---[3.DDD(HLDH,LHDH)] {Aq1} <=> {Aq2}
----[4.DDDA(HLDHA,LHDHA)] {Bq1} <=> {Bq2}
---[3.DDD(HLDL,LHDL)] {Ar1} <=> {Ar2}
----[4.DDDA(HLDLA,LHDLA)] {Bp1} <=> {Bp2}


 対応表は作るのがだるいので省略。一行のみ書いてみるとこんな感じ。

  [5.HLEHH] As,Bq1 重


見方の例:
1回目は[0.]の行の載せ方で測定する。
1回目の測定で左が下に下がれば、2回目は[1.D]の行の乗せ方で測定する。
2回目の測定で左が上に上がれば、3回目は[2.DD(HL,LH)]の行の乗せ方で測定する。
3回目の測定で釣り合えば、4回目は[3.DDE(HLE,LHE)]の行の乗せ方で測定する。
4回目の測定で左が下に下がれば、5回目は[4.DDED(HLED,LHED)]の行の乗せ方で測定する。
5回目の測定で左が下に下がれば、対応表の[5.HLEHH]の行を見て偽物コインとその軽重を
判定する。
 この場合、偽物はAsとBq1で本物よりも重い。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年2月6日付け)

 りらひいさん、DD++さん、全くもって感激です。素晴らしいです。根性なしな私は自力で解く
自信がございませんで、早速、お二方の解を読み込んでみます。

 なお、偽物が本物よりも重いとあらかじめわかっているときに、22枚中2枚の偽物を天秤
5回で判別するアルゴリズムが、月刊「理系への数学」2010年 6月号に解説されているよう
です。(手元になく、私は未読です。)

 それによれば以下が可能だそうです。

 偽物2枚が

7枚中にあるなら、3回
13枚中にあるなら、4回
22枚中にあるなら、5回
38枚中にあるなら、6回
66枚中にあるなら、7回
115枚中にあるなら、8回
 …

の天秤回数で偽物を確定できます。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年2月7日付け)

 りらひいさん、DD++さんの解を拝見して、私も学ぶ点が多々ございました。まことに有り難
うございます。ようやく私なりに考え付いたことを、下記にて御報告申し上げます。

 6 枚中 1 枚が偽物のグループが2つあるときに、天秤を 4 回使うことで、偽物が本物より
も重いか軽いのかについてと、どの 2 枚の組が偽物であるかちついてとが、確定できると
わかりました。

 A から F までに 1 個、 a から f までに 1 個の偽物があるとします。

■測定方法

 まず無条件に以下の2回の測定をします。

@ ABa:DEe
A Abe:Ead

 ここより、ケースT、ケースUに分岐します。

【ケースT】 @、Aのどちらかで天秤が傾けば、

BAEae:BDbd

とします。また、その結果を見ながらCの測定方法を選んでいきます。(後述)

【ケースU】 @、Aのどちらも天秤が釣り合えば、

 C、Fの中に偽物が 1 個、 c、f の中に偽物が 1 個あります。他は全部本物です。

 B、Cで偽物と、偽物が本物に比べ軽いか重いかについて判定します。その方法は別途
に後述します。


 ここで説明の都合上、ケースTにおいて、@からBまでの測定結果による偽物の組の候
補を一覧にしておきます。

 \は左の皿が軽く、/は右の皿が軽く、−は釣り合うことを意味します。

 表の左側に縦に並ぶのは偽物が軽いと仮定したときの偽物の組の候補を、右側に縦に並
ぶのは偽物が重いと仮定したときの偽物の組の候補を、リストアップしています。

《ケースT》

  ...軽:@AB:重   ...軽:@AB:重   ...軽:@AB:重 
Ac Af:\\\:Dd ..
.. Ab:\\−:Ed ..
.. Bb:\\/:Ec Ef
.. Aa:\−\:Dc Df
.. Ad:\−−:Eb ..
Bc Bf:\−/:Ee ..
Ca Fa:\/\:Db ..
.. Ba:\/−:De ..
.. Bd:\//:Ce Fe
.. Ae:−\\:Cd Fd
.. Be:−\−:Da ..
Cb Fb:−\/:Ea ..
.. Ea:−/\:Cb Fb
.. Da:−/−:Be ..
Cd Fd:−//:Ae ..
Ce Fe:/\\:Bd ..
.. De:/\−:Ba ..
.. Db:/\/:Ca Fa
.. Ee:/−\:Bc Bf
.. Eb:/−−:Ad ..
Dc De:/−/:Aa ..
Ec Fc://\:Bb ..
.. Ed://−:Ab ..
.. Dd:///:Ac Af

 このケースTでは、偽物の組の候補が2組ある場合と3組ある場合とがあります。

 3組ある場合には、

C Cc:Ff

で測定すれば、偽物の組の確定と、偽物が本物に比べて重いのか軽いのかについて確定
できます。

 要は、3組の候補は、「軽い1組の候補と重い2組の候補」もしくは「重いい1組の候補と軽
い2組の候補」になっていますから、2組側の候補のなかの、C、c、F、fを比較して、釣り合え
ば1組側のほうが偽物に確定し、傾けば2組側のどちらかが偽物に確定するわけです。

 ケースTで偽物の組の候補が2組ある場合には、C、F、c、fは本物確定です。このことに
留意しながら次のようにCの測定を行います。

C ABDE:CFcf

 要は、偽物が本物に比べて軽いのか重いのかを調べれば偽物の組も連動して確定する
わけです。

ここまでがケースTにおいての処理方法でした。次にケースUについて述べます。

 ケースUでは、天秤の使用回数を2回消費して、偽物の組の候補を以下の 4 組まで絞っ
ていたのでした。まだ、偽物が本物よりも重いのか軽いのかについても全くわかっていませ
ん。

Cc、Cf、Fc、Ff

 C、c、F、f以外は全部本物と確定しています。この中から、本物を 2 枚選び出して、Z、zと
記すこととします。

 3回目の測定では、次のようにします。

B Cc:Zz

 これが釣り合えば、偽物の組は確定し、Ff だとわかります。ついで、 C Ff:Zz と測定する
ことにより、偽物が本物よりも重いのか軽いのかについて確定します。

また、

B Cc:Zz

で天秤が傾いたとしたならば、以下のように考えます。

 Cc が本物の Zz よりも重ければ、偽物は本物よりも重いと確定します。

 C と c とのうち、どちらか一方、あるいは両方が、重い偽物です。

 ここで 4 回目の天秤計測として以下のように行います。

C C:c

 釣り合えば、Cc の組が 重い偽物の組であることが確定します。

 C が重ければ、c は本物と確定しますから、Cf の組が重い偽物です。

 c が重ければ、C は本物と確定しますから、cF の組が重い偽物です。

 以上、B Cc:Zz  で天秤が傾いて、Cc が本物の Zz よりも重いときの処理方法でした。

 B Cc:Zz  で天秤が傾いて Cc が本物の Zz よりも軽いときの処理方法も同様ですので記
すことを省略いたします。


 以上より、6 枚中 1 枚が偽物のグループが2つあるときに、天秤を 4 回使うことで、偽物
が本物よりも重いか軽いのかについてと、どの 2 枚の組が偽物であるかちついてとが、確
定できるとわかりました。

※当初は天秤4回で n 枚中 1 枚が偽物のグループが2つある設定で、偽物の軽重と偽物
 の組の両方の確定ができるのは、n = 5 が最大だと(証拠もないのに)信じていました。
 まさか、n = 6 で可能だなどとは思っておりませんでした。この度は本当に面白かったです。

※天秤5回で 11 枚中 1 枚が偽物のグループが2つある設定で、偽物の軽重と偽物の組の
 両方の確定ができる…という件についてはまだよく理解できていません。引き続き勉強い
 たします。


 Dengan kesaktian Indukmuさんからのコメントです。(令和3年2月18日付け)

 日経サイエンス [パズルの国のアリス] 偽造金貨と信用できない計測結果 をリスペクト
しつつ、以下を返歌といたしまして。

 迷探偵芋虫とその助手グリフォンがピカピカ光る金貨何枚かを並べて眺めながら、溜め息
をついていた。例によって好奇心旺盛なアリスが口を出す。

 「わあ、新品の金貨ですね。とっても綺麗! さわってもいいですか?」

 「ダメ、ダメ、大事な証拠品だ。お前さんの手垢がついては困る」と芋虫。

 手垢といわれてアリスは一瞬ムッとしたが、すぐに意味深な「証拠品」という言葉に反応す
る。「証拠って?」と怪訝そうな顔でグリフォンを見ると、グリフォンは了解を得るように芋虫
をチラッと見て、「まあ、この子は一味ではありえないから……」。

 「実は、この36枚の金貨は9カ所の鋳造所から4枚ずつ持ってきたサンプルなのだが、鋳
造所のうち最小0カ所、最大2カ所は金貨偽造団の拠点になっているという情報が入ってき
た。

 つまり、0枚ないし4枚ないし8枚は偽造金貨というわけだが、見かけでは区別がつかない。
実は、偽造金貨は本物よりほんの少し軽いことがわかっているのだが、それが実に微妙な
差で、特殊な電子天秤で比べないと違いがわからず、1回の計測にかなりの費用がかかる。
なお、本物どうし、偽物どうしは全く同じ重さだということもわかっている。」

 「ははあ、それで計測回数をなるべく減らしたいというわけですね」とアリス。

 芋虫は答える。「その通りなのだ。ところが、ここに別の問題があるのだ。君も知っている
あの怒りんぼうな…あわわ…もとい…せっかちかつ厳格な女王陛下にあらせられましては
明日の夕方までに金貨偽造団の拠点となっている鋳造所を全て確定せよとの御命令を下
されたのだよ。電子天秤で計測結果を得るために16時間はかかる。また、電子天秤を扱え
る技術者は、鏡の国にいる4人の騎士だけなのだ。女王から賜った期限を守るためにも、
各騎士に1回ずつ計測を頼んでみようかと考えているのだが、それで確実に贋物を見つけ
る方法がないか考えているわけだ。」

 アリスは自分の考えを言葉に出してみた。

 「各鋳造所から4枚ずつサンプルを持ってきたのは大正解で4人の騎士に1枚ずつ配布す
ることができる。すなわち電子天秤を同時平行に4機,作動させることができるわね。」

 グリフォンはそれを受けて念のためにと注意を促した。

 「もはや今日も夕刻なのだ。明日の夕刻までに結果を女王陛下に報告するためには、1
人の騎士からの電子天秤による計測結果の報告を受けての、別の騎士への計測方法の
指示・依頼を行う時間的なゆとりは全くない。4人の騎士による計測は全て平行に行わな
ければならないのだよ。」

 迷探偵芋虫はため息まじりに言う。

 「アリス。なにか良い方法はないものかね。失敗すれば女王陛下の更なるお怒りを招くこ
とになり、へたをすれば我々は全員首ちょんぱだ。」


#題意がうまく伝えきれたかどうか不安ですけれども。なにか質問が御座いましたら宜しく
 お願い申し上げます。


問題の設定を下記のように変更した場合(考える範囲を狭めたミニサイズ)を考えてみます。

・5カ所の鋳造所から3枚ずつ持ってきたサンプル15枚の金貨がある。
・鋳造所のうち最小0カ所,最大2カ所は金貨偽造団の拠点になっている
・0枚ないし3枚ないし6枚は偽造金貨
・見かけでは区別がつかない。偽造金貨は本物よりほんの少し軽い
・電子天秤を扱える技術者は,鏡の国にいる3人の騎士だけ
・時間的な都合により3人の騎士による計測はパラレルで行う


 5カ所の鋳造所から作られた金貨をa、b、c、d、eとします。3人の騎士に渡す計測の依頼を
次のフォーマットで略記します。

 左の皿に乗せる金貨と右の皿に乗せる金貨とをそれぞれ[]で囲み、

  [左の皿に乗せる金貨]^[右の皿に乗せる金貨]

と書きます。

 3人の騎士に依頼する計測はそれぞれ次のようにします。(パラレルに計測します。)

@ [ad]^[ce]
A [bd]^[ae]
B [be]^[ac]

 騎士からの計測結果は、左の皿が軽いときには「<」、釣り合うときには「=」、右の皿が軽い
ときには「>」と書くことにします。

 @ABの計測の結果をつなげて書きます。

 たとえば、@で左の皿が軽く、Aで釣り合い、Bで右の皿が軽いときには、<=> と書きます。

 得られた計測結果にもとづき、偽造団に通じている鋳造所は下記の一覧で求めることが出
来ます。

<<< bd
<< = d
< == ab
< => ad
<>> a
=<< b
=<> cd
==< de
=== 全ての鋳造所は無罪
=>= ae
=>> ac
>< = bc
> =< be
> => c
>>< e
>> = ce


 以上、小さいサイズの例題を提示させて頂きました。


 Dengan kesaktian Indukmuさんからのコメントです。(令和3年2月22日付け)

 上記のミニサイズの問題の隠れた構造の片鱗が見えたような気がいたしましたので、ご報
告させて頂ききたく存じます。氷山の一角かもしれませんけれども。

 上記のように5ヵ所の鋳造所から来たコインを a、b、c、d、eとします。更に、各コインごとに
背番号を付番します。すなわち、

 a には、 +19 、b には、 +06 、c には、 -26 、d には、 +30 、e には、 -29

と対応させます。さて、3つの集合α、β、γを定義します。

 α={0} 、β={30,19,6,-26,-29} 、γ={49,36,25,4,1,-7,-10,-20,-23,-55}

 これらには以下の性質があります。

 α∩β={ } 、α∩γ={ } 、β∩γ={ }

 任意のβの2要素の和はγの要素になっている。

 任意のγの要素はβの2要素の和になっている。

 αの要素の総和は0となっている。

 βの要素の総和は0となっている。

 γの要素の総和は0となっている。

(先ほどはβからコインに背番号を割り当てたことになります。)

 さて、数列 g[ ] でもって、各コインの重量を表します。すなわち、

 g[30] 、g[19] 、g[6] 、g[-26] 、g[-29]

 上記以外にはg[ ]は未定義とします。

 ここで、以下の数値について考えます。なお、abs()は絶対値を表す関数です。

 g[+06]+g[+-29]-g[+19]-g[-26]=0 のとき、s(0)=0

 そうでなければ、s(0)=(g[+06]+g[+-29]-g[+19]-g[-26])/abs(g[+06]+g[-29]-g[+19]-g[-26])

 g[+06]+g[+30]-g[+19]-g[-29]=0 のとき、s(1)=0

 そうでなければ、s(1)=(g[+06]+g[+30]-g[+19]-g[-29])/abs(g[+06]+g[+30]-g[+19]-g[-29])

 g[+19]+g[+30]-g[-26]-g[-29]=0 のときには、s(2)=0

 そうでなければ、s(2)=(g[+19]+g[+30]-g[-26]-g[-29])/abs(g[+19]+g[+30]-g[-26]-g[-29])

 s(0)、s(1)、s(2)は、ともに、-1 または 0 または +1 の値となります。

 次に、x を次の式 x = 25*s(2) +5*s(1) +s(0) で計算します。

 さて、x ∈ α のとき、偽物のコインは存在せず、偽造団の息がかかった鋳造所はありま
せん。

 x ∈ β のとき、x を背番号とするコインは偽物でその他は本物です。この時には偽造団
に与する鋳造所は一ヶ所です。

 x ∈ γ のとき、任意のγの要素はβの2要素の和になっていますので、x = y+z となる
y∈β、z∈β が定まります。

 y、z を背番号とするコインは偽物でその他は本物です。この時には偽造団に与する鋳造
所は二ヶ所です。

 見取り図としては以下が見やすいと思います。

+19 = +25-5-1 、+06 = +5+1 、-26 = -25 -1 、+30 = +25+5 、-29 = -25-5+1

天秤の使用方法

> @ [ad]^[ce]
> A [bd]^[ae]
> B [be]^[ac]

には、平衡五進数による記述でも説明が可能、ということになります。

※追記 以下の性質も効いているのだと思われます。

 βの要素を平衡五進数で表記したときには3桁となり、各々の桁には(1)、0、(-1)しか現れ
ません。通常の平衡五進数では、(2)、(-2)も現れることと対比可能です。
(γの要素を平衡五進数で表した場合では(2)、(-2)も現れています。)

 また、βの任意のふたつの要素を加算するときには、繰り上がりが発生しません。桁溢れ
したら天秤の算法には利用できません。


#急いで書いたので誤りがございましたならば御容赦ください。


 ミニサイズの問題については以上です。 鋳造所が9ヵ所で、バラレルに使う天秤が4器あ
るときにも、同様な考え方ができるはず、と思われます。
(手元に用意していた解でチェックしてみましたが概ね、良好です)

※現在のところ鋳造所の個数がより大であるとき、パラレルに使う天秤の台数がより大であ
 るときについては全く手が届いておりません。
※偽物を作りだす鋳造所が三ヵ所以上のときに、たとえば平衡七進数を使えばなんとかなる
 かという点については、今のところ望みを抱いていません。
(交換法則は成り立ちますが結合法則がうまくいかない気がいたします。という空想にすぎま
せんが)

 以上となります。


 DD++さんからのコメントです。(令和3年2月22日付け)

  x = 25*s(2) +5*s(1) +s(0) の定義だと、どこかの天秤で同じ皿に偽物が 2 枚載ることに
なった場合におかしくなりませんかね?


 Dengan kesaktian Indukmuさんからのコメントです。(令和3年2月24日付け)

 恐ろしいボーンヘッドでした。御指摘の通りです。ご教示をまことに有り難うございました。

 簡単には修復できそうにないミスです。あえて強引に修正するといたしましたならば次のよ
うになるのかもしれません。γの作り方がまずかったのだと観念して…もういちどγをつくり
たいと思います。

 結論から申しますと、 γ={25, -6, 24, -5, -20, 31, -24, 4, -30, 1} です。

 βの2要素からγの1要素を作ります。以前に間違えたときには単に加算していました。こ
れが間違いのもとでした。次のような関数を考えます。

 f(x,y)=(x+y)*(1-x*y/2)

 そして、βの2つの要素についてはそれぞれを3桁の平衡五進数で表現し、【各桁ごとに】
上の関数を通して、それらの3つの結果をトータルします。これを 演算とみなして † で書き
ます。

γの各要素は、次のようになります。どれも、βの2つの要素について † の演算をほどこし
たものとなります。

25=19†6,
-6=19†(-26),
24=19†30,
-5=19†(-29),
-20=6†(-26),
31=6†30,
-24=6†(-29),
4=(-26)†30,
-30=(-26)†(-29),
1=30†(-29)

 さて、 x = 25*s(2) +5*s(1) +s(0) についてはそのままとして、その x の値がγに含まれて
いれば、対応するβの2要素を求め、それが偽物の背番号となります。

 たとえば、 -5=19†(-29) ですので、xが -5 ならば、背番号が 19 と -29 のコインの鋳造
所がヤバイと……。

※これでうまくいけばよいのですが、ボーンヘッドを心配しています。楽に?このパズルを解
 きたいと思って考えましたのに、かえって混迷を深くしてしまいました。


 Dengan kesaktian Indukmuさんからのコメントです。(令和3年2月25日付け)

 あまりひっぱっても致し方ありませんので…。

 9枚中、本物よりも軽い偽物が 0 枚ないし 1 枚ないし、 2枚のときに、パラレルに天秤の計
測を4回以内で偽金貨を割り出すやりかたについて、ごく簡単にではありますが、想定してい
た解を記します。

 AからIまでにつき、@からCまでパラレルに計測します。「○」は天秤の左の皿に、「●」は
右の皿に乗せます。「ー」は天秤に乗せません。下記の図解に従って計測します。

@ABC
○●●●A
●○●●B
ー●○○C
●○ー○D
○○○○E
○ー○●F
○○●ーG
●●○●H
●●●○I

 偽物のありかについて、0枚の場合に 1 通り、1枚の場合に 9 通り、2枚の場合に 36 通り
あります。計 46 通りが上記の計測で弁別可能となっております。

 ※ここからは別のお話です。

 さきの見とり図にて、天秤の左右の皿の位置交換、コインの交換、天秤の《何回目?》の
交換をしても、偽物判別機能に違いはおきません。この意味で「等価」な解はたくさんありま
す。

 BとCとを交換すると「等価」なものが得られます。

@ABC新
@ACB旧
○●●●A
●○●●B
ー●○○C
●○○ーD
○○○○E
○ー●○F
○○ー●G
●●●○H
●●○●I

 更に、コインを交換します。

@ABC旧新
○○○○E A

○●●●A B
●○●●B C
●●○●I D
●●●○H E

ー●○○C F
○ー●○F G
○○ー●G H
●○○ーD I

 新FGHIのグループについて観察すれば、

●○○ー

がローテーションしていることが見てとれます。

 BCDEについても同様です。

 あとで触れることのために上記の解を1:4:4パターンと仮称しておきます。
(かたまりがみえるからです)

 上で見た通り「等価」な解はたくさんありますが、実は等価ではないものもあるのです。
次のものもそのひとつです。

○○○○
○○○●
●●●−

−●○○
○−●○
●○−○

○●●●
●○●●
●●○●

 これは言わば3:3:3パターンとでも……。おそらくは別解がまだまだあるのではないかと
思われます


 DD++さんからのコメントです。(令和3年2月22日付け)

 8 時間以内に解けずに首チョンパされた幽霊からの解答です。

 アリスは「4人の騎士に1枚ずつ配布することができる」と言っていますが、しかしその案を
必ず採用しなければならないわけでもなさそう。

 ということで、同じ人に同じコインを複数渡すことを認めて、9 種 4 枚ずつ計 36 枚全部使
う、こんな解答でどうでしょう。

[1] AAABBB vs EEFFGG
[2] CCCDDD  vs EEHHII
[3] AFH vs BGI
[4] CFI vs DGH

 Dengan さんに倣って、左の皿が軽いときには「<」、釣り合うときには「=」、右の皿が軽いと
きには「>」と書くことにします。

・1:<、2:< の場合(4 パターン)

 A と B のどちらかが偽物、C と D のどちらかが偽物、残り 5 つは本物確定です。このとき、
3 と 4 は A vs B と C vs D で測定しているのと同じなので、それぞれどちらが偽物か判別で
きます。

・1:<、2:= の場合(7 パターン)

 A と B のどちらかまたは両方が偽物、F と G は片方が偽物または両方本物、残り 5 つは
本物確定です。このとき、 3 と 4 は AF vs BG と F vs G で測定しているのと同じなので、4
の結果から F と G の真贋が確定し、その後 3 の結果を見れば A と B の真贋も確定します。

・1:<、2:> の場合(6 パターン)

 A と B のどちらかが偽物、E と H と I のどれかが偽物、残り 4 つは本物確定です。このと
き、 3 と 4 は AH vs BI と I vs H で測定しているのと同じなので、4 の結果から E と H と I
の真贋が確定し、その後 3 の結果を見れば A と B の真贋も確定します。

・1:=、2:< の場合(7 パターン)

 C と D のどちらかまたは両方が偽物、H と I は片方が偽物または両方本物、残り 5 つは
本物確定です。このとき、 3 と 4 は H vs I と CI vs DH で測定しているのと同じなので、3 の
結果から H と I の真贋が確定し、その後 4 の結果を見れば C と D の真贋も確定します。

・1:=、2:= の場合(1 パターン)

 全部本物です。

・1:=、2:> の場合(3 パターン)

 H と I のどちらかまたは両方が偽物、残り 7 つは本物確定です。このとき、 3 は H vs I で
測定しているのと同じなので、どちらが偽物か判別できます。

・1:>、2:< の場合(6 パターン)

 C と D のどちらかが偽物、E と F と G のどれかが偽物、残り 4 つは本物確定です。この
とき、 3 と 4 は F vs G と CF vs DG で測定しているのと同じなので、3 の結果から E と F
と G の真贋が確定し、その後 4 の結果を見れば C と D の真贋も確定します。

・1:>、2:= の場合(3 パターン)

 F と G のどちらかまたは両方が偽物、残り 7 つは本物確定です。このとき、 3 は F vs G
で測定しているのと同じなので、どちらが偽物か判別できます。

・1:>、2:> の場合(9 パターン)

 「E のみ偽物」「E が偽物で、かつ F と G と H と I のうち 1 つが偽物」「F と G の片方が偽
物で、H と I の片方が偽物」のいずれかです。このとき、 3 と 4 は FH vs GI と FI vs GH で
測定しているのと同じです。両方釣りあった場合は「E のみ偽物」。片方だけ釣りあった場合
は「F と G の片方が偽物で、H と I の片方が偽物」で、傾いたときに軽かった皿に載せた 2
つが偽物。両方傾いた場合は「E が偽物で、かつ F と G と H と I のうち 1 つが偽物」で、両
方の軽かった皿に共通で載せていたものが偽物。

 以上、全 46 パターンの偽物の混ざり方の判別が可能です。


 Dengan kesaktian Indukmuさんからのコメントです。(令和3年2月22日付け)

 DD++さんのアイデアには虚をつかれた思いです。なんて素敵なアイデアなのでしょうか。内
容をよく読み込んだ上で御返事をしたいと存じます。


 Dengan kesaktian Indukmuさんから新しい問題「赤い貯金箱には何枚の500円玉がはいっ
ているだろうか」を頂きました。(令和3年5月5日付け)

 新品の同じ重さの瀬戸物の貯金箱が16個あります。(中を見るには貯金箱を破壊するし
か方法がありません。そんな貯金箱、昔はあったような気がします。)

 貯金箱の1個は赤い色で、残りの15個は青い色です。

 あなたの友人がこのうち8個の貯金箱にそれぞれ500円玉を11枚いれました。この友人
はそれ以外の8個の貯金箱にはそれぞれ500円玉を10枚いれました。

 ところが、赤い貯金箱に何枚いれたのかについてを忘れてしまいました。

 さて、赤い色の小銭入れの中の500円玉の枚数を知りたいのですが、その方法としては
天秤を使うことにします。
(貯金箱を破壊したくないので、取り敢えず手近にあった大型の天秤を使うことにしたのです。)

 友人はこう考えました。

 赤い貯金箱にAと名付けます。青い貯金箱にB、C、D、E、F、G、H、I、J、K、L、M、N、
O、Pと名付けます。

 1回目の天秤では、AとBとの重さを比べる。

 2回目の天秤では、AからBまでの2枚とCからDまでの2枚との重さを比べる。

 3回目の天秤では、AからDまでの4枚とEからHまでの4枚との重さを比べる。

 4回目の天秤では、AからHまでの8枚とIからPまでの8枚との重さを比べる。

 上のように天秤を使えば、赤い貯金箱の中の500円玉の枚数を判定できる、友人はそう
考えてあなたに説明しました。

 そんなやりとりを聞いていた友人の兄弟のひとりが、次のように言いました。

 「天秤の使用を3回以内としても赤い貯金箱の中の500円玉の枚数を確実に判定できそ
うだ。」

 そんなことが可能でしょうか。できるとしたならばその方法は?

#この連休中に楽しんでいました。後日、出典をご案内させて頂きたく存じます。


 DD++さんからのコメントです。(令和3年5月5日付け)

 前の測定結果を見てから次の測定内容を決めていいなら、以下でできますかね。

(1) ABCDEFG vs HIJKLMN

 (1) で傾いた場合、(2a) AB vs CD

 (1) で釣り合った場合、(2b) AB vs OP

 (1) と (2) の少なくとも一方で傾いた場合、(3a) A vs B

 (1) と (2) の両方で釣り合った場合、(3b) AB vs CD


 (1) で傾いた場合、傾いた方向によって、

 「ABCDEFG の中に少なくとも 4 つ 11 枚入りがある」

 「ABCDEFG の中に少なくとも 4 つ 10 枚入りがある」

のいずれかを言うことができます。

 これは、それぞれ

 「ABCD の中に少なくとも 1 つ 11 枚入りがある」

 「ABCD の中に少なくとも 1 つ 10 枚入りがある」

が成り立つことになります。

 すると、 (2a) の測定が傾いても釣り合っても

 「AB の中に少なくとも 1 つ 11 枚入りがある」

 「AB の中に少なくとも 1 つ 10 枚入りがある」

のいずれかを言うことができ、(3a) で A の中身の枚数を知ることができます。


 (1) で釣り合った場合でも、(2b) で傾けばやはり

 「AB の中に少なくとも 1 つ 11 枚入りがある」

 「AB の中に少なくとも 1 つ 10 枚入りがある」

のいずれかを言うことができ、(3a) で A の中身の枚数を知ることができます。

 (1) と (2b) でともに釣り合った場合、ABOP は全て中身の枚数が等しいことがわかります。

 また、CDEFG の中に A とは中身の枚数が異なるものが 4 つ存在することがわかるので、

(3b) は必ず傾き、A の中身の枚数を知ることができます。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月6日付け)

 DD++さん、コンパクトでお見事な解答ですね。さすがです。

 出典をご案内いたします。

■Tanya Khovanova's Math Blog ; The Anniversary Coin

※上のブログのコメント欄には別解が載っていますが、個人的には DD++さん による解が
 サッパリしていて気持ちがいいです。

 初手を 7vs7 とする以外にあるのか、ないのか知りたいと思っております。数日間探し
ましたが…


 DD++さんからのコメントです。(令和3年5月6日付け)

 それは果たして別解なんでしょうかね。

 この問題においては一度でも傾くということが非常に大きな情報であり、それは、すなわち、
最も不運な 2 連続釣り合いが発生したときに 3 回目に絶対釣り合わない組み合わせを用意
することが手順構築の全てです。

 最初に 7 枚ずつ載せるというのはその点非常に優れていて、もしこれが釣り合ったときに
は、載せなかった 2 枚と片側の皿に載せた 7 枚のうち 4 枚、計 6 枚を適当に使えば、絶対
に釣り合わない配置を容易に作れます。

 ブログコメントの 2 つの解答と私の解答、確かにその 6 枚からどう不釣り合いを作るかに
差異があります。しかし、正直ここはどうとでも処理できる些末な部分なので、全て同じ解答
と言って差し支えないのではないかと思います。


 初手を 7vs7 とする以外にあるのか、ないのか知りたいと思っております。数日間探し
ましたが…


 初手 6 枚からでも、ちょっとテクニカルですが、可能ですよ。

(1) ABCDEF vs GHIJKL

 (1) が傾いたら、 (2a) AB vs CD から (3a) A vs B

 (1) が釣り合ったら、 (2b) CDEF vs MNOP

  (2b) が傾いたら、 (3b) AGHIJKLM vs BCDEFNOP

  (2b) が釣り合ったら、 (3c) A vs B

 これは流石に別解と呼んでいいんじゃないかと思います。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月7日付け)

 DD++さん、有り難うございます。

 この問題においては一度でも傾くということが非常に大きな情報であり、それは、すなわち、
最も不運な 2 連続釣り合いが発生したときに 3 回目に絶対釣り合わない組み合わせを用意
することが手順構築の全てです。


 なるほどっ!!

 最初に 7 枚ずつ載せるというのはその点非常に優れていて、もしこれが釣り合ったときに
は、載せなかった 2 枚と片側の皿に載せた 7 枚のうち 4 枚、計 6 枚を適当に使えば、絶対
に釣り合わない配置を容易に作れます。


 なるほどっ!!

 ブログコメントの 2 つの解答と私の解答、確かにその 6 枚からどう不釣り合いを作るかに
差異があります。しかし、正直ここはどうとでも処理できる些末な部分なので、全て同じ解答
と言って差し支えないのではないかと思います。


 なるほどっ!!

 初手 6 枚からでも、ちょっとテクニカルですが、可能ですよ。

(1) ABCDEF vs GHIJKL

 (1) が傾いたら、 (2a) AB vs CD から (3a) A vs B

 (1) が釣り合ったら、 (2b) CDEF vs MNOP

  (2b) が傾いたら、 (3b) AGHIJKLM vs BCDEFNOP

  (2b) が釣り合ったら、 (3c) A vs B

 これは流石に別解と呼んでいいんじゃないかと思います。


 これは凄いですね。唖然としました。

 《(2b) が傾いたら (3b) AGHIJKLM vs BCDEFNOP》の部分は、私には絶対に到達できそう
にありません。早期に刈り込んでしまいます。

 実際、当該分岐で A の重さをいじろうとすると、あちこちに副作用が出てしまい、分岐から
食み出てしまいます。これには参りました。

 さて、 上記で、このパズルをご案内いたしましたが、その時には例題として天秤を4回使っ
ていいならばと、以下を示しました。

 1回目の天秤では、AとBとの重さを比べる。

 2回目の天秤では、AからBまでの2枚とCからDまでの2枚との重さを比べる。

 3回目の天秤では、AからDまでの4枚とEからHまでの4枚との重さを比べる。

 4回目の天秤では、AからHまでの8枚とIからPまでの8枚との重さを比べる。

 私は、この中に流れている性質を、天秤3回でも使ってやろうと目論みました。

 赤い貯金箱を□または■で表します。その他の貯金箱を○または●で表します。白は軽
いもの黒は重いものとします。

 上記で3回目までで全て釣り合ったときには、以下の2つの可能性しか残されていません。

ABCDEFGHIJKLMNOP
■●●●●●●●○○○○○○○○

または
□○○○○○○○●●●●●●●●

 ここまでくれば、Aが■なのか□なのかについて天秤を後1回使えば判定できます。

 上を教訓に、(重いか軽いかについては二の次だっ!)Aと同じ重さのものをどんどん見つ
けていこう、そうすれば道は開ける!……というのが、私の基本方針となりました。

 その為には、初回で、7vs7で計測するのがとても便利で、《不利と思われる》釣り合う状
況が生じたときにこそ、【互いに同じ重さだとわかっているグループ】の規模を大きくできる、
その目的に合致しているのでした。

 @ABCDEFG=HIJKLMN が成立すると、O=P でもあるわけで、このOPは互いに重さが同じ、
パズルを解きやすくする種なのだと考えました。

 A が、この互いに重さが同じグループの仲間入りをするために、A A vs P と計測するこ
とを考えます。

 傾けば、Aが■なのか□なのかが判明しますし、釣り合えば、AOPは、■●●か、□○○
のどちらかです。どちらであるかについては3回目の計測で判明すれば良しとします。

 1回目の計測結果にもたち戻ると、以下の2ケースしかありえません。

 BCDEFG に●●○○○○が順不同に含まれる、このとき、AOP は、 ■●●。

 BCDEFG に●●●●○○が順不同に含まれる、このとき、AOP は、 □○○。

 こうなってくると、AOPの白黒を判定するための3回目の計測は簡単で、BCDEFGから任意
の3個を選んでAOPと重さを比べればよいとわかります。なお、このとき、釣り合うことはあり
ません。必ず傾くので、その傾きに応じて、AOPは■●●か、□○○ のどちらかについても
判明するというわけです。

※ちなみに、初回の天秤で傾くときも、同じ重さのものを探す気持ちで解いていきました。

 すなわち、2回目では A が B と同じ重さの仲間になるかどうかみます。仲間になれなけれ
ば A の重さは決定されて終わり、そうでなければ仲間が増えて次に備えます。

 3回目では AB が CD と同じ重さの仲間になるかどうかみます。仲間になれなければ AB
の重さは決定されて終わり、そうでなければ仲間が4つになりますが、初回の判定結果とあ
わせれば  ABCD の重さは決定されます。

という気持ちで解いていました。


 DD++さんからのコメントです。(令和3年5月7日付け)

 《(2b) が傾いたら (3b) AGHIJKLM vs BCDEFNOP》の部分は、私には絶対に到達できそう
にありません。早期に刈り込んでしまいます。


 そこに加えて、(2b) にあえて A を載せないというのも素直ではなく、初手 7 枚ずつかなり
思いつきにくい解答と思います。

  Aと同じ重さのものをどんどん見つけていこう、そうすれば道は開ける!

 なるほど、確かに、その発想も有力ですね。まあ、同じ重さのものが多い = それをまとめ
て載せると釣り合わせにくい、と思えば考え方として親戚なのかも?

 ところで、初手 5 枚ずつ解ってあるんでしょうかね? 3 回目どころか 2 回目で絶対釣り
合わないようにできるんですが……。


 りらひいさんからのコメントです。(令和3年5月9日付け)

 いろいろ試していたら、できました。

(1) ABCDE vs FGHIJ

 (1) が傾いたら、 (2a) AB vs CD から、 (3a) A vs B

 (1) が釣り合ったら、 (2b) AFGHIJ vs CDEKLM

  (2b) が傾いたら、 (3b) A vs B

  (2b) が釣り合ったら、 (3c) ACDKLM vs BFGHIJ


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月9日付け)

 りらひいさん、なんということ!!これ、 NOP については 1回も天秤に乗せなくてすんでい
るのですか!?早く出先から家に帰ってじっくりと鑑賞したいですっ。なんてこと!!??


 DD++さんからのコメントです。(令和3年5月9日付け)

 なるほど、(1) と (2b) の組み合わせ、(2b) と (3c) の組み合わせで、実質的に A を片側に
2個載せることを実現しているわけですね。これは思いつかなかった。

 りらひいさんの発想を使って、こんな解を見つけました。

(1) ABCD vs EFGH

 (1) が傾いたら、 (2a) AB vs CD から、 (3a) A vs B

 (1) が釣り合ったら、 (2b) AEFGH vs BCDIJ

  (2b) が釣り合ったら、 (3b) AIJ vs BCD

 軽重 8 個ずつの 16 個で A の重さがわかるのはもちろん、なんと軽重 9 個ずつの 18 個
からでもちゃんと A の重さがわかる解です。


 りらひいさんからのコメントです。(令和3年5月10日付け)

 わたしは、DD++さんの初手6枚ずつ解の

   (2b) が傾いたら (3b) AGHIJKLM vs BCDEFNOP

の箇所を見て、「その前の釣り合った結果を利用しているのか。なるほど!」と思って、やり
始めたのですが……。

 そして、DD++さんが、

  ところで、初手 5 枚ずつ解ってあるんでしょうかね?

と言っておいて、解を挙げていなかったことから、単純なやり方ではだめなんだと思って、あ
えてややこしい乗せ方から考えていったからあの解になりました。

 けれどもっと単純に考えておけば、簡単にいったんですね。

  りらひいさんの発想を使って、こんな解を見つけました。

の解にならうと、次のような感じでもっとわかりやすい初手5枚ずつ解がありましたね。

(1) ABCDE vs FGHIJ

 (1) が傾いたら、 (2a) AB vs CD から、 (3a) A vs B

 (1) が釣り合ったら、 (2b) AFGHIJ vs BCDEKL

  (2b) が釣り合ったら、 (3b) AKL vs BCD


 DD++さんからのコメントです。(令和3年5月10日付け)

  「その前の釣り合った結果を利用しているのか。なるほど!」

 いやあ、出した本人は全然意識してませんでした。(2b) が傾いた時点で状況がかなり絞ら
れるので、それら全てのパターンで A の軽重により傾きが揃う載せ方を探しただけだったの
で。自分の出した解答を分析するのも大事ですね……。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月10日付け)

 DD++さんやりらひいさんに比べて完全に周回遅れな私です。DD++さんの初手4枚ずつ解
を再掲します。

(1) ABCD vs EFGH

 (1) が傾いたら、 (2a) AB vs CD から、 (3a) A vs B

 (1) が釣り合ったら、 (2b) AEFGH vs BCDIJ

  (2b) が釣り合ったら、 (3b) AIJ vs BCD


 この解で初手で釣り合ったときのチェックシートについて、私は次のように作成したりして
います。

 各貯金箱に含まれる枚数から10を減じた数をAからPまでで表します。それぞれ 0 または 1
となります。x、y、z という変数を用意しておいて、

 x=A+B+C+D-(E+F+G+H) 、y=A+E+F+G+H-(B+C+D+I+J) 、z=A+I+J-(B+C+D)

と定義します。

 x が 0 のときに、yやzがそれぞれ正なのか、0 なのか、負なのかを知れば、Aの値が求ま
る、こうした解になっているはずです。

 たとえば、 A=1 、B=1 、C+D=2 、E+F+G+H=4 、I+J=0 、K+L+M+N+O+P=0 のケース
では、

...D H J P
A BC E I K xyz
+ -- +
1 12 4 0 0 0+
  のように書きます。(見出しがズレなければ良いのですが…)

 このケースでは、zの値を見るまでもなく y が正なので、A=1 と判定できる、ということとな
ります。

 x=0 の場合の全ケースを一覧にしてみますと、以下のようになります。

...D H J P
A BC E I K xyz
+ -- +
1 12 4 0 0 0+
1 11 3 2 0 00+
1 02 3 2 0 00+
0 12 3 2 0 0-
1 11 3 1 1 0+
1 02 3 1 1 0+
0 12 3 1 1 0-
1 11 3 0 2 0+
1 02 3 0 2 0+
0 12 3 0 2 00-
1 10 2 2 2 00+
1 01 2 2 2 00+
0 11 2 2 2 0-
0 02 2 2 2 0-
1 10 2 1 3 0+
1 01 2 1 3 0+
0 11 2 1 3 0-
0 02 2 1 3 0-
1 10 2 0 4 0+
1 01 2 0 4 0+
0 11 2 0 4 00-
0 02 2 0 4 00-
1 00 1 2 4 00+
0 10 1 2 4 0-
0 01 1 2 4 0-
1 00 1 1 5 0+
0 10 1 1 5 0-
0 01 1 1 5 0-
1 00 1 0 6 0+
0 10 1 0 6 00-
0 01 1 0 6 00-
0 00 0 2 6 0-


 y が正ならば、A=1 、y が負ならば、A=0

 y=0 かつ z が正ならば、A=1
 y=0 かつ z が負ならば、A=0
 y=0 かつ z=0 は発生しない。

ということになっています。

 いやあ、実に上手い具合になっているのですね、平伏いたします。

 16個の貯金箱中6個 K、L、M、N、O、Pについては、天秤にかけるまでもないあたり、上の
ようなチェックシートを作成して確認した後もなお、未だに信じがたい気がいたします。

#投稿後にふと思ったのですが、赤い貯金箱(A)については天秤に乗せてはならぬ、といっ
 た可笑しな制約がついていても解はありえるのでしょうか……。あるいは、天秤3回では無
 理でも、4回ならできるよ、とか?


 DD++さんからのコメントです。(令和3年5月10日付け)

 とりあえず、10 回あればできますね。C vs D、E vs F、G vs H、・・・、O vs P の後で、B が
重いか軽いか判定するのに 3 回。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月11日付け)

 なるほど、C vs D、E vs F、G vs H、・・・、O vs P の部分では、C から P までのパリティを
調べているわけでしたか。

 すると、A から B までのパリティを求めたことになる、後は B の軽重を調べるのに3回計
ればよいと。

 mod 3 でも同じことが出来ますね。

 (BCD) (EFG) (HIJ) (KLM) (NOP) と5つのグループにわけておきまして、各グループの中に
「重い」貯金箱が何個あるかについて mod 3 で調べる。 1グループあたりこれには天秤計測
が2回必要です。 5グループでは 10回必要と。

 AからPまでは 「重い」貯金箱が2個ありますから(mod 3) ……。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月15日付け)

 赤い貯金箱に触ってはいけない設定で、天秤の使用回数を9回以内でできる方法を探して
います。まだ未完ですが、次に述べるような着想を得ておりまして検討中です。皆様に是非と
も御助力を頂きたく思いきって投稿いたします。

 1個を赤い貯金箱とし、15個を青い貯金箱とします。

 青い貯金箱を3個づつ、5グループに分け、このグループ間について重さ比較をしてソート
することを考えます。

 重い貯金箱の個数が各グループにどのように分布しているかについてのパターンは12通
りになると思います。
(各パターンについては、左から右へだんだん重くなるようにしています。)

■赤い貯金箱が軽い時、6通り。

00233
01133
01223
02222
11123
11222


■赤い貯金箱が重い時、6通り。

00133
00223
01123
01222
11113
11122


 上は、個数の中身を知っているからこその一覧表となっています。ここで、各グループにつ
いては、重い貯金箱の個数をいれる変数を a、b、c、d で表すものとし、a<b<c<d と約束
します。

 さきのパターンの一覧表を書き直すと…、

■赤い貯金箱が軽い時、6通り。

00233 aabcc
01133 abbcc
01223 abccd
02222 abbbb
11123 aaabc
11222 aabbb


■赤い貯金箱が重い時、6通り。

00133 aabcc
00223 aabbc
01123 abbcd
01222 abccc
11113 aaaab
11122 aaabb


 上の一覧から、例えば5グループ間を重さについてソートしたときに、パターンが abbcd
のようになっていれば、赤い貯金箱が重いことが判定できます。

 これらabcdのパターンからだけでは赤い貯金箱の軽重の区別できないのが以下の2パタ
ーンのみです。

00233 aabcc
00133 aabcc

 この場合には、bに相当するグループ内の3個の貯金箱のうち、重い貯金箱が1個なのか
2個なのかについて2回の天秤使用を追加することになります。

 当該グループの貯金箱を X、Y、Zとしたときに、XとYとで重さの比較をし、さらにXとZとで
重さの比較をすればよいわけです。この結果から、

00233 aabcc
00133 aabcc

のどちらなのか判定できる、すなわち、赤い貯金箱の軽重が判定できる、というわけです。

 さて、先の一覧表にあてはめる目的で、5つのグループ間での重さのソートをするためには
何回の天秤使用回数があれば良いでしょうか。

 「7回」であれば、 aabccパターンでの追加の2回を加算しても、計9回で、赤い貯金箱の軽
重を判定できることとなります。


 実は、調べてみたところ、

 どの重さも互いに等しくはなっていないという設定で、5個の物体の間で重さの順にソートを
するアルゴリズムでは、天秤使用回数が 最大 7回 で済ませられるということが、

ドナルド・クヌースの

『The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition 日本語版』

に載っているということがわかりました。

※手元にはないので、どのようなアルゴリズムなのかについて調べられません。

※もしもクヌースによるものが、互いに重さが異なることを利用したアルゴリズムであれば、
 たとえば、aabccパターンであると出力できるのかどうか…今のところは…わかりません。

 今、作りたいのは、最小2種類、最大4種類の重さからなる 5個の物体を、天秤7回以下
でソートするアルゴリズムです。皆様、どうかお知恵を御貸しくださいますよう、お願い申し
上げます。


 DD++さんからのコメントです。(令和3年5月15日付け)

 私が最初に挙げた 2 個ずつ分ける方針は、回数の最少性を全く気にしてなかった解で、
後から考えて、この方針で 9 回で済むことに気づきました。(投稿しておけばよかった)

 2 個ずつ 7 回の測定をする中で一度でも傾いた回があった場合、その片方と B を比較す
れば B の軽重は あと 1 回の測定で判別可能です。

 問題は、不幸にも 7 連続で釣り合った場合ですが、この場合は B vs C を測定し、それも
釣り合ったら、 BCD vs EGI をすればあと 2 回の測定で判別可能です。

 すなわち 9 回で A の軽重は特定可能です。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月15日付け)

 問題は、不幸にも 7 連続で釣り合った場合ですが、この場合は B vs C を測定し、それも
釣り合ったら、 BCD vs EGI をすればあと 2 回の測定で判別可能です。


 あーーー

 BCD=EGI となることは絶対にありえませんね。なんとならば、EGI=FHJ の状況下にあった
から、BCD=EGI=FHJ などという、同じ重さが 9個 なんてありえないと。

 はあー…

 B=C=D と EGI との比較で、Bの重さが確定、Aの重さもわかってメデタシメデタシですね。

 DD++さん、有り難うございました。


 DD++さんからのコメントです。(令和3年5月15日付け)

 Dengan さんの方針なら、8 回で行けそうです。

 3 個ずつ 5 グループを作ります。

(1-3) 5 グループのうち 3 グループを取り出し、全ての組み合わせを比較し、これらを軽い
   順に一列に並べます。

   同じ重さのものがあった場合は暫定的に片方を前、片方を後としておき、同じ重さだっ
  たことを記録しておきます。完成した列を X とします。

(4) 残った 2 グループを比較し、軽い順に一列に並べます。同じ重さのものがあった場合は
  暫定的に片方を前、片方を後としておき、同じ重さだったことを記録しておきます。完成
  した列を Y とします。

(5-6) X と Y の、先頭同士、末尾同士をそれぞれ比較します。

 もし、(5-6) が両方釣り合った場合、(5-6) で載せなかったグループと赤い貯金箱の中に、
重いものと軽いものが 2 つずつあると確定します。

 よって、(7-8) で未使用グループ内の重い貯金箱の個数を調べれば終わります。

 もし、(5-6) の片方でも傾いた場合、「X の先頭と Y の先頭を比較し、軽い方を所属列から
取り除く」を繰り返すことで、全てのグループの重さの順位がわかり、Dengan さんの作成した
一覧を参照することで終わります。

 問題は、これに何回かかるかですが、まず 1 つめは (5-6) での結果を参照することで、天
秤を使わずに済ませられます。そして、(7-8) でさらに 2 つ取り除きます。このとき、 X や Y
がなくなれば操作は終了ですし、X と Y に 1 つずつ残った場合は再び (5-6) の結果を参照
することで最後の操作を行えます。

 すなわち、この作業はどんな場合でも 2 回以内で済みます。

ということで、天秤 8 回で赤い貯金箱の軽重を判別できました。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月16日付け)

 おおっ!!、DD++さんは天秤の神様ですかっ!!!

 遅ればせながらちょっと訂正です。

00233 aabcc
00133 aabcc

 この場合には、bに相当するグループ内の3個の貯金箱のうち、重い貯金箱が1個なのか
2個なのかについて2回の天秤使用を追加することになります。


 これ、1回追加で済みますね…。完全にボーンヘッドです。

 話は変わります。

 5グループのソートで更にうまいことできれば、この追加1回分もなくせるかもと、もう少し
粘ってみたくなりました。ソート途中で、同じ重さのグループが必ず一組以上はあるというこ
とを念頭に、早終わりがありえるか検討してみます。

 夢は7回です。

 なお、重さが互いに異なる場合の5個の物体を天秤7回でソートするやり方をひとつ見つけ
ました。これを元に…です。


 DD++さんからのコメントです。(令和3年5月17日付け)

 これ、1回追加で済みますね…。

 あれ?1 回目が釣り合ったとしても傾いたとしても 2 回目が必要じゃないですか?私も何
か見落としてるのかな。

 あ、わかりました。

 他のグループから重い貯金箱が 1 つか 2 つになるように用意すればいいんですね。私も
ボーンヘッドでした。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月21日付け)

 赤い貯金箱に触れない設定のほうの問題で、知人が天秤の使用を最大7回で済ます方
法をみつけてくれました。概要を以下に報告いたします。

 15個 の青い貯金箱を 4つ のグループにわけます。4つ のグループを A、B、C、D とします。
A、B、C、には 4個、Dには 3個の貯金箱が含まれます。

T:天秤3回を消費して、A、B、C 間の大小関係を調べます。

U:天秤2回を使って D のなかの重い貯金箱の数を数えます。 0個 と 3個 との区別はでき
  ませんが、問題ありません。

 以上、5回の天秤使用である程度のデータを得たことになります。

 大変に興味深いことですが、上記のTのデータを鑑みることで、Uでの 0個 と 3個 との、
どちらであるのかについてが既に確定しています。

 あと2回の天秤で、15個の青い貯金箱中のうち、重い貯金箱の個数が 7個 なのか 8個 な
のかについて判定できます。(*難しいものでは無いので詳細を割愛させていただきます。)

 トータル 7回 の天秤で赤い貯金箱が軽いのか重いのかについて判定できることになります。

 以上、概要のみの御報告となります。もしも御興味を頂ければ、(*)あたり、追試を試みて
頂ければ幸いです。

#私はというと、最大 6回 に挑戦中です。 …できるような気がしてならないのです。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月22日付け)

 失礼いたしました。バグが報告され、修正が完了しました。7手でうまくいくことが確認でき
ました。お騒がせしまして、たびたび申し訳けありませんでした。


 DD++さんからのコメントです。(令和3年5月22日付け)

 大変に興味深いことですが、上記のTのデータを鑑みることで、Uでの 0個 と 3個 との、
どちらであるのかについてが既に確定しています。


の意味がよくわからなかったのですが、もう少し詳細な解説をお願いしてもいいですか?


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月23日付け)

 私が間違っておりました。知人のせいではありません。

Tで、大小関係のみならず、それぞれのグループのなかにある重い貯金箱の個数が明らか
になれば、当然のことながらUでの 0個 か 3個 かについては確定するわけでして、このこと
は興味深いことでもなんでもありません。

Tで、大小関係のみを知っているときには、Uでの 0個 か 3個 かについては確定しており
ません。大変申し訳ございませんでした。


 Aに4個の貯金箱、Bに4個の貯金箱、Cに4個の貯金箱、Dに3個の貯金箱が含まれるよう
に、グループ分けをしたものとします。

 3手をかけて、ABC間の重さの大小関係を確定し、更に2手をかけて、Dのなかの重い貯金
箱の個数について、「1」なのか、「2」なのか、「0または3」なのかについて調べるものとします。

 ここまで計5回の天秤使用をしました。

 さて、ここで、A>B、B>C  のケースのみについて考えてみます。Dについては、0と3との
どちらかであるとします。

 ありえるパターンとしては、以下があります。

ABCD t
4310 8
4300 7
4210 7
4103 8
3203 8
3103 7


 ただし、t はABCDの小計とします。t の値によって赤い貯金箱の軽重がわかります。

 あと2回の天秤、総計7回の天秤使用で、t の値を確定できるかどうか考えてみなければな
りません。

 Aから3個を抜き出したものをEとよびます。Eの中の重い貯金箱の個数は、

 Aが4のときにEは3 、Aが3のときにEは3または2 です。

 DもEも貯金箱が3個づつですが、これを天秤で比べます。

 D<E ならば、D=0 、D≧E ならば、D=3

とわかります。以上は 6手目に相当します。

 7手目は、Dの値によって分岐します。

7手目。(D=0)

ABCD t
4310 8
4300 7
4210 7


 AからCに2個 、DからBに2個、移動して、BもCも6個づつにします。

ABCD t
2330 8
2320 7
2230 7


 B=Cのときにのみ、t=8です。B≠Cのときにのみ、t=7です。

 ですから、BとCとを比較すれば、t を確定することになります。ここまでが、D=0のときの
7手めです。

7手目。(D=3)

ABCD t
4103 8
3203 8
3103 7


 DからBに2個 、CからAに2個、移動して、AもBも6個づつにします。

ABCD t
4301 8
3401 8
3301 7


 A=Bのときにのみ、t=7です。A≠Bのときにのみ、t=8です。

 ですから、AとBとを比較すれば、t を確定することになります。ここまでが、D=3のときの
7手めです。

 上記は、5手め終了時にて、A≠B、B≠C、C≠A のケースについて、Dが0または3のとき
を考えてまいりました。

 他の分岐に於いて必ずしも上手くいくわけではないのではないかと、知人に連絡を取って
いるところです。全体で 7手では済まないのではないかと。

 もっときちんとした確実なことがわかってから投稿すべきであったと猛省しております。
何卒御容赦を賜りたくお願い申し上げます。


 DD++さんからのコメントです。(令和3年5月23日付け)

 あ、やっぱりもう 1 手いりますよね。確認してくださりありがとうございます。全パターン 7手
で可能かどうか、こちらでも確認してみます。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月24日付け)

 A>B、B>C かつ (D=0 or D=3) については、前回投稿いたしました。今回は、

 A>B、B>C かつ D=1 のケースと、A>B、B>C かつ D=2 のケースについて、

それぞれを考えてみます。

 まずは、A>B、B>C かつ D=1 のケースを考えます。ありえるパターンとしては、以下が
あります。

ABCD t
4301 8
4211 8
4201 7
3211 7


 6回目の天秤で、Aの偶奇を調べます。
※Aの4個の貯金箱を2個づつに分けて両者を比較します。結果が奇数ならば可能性として、

ABCD t
3211 7


だけが生き残り、t の値が確定しますので、これで終了です。結果が偶数ならば次に進みま
す。残った可能性は次の通りです。

ABCD t
4301 8
4211 8
4201 7


 天秤を使う前に準備をします。Aから重い貯金箱を2個、Cに加えてCを計6個にします。ま
た、Dの中から軽い貯金箱を2個選び、Bに加えてBを計6個にします。準備した結果は以下
の通りとなります。

ABCD t
2321 8
2231 8
2221 7


 準備が終わりましたので、7回目の天秤として、BとCとを比較します。釣り合えば t=7 、
傾けば  t=8 となり、 t の値は確定されます。

 以上で、A>B、B>C かつ D=1 のケースで 7手 で済むことが分かりました。

 次に、A>B、B>C かつ D=2 のケースについて考えます。ありえるパターンとしては、以
下があります。

ABCD t
4202 8
4102 7
3212 8
3202 7


 6回目の天秤で、Cの偶奇を調べます。
※Cの4個の貯金箱を2個づつに分けて両者を比較します。結果が奇数ならば可能性として、

ABCD t
3212 8


だけが生き残り、t の値が確定しますので、これで終了です。結果が偶数ならば次に進みま
す。残った可能性は次の通りです。

ABCD t
4202 8
4102 7
3202 7


 天秤を使う前に準備をします。Dから重い貯金箱を2個、Bに加えてBを計6個にします。ま
た、Cの中から、軽い貯金箱を2個、Aに加えてAを計6個にします。準備した結果は以下の
通りとなります。

ABCD t
4400 8
4300 7
3400 7


 準備が終わりましたので、7回目の天秤として、AとBとを比較します。釣り合えば t=8 、傾
けば  t=7 となり、 t の値は確定されます。

 以上で、A>B、B>C かつ D=2 のケースで 7手 で済むことが分かりました。

 ここまで示したことをまとめますと、5手をかけて A>B、B>C を得て、かつ D の値を知れ
ば、残り2手、トータル7手で 赤い貯金箱の軽重が分かる…ということになります。


 りらひいさんからのコメントです。(令和3年5月27日付け)

 A>B=C 、A=B>C のケースについて、別のアプローチとなりますが、天秤7回で出来
ました。手順は結構複雑です……。 ※A=B=C のときは自明なので説明省略。

 手順を示す前に、この方法のポイントを書いておきます。

ポイント@ 15個の[軽]/[重]の内訳が偶数/奇数なのか奇数/偶数なのかがわかれば、残り
       の1個は奇数個だった方と同じ重さです。

ポイントA ある測定で釣り合ったとき、天秤の左右に乗せたものを合わせると[軽]/[重]の
       内訳は偶数個/偶数個になります。

ポイントB 「ST vs UV」および「SU vs TV」という2回の測定をしたとします。
      ・2回とも釣り合えば、STUVは4個とも同じ重さか[軽]/[重]2個ずつかのどちらかです。
      ・1回釣り合い1回傾けば、[軽]2個と[重]2個が特定されます。
      ・2回とも傾けば、[軽]1個と[重]1個が特定され、残りの2個は同じ重さです。

 手順は以下の通り。

 行末のしるしの意味:

□…結果で分岐して次へ続く
△…結果により判定完了または次へ続く
○…判定完了

 Aに4個の貯金箱、Bに4個の貯金箱、Cに4個の貯金箱、Dに3個の貯金箱が含まれるよう
に、グループ分けをします。それぞれの貯金箱をA1、A2、... のように名付けます。

(1) A1A2 vs A3A4 / (2) B1B2 vs B3B4 □

(1)(2) で1回か2回釣り合ったら、 (3a) C1C2 vs C3C4 □

(1)(2)(3a) が3回とも釣り合ったら、 (4a) D1 vs D2 / (5a) D2 vs D3 △
(4a)(5a) が2回とも釣り合ったら、 (6a) A1A2A3 vs D1D2D3 △
(6a) が釣り合ったら、 (7a) B1 vs D1 ○

(1)(2)(3a) が2回釣り合い1回傾いたら、傾いたグループをXとして、
 (4b) X1X3 vs X2X4 / (5b) D1 vs D2 / (6b) D2 vs D3 △

 (5b)(6b) が2回とも釣り合ったら、 (7b) [軽]1個 vs D1 ○

(1)(2)(3a) が1回釣り合い2回傾いたら、傾いたグループをXYとして、
 (4c) X1X3 vs X2X4 / (5c) Y1Y3 vs Y2Y4 から (6c) [軽]2個+[重]1個 vs D1D2D3 △
 (6c) で右が重くなったら、 (7c) [軽]1個+[重]2個 vs D1D2D3 ○


(1)(2) で2回とも傾いたら、 (3d) A1A3 vs A2A4 / (4d) B1B3 vs B2B4 □

 (3d)(4d) が2回とも釣り合ったら、 (5d) [軽]4個+[重]3個 vs C1C2C3C4D1D2D3 ○

 (3d)(4d) が1回釣り合い1回傾いたら、 (5e) [軽]2個+[重]2個 vs C1C2C3C4 □

 (5e) で釣り合ったら、(6e) [軽]2個+[重]1個 vs D1D2D3 △
 (6e) で右が重くなったら、 (7e) [軽]1個+[重]2個 vs D1D2D3 ○

 (5e) で右が軽くなったら、
  (6f) [軽]3個+[重]1個 vs C1C2C3C4 / (7f) [軽]1個+[重]2個 vs D1D2D3 ○

 (5e) で右が重くなったら、
  (6g) [軽]1個+[重]3個 vs C1C2C3C4 / (7g) [軽]2個+[重]1個 vs D1D2D3 ○

 (3d)(4d) が2回とも傾いたら、
  (5h) [軽]1個+[重]1個 vs Aの未確定1個+Bの未確定1個 □

 (5h) で釣り合ったら、
  (6h) [軽]2個+[重]1個+Aの未確定2個+Bの未確定2個 vs C1C2C3C4D1D2D3 ○

 (5h) で右が軽くなったら、 (6i) [軽]1個+[重]2個 vs D1D2D3 △
 (6i) で釣り合ったら、(7i) C1C2 vs C3C4 ○
 (6i) で右が重くなったら、 (7j) [軽]2個+[重]2個 vs C1C2C3C4 ○

 (5h) で右が重くなったら、 (6k) [軽]2個+[重]1個 vs D1D2D3 △
 (6k) で釣り合ったら、(7k) C1C2 vs C3C4 ○
 (6k) で右が軽くなったら、 (7l) [軽]2個+[重]2個 vs C1C2C3C4 ○


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月27日付け)

 素晴らしいです!!行末の記号 ○△□ も、なるほどとても格好いいですね、説明方法とし
て素晴らしいと思います。途中、7個vs7個まで出ていまして驚いています。じっくりと読解いた
したく存じます。

 りらひいさんによる解の一部の考え方を拝借すれば、別の方法でもイケると気がつきまし
たので、別解を投稿する準備を始めます。
(早とちりになっているかもしれませんので、今度こそ落ち着いて)


 これまで、この問題の解き方には大別して以下の二通りがありました。

1:重い貯金箱の個数そのものをカウントしていく
2:重い貯金箱の個数を剰余系でカウントしていく。mod 2 や mod 3 などで。

 そこで、上記の二通りのやり方をチャンポンで使うことも考えてみたいと思います。

 さて、15個の青い貯金箱を 4個づつの3グループ(A、B、C)と 3個の1グループ(D)とに分
割します。今まで通りです。

 最初に天秤使用回数を3回使用してA、B、Cの間での重さの大小関係を調べます。

 A vs B 、B vs C 、C vs A

 一般性を失うことなく、結果は以下の4通りのどれかになるということができます。

@ A > B > C
A A = B > C
B A > B = C
C A = B = C

(これらについて全て、重い貯金箱の個数そのものをカウントしていくやり方を取ろうとして躓
いていました。Dについても2回の天秤を使用して…しかしながらこのこと自体、既にチャンポ
ンになっています。Dについては、重い貯金箱の数について、0になるか3になるか区別をつけ
るにはまだ情報が足りていない事情もあり、ある意味で mod 3 的です。カバーするためには
更に天秤の使用回数を増やす必要があり、ここまでで計6回にも膨らんでしまいます)

 @では、Dについて調べた後であっても、幸いにも個数そのものをカウントすることで解決
できることを既に書きました。

 Cでは、やはりDについて調べれば、A=B=C=2 ですから、解決できます。

 AとBとでは、Dの内容を調べた後に、重い貯金箱の個数そのものをカウントしながら解
決する方法を…私はみつけられませんでした。

 そこで、AとBとでは、mod 2 で解決する道を調べてみました。その動機は簡単で、

A A = B > C では、A、B全体に含まれる重い貯金箱の個数は偶数、8個の貯金箱を3回
で調べられるのは効率的に思えたからでした。2個づつペアにして調べると天秤使用が4回
かかりますので。

B A > B = C でも同様です。

 mod 2 で行こうと覚悟を決めて、

A A = B > C のとき、重い貯金箱の個数の分布について、ありうるパターンは以下の通
りとなります。(Dについては調べておらず、ここまで天秤を3回使っているものとします)

ABC
440
332
331
330
221
220


 Cには貯金箱が4個含まれていて、うち、重い貯金箱が0個または1個または2個含まれて
います。3個、4個の可能性がないところに目をつけます。

 天秤を2回使用して、以下の2項について調べます。

・Cに含まれる重い貯金箱の個数。
・Cに含まれていて、重いのか軽いのかが確定している貯金箱を少なくとも1個。
【これをαと名付けておきます】

 Cに含まれる4個の貯金箱を uvwx とし、これらを2個づつに分けて、天秤で比較します。一
般性を失うことなく、uv≧wx とできます。更に、u と v とを比較します。一般性を失うことなく
u≧v とできます。

 細かく分類すると4通りにわかれます。

・uv=wx かつ u=v のとき、

 Cに含まれる重い貯金箱はありません。vをαとし、αは軽いとできます。

・uv=wx かつ u>v のとき、

 Cに含まれる重い貯金箱は2個です。vをαとし、αは軽いとできます。

・uv>wx かつ u=v のとき、

 Cに含まれる重い貯金箱は2個です。uをαとし、αは重いとできます。

・uv>wx かつ u>v のとき、

 Cに含まれる重い貯金箱は1個です。uをαとし、αは重いとできます。

 ここまで、天秤を3回使って A=B>C を得たときに、更に天秤を2回(小計5回)使うことで、
以下が得られました。すなわち。

・ABに含まれる重い貯金箱の個数は偶数。
・Cに含まれる重い貯金箱の個数の偶奇。
・軽いか重いかが判明している貯金箱αを1個。

 残り2回、総計7回の天秤使用で、15個の青い貯金箱のうち、重い貯金箱の個数の偶奇を
確定出来れば目的は達せられます。

 今まで天秤に乗せられた貯金箱はABCに含まれる12個で、まだ乗せていない貯金箱は3個
です。これを、β、γ、δとしましょう。

 6回目の天秤は、β vs γ とします。

 7回目の天秤は、δ vs α とします。

 以上で、目的は達せられました。


B A > B = C についても、Aと同様な詰め方で解決できます。

 重い←→軽い を入れ換えて、A←→C を入れ換えます。
(鏡像ですね)


 @、A、B、Cについて、解決できました。個数をキッチリ数えるやり方と、mod 2 で弾くや
り方とのチャンポンで、美しくはありませんけれども、以上となります。拙速を怖れますがイキ
のいいタイミングにてチャレンジいたしました。

 何卒御批正を頂戴いたしたく宜しくお願い申しあげます。


 DD++さんからのコメントです。(令和3年5月30日付け)

 目的のやつを載せられない問題、天秤 6 回の解です。

 8 個のうちの重い個数の偶奇を天秤 2、3 回を用いて決定する手順を、手順 X としてモ
ジュール化しておきます。

 次に示す手順により、

・2 回で偶奇が決定し、8 個を釣り合うように 4 個ずつ載せる方法の一例が得られる
・3 回で偶奇が決定し、8 個のうち 1 つを軽いものと確定できる

のいずれかの結果が得られます。
(1 回で決定した場合も説明の都合上 2 回使ったことにします)

[手順 X]

(1) 8 個を 4 枚ずつに分けて左右の皿に載せる

(2) (1)の状態で左右の皿から任意に 2 個ずつを選び、反対の皿に移す

  どちらかで釣り合えば、その時点で偶数であると決定され、手順 X を終了とします。

  どちらも傾いた場合は、

(3) どちらも下がった方に載っていたもの 1 つと、どちらも上がった方に載っていたもの 1 つ
 を (2) の状態から反対の皿に移す

  これで釣り合えば、偶数であることが決定され、しかも (3) の前に上がった側から下がっ
 た側へ移したものが軽いと確定します。

  やはり傾いた場合は、奇数であることが決定され、3 回とも上がった方に載っていたもの
 が軽いと確定します。

 これを用いて、目的のもの以外の 15 個のうちの重い個数の偶奇を決定します。

 まず、15 個のうちの 8 個を用いて [手順 X] (以後「前半」と呼称)を実行します。

 その後、8 個のうち 1 個と前半で使わなかった 7 個で再び [手順 X] (以後「後半」と呼称)
を実行します。

 ただし、前半で 3 回を要した場合、後半にも使う 1 つとして前半で軽いと確定したものを
選択することとします。

 前後半それぞれで偶奇決定までにそれぞれ何回かかったかで 3 つに場合わけします。

[1] 3+3 または 3+2 だった場合

 両方に使ったものは軽いものなので、前後半延べ 16 個の中に重いものが何個あったか、
その偶奇を考えれば解決です。

[2] 2+3 だった場合

 (6) 両方に使ったもの vs 後半で軽いと確定したものとすることで、両方に使ったものが重
  いものか軽いものかわかります。
(後半で軽いと確定したものがまさに両方に使ったものだった場合は、載せるまでもなくわ
かったことになります)

 その結果を踏まえて、前後半延べ 16 個の中に重いものが何個あったか、その偶奇を考
えれば解決です。

[3] 2+2 だった場合

 両方に使ったものを T、後半 8 個で 4 個ずつ釣り合わせるときに T と同じ皿に載せる 3
つを X, Y, Z として、

 (5) T vs X
 (6) TX vs YZ

とすれば、どちらかは必ず傾くため、T の軽重がわかります。

 その結果を踏まえて、前後半延べ 16 個の中に重いものが何個あったか、その偶奇を考
えれば解決です。

 以上、どのパターンでも天秤 6 回で 15 個のうちの重い個数の偶奇が決定されますので、
残り 1 個の軽重も判明します。


 Dengan kesaktian Indukmu さんからのコメントです。(令和3年5月30日付け)

 6 回 で mod 2 …… 、ありきたりの言葉しか言えないことが辛いです。こんなじゃあ言い
たりませんが… 、☆凄すぎますっ☆ DD++さんといい りらひいさんといい、魔物ですね…。

 私には才能がないのでじっくり地道にやるしかありません。とりあえず、重いやつをカウント
する方向で(mod 2 ではなく)6回、トライしてみます。

 ネタは、以前にも投稿した5グループをソートする方向性で、但し、貯金箱の軽重の個数に
於いて強い束縛条件がついているので、一般には天秤7回かかるソートをチューンして6回で
留める、あるいはケースによってはソートを途中でやめる等などです。



   以下、工事中!