面白い数学の問題おしえて～な 44問目 (373ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
251(2): 08/27(水)21:02 ID:xqGeek16(1)調 AAS
1000本のワインがありそのうち半数の500本には毒が入っている。
その毒は飲んだら15～20時間の間のランダムな時間で死ぬ。
全ての毒入りワインを24時間以内に確実に特定するには最低何人の奴隷が必要か。
264: 08/29(金)03:54 ID:cgED+EFx(1)調 AAS
これか
math.stackexchange.com/questions/639/logic-problem-identifying-poisoned-wines-out-of-a-sample-minimizing-test-subje
でも>>251の答えはないな
265(2): 08/29(金)06:34 ID:e60Qap8s(1/2)調 AAS
>>251 のヒント
ワイン全体の集合をW、奴隷全体の集合をSとおく。
集合Xに対し、Xの部分集合全体からなる集合を2^Xとおく。
また、集合Xと整数kに対し、X(k) = {Y⊂X : |Y| = k} とおく。
どのワインをどの奴隷に飲ませるかを表す写像 f:W→2^S を考える。
V⊂Wに対して f(V):=∪_(v∈V)f(v) と定めることにより、fは2^Wから2^Wへの写像に拡張できる。
問題は、拡張したfの W(500) への制限が単射になるような f が存在する最小の |S| を求めることと言い換えられる。
（ここからヒントの本題）
全ての正の整数 k≦500 に対し、f の W(k) への制限は単射になる。（なぜか？）
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.019s