問題

　すべての行和・列和が整数の時, それらの値を変えることなく書かれている実数をすべて整数化できることを主張しています. 例えば次のようなマス目は全ての行和・列和が整数ですが,

$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline 0.3 & 1 & 1.7 \\ \hline 1.5 & 0.4 & 0.1 \\ \hline 0.2 & 0.6 & 2.2 \\ \hline \end{array}$$

次のように9個の実数を切り捨てor切り上げれば全ての行和・列和は変わらないままです. 割と非自明な気もします.

$$\def\arraystretch{1.3} \begin{array}{|c|c|c|}\hline 0 & 1 & 2 \\ \hline 2 & 0 & 0 \\ \hline 0 & 1 & 2 \\ \hline \end{array}$$

　 　 　 　

$$ 　$$

---

---

---

---

---

---

解答は以下.

---

---

---

---

---

---

$$ 　 　$$

　

　 　

解答

　$R=\{r_1,r_2,\dots,r_m \}$を$m$個の行に対応する頂点集合, $C=\{c_1, c_2,\dots,c_n\}$を$n$個の列に対応する頂点集合として$R, C$から構成される完全2部グラフ$K_{m,n}$(以下$K$と書きます)を考えます. この$K$には辺が$mn$本ありますが, その各辺$(r_i, c_j)$の重みをマス目の$i$行$j$列に書かれている実数と対応させます. すなわちあるマスの実数を書き換えることは$K$のある辺の重みを変えることに対応します.

　このようにマス目の実数と$K$の辺の重みを対応づけると, 行和あるいは列和は各頂点に接続している辺の重みの和と解釈されます. よって与えられたマス目から$K$を作ると$K$の各頂点に接続している辺の重みの和は整数ということになります.

　以下, $K$に以下の性質を保ったまま操作を行ない, 辺の重みを変えていきます.

1. 初期状態で非整数の重み$x$を持つ辺に対して, その重みが$y$になっているとき$\lfloor x\rfloor\le y \le \lfloor x\rfloor +1$
2. 各頂点に接続している辺の重みの和は初期状態から変わらないある整数.

　操作は次の一連の流れで与えられます.

• 非整数重みの辺が一つでもあれば, その辺をスタートとして非整数の辺をたどっていき非整数重みの辺のみからなるサイクル$C$を見つける. (本当に非整数の辺をたどっていけるのかが疑問にはなりますが, 上述の2つ目の性質から「ある頂点$v$に非整数重みの辺が接続していれば, $v$には少なくとも一つの別の非整数重みの辺が接続している」ことが保証されているので, このステップは実行できます.)
• $C$の辺の重みの中で整数に一番近いもの$a$を考え, $a$とその最近接整数の差を$d$とします. $(d = \min_{e\in C} {\rm dist}(w(e), \Z))$.
• $C$の各辺の重みを順番に$(+d, -d, +d,-d,\dots,+d,-d)$します. $K$が2部グラフなので$C$は偶数サイクルであることに注意しましょう. またどの辺を$+d, -d$するか2通りの択が存在しますが, $a+d$または$a-d$のどちらかは整数になるはずなのでそれが整数になる方を選びます.

　この操作を行っても上述の性質は常に保たれたままであることは簡単に確認できます. 1つ目の性質に関しては$d$の定義から$C$の各辺の重みを$+d, -d$しても整数を跨ぐことはないという事実から, 2つ目の性質に関しては$C$の各辺の重みを$+d, -d$交互に作用させていることからわかります. 一方で非整数重みを持つ辺はこの操作で必ず一つは減っているので, この操作を繰り返せばいつかは$K$のすべての辺の重みが整数になります. その$K$に対応するマス目が求めるものです.

操作例

マス目が冒頭の例だとしましょう:

$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline 0.3 & 1 & 1.7 \\ \hline 1.5 & 0.4 & 0.1 \\ \hline 0.2 & 0.6 & 2.2 \\ \hline \end{array}$$

これに対応する$K$の初期状態は次のグラフです.

• この中には非整数重みの辺$(r_2,c_2)$があります. そこからスタートして例えば$r_2\rightarrow c_2\rightarrow r_3\rightarrow c_3\rightarrow r_2$という非整数重み4辺からなるサイクル$C$が見つかります.
• $C$の各辺の重み$(0.4, 0.6, 2.2, 0.1)$の中で整数に一番近いものは$a=0.1$で$d=0.1$となります.
• 重み$0.1$が$0$になるように, 各辺の重みを$(0.4+d, 0.6-d, 2.2+d, 0.1-d)$に書き換えます.

これで他の辺をほとんど変化させることなく(=重みが整数を跨ぐことなく), また各頂点周りの辺の重みの和を変えることなく辺$(r_2,c_3)$の重みを整数にすることに成功しました. 後はこれを繰り返すだけです.