プログラミングパズルに関心のある人は雑談しましょう！
説明つけます。間違ってないとよいですが。 (1) 連結成分３個以上の解はない 例えば解が連結成分 A,B,C からできているとして、それぞれ A,B,C から要素 p,q,r をとってくると解の中にに組 (p,q,r) と２個以上の 共通の数を持つ組はない。 (2) 連結成分２個の解の場合、各成分中の任意の２個はつながっている ２個の連結成分 A,B としそれぞれの要素数を a,b とする。a+b = n。 A の任意の要素 p と直接つながっている（p自身も含めた）要素数を x とすると x <= a。（等号は A の要素すべてと直接つながっているとき） 同様に B の任意の要素 q と直接つながっている（q自身も含めた） 要素数 y は y <= b。 p と q はつながっていないので組 (p,q,i) 1<=i<=n との共通の数を 考えると 1<=i<=n は p か q のどちらかと直接つながっていないと いけない。よって n <= x+y a+b = n, x <= a, y <= b と合わせると n <= x+y <= a+b = n。よって x = a, y = b で p,q はそれぞれ A,B の要素すべてと直接つながっていなければならない。 (3) 下界について 解において直接つながっている（自身も含めた）要素数が最小値を とる要素を p そのときの最小値を x とする。p と直接つながって いるグループを A（要素数は x個）、つながっていないグループを B（要素数は n-x個）とする（ここでは A と B は連結していても かまわない）。 B の任意の要素 q は p と直接つながっていないので上記 (2) と 同じ考え方で q と直接つながっている要素数 y は y >= n-x。 x は最小値だったので A の任意の要素についても 「直接つながっている要素数」>= x よってこの解から生成されるペアの数は x*(x-1)/2 + (n-x)(n-x-1)/2 以上である。これを x の２次式と みるとこの値は n*(n-2)/4 以上である。 無駄なく３つのペアを１つの組にまとめられたとしても 「組の個数」 >= n*(n-2)/12。 (4) n = 2^h - 1の場合は nC2/3個の組から重複なく nC2個のペアを 生成できるだろう。 プログラムで試したところ 7,15,31,63,125 のときも重複なく生成 できた。まだ証明できていないが 2^h - 1 のときは重複なく生成 できそうだ。 (5) n = 2*(2^h - 1) のときの位数は n*(n-2)/12 だろう。 n = (2^h - 1) + (2^h - 1) の２連結成分にわけた場合の組の 数は (4) を仮定すると n*(n-2)/12。これは下界と一致するので これが位数となる。 > 「最小位数の解が必ず連結成分２個からなる」ことは、ｎ＝１５ > まで成り立つことを確認しました。 > これは、一般のｎについても成り立つのでしょうか？ 成り立つだろうと予想していたのですが高橋さんの「５個から ３個以上では成り立たない」という報告を見てぐらついてきました。
deepgreenさんのプログラムはとても優秀で感激しています。 Ｎ＝１４まで最適解を見つけるなんて、私としては、もうお手上げ状態です。 何か別の切り口はないかと考えていましたが、私が考えていたことは三吉さんの考えているものと 同じものだったようです。今ごろ気づきました。ただし、私の場合は「５個から３個以上」のこと しか考えていなかったので「３個から２個以上」の三吉さんの解析結果を、「５個から３個以上」 の場合に適用してみた結果として報告しておきます。 結果は以下の通りで、塗り壁さんが最初に報告してくれたものと一致しています。ただし、N=13の 最適解は９ではなく８なので「最小位数の解が必ず連結成分２個からなる」という三吉さんの仮説 には、少なくとも「５個から３個以上」の場合には例外があることになります。 「N=13の最適解８には連結成分２個からなるものがひとつも存在しない」という言い方も出来ます。 N=10=5+5 -> 1+ 1= 2 N=11=5+6 -> 1+ 4= 5 N=12=5+7 -> 1+ 5= 6 N=13=6+7 -> 4+ 5= 9 ←最適解ではない N=14=7+7 -> 5+ 5=10 N=15=7+8 -> 5+ 8=13 ←？ N=16=8+8 -> 8+ 8=16 ←？ N=17=8+9 -> 8+12=20 ←？ N=18=9+9 ->12+12=24 ←？ yahoo掲示板で議論されていたというのは、きっとこのことだったのでしょう。例外が存在する以上 数学的な証明は有り得ないでしょうから、「どういう場合に例外になるのか」を数学的に明示でき れば大きな進歩になると考えています。また、もうひとひねりすれば例外と思えたものも吸収できる もっと突っ込んだ理論があるのかも知れません。 とろこで、私も三吉さんから、もう少し詳しい説明をしてほしいと思っています。あんな簡単な計算式 で近似値を得られるのには理由があるのでしょうから。よろしくお願いします。 【補足説明（５個から３個以上）】 Ｎを２つのグループに分割し、それぞれをＡグループ、Ｂグループとします。Ａグループから 任意の３列を選んだとき、その列を含むいづれかの行に３つ以上の１がある行が存在し、また、 Ｂグループから任意の３列を選んだときも、その列を含むいづれかの行に３つ以上の１があると します。このとき、列全体（Ｎ）から任意の５列を選んだとき、いづれかの行に３つ以上の１を 持つ行が必ず存在します。何故ならＡかＢのどちらかで３つ以上の列が選ばれるからです。
三吉さん、こんばんは。deepgreenです。 三吉さんの投稿を興味深く拝見しております。 いろいろ考えてみましたが、解らないことが多いので、ちょっと教えてください。 ＞簡易ロト問題、３個から２個以上 投稿者：三吉 投稿日：02月24日(木)14時50分48秒 ＞また「連結成分３個以上の解はありえない」「連結成分２個の解の ＞場合、各成分中の任意の２個はつながっていなければならない」が ＞成り立つこともわかりました。 「連結成分２個の解の場合、各成分中の任意の２個はつながっていなければならない」 というのは、ｎ＜＝７の場合でしょうか？ （ｎ＝９の時は、成り立たないような気がします） ＞仮に最小位数の解が必ず連結成分２個からなるのであれば問題は ＞nC2 が最小何個の３個組数から生成できるかが問題になってきます。 「最小位数の解が必ず連結成分２個からなる」ことは、ｎ＝１５まで成り立つことを 確認しました。これは、一般のｎについても成り立つのでしょうか？ ＞Re: 簡易ロト問題、３個から２個以上 投稿者：三吉 投稿日：03月01日(火)00時32分00秒 ＞「３個から２個以上」の方ですが、まあまあの下界がわかりました。 ＞n が偶数のとき n*(n-2)/12 ＞n が奇数のとき (n-1)^2/12 前回投稿された「最小位数の解が必ず連結成分２個からなる」ことを前提に考えると なんとなく（近似値としては）解るのですが、一般的に成り立つ命題でしょうか？ ＞n = 2^m - 2 の形に書ける偶数のとき、位数がちょうど上記の下界 ＞n*(n-2)/12 に一致するようです。 ＞（例えば n=6 のとき 6*(6-2)/12 = 2） そのような解が存在する保証は、あるのでしょうか？ 非常に重要な面白い結果と思っています。 解りやすい解説をしていただけると助かります。 よろしくお願いします。
「３個から２個以上」の方ですが、まあまあの下界がわかりました。 n が偶数のとき n*(n-2)/12 n が奇数のとき (n-1)^2/12 n = 2^m - 2 の形に書ける偶数のとき、位数がちょうど上記の下界 n*(n-2)/12 に一致するようです。 （例えば n=6 のとき 6*(6-2)/12 = 2）
どうもご無沙汰しております。 ホームページを移転したのですが、Ｃマガ電脳クラブからもう卒業してしまっているので、 連絡するかどうか迷っていたのですが、高橋さんのページからまだリンクが残されていたので、お知らせします。時間あるときにリンク先を修正していただけるとうれしいです。 最近はCマガでちょこちょこ記事を書くことがあるので、いつかパズルのことも 書いてみたいと思います。http://hp.vector.co.jp/authors/VA013320/
こんばんは、deepgreenです。 あれから、いろいろ高速化をやってみましたが、ことごとく失敗しました。 残ったのは、つまらないプログラミング上のの改善しか有りません。 何とかＮ＝１４の結果をだしました。 「５個の数字から３個以上」の問題で、Ｎ＝１４の最適解は、１０個でした。 以下は、実行結果のログです。 ==== (10, 2, 1) ==== Wed Feb 23 13:20:45 2005 ==== Congratulation !!! ==== Wed Feb 23 13:20:45 2005 1 1 1 1 1 . . . . . . . . . . 1 1 1 1 1 ==== (11, 3, 1) ==== Wed Feb 23 13:20:45 2005 ==== (11, 4, 1) ==== Wed Feb 23 13:20:45 2005 ==== (11, 5, 2) ==== Wed Feb 23 13:20:45 2005 ==== Congratulation !!! ==== Wed Feb 23 13:20:45 2005 1 1 1 1 1 . . . . . . 1 1 1 1 . . . . 1 . . . . . . 1 1 . . 1 1 1 . . . . . 1 1 1 . 1 1 . . . . . . 1 1 1 1 1 ==== (12, 5, 2) ==== Wed Feb 23 13:20:45 2005 ==== (12, 5, 1) ==== Wed Feb 23 13:20:45 2005 ==== (12, 6, 2) ==== Wed Feb 23 13:20:45 2005 ==== Congratulation !!! ==== Wed Feb 23 13:20:45 2005 1 1 1 1 1 . . . . . . . 1 1 1 . . . 1 1 . . . . . . . 1 1 1 1 1 . . . . . . . . . 1 . . 1 1 1 1 . . . . . . 1 . 1 1 1 1 . . . . . . . 1 1 1 1 1 ==== (13, 6, 2) ==== Wed Feb 23 13:20:45 2005 ==== (13, 6, 1) ==== Wed Feb 23 13:20:45 2005 ==== (13, 7, 2) ==== Wed Feb 23 13:20:46 2005 ==== (13, 7, 1) ==== Wed Feb 23 13:21:26 2005 ==== (13, 8, 3) ==== Wed Feb 23 13:21:56 2005 ==== Congratulation !!! ==== Wed Feb 23 13:21:57 2005 1 1 1 1 1 . . . . . . . . 1 1 1 . . 1 . . . . . . 1 1 1 1 . . . 1 1 . . . . . . . . 1 1 1 . 1 1 . . . . . . . 1 1 . 1 . 1 . . . 1 . . . . . 1 1 . . 1 1 1 . . . . . . . . 1 . 1 1 1 1 . . . . . . . . 1 1 1 1 1 ==== (14, 8, 2) ==== Wed Feb 23 13:21:57 2005 ==== (14, 8, 1) ==== Wed Feb 23 13:31:39 2005 ==== (14, 9, 3) ==== Wed Feb 23 13:36:47 2005 ==== (14, 9, 2) ==== Wed Feb 23 14:35:09 2005 ==== (14, 9, 1) ==== Thu Feb 24 13:04:59 2005 ==== (14,10, 3) ==== Thu Feb 24 20:56:06 2005 ==== Congratulation !!! ==== Thu Feb 24 23:14:49 2005 1 1 1 . . . 1 . . . . 1 . . 1 1 1 . . . . 1 . . 1 . . . 1 1 1 . . . . . 1 1 . . . . . . . 1 1 1 1 . . . 1 . . . . . . 1 1 1 . 1 . . . 1 . . . . . 1 1 1 . . . . . . 1 1 . . . . . . 1 1 1 1 . . 1 . . . . . . . 1 1 1 1 . . . 1 . . . . . . . . 1 . 1 1 1 1 . . . . . . . . . 1 1 1 1 1 ==== (15,10, 3) ==== Thu Feb 24 23:14:49 2005
N=7 のときの表がずれて表示されるので書き直します。 1 2 3 4 5 6 7 5 3 2 2 1 1 1 6 4 4 3 6 5 5 7 _ _ _ 7 7 6
「３個から２個以上」について高橋さんの miniloto.c が出力する 解をみていていくつかの事実に気づきました。 例えば N=7 の解 {567,234,167,157} について １行目に１〜７、その下につながっている数字を並べると 1 2 3 4 5 6 7 5 3 2 2 1 1 1 6 4 4 3 6 5 5 7 7 7 6 234 と 1567 がそれぞれ連結していてその２成分から構成されています。 （以下これを 7=3+4 のように書きます） N=6〜12（ただし9を除く） について調べてみましたがすべて連結 成分は２個でした。N=9 で出てきた解は連結成分１個なのですが 連結成分２個からなる別解もあるので N=6〜12 についてすべてと 言ってよいでしょう。 また「連結成分３個以上の解はありえない」「連結成分２個の解の 場合、各成分中の任意の２個はつながっていなければならない」が 成り立つこともわかりました。 各Ｎについて２成分を書くと N=6 = 3+3 N=7 = 3+4 N=8 = 3+5 N=9 = 4+5 N=10 = 5+5 N=11 = 5+6 N=12 = 5+7 N=8 が 4+4 でなくて 3+5 になる理由ですが、４個から２個とる 組み合わせ 4C2 を生成する３個組の最小組数は３個（例えば {123,234,134}）のなので 8=4+4 から作られる解の位数は ３個＋３個で６個、一方 3C2 を生成する最小組数は１個、 5C2 を生成する最小組数は４個なので 8=3+5 から作られる解の 位数は１個＋４個で５個と後者の方が小さくなります。 N=12 についても同様で 12=6+6 から作られる解の位数は ６個＋６個で１２個、一方 12=5+7 から作られる解の位数は ４個＋７個で１１個と後者の方が小さくなります。 仮に最小位数の解が必ず連結成分２個からなるのであれば問題は nC2 が最小何個の３個組数から生成できるかが問題になってきます。 n=3〜7 の最小生成組数を並べると 3C2 <- 1 4C2 <- 3 5C2 <- 4 6C2 <- 6 7C2 <- 7 n(n-1)/6 <= 「nC2の最小生成組数」<= n(n-1)/2 上界はもっと抑えられるでしょう。 ｎ＝７の場合は７個の組から重複なく 7C2 を生成できてますね。
高橋謙一郎さん、今晩は。 ＞ところで、塗り壁さんにくどいような質問で申し訳ありませんが、以下の結果は最適解 ＞と断定されたものなのでしょうか、それとも見つかった解の最小記録なのでしょうか。 最適解だという記述を私は見ていません。が、私が見落とした可能性 はあるかも知れません。 ところで、最適解はたくさんあります（数百万、あるいは数百億かもしれません） のでそれらを特徴付けるために、下記の定義を置くことにします。 （以下、「５個の数字から３個以上」で、Ｎが１０以上１４以下の場合とします） 標準的な解とは二つの組＜１,２,３,４，５＞＜６，７，８，９，１０＞ を含む最適な解のこととする。 問題 与えられたＮに対し標準的な解は存在するか。存在するとき、 その個数はいくつか。 プログラムである程度の結果を出されたようですけど、上記の問題に関する結果が 得られていれば教えてもらえますか。 ＜１,２,３,４，５＞だけだったら、それを含む最適解があるのはすぐわかりますし、 標準的な解の場合ももしかすると存在は当たり前かもしれないですね。 なお、プログラムは参考にさせてもらいます。
deepgreenの探索リ論理は、以下の順で幅優先探索を行うものです。 （小さいものから順にみつけていくだけ） ↓ 解が見つかったとき → 解が見つからないとき (10,2) ↓ (11,2)→(11,3)→(11,4)→(11,5) ↓ (12,5)→(12,6) ↓ (13,6)→(13,7)→(13,8) ↓ ここでとまっている ------> (14,8) ＊＊（１４，８）の探索は、もっともっと、高速化しないと無理ですね。 □内部の（Ｎ，Ｍ）の探索論理 以下のような解の性質から標準形に絞った探索をします。 （高橋謙一郎さんが対称性を考慮したのと同じと思います） ａ．任意の列（ｎｉ，ｎｊ）を入れ換えても、本質的には同じ ｂ．任意の行（ｓｉ，ｓｊ）を入れ換えても、本質的には同じ 従って、以下の条件を満たす解を標準形とする。 （１） 各列の順序：ｉ＜ｊのとき、数字ｉの出現頻度＜＝数字ｊの出現頻度 （２） 各行の順序：ｉ＜ｊのとき、ｓｉ＞ｓｊ（数字の１が最上位桁とする） （１３，８）の標準形の例 1 2 3 4 5 6 7 8 9 0 1 2 3 ------------------------- s1 1 1 1 1 1 . . . . . . . . s2 1 1 1 . . 1 1 . . . . . . s3 . . . 1 1 1 . . . . . 1 1 s4 . . . 1 1 . 1 . . 1 1 . . s5 . . . . . 1 . 1 1 1 1 . . s6 . . . . . . 1 1 1 . . 1 1 s7 . . . . . . . 1 . 1 1 1 1 s8 . . . . . . . . 1 1 1 1 1 探索は、まず、数字１をｓ１〜ｓ８に割り当てる。 次に、数字２をｓ１〜ｓ８に割り当てる。 ．．． 最後に、数字１３をｓ１〜ｓ８を割り当てる。 という順に行っていく。（通常は、ｓ１，ｓ２，．．と割り当てていくでしょうが） □枝刈りの論理 １）標準形に合致しているかどうかの検査 ２）５／３のチェック（これを入れるため、数字を割り当てていく方式を採用） 数字の５までを割り当てると、[1,2,3,4,5]の中で３つの数字をもつｓｋ が存在しなけれなならない。（この場合はｓ１，ｓ２ともＯＫ） 数字ｎまで割り当てると、[1,2,3,...,n]のなかの任意５つの数字について 同様のチェックを行うことができる。 ３）割り当てた数字の数と残りの数字による過不足チェック 例えば、以下の例のように数字９を１ヶしか割り当てないと、40-(9+28)＝３ 個の不足となるので、このような解は存在しないと判明する。 （この場合、数字９はすくなくとも４個必要） 割り当てる数字の数は、全体では８ｘ５＝４０ 割り当て済みの数字の数は、 ９ 今後割り当て可能な数字の数は、７ｘ４＝２８ 1 2 3 4 5 6 7 8 9 0 1 2 3 ------------------------- s1 1 1 1 1 1 . . . . . . . . s2 . . . . . 1 1 1 1 . . . . s3 . . . . . . . . . . . . . s4 . . . . . . . . . . . . . s5 . . . . . . . . . . . . . s6 . . . . . . . . . . . . . s7 . . . . . . . . . . . . . s8 . . . . . . . . . . . . .