数理解析研究所講究録 1422 巻 2005 年 106-119106

超離散代数方程式の解
早稲田大学・理工学部 広田 良吾, 高橋 大輔
Ryogo Hirota and Daisuke Takahashi
School of Sci. and Eng., Waseda University

1

はじめに

1J

何をやるのか ?

例えば次の代数方程式$A_{3}X^{3}-A_{2}X^{2}+A_{1}X-A_{0}=0$ ,$A_{3}$, A2,$A_{1},$$A_{0}\geq 0$を超離散化した方程式$\max(a_{3}+3x, a_{1}+x)=\max(a_{2}+2x, a_{0})$の解法について考える。

1.2

研究の動機

1. 離散的ソリ トン方程式, 例えば$\mathrm{K}\mathrm{d}\mathrm{V}$方程式、 Lotka-Volterra 方程式、 戸田方程式など型の方程式などに、 空間的な周期構造を課すと必然的に方程式は従属変数にたいする代数方程式になる。
の$\mathrm{K}\mathrm{P}$

したがって周期的ソリトン方程式を超離散化しようとすると代数方程式の超離散化型の場合には複雑な係数をもつ 2 次の代数方程式になる。
が必要になる。
$\mathrm{K}\mathrm{P}$

2.

1.3

-Kotera 方程式や Hungry Lotka-Volterra の場合には 3 次以上の代数方程式が現れる。 従って 3 次以上の代数方程式の超離散化が必要となる。 一般の超離散代数方程式とその解について考える。
しかし$\mathrm{K}\mathrm{d}\mathrm{V}+\mathrm{S}\mathrm{a}\mathrm{w}\mathrm{a}\mathrm{d}\mathrm{a}$研究の歴史

超離散代数方程式とその解に関する過去の研究についてほとんど何も分からない。 知っていることは次の事柄だけである。

107
131

1 次代数方程式$A_{0}X+B_{0}=A_{1}X+B_{1}$ ,$A_{0},$ $B_{0},$ $A_{1},$$B_{1}>0$の解は$X=-(B_{0}-B_{1})/(A_{0}-A_{1})$ .

である。
しかし 1 次代数方程式を超離散化した方程式$\max$($a_{0}$

十 $x,$ $b_{0})= \max(a_{1}+x,$$b_{1})$の解は場合分けが必要である。 これについては次の記述がある。
Qudrat J.-P. Synchronization andBaccelli F., Cohen.
Discrete Event Systems. John Wiley and
すなわち超離散方程式$L\mathrm{i}near\mathrm{i}ty_{f}$$\mathrm{G}.\mathrm{J}.,\mathrm{a}\mathrm{n}\mathrm{d}$$\mathrm{S}\mathrm{o}\mathrm{n}\mathrm{s},1992$$\max$($a_{0}$

十 $x,$$b_{0}$) $= \max(a_{1}+x,$$b_{1})$の解は次の 5 つの場合に分類される :1. If ( $a_{0}>a_{1}$ andthen$b_{0}<b_{1}$) or ( $a_{0}<a_{1}$ and$b_{0}>b_{1}$)$x_{1}= \max(b_{0}, b_{1})-\max(a_{0}, a_{1})$(1):unique solution.

) and (1) does not hold,
and
2. If
No solution exists in .
$b_{0}\neq b_{1}$$a_{0}\neq a_{1}$$R$

3. If $a_{0}=a_{1}$ or$b_{0}\neq b_{1}$then$x \geq\max(b_{0}, b_{1})-a_{0}$4. If$a_{0}\neq a_{1}$

or

then

$b_{0}=b_{1}$$x \leq b_{0}-\max(a_{0}, a_{1})$5. If $a_{0}=a_{1}$ or$b_{0}=b_{1}$: nonunique solution.

.

:nonunique solution.

All $x\in R$ are solutions.

An Algebra for

108

$y$

