面白い数学の問題おしえて～な 44問目 (372ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
268(3): １３２人目の素数さん [sage] 2025/08/29(金) 08:36:52.20 ID:pG2i3ifz(1) AAS
とりあえず995人以上は必要>>257
999人では可能
∵ 999本のワインを999人に飲ませる。500人死ねば死んだ500人の飲んだワインが毒入り。499人死ねばその499本と誰も飲んでないワインが毒入り
この隙間を埋める問題
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 より可能。
（終わり）
302: １３２人目の素数さん [] 2025/09/03(水) 08:38:15.85 ID:wC3sbrDB(1) AAS
をーなんかすごいな
素人の疑問なんだけど、ワインの数とか毒の数によっては
>>268みたいな自明解以外の解が存在するのだろうか
304: １３２人目の素数さん [sage] 2025/09/03(水) 09:06:26.14 ID:AK+unjCX(2/2) AAS
正確には “ワインが n 本、毒をいれる本数が ⌈(n-1)/2⌉ 本の場合の必要な奴隷の人数の最小数は n-1 人” の証明が >>289-299。n = 1000 のときは ⌈(n-1)/2⌉ = 500 となるので問題の設定をカバーしてる。>>268 の “解は 995人以上、999人以下” の中で 999 人が答えでしたとさというお話。ワインが1000本、毒が500を拡張する方法は他にも色々あるだろうけど。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.015s