<組合せ>一番仕事量の多いパターンについて

質問

従業員3人（従業員A～従業員C）に対して、
以下の仕事をそれぞれ任せるとします。

仕事量１の仕事が４個
仕事量２の仕事が４個
仕事量４の仕事が４個
仕事量１０の仕事が２個

割り振りのルールですが、
・仕事は、１つずつランダムに割り振ります。
・仕事を振るタイミングで、一番仕事を割り振っていない人に優先的に割り振ります。
・各人に振っている仕事量が同じ場合、A（優先度高）→B→C（優先度低）で割り振ります。
・一度割り振った仕事については終了は考慮しません。（仕事量が減ることはない）

例）
ターン１．仕事量１(1個目)の仕事→A（仕事量合計１）
ターン２．仕事量２(1個目)の仕事→B（仕事量合計２）
ターン３．仕事量１(2個目)の仕事→C（仕事量合計１）
と振った場合、
ターン４．仕事量４(1個目)の仕事が来た場合、
→A（仕事量合計５）となります。
ターン５．仕事量１０(1個目)の仕事が来た場合、
→C（仕事量合計１１）となります。

ターン５までで、A=５、B＝２、C＝１１なので、
次の仕事の割り振りは、Bとなります。

上記ルールにしたがうとして、すべての仕事を割り振ったとき、
（運が悪く）ある1人の従業員が行う仕事量の最大が
いくらになるかを論理的（数学的）に証明したいです。
よろしくお願いします。

回答No.1

nag0720

1人の従業員が行う仕事量の最大は２２ですね。

最後のターンを仕事量１０にすれば、１人の仕事量を２２にするのは簡単にできるでしょう。

問題は、１人の仕事量が２３以上にできるかどうかですが、最後のターンの仕事量を考えれば容易に証明できます。

もしあるターンで仕事量の合計が２３以上になったとしたら、
そのターンの仕事量をＸとすれが、１つ前の仕事量の合計は、２３－Ｘ。
で、その人に割り振られたのだから、全員が２３－Ｘ以上でなければならない。
Ｘ＝１０の場合、２３－Ｘ＝１３
３人の仕事量の合計は、１３×３＋１０＝４９以上になる。
しかし、すべての仕事量の合計は４８だから不可能。

Ｘ＝１，２，４の場合についても同様。

お礼

ご回答ありがとうございます。理解できました