高校の問題で。。。[問]A:={x|xは1以上100以下の自然数}

皆様こんにちは。宜しくお願い致します。

[問]
A:={x|xは1以上100以下の自然数}
今、集合Aの部分集合で次の性質を持つものの内、要素の個数が最大のもの(複数の集合が該当するかもしれない)を考える。
(性質)その部分集合から異なる任意の3つの要素を取り出す時、小さい方の和は最大のものに一致しない。
(1) (性質)を満たす部分集合の要素の個数は(　)である。
(2) 与えられた性質を満たすAの部分集合の要素の個数の最大値は(1)で答えた数である事を入り法で示せ。

いろいろと考えたのですが頓挫してしまいました。うーん、、、
(1)は{50,51,…,100}だと推測(?)するのですがどのようにして求めれるのでしょうか?

No.1 回答者： eatern27 回答日時： 2005/11/21 21:26

問題文に背理法を使え、というのがあるんですから、その方針で考えるのがよさそうですね。

とりあえずは、ヒントを。(不明な点は補足してください)

条件を満たし、要素が５２個以上であるようなＡの部分集合Ｂが存在すると仮定します。

Ｂから、異なる５２個の自然数を任意に取り出します。
小さい方から順に、n_1<n_2<n_3<・・・<n_52としましょう。
自然数i(2≦i≦52)に対してm_i＝n_i-n_1という51個の自然数が作れますよ。このm_iについて考えてみてください。

この回答への補足

ご回答大変有り難うございます。
参考にさせていただいております。

うーん、所で(1)はどうやって求めれるのでしょうか?

補足日時：2005/11/22 14:48

この回答へのお礼

ありがとうございました。
お陰さまで解決致しました。

お礼日時：2006/09/28 08:36

No.2 回答者： eatern27 回答日時： 2005/11/22 22:00

＞うーん、所で(1)はどうやって求めれるのでしょうか?

(2)が、「(1)が正しいことを証明せよ」という問題になっていることから分かると思うのですが、
(1)の段階では、厳密に最大個数がいくつか、という事を聞いているのではありません。(その答えが最大値である事の証明を求めているのではのではない)

単に、
＞(1)は{50,51,…,100}だと推測(?)するのですが
のような予想をしてくれ、と要求しているんですね。(その予想が正しいことは(2)で証明する)


まぁ、要するに、(1)は、
「与えられた性質を満たすAの部分集合の要素の個数の最大値を求めよ」という問題を、「最大値を予想→その予想が正しいことを証明」という順番に解け、という『誘導』ですかね。(この誘導がなくても、こういう解き方をする事になると思いますが)

最大値は５１個ではないか、という予想がたったのですから、あとは、(2)で、その事を証明するだけですね。

この回答への補足

ご回答大変に有り難うございます。

> まぁ、要するに、(1)は、
>「与えられた性質を満たすAの部分集合の要素の個数の最大値を求めよ」という問題を、「最大値を予想→その予想が正しいことを証明」という順番に解け、という『誘導』ですかね。(この誘導がなくても、こういう解き方をする事になると思いますが)
納得です。

> 条件を満たし、要素が５２個以上であるようなＡの部分集合Ｂが存在すると仮定します。
> Ｂから、異なる５２個の自然数を任意に取り出します。
> 小さい方から順に、n_1<n_2<n_3<・・・<n_52としましょう。
> 自然数i(2≦i≦52)に対してm_i＝n_i-n_1という51個の自然数が作れますよ。
> このm_iについて考えてみてください。
(1≦)m_2<m_3<…<m_52(<100)
という構図になりますよね。
うーん、これから何らかの矛盾が発生する筈なんですよね。
う、うーん、これからどういう矛盾が発生するのでしょうか???


お手数お掛けしましてスイマセン。

補足日時：2005/11/23 15:31

No.3 回答者： eatern27 回答日時： 2005/11/23 16:54

どういう矛盾が発生するのかというと、

Ｃ＝{m_i=n_i-n_1|2≦i≦52}
とおくと、
Ｂ∪Ｃは、Ａの部分集合です。
Ｂ∪Ｃの要素の数を実際に数えてみると、１０２個以上である事が分かります。
Ａの部分集合Ｂ∪Ｃの要素の数＞Ａの要素の数(１００個)
となるのは、矛盾ですよね。