図 1: $g\circ f(x)=x$ ,$f(x)= \max((2x+1, x+2)$$f(x)= \max(2x+1, x+2)$ ,$g(x)= \max((x-1)/2, x-2)$

岩尾昌央君の結果 (2000 年頃, 未発表)

132
$f(x)$

を単調増大関数とし $g(x)$ を $f(x)$の逆関数とする。 すなわち

$g\circ f(x)=x$である。
岩尾君は $\max$-pius 関数$f(x)= \max(a_{1}x+b_{1}, a_{2}x+b_{2})$ ,$(a_{1}, a_{2}>0)$, の逆関数は$g(x)= \min((x-b_{1})/a_{1}, (x-b_{2})/a_{\mathit{2}})$であることを発見した (図 1 参照)。 なぜなら$g\circ f(x)$$= \min((f(x)-b_{1})/a_{1}, (f(x)-b_{2})/a_{2}$$= \min(\max(a_{1}x+b_{1}, a_{2}x+b_{2})-b_{1})/a_{1},$ $\max(a_{1}x+b_{1}, a_{2}x+b_{2})-b_{2})/a_{2})$$= \min(\max(a_{1}x, a_{2}x+b_{2}-b_{1})/a_{1},$ $\max(a_{1}x+b_{1}-b_{2}, a_{2}x)/a_{2})$となるが場合分け$(\mathrm{i})$if $a_{1}x>=a_{2}x+b_{2}-b_{1}$ then.

