◆東京都 ぱずきち さんからの解答。
i番目の部屋の人数をx(i)とする。
この時j番目の部屋に集まるための総移動距離をL(j)とする。
【問題１】
L(2)=13
【問題２】
x(1)=1,x(2)=x(3)=x(4)=x(5)=2の時、L(5)=16
【本命問題】
| L = | (n-1)m - n + gcd(n,m) 2 |
【解説】（厳密な証明にはなっていませんが）
一般に
| L(j) = | j Σ i=1 | (j-i)x(i) + | n Σ i=j+1 | (n+j-i)x(i) (式1) |
L(j)の最小値を見つけるには 、
L(j+1) - L(j) = m - n x(j+1) (式2)
を利用し、
m/n - x(i) を1からjまで加えたときに、最小となるjを見つければよい。
一方、jを変化させたときのL(j)の平均値は
（(式1)から求めてもよいが）、
各人の移動距離の平均値が(n-1)/2であることを考えると
| <L(j)> = | (n-1)m 2 | (式3) |
となり、x(i) の分布によらない。
したがって、最小値が最大になるようにするには、
L(j)の平均値からの変動が小さくなるよう、
できるだけ均等にx(i)を決めればよい。
このためには、
| x(i) = floor(i* | m n | )- floor((i-1)* | m n | ) (式4) |
とすればよい。
ただし、floor(t)はtを越えない最大の整数（ガウスの記号）。
このとき、L(j) は(式2)を用いて
| L(j)= m*j - n*floor(j* | m n | )+ c= (m*j mod n) + c |
第１項m*j mod nは0からn-gcd(n,m)の範囲にgcd(n,m)刻みで均等に分布するので、
| その平均値は | n - gcd(n,m) 2 | 、最小値は0である。 |
L(j)の平均値が(n-1)m/2となるようにcを定めると
| c = | (n-1)m 2 | - | n - gcd(n,m) 2 | (式6) |
であり、これがL(j)の最小値である。
◆出題者の山梨県 Footmark さんからのコメント。
『分散のミニ・マックス』 に解答が寄せられて嬉しく思っています。 私の考えていたのよりずっとスマートな解答です。
| ただ、総移動量＝ | m･n-(m＋n)＋gcd(m,n) 2 |