「Ｂ∪ＣがＡの部分集合である」という事は、
＞(1≦)m_2<m_3<…<m_52(<100)
この辺りとＢの定義から分かるはずです。

そして、Ｂ∪Ｃの要素の数は、
Ｂ∩Ｃの要素の数が分かれば、求める事ができますよね。
Ｂの定義から、Ｂ∩Ｃの要素の数が高々１つといえます。
(m_i+n_1=n_iが成り立つことと、Ｂの性質から分かる)

この回答への補足

ご回答大変有り難うございます。m（＿ ＿）m


> どういう矛盾が発生するのかというと、
> Ｃ＝{m_i=n_i-n_1|2≦i≦52}
> とおくと、
> Ｂ∪Ｃは、Ａの部分集合です。
> Ｂ∪Ｃの要素の数を実際に数えてみると、１０２個以上である事が分かります。
(m_j=)n_j-n_1=n_1なる2≦j≦52が存在するか、
全ての2≦j≦52に対してn_j-n_1≠n_1となるか
のどちらかですよね。
よってB∩C={n_1}かB∩C=Φですね。

> Ａの部分集合Ｂ∪Ｃの要素の数＞Ａの要素の数(１００個)
>となるのは、矛盾ですよね。
B∩C={n_1}かB∩C=Φより
B∪Cの要素数は(52+50=)102か(52+51=)103ですね。


> 「Ｂ∪ＣがＡの部分集合である」という事は、
> (1≦)m_2<m_3<…<m_52(<100)
> この辺りとＢの定義から分かるはずです。
C⊂Aを言うには
任意のm_p,m_q,m_r∈{m_2,m_3,…,m_52}(2≦p<q<r≦52)に対して
m_r≠m_p+m_qが成立する筈なんですよね。。。
これは簡単に言えますかね?

一応、自分なりに考えて、、、
もし、m_r=m_p+m_qなるm_rが存在したと否定してみるとこの等式は
n_r-n_1=n_p-n_1+n_q-n_1と書け、
n_r-n_p=n_q-n_1
となり、、、????
うーん、また行き詰まってしまいました。。。
ここからどう導き出せますでしょうか?

補足日時：2005/11/24 17:42

この回答へのお礼

ありがとうございました。
お陰さまで解決致しました。

お礼日時：2006/09/28 08:37

No.4 ベストアンサー 回答者： eatern27 回答日時： 2005/11/24 19:10

＞(m_j=)n_j-n_1=n_1なる2≦j≦52が存在するか、

＞全ての2≦j≦52に対してn_j-n_1≠n_1となるか
＞のどちらかですよね。
＞よってB∩C={n_1}かB∩C=Φですね。

申し分ありません。全く、その通りです。

＞B∪Cの要素数は(52+50=)102か(52+51=)103ですね。
Ｂの要素が５２個の場合に、矛盾する事を言えば十分ですので(Ｂの要素が５２個より多ければ、その部分集合を考えればいいから)、それでＯＫですね。
(なお、＃１、＃３では、Ｂの要素が５２個以上の場合を想定していたので、「Ｂから異なる５２個の元を取り出す」とか「１０２個以上」という書き方をしています)

＞C⊂Aを言うには
＞任意のm_p,m_q,m_r∈{m_2,m_3,…,m_52}(2≦p<q<r≦52)に対して
＞m_r≠m_p+m_qが成立する筈なんですよね。。。

あ～、#3で「この辺りと『Ｂの定義』から分かるはずです」なんて書かない方がよかったかもな・・・。すいません。
その条件は、Ｃ⊂Ｂが成り立つための条件ですよね。
(もちろん、Ｃ⊂Ｂが証明できれば、それはそれで矛盾が生じますが・・・)

Ｃ⊂Ａが成り立つには、任意のＣの元mに対して、m∈Aが成り立つ事を言えばいいですよね。
Ａの定義は、
A:={x|xは1以上100以下の自然数}
でしたから、結局、Ｃの元ｍに対して、「mが1以上100以下の自然数である」が成り立つ事を言えばいいんです。
＞(1≦)m_2<m_3<…<m_52(<100)
から直ちに分かると思います。

そして、Ｂ⊂Ａも成り立つので(←Ｂの定義はここで使うｗ)、(Ｂ∪Ｃ)⊂Ａが成り立ちますよね。

この回答へのお礼

ありがとうございました。
お陰さまで解決致しました。

お礼日時：2006/09/28 08:37