109
$r.h.s.= \min(x, \max(a_{1}x+b_{1}-b_{2})/a_{2})=x$ ,(\"u )

if $a_{1}x<a_{2}x+b_{2}-b_{1}$ then$r.h.s.= \min((a_{2}x+b_{2}-b_{1})/a_{1}, x)=x$ ,によって結局$g\mathrm{o}f(x)=x$.

となる。 証明終わり。 もう一度書くと$f(x)= \max(a_{1}x+b_{1}, a_{2}x+b_{2})$の逆関数は$g(x)= \min((x-b_{1})/a_{1}, (x-b_{2})/a_{2})$である。 以下で、 この結果を一般化する。 記号$\sum_{j=1}^{N}\max(a_{j}x+b_{j})\equiv\max(a_{1}x+b_{1}, a_{2}x+b_{2}, \cdots, a_{N}x+b_{N})$を導入すると$f(x)= \sum_{j=1}^{N}\max(a_{j}x+b_{j})$, for $a_{j}>0$ .

の逆関数は$g(x)= \sum_{j=1}^{N}\min((x-b_{j})/a_{j})$となる。

たとえば次の $f(x)$ の場合には、 書き直すと$f(x)= \max(a_{1}x+b_{1}, a_{2}x+b_{2}, a_{3}x+b_{3})$$= \max(\max(a_{1}x+b_{1}, a_{2}x+b_{2}),$ $a_{3}x+b_{3})$ .

となるので、$f(x)$の逆関数は$g(x)$$=$$\min(\min((x-b_{1})/a_{1}, (x-b_{2})/a_{2}),$ $(x-b_{3})/a_{3})$ ,$=$$\min((x-b_{1})/a_{1}, (x-b_{2})/a_{2},$ $(x-b_{3})/a_{3})$ .

である。

岩尾君はさらに次のような超離散代数方程式の解も求めている。

110
1. $\max(0, a_{1}+x, a_{2} +2x, \cdots, a_{\tau\iota}+nx)=c,$ $c>0$ の$\mathrm{g}_{\mathit{1}}^{y7}\mathrm{F}$は$x= \min(c-a_{1}, (c-a_{2})/2,$ $\cdots,$ $(c-a_{n})/n)$ ,2. $\max(x+a, \min(2x+b, 3x+c))=y$ の解は$x= \min(y-a, \max((y-b)/2, (y-c)/3))$ ,で与えられることなども示している。

22 次の代数方程式の超離散化
2 次の代数方程式$A_{0}+A_{1}X+A_{2}X^{2}=B_{0}+B_{1}X+B_{2}X^{2}$の超離散化を考える。

2.1

方程式の標準化

1 次の代数方程式の解の分類でも面倒なので、 まず方程式の標準化を考える。
2 次方程式$A_{0}-B_{0}+(A_{1}-B_{1})X+(A_{2}-B_{2})X^{2}=0$を書き直す。 $A_{0}-B_{0}\neq 0$ のとき$1+ \frac{A_{1}-B_{1}}{A_{0}-B_{0}}X+\frac{A_{2}-B_{2}}{A_{0}-B_{0}}X^{2}=0$である。 これを書き直すと$1+ \frac{(A_{1}-B_{1})(A_{0}-B_{0})}{(A_{0}-B_{0})^{2}}X+\frac{(A_{2}-B_{2})(A_{0}-B_{0})}{(A_{0}-B_{0})^{2}}X^{2}=0$である。 この形式 (分母を 2 乗化した形式) を標準化と呼ぶ。
$A_{0}-B_{0}=0$ のときは

1 次方程式に因数分解される。 この標準化を使うと、 すぐ前で調べた 1 次方程式$A_{0}$

十 $A_{1}X=B_{0}$ 十 $B_{1}X$の場合は $A_{1}-B_{1}\neq 0$ のとき$X= \frac{(B_{0}-A_{0})(A_{1}-B_{1})}{(A_{1}-B_{1})^{2}}$,or$X= \frac{A_{1}B_{0}+A_{0}B_{1}-(A_{0}A_{1}+B_{0}B_{1})}{(A_{1}-B_{1})^{2}}$となり、 超離散解の分類は $A_{0}\neq B_{0}$ and $A_{1}\neq B_{1}$

のとき

111
1. 解なし。 If $\max(a_{1}+b_{0}, a_{0}+b_{1})<\max(a_{0}+a_{1}, b_{0}+b_{1})$2. 一個 (PJ 舟 77 $\max(a_{1}+b_{0}, a_{0}+b_{1})-2\max(a_{1}, b_{1})$ がある。 If $\max(a_{1}+b_{0}, a_{0}+b_{1})>$$\max(a_{0}+a_{1}, b_{0}+b_{1})$と簡明になる。

2.2

2 次の代数方程式の超離散解

2 次の代数方程式の標準形 $(A_{0}\neq B_{0})$$1+ \frac{(A_{1}-B_{1})(A_{0}-B_{0})}{(A_{0}-B_{0})^{2}}X+\frac{(A_{2}-B_{2})(A_{0}-B_{0})}{(A_{0}-B_{0})^{2}}X^{2}=0$を使う。 ここで $X$ の 1 次と 2 次の係数を改めて$A_{1}$

2 次の代数方程式は次の 3 つの場合に分類される, A2 と置くと,$A_{17}$

A2 の正負に対応して$(A_{1}, A_{2}>0)_{\text{。}}$

1. $1+A_{1}X=A_{2}X^{2}$
2. $1+A_{2}X^{2}=A_{1}X$$3$. $A_{1}X+A_{2}X^{2}=1$

注。 $1+A_{1}X+A_{2}X^{2}=0$ の場合は $X$ の正値解は存在しないので場合分けに含めな 1,$\backslash \text{。}$こ

れらの場合に対応して超離散 2 次代数方程式は

1. $\max(0, a_{1}+x)=a_{2}+2x$$2$. $\max(0, a_{2}+2x)=a_{1}+x$$3$. $\max(a_{1}+x, a_{2}+2x)=0$と分類される。

2 次方程式の解を超離散化したものと超離散 2 次方程式の解は一致するか?

112
2.3

2 次方程式の解の超離散化最初によく知られている 2 次方程式の解を超離散化する。

1. 2 次方程式$A_{2}X^{2}-A_{1}X-1=0$ の解は次の 2 つである。
$X_{1}= \frac{A_{1}+(A_{1}^{2}+4A_{2})^{1/2}}{2A_{2}}$$X_{2}= \frac{A_{1}-(A_{1}^{2}+4A_{2})^{1/2}}{2A_{2}}$これを超離散化すると, 只 1 つの解$x_{1}= \max(a_{1}, \frac{1}{2}\max(2a_{1}, a_{2}))-a_{2}$$= \max(a_{1}-a_{2}, -\frac{1}{2}a_{2})$が得られる。

$X_{2}$

は値が負であるので超離散解にならない。

2. 2 次方程式 $A_{2}X^{2}-A_{1}X+1=0$ の解は次の 2 つである。
$X_{1}= \frac{A_{1}+(A_{1}^{2}-4A_{2})^{1/2}}{2A_{2}}$,$X_{2}= \frac{A_{1}-(A_{1}^{2}-4A_{2})^{1/2}}{2A_{2}}$2$=\overline{A_{1}+(A_{1}^{2}-4A_{2})^{1/2}}$

これを超離散化すると,(i) 解なし

if $2a_{1}<a_{2}$ .

(ii) 2 っの解 $x_{1}=a_{1}-a_{2}$ ,if $2a_{1}>a_{2}$ , が得られる。

$x_{2}=-a_{1}$3. 2 次方程式 $A_{2}X^{2}+A_{1}X-1=0$ の解は次の 2 つである。

$X_{1}= \frac{-A_{1}+(A_{1}^{2}+4A_{2})^{1/2}}{2A_{2}}$2$=\overline{A_{1}+(A_{1}^{2}+4A_{2})^{1/2}}$’$X_{2}= \frac{-A_{1}-(A_{1}^{2}+4A_{2})^{1/2}}{2A_{2}}$

113

$y$

$x$

図 2: $\max(0, a_{1}+x)=a_{2}+2x1$ っの$\hslash^{7}\not\simeq^{\mathrm{J}}$,$x$

これを超離散化すると, 只 1 つの解$x_{1}=- \max(a_{1}, \frac{1}{2}\max(2a_{1}, a_{2}))$$=- \max(a_{1}, \frac{1}{2}a_{2})$が得られる。

2.4

超離散 2 次代数方程式の解の分類

次に超離散化された 2 次代数方程式の解を調べる。

1.

$\max(0, a_{1}+x)=a_{2}+2x$

この場合、 解は 1 つの直線 $y=a_{2}+2x$ と二つの直線 $y=0,$ $y=a_{1}+x$ の交点のx 一座標 $\{p(2,0), p(2,1)\}$ の中にある。 図 2 より解は只 1 つ:
$x= \max(p(2,0),p(2,1))=\max(-a_{2}/2, a_{1}-a_{2})$である。

この解は 2 次代数方程式の解を超離散化したものと一致している。

2.

$\max(\mathrm{O}, a_{2}+2x)=a_{1}+x$

この場合、 解は 1 つの直線 $y=a_{1}+x$ と二つの直線 $y=0,$ $y=a_{2}+2x$ の交点の $x-$

114

$y$

$x$

図 3: $\max(0, a_{2}+2x)=a_{1}+x$ : 宿なし

座標 $\{p(1,0),p(1,2)\}$ の中にある。 図 3 より(i) 解なし if $0>a_{1}+p(0,2)=a_{1}- \frac{1}{2}$ a2 or if $2a_{1}<a_{2}$ .
(ii) 2 つの解 $x_{2}=p(1,0)=-a_{1}$ , $x_{1}=p(1_{1}2)=a_{1}-a_{2},$ if $2a_{1}>a_{2}$ ,である。

この解も 2 次代数方程式の解を超離散化したものと一致している。

3. $\max(a_{1}+x, a_{2}+2x)=0$

この場合、 解は 1 つの直線 $y=0$ と二つの直線$y=a_{1}+x,$ $y=a_{2}+2x$ の交点の x 一座標 $\{p(0,1)_{7}p(0,2)\}$ の中にある。 グラフより

解は只 1 つ:$x= \min(p(0,1),p(02)\rangle)=\min(-a_{1_{\rangle}}-a_{2}/2)=-\max(a_{1}, a_{2}/2)$である。 この解も 2 次代数方程式の解を超離散化したものと一致している。

注

記号 $p(1,0)7p(1,2)$ などについては第 4 章 {一般的超離散方程式の解} を見よ。

3

超離散 3 次方程式の解
結果だけをまとめると、 超離散 3 次方程式は代数方程式$1+A_{1}X+A_{2}X^{2}+A_{3}X^{3}=0$の係数$A_{1_{7}}$A2,$A_{3}$の正負によって次の 7 通りに分類される。

1. $\max(0, a_{1}+x, a\mathit{2}+2x)=a_{3}+3x,$

$1$

115
2. $\max(0, a_{1}+x_{7}a_{3}+3x)=a_{2}+2x,$
3. $\max(0, a_{2}+2x, a_{3}+3x)=a_{1}+x,$

$0$

or 2

$0$

or 2

4. $\max(a_{1}+x, a_{2}+2x, a_{3}+3x)=0,1$
5. $\max(0, a_{1}+x)=\max(a_{2}+2x_{7}a_{3}+3x)$ , 1

6. $\max(0, a_{2}+2x)=\max(a_{1}+x, a_{3}+3x),$7. $\max(a_{1}+x, a_{2}+2x)=\max(0, a_{3}+3x),$

$1$

or 3

$0$

or 2

注、 最後の数字は超離散方程式の解の個数を示す。

4

一般的超離散方程式の解
次の形の一般的超離散方程式を考える。
$\sum_{j=1}^{N}\max(ajx+bj)=\sum_{k^{n}=1}^{M}\max(c_{k}x+d_{k})$ただし$a_{j},$

and$c_{karrow}\geq 0$$a_{j}\neq c_{k}$for $j=1,2,$

準備として 2 つの直線 $a_{j}x+b_{j}$ と点の x 座標 p(広 ) は次式で決まる。

$\ldots,$$c_{k^{\wedge}}x+d_{k}$$Nk=1,2,$$\ldots,$

$M$

とする。

の交点の座標 $\{p(j, k), q(j, k)\}$ を定義する。 交$k$$a_{j}p(j, k)$

十 $b_{j}=c_{k}p(j, k)$ 十$d_{k^{\wedge}}$

,

したがって

.

$p(j, k)=- \frac{b_{j}-d_{k}}{a_{j}-c_{k}}’$である。 一方 yy 座標 $q(j, k)$ は交点の x 座標 $p(j, k)$ より$q(j, k)=a_{j}p(j, k)+b_{j}=-a_{j} \frac{b_{j}-d_{k}}{a_{j}-c_{k}}.+b_{j}=\frac{a_{j}d_{k}-c_{k}b_{j}}{a_{j}-c_{k}}\sim$である。

焼方程式の解 はもし存在すれば交点 $p(j, k)=-(bj-dk)/(aj-ck)$
大事なポイントは『$M$$N$ and $k=1,2,$} の一つに等しし と う事実である。
$j=0,1,2,$$x$$\epsilon_{\mathrm{I}\mathrm{z}}^{71}\text{離}$$\backslash \ovalbox{\tt\small REJECT}$$\ldots,$$\ldots,$$\mathrm{i}_{\sqrt}\backslash$

,

116
4.1

主要結果

超離散方程式$\sum_{j=1}^{N}\max(a_{j}x+b_{j})=\sum_{k=1}^{M}\max(c_{k}x+d_{k})$を考える。

I. 特定の交点が解になるための必要十分条件は次式が成り立つことである。

$p(j_{1)}k_{1})$$q(j_{1}, k_{1})$

