『部分集合』解答


◆山梨県 Footmark さんからの解答。

任意の2つの部分集合S(i),S(j)における共通要素の個数f(i,j)の、最大値Mを最小にするには、
0〜9の10要素の内の5要素がS(1)〜S(10)の各部分集合に均等に偏るようにすればよい。

図はその1例である。

図からも明らかなように、このとき M=4。
よって、求めるMの最小値=4。


◆愛知県 Y.M.Ojisan さんからの解答。

【解答】 答え 3

たとえば下図 A〜Jグループにする。
全てAのシフトであるので、Aに対する∩要素のみをチェックしてある。

 

【証明】

M=2では不可能であることを示します。

【おおよその証明】

全部で10×5個の要素が必要で、各数字を一様に使用すると、各数字5個ずつの使用である。
するとグループ間で重複するものを線で結んだ結合線の数は
10×5C2=100である。

一方、最大が2であるとすると、全体で許容される結合線の数はグループ間の組み合わせ数×2 であり
10C2×2=90<100である。
すなわち結合線が不足である。
よってM=2は不可能である。

【一様な使用が最小の証明】

50個を 50=p0+p1+p2〜p9に分けたとき 
結合線の数の合計Σi2を最小にするpi

Σi2=Σpi2/2−25 を最小にするpiである。

10Σpi2=(Σpi)2+Σ(pi−pj)2≧502

よりpiが同じ値である時最小であり、pi=5が最小値を与える。

【感想】

私には新鮮で興味深い問題と思いました。


◆山梨県 Footmark さんからのコメント。

なるほど、最小値は3でも可能でしたか。
ただ均等に偏っただけではダメでしたね。(^^;

この問題はとても面白いですね。
明らかに、1010101010を1つずつずらしたのでは5になってしまいます。
また、私のように単純に1111100000を1つずつずらしたのでは4になってしまいます。
試しに、1101011000を1つずつずらしてみると、これもやっぱり4でした。

どうして、Y.M.Ojisan さんが示したように、1101101000を1つずつずらすと3になるのでしょう?
そこで追加問題。


◆愛知県 Y.M.Ojisan さんからの解答。

【追加問題1】

直接の解答では無いですが、作り方をいくつか。

【M1】

5個ずつ2グループ(下図 紫と黄)にわけ、3個と2個を分布させます。
CC=10であり、いずれも丁度10とおりあります。
紫3個のグループでは最大2個しか重複せず、黄2個のグループでは最大1個です。
従って両方で最大3個です。
紫グループと黄グループの組み合わせだけでも 10!とおりになります。

【M2】

奇数か偶数かで5個ずつ2グループ(下図 紫と黄)にわけ、Aにおいてそれぞれ4個と1個を配置し、以後1づつシフトさせます。
奇数シフト差の場合、4個と1個のグループ間では最大1個しか重複しませんから、両方で最大2個です。
一方偶数シフト差の場合、4個グループ同士では最大3個重複し、1個グループ同士では重複しないので合計最大3個になります。

【M3】

M2と同様、奇数か偶数かで5個ずつ2グループ(下図 紫と黄)にわけ、Aにおいてそれぞれ3個と2個を配置し、以後1づつシフトさせます。
奇数シフト差の場合、3個と2個のグループ間では最大2個重複するので、両方で最大4個の可能性があり、さらに条件が必要です。
一方偶数シフト差の場合、3個グループ同士では最大2個重複し、2個グループ同士では1個が重複なので合計最大3個になります。

条件としては、3個の方を固定しておいて、2個のほうを前後に奇数シフトして得られた下図(1,3,5,7,9欄)において、重複が4個になる2,1,1を選ぶ、ないし2,2を含む組み合わせである(1,3,9)と(5,7,X)を除く6通りの選び方がOKとなります。

なお、偶数グループを0と4にとるケースも同様です。

【追加問題2】 30個

実例としては 次のA1、A2,A3およびそれらを回転シフトしたもの3×10個。
なお、これらはM2,M3の方法の援用で得たものです。

【30が最大の証明】

(1) ある3個が互いに重複するグループの数は最大3個です。
なぜなら残り2個を7種の中から重複せず選択しなければならず、
7/2=3あまり1だからです。

(2) そういう数字3個の組み合わせは 10=120とおりです。

(3) そういう3個の組み合わせ中の結合線の数は3×3=9ですから、
120×9=1080以上の結合線は存在しえません。

(4) 一方、問題1に示したように結合線の数が最小となる
おのおのn/2前後個ずつ用いた場合の結合線の数は
 5[n/2][(n-1)/2]です。

(5) 計算すると n=30の時1050<1080で
n=31のとき1125>1080です。
よって30が最大です。

【追加問題3】 5個

【6個以上不可能の証明】

6個でできないものはそれ以上ではできない。
従って、6個では不可能であることを示す。

(1) ある3個が互いに重複するグループの数は最大2個です。
なぜなら残り3個を7種の中から重複せず選択しなければならず、
7/3=2あまり1だからです。

(2) そういう数字3個の組み合わせは 10=120とおりですが、
一方ABのようなグループの組み合わせは以下である必要もあり、
n=10のときは45とおりが最大です。

(3) そういう組み合わせ中の結合線の数は=3ですから、
45×3=135以上の結合線は存在しえません。

(4) 一方、問題1に示したように結合線の数が最小となる
おのおの0.6n前後個ずつ用いた場合の結合線の数は
 5(0.6n)(0.6n-1)以上です。

(5)  n=10の時計算すると150であり、135より多いので不可能です。

ちなみにn=5のとき 5*3*2=30 ≡  3*5C2=30 であり6個でも可能性ありとなります。

実際下図のように、考える方向を変えてA〜Eから3個取り出す組み合わせ全部により、きれいな形で可能です。

【P.S.】

追加問題4 は挑戦中です。

5と10 、2003と1338004は3m-1とm(3m-1)と考えられ、01の乱数列での期待値を考えると、この式中の3が3個重複と結びつきます。
実際 8と24 や11と44はでは容易にシフトでOKのものが見つけられました。
「2003」が用いられているので、新年問題として正月に再トライしてみます。


 『部分集合』へ

 数学の部屋へもどる