エレファント・ビジュアライザー調査記録

ビジュアルプログラミングで数式の変形を表すことを考えていくブロクです。

たらい回し関数(3)

たらい回し関数

(3)の場合を \delta(x, y, z) に関する帰納法の仮定から証明することができます。

(3) x > y かつ y > z ならば t(x, y, z) = x

x - 1 \le y のときは定義より t(x-1, y, z) = y、 x - 1 > y のときは \delta(x, y, z) に関する帰納法の仮定(*)より t(x-1, y, z) は定義されていて
t(x-1, y, z) = \begin{cases} y & (x-1 \leq y\ のとき) \\ z & (x-1 > y \ かつ \ y \leq z \ のとき) \\ x-1 & (x-1 > y \ かつ \ y > z \ のとき) \\ \end{cases}
となります。よって
\begin{eqnarray*} t(x, y, z) & = & t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y)) \\ & = & \begin{cases} t(y, z, x) & (x - 1 \le y \ かつ \ y - 1 \le z \ のとき) \\ t(y, x, x) & (x - 1 \le y \ かつ \ y - 1 > z \ のとき) \\ t(x-1, z, x) & (x - 1 > y \ かつ \ y - 1 \le z \ のとき) \\ t(x-1, x, x) & (x - 1 > y \ かつ \ y - 1 > z \ のとき) \\ \end{cases} \\ & = & \begin{cases} x & (x - 1 \le y \ かつ \ y - 1 \le z \ のとき) \\ x & (x - 1 \le y \ かつ \ y - 1 > z \ のとき) \\ x & (x - 1 > y \ かつ \ y - 1 \le z \ のとき) \\ x & (x - 1 > y \ かつ \ y - 1 > z \ のとき) \\ \end{cases} \\ & = & x \end{eqnarray*}