$\Pi$

.

$=$

$\sum_{j=1}^{N}\max(a_{j}x+b_{j})|_{x=p(j_{1},k_{1})}$$=$$\sum_{k=1}^{M}\max(c_{j}x+d_{j})|_{x=p(j_{1},k_{1})}$

超離散方程式$\sum_{j=1}^{N}\max(a_{j}x+b_{j})=\sum_{k^{\wedge}=1}^{M}\max(c_{k}x+d_{k})$は次式に形に書き換えられる。
$\min_{k=1}^{M}(\max_{1}^{N}(a_{j}xj=+b_{j}-c_{k}x-d_{k}))=0$

この場合特定の交点 $p(j_{1}, k_{1})$ が解になるための必要十分条件は次式が成り立つことである。
$\min_{k=1}^{M}(\max_{1}^{N}(a_{j}xj=+b_{j}-c_{k}x-d_{k}))|_{x=p(j_{1},k_{1})}=0$

最後に$\mathrm{I}\mathrm{I}$の結果を使って一般的超離散方程式$\sum_{j=1}^{N}\max(a_{j}x+b_{j})=\sum_{k=1}^{M}\max(c_{k}x+d_{k})$を数値的に解$\langle$

REDUCE Program と最後に 6 個の方程式の解の計算例を以下に示す。

