日本数学オリンピック予選問題について

質問

第14回（2004年）日本数学オリンピック予選問題の問題９について説明をお願いします。解答は手元にありますが、数学好き向けに説明しているので、全然わかりません。数学が得意でない人向けにわかりやすく説明してください。
問題９
　「７人の政治家がおり，いくつかの派閥がある．派閥とは１人以上の政治家が属する集団である．２つの派閥は，もしその両方に属する政治家と，どちらにも属さない政治家がともに存在すれば，必ず一方が他方を含むという．派閥の個数の最大値を求めよ．ただし，７人全員からなる集団も派閥であるとする．」

回答No.4

eatern27 · ベストアンサー

#2です。２３通りであっていたんですね。

★の条件を式で表すのなら、(Ａを派閥の集合とします)

「任意のＰ,Ｑ∈Ａに対して
((Ｐ∩Ｑ≠φ)∧(Ｐ∪Ｑ≠Ｕ))⇒((Ｐ⊃Ｑ)∨(Ｐ⊂Ｑ))」
という感じになります。

「任意のＰ,Ｑ∈Ａに対して」の部分についてですが、
もし、Ａ内に派閥がn個あれば、Ｐ,Ｑの選び方はnＣ2通りあります(Ｐ,Ｑの順番を考えない)。そのnＣ2通り全てに対して、という事になります。

また、
Ｐ∩Ｑ≠φ：両方に属する政治家が存在する
Ｐ∪Ｑ≠Ｕ：両方に属さない政治家が存在する
(Ｐ⊃Ｑ)∨(Ｐ⊂Ｑ)：一方が他方を含む
の部分に相当します。また、

この条件は
「任意のＰ,Ｑ∈Ａが
(1)Ｐ∩Ｑ＝φ
(2)Ｐ∪Ｑ＝Ｕ
(3)Ｐ⊃Ｑ
(4)Ｐ⊂Ｑ
のうち、少なくとも１つを満たす」と同値です。
(★が↑の意味だと思って差し支えないかも)

それぞれを日本語で書けば
(1)Ｐ,Ｑの両方に属す政治家がいない
(2)全ての政治家はＰ,Ｑの少なくとも一方に属す
(3)Ｑに属す政治家はＰに属している
(4)Ｐに属す政治家はＱに属している
という感じです

＞派閥ＰがＡの要素であるならば、Ｐ~(＝Ｐに属さない政治家からなる派閥)をＡに付け加えても★を満たします
について

ＡにＰ~を付け加えた集合をＢとします。
Ａ内のどの２つの要素をとってきても、(1)～(4)のどれかを満たすのですから,結局Ｐ~とＡの要素Ｑが(1)～(4)のどれかを満たせばＯＫとなります。
これは、Ｐ,Ｑが(1)～(4)のどれを満たしているかで場合分け(ＰもＱもＡの要素なので,(1)～(4)のどれかを満たす事が保証される)します。

(1)Ｐ∩Ｑ＝φ⇒Ｐ~⊃Ｑ
(2)Ｐ∪Ｑ＝Ｕ⇒Ｐ~⊂Ｑ
(3)Ｐ⊃Ｑ　　⇒Ｐ~∩Ｑ＝φ
(4)Ｐ⊂Ｑ　　⇒Ｐ~∪Ｑ＝Ｕ
ですから、Ｐ~とＱも(1)～(4)のうち、少なくとも１つを満たしています。

よって、集合Ｂも★の条件を満たします。だから、
＞なので、ＰとＰ~が共にＡの要素であった方が、Ａの要素の数は多くなります。
と言えます

＞派閥に含まれる政治家の人数が…が最大です。
の部分について。

1人・6人からなる派閥および7人からなる派閥は、そもそも７通りおよび１通りしかありませんから、「1人・6人の派閥は７つ」「7人の派閥は１つ」が最大というのは明らかです。

