A - +3 +5 +7

3つの値を同じにする問題は割と良く見る気がします。そして、この系統の問題は、差をどのように詰めるのか、という視点で見ると解ける場合が多いです。

今回、 $x_2-x_1$ 及び $x_3-x_2$ をそれぞれ $p,q$ とおきます。目標は、 $p=q=0$ にすることです。

操作によって $p,q$ がどのように変化するか考えます。例えば、(+3, +5, +7)の操作の場合、 $p,q$ はそれぞれ+2, +2されます。

操作として考え得る6通りについて、 $(p,q)$ がどのように変化するか、その変化量を書き出します。

(+2, +2), (+4, -2), (-2, +4), (+2, -4), (-4, +2), (-2, -2)

ここからわかることとして、 $p,q$ は偶数しか変化しません。
そこで、 $p,q$ いずれかが奇数である場合、0にするのは不可能です。

以下、 $p,q$ が偶数である場合を考えます。
わかりやすくするため、 $p,q$ 及び操作による変化量を全て2で割っておきます。
変化量は、
(+1, +1), (+2, -1), (-1, +2), (+1, -2), (-2, +1), (-1, -1)
です。

$p,q$ が異なる場合、(+2, -1), (-1, +2), (+1, -2), (-2, +1)のいずれかで $p=q$ にした後、(+1, +1), (-1, -1)のいずれかで0にすることになります。

そこで、次は $q$ と $p$ の差を考えます。 $r=q-p$ とおきます。

(+2, -1), (-1, +2), (+1, -2), (-2, +1)では、 $r$ は3の倍数ずつしか変化しません。そこで、 $p,q$ が3の倍数でない場合、0にすることは不可能です。

以下、3の倍数であるとします。
このままだと変化量が多く、ややこしいので、適切に値を入れ替えて、 $p,q$ が非負整数かつ、 $p\leq q$ となるようにします。

[補足]
値を入れ替えてもよい理由を説明します。
例えば $x_1,x_2,x_3$ にそれぞれ(+3, +5, +7)するという操作を考えます。

値を $x_2,x_1,x_3$ と入れ替えた場合に、操作についても入れ替えて(+5, +3, +7)にすると、先程の操作を再現できます。

値を入れ替えることで不可能となるような操作が無いことから、値を入れ替えても問題ない、と言えると思います。

こうしておくことで、選ぶべき変化量は(+1, -2), (-1, -1)に限定されます。

$r\geq 0$ になっていることから、最小の操作回数は以下のようになります。

geam1113’s diary