Welcome to Reduce (Forbs System Co.Ltd)
REDUCE 3.7,
nil . . .
patched””
1: in a:.red ;;
a:$15-\mathrm{J}\mathrm{a}\mathrm{n}-99$$\backslash \max-\mathrm{p}\mathrm{l}\mathrm{u}\mathrm{s}-\mathrm{e}\mathrm{q}2$$0/\triangleright^{\mathrm{o}\mathrm{u}\mathrm{t}}\uparrow’$Za$\backslash \max-\mathrm{p}\mathrm{l}\mathrm{u}\mathrm{s}-\mathrm{e}\mathrm{q}2.\log’’$$: \backslash \max-\mathrm{p}\mathrm{l}\mathrm{u}\mathrm{s}-\mathrm{e}\mathrm{q}2$$9/0\mathrm{J}\mathrm{u}\mathrm{l}\mathrm{y}29,04$. red$\mathrm{t}\mathrm{o}$117Solve the max-piu equations
The equation to be solved) $= \max$ ((forcollect$—^{\mathrm{Q}}/_{0}^{\mathfrak{g}}/_{0}$$0/_{u}\%----$$\mathrm{s}$$—–^{0}/_{u^{0}}/_{l}^{0}/_{\theta}$$\iota_{0}/\%\%^{----}$$0/_{0} \max$$\mathrm{h}\mathrm{l}(\mathrm{j},\mathrm{x})$$\mathrm{j}:=1:\mathrm{n}\mathrm{n}$$\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{j}:=1:\mathrm{n}\mathrm{n}$collect$\mathrm{h}\mathrm{r}(\mathrm{j},\mathrm{x})$

)

where

$0/\mathrm{Q}$%%load sets$load assist$
operator
operator check;$\mathrm{h}1(\mathrm{j},\mathrm{x})$$:=\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{a}\mathrm{a},\mathrm{j})*\mathrm{x}+\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{b}\mathrm{b}_{2}\mathrm{j})$$\mathrm{h}\mathrm{r}(\mathrm{k},\mathrm{x})$$:=\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{c}\mathrm{c},\mathrm{k})*\mathrm{x}+\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{d}\mathrm{d},\mathrm{k})$$\mathrm{a},\mathrm{b},$$$$\mathrm{c},\mathrm{d},\mathrm{x},\mathrm{e}\mathrm{q}0,\mathrm{e}\mathrm{q}\mathrm{l},\mathrm{e}\mathrm{q}2,\mathrm{e}\mathrm{q}3,\mathrm{f},\mathrm{g},\mathrm{h}1_{2}\mathrm{h}\mathrm{r}$;nO: =12$Range of the parameter ,b.–$:=12$ %-- Range of the parameter ,d.–$A number of terms in the left hand0$
nn1
A number of terms in the right hand
mm1: $=7$$\mathrm{a}$$\Phi/_{\phi}--$$\mathrm{c}$$\mathrm{m}\mathrm{O}$$:^{=}1$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}--\%^{\mathfrak{g}}/_{\iota}$$\mathrm{Q}/_{f}-$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}--^{\mathfrak{g}}/_{\theta}^{\mathfrak{g}}/_{\sigma}$$\epsilon/_{0}-$$l/_{0}^{\mathfrak{g}}/_{0}--\mathrm{T}\mathrm{r}\mathrm{y}$

