|
おーちゃん |
|
[1] まず、ハイタッチ回数を最大化するのは属性2つずつの分配のいずれかであることを示す。
属性4つの人がいるとき： (1-a) 属性０の人がいればその人に属性を1つ渡す。 (1-b) 属性1つの人がいればその人に属性を1つ渡す。 これを属性4つの人がいなくなるまで行う。 属性3つ（ABC）の人がいるとき： (2-a) 属性０の人がいればその人に属性を1つ渡す。 (2-b) 属性1つの人がいて、その属性が A ならば、C を渡す。（ABC+A → AB+AC） (2-c) 属性1つの人がいて、その属性が D ならば、この時点で ABC,AB,AC,BC,AD,BD,CD,D が残っている。ここで AD,BD,CD で一番人数の少ないものが CD であれば、C を渡す。（ABC+D → AB+CD） これを属性3つの人がいなくなるまで行う。 上記の手順は必ずハイタッチ回数を増やすようになっている。 （※ (2-c) がそうなっていることは、CD (=min{AD,BD,CD}) が高々 2人までであり、ABC→AB によって減るハイタッチ回数 CD≦2 に対して D→CD によって増えるハイタッチ回数 (ABC-1)+AC+BC=7-CD≧5 が上回ることによる） つまり、属性3つor4つの人がいる分配に対しては、必ず属性2つずつの分配でもっとハイタッチ回数を多くするものが存在する。 したがって、ハイタッチ回数を最大化するのは属性2つずつの分配のいずれかである。 [2] 次に、属性2つずつの分配でハイタッチ回数を最大化するものを求める。 AB=αとすると AC+AD=BC+BD=8-α、したがって CD=(16-(AC+AD+BC+BD))/2=α である。 そこで AB=CD=α, AC=BD=β, AD=BC=γ とする。（α+β+γ=8） このときハイタッチ回数は、 (8*7/2)*4 - (α(α-1)/2)*2 - (β(β-1)/2)*2 - (γ(γ-1)/2)*2 = 120 - α^2 - β^2 - γ^2 これを最大化するのは α=β=3, γ=2 のときとなる。 |
|
4月27日（木） 22:07:31
46284 |