プログラミングパズルに関心のある人は雑談しましょう！
>> ｘ＜ｎ−１の場合もありますか？ >ｎ＝９の連結成分１個の解では x = (9-1)/2 = 4 でした 全くわからなくなりました。 ｘというのは、グレープＡの要素数ですよね。成分が１個なので、Ｂは空。 残りの５個（ｎ−ｘ）は？ ｐａｎｉｃ寸前です？？？
> ｘ＜ｎ−１の場合もありますか？ ｎ＝９の連結成分１個の解では x = (9-1)/2 = 4 でした。
>> 連結なしの場合は、ｘ＝ｎとなる（正しい？） >「連結なし」というのは２成分にはわかれないという意味ですよね。 >このときはｘ＝ｎとならなくてもよいと思いますが。 x=n-1の場合がありましたね。この場合、（ｎ−１）（ｎ−２）／６が下界ですか。 ｘ＜ｎ−１の場合もありますか？
補足です。 １つの要素がすべてと直接つながっていなくても「友達の友達は友達」 的につながってさえいれば連結していますので。
> 連結なしの場合は、ｘ＝ｎとなる（正しい？） 「連結なし」というのは２成分にはわかれないという意味ですよね。 このときはｘ＝ｎとならなくてもよいと思いますが。
三吉さん、ありがとうございます。 ＞Re: 簡易ロト問題、３個から２個以上 投稿者：三吉 投稿日：03月02日(水)21時43分23秒 ＞(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。 連結なしの場合は、ｘ＝ｎとなる（正しい？）ので、ペアの数は、 ｎ（ｎ−１）／２。組の個数は、ｎ（ｎ−１）／６となる。 従って、連結なしの場合の下界は、ｎ（ｎ−１）／６。 ｎ＝９について、計算すると、９（９−１）／６＝１２となる。 しかし、以下の以前の書き込みでは、ｎ＝９では、連結成分１個も 連結成分２個も同じ位数（７）であり、上記の下界１２と矛盾する。 ＞簡易ロト問題、３個から２個以上 投稿者：三吉 投稿日：02月24日(木)14時50分48秒 ＞成分は２個でした。N=9 で出てきた解は連結成分１個なのですが ＞連結成分２個からなる別解もあるので N=6〜12 についてすべてと ＞言ってよいでしょう。 （相違点） おそらく、以下の認識が相違していると思います。 連結なしの場合、３つ組（１，２，３）に対して、これをカバーするには、 （１，２），（２，３），（３，１）の少なくとも１つのペアがあればよく、 （２，３），（３，１）のペアが存在しない解もありうる。 従って、全体としてｎＣ２個のペアを要求するのは過剰である。 一方、連結あり（２個）の場合、Ａの中の数字２個（ｕ，ｖ）とＢの中の 数字１個（ｗ）の３つ組（う，ｖ，ｗ）をカバーするためには、Ａの中の （ｕ，ｖ）がペアでなければならない。しかも、ｕ，ｖはＡの中の任意の 数字をとりうるので、Ａのすべてのペア（ｎＣ２個）が必要となる。
「生成」という言葉は ・{123} は {12,13,23} の３個のペアを生成する。（重複なし） ・{123,345} は {12,13,23,34,35,45} の６個のペアを生成する。 （重複なし） ・{123,124} は {12,13,14,23,24} の５個のペアを生成する。 （12 のペアが重複） ・{123,145,167,246,257,347,356} は {12,13,14,...略} の ２１個のペア（これは７個の数字から２個を取り出すすべての ペアになっている）を生成する。（重複なし） という使い方をしています。 組を１つ増やしても最大３個のペアしか増えませんから m個の ペアを生成する組の個数は m/3個以上ということになります。 上記の最後の例が 7C3/3(=7)個の組からちょうどその３倍の 7C3(=21)個のペアを重複なく生成している例です。（7 = 2^3 - 1）
三吉さん、解説ありがとうございます。 ＞Re: 簡易ロト問題、３個から２個以上 投稿者：三吉 投稿日：03月02日(水)21時43分23秒 ＞(2) 連結成分２個の解の場合、各成分中の任意の２個はつながっている 「つながっている」という意味を全く誤解していました。すみません。 （３つ組の数字の中に連続数が存在すると誤解） ＞(3) 下界について ＞B（要素数は n-x個）とする（ここでは A と B は連結していても ＞かまわない）。 連結成分２個の場合も、連結成分なし（１個）の場合もという意味ですね。 ＞よってこの解から生成されるペアの数は ＞x*(x-1)/2 + (n-x)(n-x-1)/2 以上である。これを x の２次式と ＞みるとこの値は n*(n-2)/4 以上である。 「生成されるペア」の定義・意味を教えてください。 例えば、以下のようなｓ１，ｓ２の場合はどうなりますか？ 1 2 3 4 5 s1 x x x s2 x x x ＞(4) n = 2^h - 1の場合は nC2/3個の組から重複なく nC2個のペアを ＞生成できるだろう。 「nC2/3個の組から重複なく nC2個のペア」？ ＞プログラムで試したところ 7,15,31,63,125 のときも重複なく生成 １２５は、１２７の誤り？ ＞(5) n = 2*(2^h - 1) のときの位数は n*(n-2)/12 だろう。 ＞> 「最小位数の解が必ず連結成分２個からなる」ことは、ｎ＝１５ ＞> まで成り立つことを確認しました。 ＞> これは、一般のｎについても成り立つのでしょうか？ ＞ 成り立つだろうと予想していたのですが高橋さんの「５個から ＞３個以上では成り立たない」という報告を見てぐらついてきました。 「５個から３個以上」の場合と「３個から２個以上の場合」は別ではないか と思っています。単なる予測ですが。。。 頭が固くてなかなか理解できず、しつこくなってしまいました。 すみませんが、よろしくお願いします。
>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 ←？ 高橋謙一郎さんの上記結果（？）をクリアしておきます。 Ｎ 上限値 構成要素 ------------------------ 15 13 [7]+[8] 16 16 [8]+[8] 17 20 [8]+[9] 18 24 [9]+[9] （構成要素） ［８］．．．８個 ---------------------- 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 s6 . . 1 . 1 1 1 1 s8 . . . 1 1 1 1 1 ［９］．．．１２個 ---------------------- s01 1 1 1 1 . . 1 . . s02 1 1 1 . . . . 1 1 s03 1 1 . . 1 1 . . 1 s04 1 . 1 . 1 1 . 1 . s05 1 . . 1 1 1 1 . . s06 1 . . 1 . . 1 1 1 s07 . 1 1 . 1 1 1 . . s08 . 1 . 1 1 1 . 1 . s09 . 1 . 1 . . 1 1 1 s10 . . 1 1 1 1 . . 1 s11 . . 1 1 . . 1 1 1 s12 . . . . 1 1 1 1 1
誤読をまねきそうな文がありましたので修正です。 > A の任意の要素 p と直接つながっている（p自身も含めた）要素数を > x とすると A の任意の要素の一つを p とする。p と直接つながっている（ p自身も含めた）要素数を x とすると q についても同様に読みかえてください。