for

$6$

$\mathrm{s}:=1:6$

times
do

$—\%^{0}/_{9}$$<<$%%- Initial data set
aal:
ccl

$=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}$$\mathrm{n}\mathrm{n}\mathrm{l}$)$, mml ) $Simplify the data set$:=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}$$\%^{0}/_{\iota}--$(nO,$—-^{0}/\emptyset \mathfrak{g}/\alpha$($\mathrm{m}\mathrm{O}$$—^{0}/_{l}^{0}/_{0}$$\mathrm{s}\mathrm{a}\mathrm{a}:=\mathrm{m}\mathrm{k}\mathrm{s}\mathrm{e}\mathrm{t}(\mathrm{a}\mathrm{a}\mathrm{l})$$\mathrm{s}\mathrm{c}\mathrm{c}:=\mathrm{m}\mathrm{k}\mathrm{s}\mathrm{e}\mathrm{t}$

sac:
aa:
cc
nn

$=\mathrm{s}\mathrm{a}\mathrm{a}$(ccl)$

intersect scc$$=\mathrm{m}\mathrm{k}\mathrm{s}\mathrm{e}\mathrm{t}(\mathrm{s}\mathrm{a}\mathrm{a})\backslash \mathrm{s}\mathrm{a}\mathrm{c}$$:^{=}\mathrm{m}\mathrm{k}\mathrm{s}\mathrm{e}\mathrm{t}(\mathrm{s}\mathrm{c}\mathrm{c})\backslash \mathrm{s}\mathrm{a}\mathrm{c}$$:^{=}1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(\mathrm{a}\mathrm{a})$$\mathrm{m}\mathrm{m}:=\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}$(cc)$$\mathrm{b}\mathrm{b}:=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{l}\mathrm{i}$st (nO,$\mathrm{n}\mathrm{n}$)$$\mathrm{d}\mathrm{d}:=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}(\mathrm{m}0,\mathrm{m}\mathrm{m})$$%%-- Possible solutions to the ultradiscrete algebraic
off$\mathrm{f}$$\mathrm{f}$oror$\mathrm{n}\mathrm{a}\mathrm{t}_{i}$$\mathrm{j}$$:=1$$\mathrm{k}:=1$$\%^{4}/_{\mathfrak{g}}--\mathrm{T}\mathrm{h}\mathrm{e}$: nn do: mm doequation to be solved$\mathrm{h}1(\mathrm{j},\mathrm{x})$$\mathrm{h}\mathrm{r}(\mathrm{k},\mathrm{x})$$:=\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{a}\mathrm{a}, \mathrm{j})*\mathrm{x}+\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{b}\mathrm{b},\mathrm{j})$$$:=\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{c}\mathrm{c},\mathrm{k})*\mathrm{x}+\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{d}\mathrm{d},\mathrm{k})$$–^{0}/_{\theta}\%$$\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}.--^{0}/_{0}^{\mathfrak{g}}/_{\alpha}$

