お気づきの点や感想要望などなんでもＯＫ！
見事な解析結果だと思います。こう言う事を思い付ける
deepgreenさんがとても羨ましいです。種明かしを見せら
れると「そうか」となるのですが、そういう事がなかなか
思い付かないんですよね。(驚きです)
「秤の問題」は確かに有名なパズルですね。それにしても
１３個を３回でとは最初に思い付いた人に先ず敬意を評し
たいです。私には解けないですが、この問題の答えなら、
(３＾ｎ - 1)／２ 個
になるそうです。何故そうなるかは分かりませんし、具体
的に４０個を４回で調べろと言われてもどうやったら良い
のか？？？(答えの式しか書いてないものを見ただけです)
deepgreen さん、こんばんは。
０解から最長手数解を求める方法には驚きました。
力任せに探索するしか方法はない、と思い込んでいたので、
目からウロコが落ちました（笑）。
deepgreen さんは凄いです。
ライツアウトのような一見単純なパズルに、これだけの理論的背景が潜んでいようとは。
これらの情報は、ライツアウトの問題を作る際にもかなり有用だと思います。
（どうやって解答可能解の存在範囲内でデザイン的に優れた問題を作るか、もしくは如何にして
手数のかかる難しい問題を作るか…優れた問題作成がかなり楽になりますよね。）
さて、今回は題名の通り、秤を使った問題について皆さんのお知恵を拝借したいと思いまして。
皆さんはこのような問題はご存じでしょうか？
『ここに１３個の、外見上見分けのつかない球が存在する。
そのうちの１個のみが、他の球と重さが異なっている。（他の球より重いか軽いかは不明）
この他と重さが異なる球を、秤を使って探し当てる方法を述べよ。
なお、秤は３回までしか使用できないものとする。』
この問題の解法自体は、試行錯誤によって求めることが出来ました。
しかし、秤の使用可能回数をｎとした場合、玉の総数は何個の場合まで判別可能でしょう？
もし、一つの玉の重さが他より重い（軽い）と最初から分かっている場合なら、秤の使用可能
回数をｎとして、（３＾ｎ）個の球を判別できるのは自明と思われます。
しかし、今回のケースでは本当に一般解は求められるのでしょうか？
特殊な解法を用いれば手数を短縮できる可能性があるため、帰納法が使えるかどうか不明です。
手始めに、ｎ＝４での最大識別可能個数を求めようとして挫折しました…。
そういうわけで、よければ皆さんも考えてみて下さいませんか？
追記：
この問題には更にバリエーションがあります。
本当に他と重さの異なる球が混じっているのかどうか不明という場合です。
この場合はｎ＝３の時の最大識別個数が１２個となるようです。
こちらのケースの一般解についても、お知恵を拝借したいのですが…。
０解から最長手数解を求める方法です。(長文失礼）
ライツアウトの解の存在条件式のパターンと０解のパターンが一致することが
前提となります。（私のＨＰを参照してください）
５ｘ５のライツアウトの０解は、以下の３パターンである。
(p1) -BCD-F-H-JKL-NOP-R-T-VWX-
(p2) A-C-EF-H-J-----P-R-TU-W-Y
(p3) AB-DE-----KL-NO-----UV-XY
ただし、p1,p2,p3は互いに独立ではなく、他の2つのＸＯＲにより求めることができる。
ｐｕｓｈ位置Ａ〜Ｙを以下のように分類する。
（１）p1,p2,p3のいずれにもでてこないもの ：G,I,M,Q,Sの５個
（２）p1,p2に共通にでてくるもの ：C,F,H,J,P,R,T,Wの８個
（３）p2,p3に共通にでてくるもの ：A,E,U,Yの４個
（４）p3,p1に共通にでてくるもの ：B,D,K,L,N,O,V,Xの８個
最長手数の解を考えると、
（１）は無条件に１にすればよい（∵解の存在には関係ない）
（２）は、丁度半分を1にすることができる。半分を超えているものは０解
とのＸＯＲにより半分未満の解が存在することになるので、丁度半分
が最大となる。
（３），（４）も同様である。
なお、(2),(3),(4)を丁度半分づつ１にしたものは、解の存在条件をみたして
いることは明らかである。
よって、最長手数は、５＋８／２＋４／２＋８／２＝１５となる。
次に、最長手数解の個数について考える。
（２）の候補の選び方は、８個から４個選ぶ組み合わせ＝8！／４！＝７０
（３），（４）もそれぞれ、４！／２！，８！／４！となる。
全体としては ６ｘ７０ｘ７０＝２９４００パターン
これは、ｐｕｓｈパターンの数であるから、問題面の数としては、この１／４
になる。
２９４００／４＝７３５０通り
これは、広井さんの探索結果と一致する。
参考までに、最長手数解を示す。
（ｐｕｓｈパターン） （問題面）
１１１１１ １０００１
１１１１１ ０１１０１
１１１００ １１１１１
０１０１０ ００１１１
０００００ ０１０１０
高橋さん、こんばんは。広井です。
高橋さんのＨＰからリンクしていただけるとのこと、ありがとうございます。
「実践アルゴリズム戦略」にはよくお世話になりました。単行本にはなっていない
ようなので、手に入れるのは難しいかもしれません。昔のＣマガジンは、このような
アルゴリズムの解説記事が連載されていて、とても参考になりました。
ライトが全部点灯しているパターンが一番難しい問題というのは、ちょっとがっかりな
結果ですね。また、最長手数のパターンは少ないと思っていたので、7350 通りもある
とは意外な結果でした。
合計数に間違いがないことを確認した時は、本当にほっとしました（笑）。
こちらこそ、よろしくお願いいたします。
広井さん、はじめまして。
ＨＰ拝見させて頂きました。パズル問題をプログラミングで解くことを
扱ったＨＰはとても少ないので貴重な存在だと思います。私のＨＰから
もリンクさせて下さい。(2〜3日後になりそうですが)
広井さんのパズル関係のページを見ていると、参考文献にＣマガジンの
「実践アルゴリズム戦略 解法のテクニック」が目に付きます。これは
Ｃマガ電脳クラブに挑戦していた時に投稿者の参考文献としてときどき
目にしたもので直接的にその記事を読んだことは無いのですが、かなり
広い影響力のある記事だったようですね。
実は最近、私も某雑誌から執筆依頼があってパズルを解くアルゴリズム
の入門編を書かせて頂いたのですが、元ネタを辿っていくとどうやら
「実践アルゴリズム戦略」に行き着くものが多くあるようです。読んだ
ことのない記事であっても参考文献として載せない訳にはいかない重要
な存在なのでしょう。−−急いで原稿の訂正をお願いしなくては！−−
ただし私の書いた原稿が本当に掲載されるかどうかは今のところ全く
不明です。(内容は私のＨＰにあるものとほとんど同じです)
ところで広井さんのライツアウトの解析結果はとても面白いです。
最長手数が15手というのは貴重な情報ですね。ただ、ライトが全部点灯
しているパターンも最長手数のパターンに含まれるというのは意外性の
無いちょっと残念な結果だったかな。解の存在するパターンは理論的に
2の23乗通りなので広井さんの結果に「0手のパターン数=1」というのを
追加すると合計数が2の23乗=8,388,608個になるのでホッとする結果で
もあるようです。
これからも宜しくお願いします。
はじめまして、広井と申します。
高橋さんのパズルゲームとパズル解法プログラムは素晴らしいですね。
私のホームページ M.Hiroi's Home Page から高橋さんのコンピュータ＆パズルへ
リンクを張らせていただきました。よろしくお願いします。
ライツアウトの考察は丁寧な説明でよくわかりました。
それにしても、連立方程式によるライツアウトの解法には驚きました。
ライツアウトの解法は私も挑戦したことがあります。解くだけではなく、
最長手数（一番難しい問題）を求めてみました。
1手のパターン数 25
2手のパターン数 300
3手のパターン数 2300
4手のパターン数 12650
5手のパターン数 53130
6手のパターン数 176176
7手のパターン数 467104
8手のパターン数 982335
9手のパターン数 1596279
10手のパターン数 1935294
11手のパターン数 1684446
12手のパターン数 1004934
13手のパターン数 383670
14手のパターン数 82614
15手のパターン数 7350
ライツアウトは最長でも 15 手で解けることがわかりました。
たとえば、ライトが全部点灯しているパターンが 15 手かかります。
長い書き込みで失礼しました。これからもよろしくお願いします。
高橋さん、ありがとうございます。
そっくり写したのがまちがいでした。はずかしいので、早速修正しました。
別件に浮気している間に高橋の数は総て解決してしまったんですね。
deepgreenさんは解析が早いなあ。ところでtypeBは以前に書いた通り、
typeB: (1,4,6,7) x 1 + (3,6) x m
となります。最初の私の間違いが跡を引いているようですね。
タイプ２の「高橋の数」を求めるアルゴリズム：Ａ２を改造して、タイプ１の
「高橋の数」の記述式を求めてみました。
type A〜D は共通で、type F〜H はタイプ１固有です。
【高橋の数の記述式】
type A ：(4,5,9) x n
type B ：(1,4,6,7) x n + (3,6) x m
type C ：(1,2,3,4,5,6,7,8,9) x n + (3,6) x m
type D ：(1,2,3,4,5,6,7,8,9) x n
+ (2,2,2,3,4,4,5,5,6,7,7,7,9,9) x m
ただし、m >= 0, n >= 1 の整数
<<タイプ１の場合>>
type F : (0,2,5,6,6,8) x 1 + (3,6) x a
ただし、a >= 0 の整数
type G : (0,2,2,4,4,5,6,7,7,8) x 1 + (3,6) x a
ただし、a >= 0 の整数
type H : (1,2,4,5,7,8) x m
+ (0,9) x n
+ (3,6) x a
+ (1,2,3,4,5,6,7,8,9) x b
ただし、m >= 1, n >= 1, a >= 0, b >= 1 の整数
<<タイプ２の場合>> 参考
type E : (1,2,4,5,7,8) x m
+ (0,9) x n
+ (3,6) x a
+ (1,2,3,4,5,6,7,8,9) x b
ただし、m >= 1, n >= 1, a >= 0, b >= 0 の整数
type E と type H は非常によく似ています。
これでようやく「高橋の数」を終わりにできました。