面白い数学の問題おしえて～な 44問目 (373ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
282(2): １３２人目の素数さん [sage] 2025/08/31(日) 18:56:12.09 ID:QaV2l/9l(1/2) AAS
>>274 ヒント続き
（今更だけど「/」は差集合。＼と間違えたけどこのまま進めます。ごめんちょ）
Wの部分集合A,Bが A⊂B でも B⊂A でもなく、|A|, |B| ≦ 500 を満たすならば、f(A)≠f(B).
（証明）
|A|=|B|の時は証明済み。
|A|<|B|として一般性を失わないのでそのように仮定する。
0 < |A/(A∩B)| < |B/(A∩B)| より、集合 B/(A∩B) から任意に |B|-|A| 個の元を選んでその集合をCとおくと、
A':=A∪C は A⊂A'⊂B、 |A'|=|B|、 0<|A'/(A'∩B)| (すなわち A'≠B) を満たす。
f(A)=f(B) と仮定すると f(A') = f(A)∪f(C) = f(B)∪f(C) = f(B) より、f の W(|B|) への制限の単射性に反する。
（終わり）
284: １３２人目の素数さん [sage] 2025/08/31(日) 21:44:05.05 ID:QaV2l/9l(2/2) AAS
>>282
誤 A⊂A'⊂B
正 A⊂A'
301: １３２人目の素数さん [sage] 2025/09/02(火) 22:27:43.25 ID:Mll4sRUZ(1) AAS
>>299
うお…すごい大作だ 本当にお疲れ様
まじでごめんなんだけど、正しさを確かめる気力が無いから想定解だけ書かせてもらうね
>>282 の続き
Wの部分集合A,Bが A⊂B かつ |A|+2≦|B|≦500 を満たすならば、f(A)≠f(B).
（証明）
Bの元のうちAに属さないものが２つ存在するのでそれらを w_1,w_2 とおく。
A_1:=A∪{w_1}, A_2:=A∪{w_2} とおくと、最初に証明した補題より f(A_1)≠f(A_2) であるから、
f(A) ⊂ f(A_1)∩f(A_2) は f(B) ⊃ f(A_1)∪f(A_2) の真の部分集合である。
（終わり）
（主張の証明）
2^W の部分集合 W_0 を W_0 := W(500) ∪ W(498) ∪ W(496) ∪… と定める。
この時、A,B∈W_0 が A⊂B または B⊂A を満たすならば３つ目の補題から f(A)≠f(B) が導かれ、
どちらも満たさなければ２つ目の補題から f(A)≠f(B) が導かれるので、
f の W_0 への制限は単射であることがわかる。…(1)
2|W_0| = 2Σ_(k=0,250) 1000C(2k) = 1000C500 + Σ_(k=0,500) 1000C(2k) であるが、
(1 + (-1))^1000 の二項展開と (1 + 1)^1000 の二項展開を足し合わせることで Σ_(k=0,500) 1000C(2k) = 2^999 が導けるから、
|W_0| > 2^998. …(2)
(1)と(2)より、|2^S| ≧ |W_0| > 2^998 であるから |S|≧999.
等号成立は >>268 より可能。
（終わり）
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.024s