118
on

$\mathrm{n}\mathrm{a}\mathrm{t}$;write $\max$ ( or$\mathrm{f}$$|’=^{11}$off, $\max$ (for$\mathrm{n}\mathrm{a}\mathrm{t}$$\mathrm{k}:=1$:$\mathrm{m}\mathrm{m}$$\mathrm{c}\mathrm{c}$,k)$x part$+$$\mathrm{j})$$(\mathrm{d}\mathrm{d},\mathrm{k})$),);$\mathrm{i}$$\mathrm{e}\mathrm{q}\mathrm{l}(\mathrm{x}):=\min$($\mathrm{j}1$$:=1$$\mathrm{x}(\mathrm{j}1,\mathrm{k}1)$:

collect
solutions –Z7;$\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{k}:=1:\mathrm{m}\mathrm{m}$$\%^{0}/0--\mathrm{P}\mathrm{o}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{b}1\mathrm{e}$or$(\mathrm{a}\mathrm{a},\mathrm{j})*\mathrm{x}+\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{b}\mathrm{b},$The traIlSformed equat on —%%$l/0\mathfrak{g}/\mathfrak{g}---$$\mathrm{f}$collect partcollect part ($\mathrm{j}:=1:\mathrm{n}\mathrm{n}$$\mathrm{n}\mathrm{n}$do$\mathrm{f}$or$\mathrm{k}1$

$:=1$

:

$\mathrm{m}\mathrm{m}$$\max(\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{j}:=1:\mathrm{n}\mathrm{n}$collectdo$:=-(\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{b}\mathrm{b}, \mathrm{j}1)-\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{d}\mathrm{d},\mathrm{k}\mathrm{l}))/(\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{a}\mathrm{a},\mathrm{j}1)-\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}(\mathrm{c}\mathrm{c},\mathrm{k}1))$

