プログラミングパズルに関心のある人は雑談しましょう！
プログラミングパズルではなくキュービックパズルのやり方ってありますか?
先月から「５個から３以上」の問題を考えていますが全然進展がありません。 ところで n = 1,3 (mod 6) のときシュタイナーのトリプル系が存在すると いう証明ですが、たまたま図書館でみつけた 「現代組合せ論」 Peter Frankl, 秋山 仁 著 http://www.amazon.co.jp/exec/obidos/ASIN/4320013964/qid=1115794406/sr=1-84/ref=sr_1_0_84/250-1251457-2807414 の第3章「デザイン」3.3「シュタイナー系」に証明が書いてありました。 まだちゃんと読んでいませんが帰納法を使った構成的な証明のようです。
> A Steiner triple system of order v exists iff v = 1,3 (mod 6) を使って「３個から２個以上」の問題で n が偶数の場合の位数を 整理してみました。 位数の下界は n(n-2)/12 で評価。 位数の上界は n = 12k のとき n = 6(k-1)+3 + 6k+3 に分割 n = 12k + 2 のとき n = 6k+1 + 6k+1 に分割 n = 12k + 4 のとき n = 6k+1 + 6k+3 に分割 n = 12k + 6 のとき n = 6k+3 + 6k+3 に分割 n = 12k + 8 のとき n = 6k+1 + 6(k+1)+1 に分割 n = 12k + 10 のとき n = 6k+3 + 6(k+1)+1 に分割 して評価。 n = 12k のとき 位数 = n(n-2)/12 + α 0 <= α <= 3 n = 12k + 2 のとき 位数 = n(n-2)/12 n = 12k + 4 のとき 位数 = (n(n-2) + 4)/12 n = 12k + 6 のとき 位数 = n(n-2)/12 n = 12k + 8 のとき 位数 = n(n-2)/12 + α 0 <= α <= 3 n = 12k + 10 のとき 位数 = (n(n-2) + 4)/12 + α 0 <= α <= 1
私もざっと見ただけなのですが 3(mod 6) の部分だけみたいですね。 ネットで証明を探してみたのですが but as this is rather long and messy we will no present it という感じみたいです。 ただ、 http://www.kalva.demon.co.uk/balkan/bsoln/bsol894.html に証明のあらすじが書いてあるようです。英語なのでちゃんと 読んでいませんが。
三吉さん、貴重な情報有難うございます。 >http://www.sci.osaka-cu.ac.jp/~nonomura/wakate/1999/pdf/1999_ohta.pdf >に証明が載っているようです。 難しくてよくわかりませんが、Theorem 1.3.1 は、ｎ＝６ｋ＋１については証明 していないようですが？ theorem 1.3.4 は、ｎ＝６ｋ＋１が素数の場合なので、合成数の場合は？ですね。
> 証明知りたいですね。 http://www.sci.osaka-cu.ac.jp/~nonomura/wakate/1999/pdf/1999_ohta.pdf に証明が載っているようです。
> インターネットで検索した結果、このカークマンの問題は、 > ｎ＝６ｋ＋３の場合も解が存在するとの記述がありました。 http://mathworld.wolfram.com/SteinerTripleSystem.html を見たら 私が考えていた問題は Steiner Triple System という問題でした。 Let X be a set of elements together with a set B of 3-subset (triples) of X such that every 2-subset of X occurs in exactly one triple of B. Then B is called a Steiner triple system and is a special case of a Steiner system with t = 2 and k = 3. A Steiner triple system of order v exists iff v = 1,3 (mod 6) (Kirkman 1847). Kirkman, T. P. "On a Problem in Combinatorics." Cambridge Dublin Math. J. 2, 191-204, 1847 とありますので n = 1,3 (mod 6) のとき、かつそのときにのみ 完全解が存在する、ということですね。
> しかし、これ以外にも完全解の存在するｎは、沢山存在するようです。 ... > （ケース２）ｎ＝６ｋ＋３（ｋ＝1,2,3,...）の場合、完全解が存在する > ｢カークマンの女学生の問題｣の解は、ｋ＝２の完全解になります。 あああ、言われてみればまさに「カークマンの女学生の問題」でした。 情報だけ知っていて身についていない典型だ・・・ orz ということは、上記のとおりとすると 「３個から２個以上」のミニロト問題では n = 2(6k+1) と n = 2(6k+3) のときの位数は n(n-2)/12 ということになりますか。 それ以外の場合でも n(n-2)/12 にかなり近いことが期待できますね。 n^2 の係数は 1/12 で確定、でよいのかな。 > （残念ながら、その証明はみあたりませんでしたが、） 証明知りたいですね。
（単なる推測ですが）
nＣ2個のペアを生成する組の個数の最小値がその下界（＝ｎ（ｎ−１）／６）と
一致する場合、その解を完全解と呼ぶことにする。ｎ＝２＾ｍ−１の場合は、
三吉さんによって、完全解が存在することが示されました。
しかし、これ以外にも完全解の存在するｎは、沢山存在するようです。
（ケース１）ｎ＝６ｋ＋１（ｋ＝1,2,3,...）の場合、完全解が存在する
ｋ＝１〜２０までは解を求めました。任意のｋについて完全解が
存在することは予想できますが、証明はできていません。
（ケース２）ｎ＝６ｋ＋３（ｋ＝1,2,3,...）の場合、完全解が存在する
｢カークマンの女学生の問題｣の解は、ｋ＝２の完全解になります。
インターネットで検索した結果、このカークマンの問題は、
ｎ＝６ｋ＋３の場合も解が存在するとの記述がありました。
（残念ながら、その証明はみあたりませんでしたが、）
上記の予想を基に、一般のｎについての上界を求めると、
nＣ2個のペアを生成する組の個数の最小値 ＜＝ ｓ（ｓ−１）／６
ただし、ｓは、ｎを６ｋ＋１，６ｋ＋３の近い方に切り上げたもの
ｅｘ ｎ＝１０ −−＞ ｓ＝１３
ｎ＝１５ −−＞ ｓ＝１５
ｎ＝１６ −−＞ ｓ＝１９
試算例
ｎ ｓ 下界 上界 上界／上界
----------------------------
100 (103) [1650-1751] 1.06
101 (103) [1683-1751] 1.04
102 (103) [1717-1751] 1.02
103 (103) [1751-1751] 1.00
104 (105) [1785-1820] 1.02
105 (105) [1820-1820] 1.00
106 (109) [1855-1962] 1.06
107 (109) [1890-1962] 1.04
108 (109) [1926-1962] 1.02
109 (109) [1962-1962] 1.00
110 (111) [1998-2035] 1.02
111 (111) [2035-2035] 1.00
> 上界の分母の４をどこまで大きくできるか興味があります。 n^2 の係数について近似（と勝手に思っている）解で 8〜15, 16〜31, 32〜63, 64〜127, 128〜255, 255〜511, 512〜1023, 1024〜2047 の範囲を調べてみたのですが、n が大きくなってくると n = 2^m - 1 で係数 1/6 をとり、そこから小刻みに揺れながらも だんだん係数は大きくなっていき n = 2^m * 1.33... 辺りで最大値 1/5.33... をとった後、だんだん小さくなっていき n = 2*2^m - 1 でまた 1/6 に戻る という傾向があるようにみえます。 なんの根拠もありませんが 5.33... = 16/3 1.33... = 4/3 かなと考えています。