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枚だけを乗せてみる
 (釣り合えば正直確定、傾けば嘘つき確定)

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



   以下、工事中!