counterl: $=0$$\mathrm{O}\mathrm{Z}\mathrm{l}--\mathrm{C}\mathrm{h}\mathrm{e}\mathrm{c}\mathrm{k}$forthe possible solutions$\mathrm{j}1:=1:\mathrm{n}\mathrm{n}$do for$\mathrm{k}1:=1:\mathrm{m}\mathrm{n}$$–^{\alpha}/0\%$

do

$<<$

if sub$(\mathrm{x}=\mathrm{x}(\mathrm{j}1,\mathrm{k}1),\mathrm{e}\mathrm{q}\mathrm{l}(\mathrm{x}))=0$

then

$<<$

counterl:$\mathrm{x}$$=\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{l}+1$(counterl):$=\mathrm{x}(\mathrm{j}1,\mathrm{k}1)$

$>>$
$>>$
$4/\mathfrak{g}\mathfrak{g}/\alpha---$

write
write

,

The set of solutions$\mathrm{x}\mathrm{x}:=\mathrm{m}\mathrm{k}\mathrm{s}\mathrm{e}\mathrm{t}$(for$\mathrm{s}:=1:$$|’----------\mathfrak{l}’,$$—\%^{\mathfrak{g}}/$counterl collect$\mathrm{s}:=\mathrm{s},$$\mathrm{x}(\mathrm{s})$)$11———-$ $”$>>$$\max(\mathrm{x}+5,2*\mathrm{x}+9,6*\mathrm{x},8*\mathrm{x}+3)=\max(9*\mathrm{x}+10,10*\mathrm{x}+4)$$\mathrm{x}\mathrm{x}$$:^{=}\{(-1)/7\}$$———-\mathrm{s}$$:^{=}1$———-$$\max(2*\mathrm{x}+3,7*\mathrm{x}+7)=5*\mathrm{x}+2$

xx

$:=$

$\{\}$$$———-\mathrm{s}$$:^{=}2$———-$$\max(5*\mathrm{x}+10,9*\mathrm{x}+3,10*\mathrm{x}+1)=\max(3*\mathrm{x}+5,4*\mathrm{x}+3,6*\mathrm{x})$$\mathrm{x}\mathrm{x}$$\mathrm{h}\mathrm{l}(\mathrm{j},\mathrm{x})-\mathrm{h}\mathrm{r}(\mathrm{k},\mathrm{x}))$$:=\{(-5)/2\}$)

119$———-\mathrm{s}$

$:=3$

———-$

$\max(2*\mathrm{x}+6,3*\mathrm{x}+10,7*\mathrm{x}+2)=\max(11,6*\mathrm{x}+8)$xx$:=\{2/3,1/3,6\}$$———-\mathrm{s}$$:^{=}4$———-$$\max(0,2*\mathrm{x}+2,11*\mathrm{x})=\max(3*\mathrm{x}+5,4*\mathrm{x}+1,8*\mathrm{x}+4)$xx$:^{=}\{(-5)/3,4/3\}$$———-\mathrm{s}$$:^{=}5$———-$$\max(2*\mathrm{x}+9,4*\mathrm{x},8*\mathrm{x}+4)=\max(6*\mathrm{x}+4,9*\mathrm{x}+1,10*\mathrm{x}+7)$$\mathrm{x}\mathrm{x}$$:^{=}\{1/4\}$$———-\mathrm{s}$end;$:^{=}6$———-$