次に、2人からなる派閥について。
まず、[ab]という派閥を作ります。(この書き方は#2と同じです)
ここに１つ派閥を付け加えるのを考えてみます
[ac]という派閥を付け加えると、[ab][ac]が★の部分の条件を満たしていません。なので、[ac]という派閥を付け加える事ができません。

aまたはbを含む派閥を付け加える事ができないので、付け加えることができるのはaもbも含まない[cd]となります。さらに、もう１つ付け加えるとしたら、[ef]となります。[ab][cd][ef]に属さない政治家はgのみですから、これ以上付け加える事ができません。なので、2人からなる派閥は３つまで。
同様に３人からなる派閥は２つまでとなります。
4人からなる派閥はＰに対するＰ~のようなものを考えれば,結局３人からなる派閥に帰着できます。よって、２つまで。5人からなる派閥も同様に３つまで。

「★の条件を満たしたまま２５個の派閥を作ることはできません。」
について。

まず、２５個の派閥を作れるとしたら、
1人・6人の派閥は７つ
2人・5人の派閥は３つ
3人・4人の派閥は２つ
7人の派閥は１つ
存在しないといけません。

2人の派閥を３つ作るとしたら,
[ab][cd][ef]となります。ここに3人の派閥を１つ付け加える事を考えます。
この３人の派閥はabcdefのどれかを含みます。
そこでaを含むとします。もし、bを含まなかったら,★を満たしません。なので、bを含みます。
さらに、c～fを含んだら、★を満たさないので,gを含みます。
よって、[abg]という派閥を付け加えることになります。さらに、もう１つ3人の派閥を付け加えるとしたら、[cdg]となります。ところが、

[abg][cdg]の２つに注目すれば、★を満たさないことが分かります。

よって、2人の派閥が３つあったら、3人の派閥は１つまで、ですね。なので、２５個の派閥は不可能、となります。

うーむ、下手な説明ですいません。分からない所があれば、補足してください。

お礼

丁寧な解答本当にありがとうございます。
非常にわかりやすい説明で、数学がダメな私でも正確に理解することができました。これからも質問することがあるかもしれませんが、よろしくお願いします。

回答No.5

eatern27

#2,#4です。

やっぱり、#2のような解き方じゃなくてよさそうです。

#4に書いてある事から派閥は２５個以下、というのが言えます。さっきは、この後、2人の派閥と3人の派閥に注目して、2人の派閥が３つ、３人の派閥が２つ、というのは不可能、というのを証明しました。

さらに、4人の派閥が２つ、５人の派閥が３つ、というのも不可能、というのが証明できるはずです。(2人の派閥３,4人の派閥２が不可能,とかでもＯＫ)

なので、結局、派閥は２３個以下,となります。

#2に挙げたような２３個の例が存在するので、最大値は２３個

こんな風にも証明できますね。

＞派閥ＰがＡの要素であるならば、Ｐ~(＝Ｐに属さない政治家からなる派閥)をＡに付け加えても★を満たします。
などは、２３個の例を探すための道具、とでも思って下さい。

回答No.3

elmclose

#1です。

私は、問題の中の★に相当する部分の解釈を間違っておりました。
それで、考慮すべき場合が漏れており、「13個」と書いてしまいました。

#2さんの説明はわかりやすいと思います。

あと、
「派閥ＰがＡの要素であるならば、Ｐ~(＝Ｐに属さない政治家からなる派閥)をＡに付け加えても★を満たします。」の部分と、
「★の条件を満たしたまま２５個の派閥を作ることはできません。」の部分が、
それぞれ、なぜそう言えるのかがはっきりすると、より一層理解しやすいと思うのですが。

回答No.2

eatern27

答えは２３通りですか？

あっているかどうかも分からないので,大雑把な説明だけ書きます。もっと詳しい証明が必要であれば補足をしてください。(２３通りが違う場合も、補足してください。もう一度考えてみますので)

まず、
「２つの派閥は，もしその両方に属する政治家と，どちらにも属さない政治家がともに存在すれば，必ず一方が他方を含む」…★
という条件を満たす集合Ａを考えます。(Ａの要素は派閥です)

派閥ＰがＡの要素であるならば、Ｐ~(＝Ｐに属さない政治家からなる派閥)をＡに付け加えても★を満たします。

なので、ＰとＰ~が共にＡの要素であった方が、Ａの要素の数は多くなります。

よって、７人全員からなる派閥に対してだけは「ＰとＰ~」のようなペアを持ってくる事ができない、という事に注意すれば、最大値は奇数という事になります。

派閥に含まれる政治家の人数が
1人・6人の派閥は７つ
2人・5人の派閥は３つ
3人・4人の派閥は２つ
7人の派閥は１つ

が最大です。よって、派閥の数の最大値は
７×２＋３×２＋２×２＋１＝２５以下となります。

ところが、★の条件を満たしたまま２５個の派閥を作ることはできません。

よって、(最大値が奇数であるから)最大値は２３以下、となります。もし、２３個の派閥が作れれば、２３が最大,となります。

政治家にa～gという名前をつけて、
abcだけが属す派閥を[abc]
abcだけが属さない派閥を[-abc]
のように表す事にすれば、

[abcdefg]
[a][b][c][d][e][f][g]
[-a][-b][-c][-d][-e][-f][-g]
[ab][abc][abcd][abcde]
[-ab][-abc][-abcd][-abcde]

という派閥は★の条件を満たします。(←満たしていますよね？確認してください)

よって、２３個の派閥を作る事ができます。

∴最大値は２３個。

補足

正解は「23個」です。
とても丁寧な解答、本当にありがとうございます。
私は、どうやら数学だけでなく日本語の勉強もした方がいいみたいで、どうしても★の部分の題意が読み取れません。もしよろしければ、★の部分の解説と、全体のより詳しい説明をお願いします。

回答No.1

elmclose

補足要求をいたします。答えは１３でしょうか。
もし１３が合っていれば、説明可能かもしれません。

補足

解答していただいて本当にありがとうございます。
正解は「23個」となっています。