『今週の問題』第190回　解答

◆東京都　ぽこぺん さんからの解答

【問題１】

[ 7: 5回] C4+4+4/4+4=
[ 17: 5回] C4*4*4+4/4=
[ 27: 7回] C4+4*4-4*4-4/4=
[ 37: 7回] C4+4*4*4+4/4+4=
[ 47: 7回] C4+4+4*4*4-4/4=
[ 57: 8回] C4*4*4-4-4*4+4/4=
[ 67: 7回] C4*4*4*4-4/4+4=
[ 77: 8回] C4*4+4*4-4*4+4/4=
[ 87: 9回] C4*4+4*4*4-4/4+4+4=
[ 97: 8回] C4*4+4+4*4*4+4/4=

【問題２】

以下で，文字はすべて整数とします。

表示させる数を qn+r (0<r<n) とするとき，
n から qn+r に達するときの最小演算回数 （[n]キーを押す回数）
を f(n) とします。
f(n)＝1 です。

この過程は，ある適当な a（a≧0）に対して，

という3つの部分に分けることができます。
各部分における操作とその最小演算回数は，以下のように決定します。
（演算の形で最後の = は省略します）

[1]

(1-1)

rn (1≦r≦n）については，
nを作るには“C n”(1回)
n2 を作るには“C n * n”(2回)

であり，その間の数に関しては 

n → 2n → … → rn ← … ← (n-1)n ← n2
1　　 2　　(+ n)　　　(- n)　　3　　　　2
のように両方向から近づくときの最小な方を選べばよいから
f(rn) ＝ r　　　（r≦[n+2/2] のとき）
      ＝ n-r+2　（r＞[n+2/2] のとき）
となります。

(1-2)
それ以降は，長さ n2 の区間ごとに，区間の上限での値を

f(kn2) ＝ f(kn)＋1 　（k＝2，3，…）
（演算は“* n”を追加）

によって定め，途中の値を

(k-1)n2 → (k-1)n2+n → …
　　→ (k-1)n2+rn ← … ← kn2-n ← kn2
（演算は→のとき“+ n”を追加，←のとき“- n”を追加）

のように両方向から近づくときの最小な方として選びます。

[2][3]は両方を合わせて次のように求めます。

まず

g(kn+r) ＝ f(n(kn+r))＋1　　（k＝0，1，…）
（演算は“/ n”を追加することに対応）

により，[2]だけを使って求めた値 g(kn+r) を作ります。

次に，f(r) ＝ g(r)とし，k＝1，2，3，… に対して 

f(kn+r) ＝ f((k-1)n+r)＋1　（f((k-1)n+r)＋1 ≦ g(kn+r)）
        ＝ g(kn+r) 　　  　（f((k-1)n+r)＋1 ＞ g(kn+r)）
により下から n ずつ増やして近づくときの最小値 f(kn+r) の値を仮に定めます。

第1の式を選んだとき，演算は (k-1)n+r に対する演算に“+ n”を追加します。
第2の式を選んだときには，n(kn+r) に対する演算に“/ n”を追加します。

最後に，各 k に対して f(kn+r) と f((k-1)n+r) とを比較して，

　　f((k-1)n+r) ＞ f(kn+r)＋1

であれば，上から n ずつ減らして近づく方が操作が短いということだから，

f((k-1)n+r)の値を　f((k-1)n+r) ＝ f(kn+r)＋1　により修正し，その結果を同様に下に伝播させます。

このとき演算は，上の演算結果に“- n”を追加します。

以上で最小演算回数とそれを与える演算の内容が求まりました。

【感想・その他】

操作過程を表現する方法を見つけるまでの試行錯誤に一番時間がかかりました。

　　32
　　↑
４→８→12→16
　　｜
　　｜　24→28
　　↓　↑
　　２→６→10
などとやっていくうちにだんだん余白が狭くなり，別の紙に書き直したりと， 最終的に Excel で表現する形式を見つけるまでに相当苦労しました。

●ｎ＝４の結果，ｎ＝９の結果(Excel)

●perlによるプログラム

◆山梨県　Footmark さんからの解答

４を足しても４を引いても４を掛けても、必ず４の倍数である。
よって、４の倍数でない数を作成するには、１回は４で割らなければならない。

一般に、唯一許される数字キーを[ｎ]とすると、

【キー操作】Ｃ　ｎ(□ｎ…□ｎ)　×ｎ×…×ｎ　±ｎ±…±ｎ　÷ｎ　±ｎ±…±ｎ　＝
【ｎの回数】　 　　　ｐ回 　　　　　ｋ回　　　　　ｒ回　　　１回　　　ｑ回

のようにキー操作をすると、数値(ｐ'ｎk±ｑｎ±ｒ)が作成される。
このとき、[ｎ]を叩く回数は(ｐ＋ｋ＋ｑ＋ｒ＋１)回である。
ただし、□は最後は必ず＋である＋または×である。
当然のことだが、ｒ個の演算子もｑ個の演算子も、どちらもそれぞれ同一である。

このとき、ｐ,ｋ,ｑ,ｒは、それぞれ数値(ｐ'ｎ),(ｎk),(ｑｎ),(ｒ)を作成するｎの使用回数である。

それ故、作成する数を(ｐ'ｎk±ｑｎ±ｒ)の形で表したとき、
ｐ＋ｋ＋ｑ＋ｒ が最小になる表し方を求めればよいことになる。

例えば、唯一許される数字キーが[９]のとき、５５を作成するには[９]を叩く回数は、

５５＝６×９1＋１　　　　　とすると　Ｃ９＋９＋９＋９＋９＋９×９＋９÷９＝　の９回だが、
５５＝１×９2ー３×９＋１　とすると　Ｃ９×９×９＋９÷９−９−９−９＝　　　の８回で済む。

結局、本問における求めるキー操作は以下となる。
ただし、キーを叩く回数＝２([４]を叩く回数)＋１＝２(ｐ＋ｋ＋ｑ＋ｒ＋１)＋１

作成数キー操作[４]を叩く回数(p+k+q+r+1)
　７＝２*４1　　 　ー１Ｃ４＋４×４ー４÷４＝２＋１＋０＋１＋１＝５
１７＝１*４2　　 　＋１Ｃ４ｘ４ｘ４＋４÷４＝１＋２＋０＋１＋１＝５
２７＝２*４2ー１*４ー１Ｃ４＋４×４×４−４÷４−４＝２＋２＋１＋１＋１＝７
３７＝２*４2＋１*４＋１Ｃ４＋４×４ｘ４＋４÷４＋４＝２＋２＋１＋１＋１＝７
４７＝３*４2　　 　−１Ｃ４＋４＋４ｘ４×４ー４÷４＝３＋２＋０＋１＋１＝７
５７＝１*４3ー２*４＋１Ｃ４×４×４×４＋４÷４−４−４＝１＋３＋２＋１＋１＝８
６７＝１*４3＋１*４ー１Ｃ４×４×４ｘ４ー４÷４＋４＝１＋３＋１＋１＋１＝７
７７＝５*４2ー１*４＋１Ｃ４×４＋４×４×４＋４÷４ー４＝３＋２＋１＋１＋１＝８
８７＝５*４2＋２*４ー１Ｃ４×４＋４×４×４ー４÷４＋４＋４＝３＋２＋２＋１＋１＝９
９７＝６*４2　　 　＋１Ｃ４×４＋４＋４×４×４＋４÷４＝４＋２＋０＋１＋１＝８

◆東京都　明 さんからの解答

【問題１】

NUMBER = 7

C4+4*4-4/4=7
C4*4-4/4+4=7
C4+4+4/4+4=7
たたいた回数: 5

NUMBER = 17

C4*4*4+4/4=17
C4/4/4+4*4=17
たたいた回数: 5

NUMBER = 27

C4+4*4*4-4/4-4=27
C4+4*4-4*4-4/4=27
たたいた回数: 7

NUMBER = 37

C4+4*4+4*4+4/4=37
C4+4*4*4+4/4+4=37
C4/4/4+4+4*4+4=37
C4/4+4/4+4+4*4=37
たたいた回数: 7

NUMBER = 47

C4*4-4*4*4-4/4=47
C4+4+4*4*4-4/4=47
たたいた回数: 7

NUMBER = 57

C4*4*4*4+4/4-4-4=57
C4*4*4-4*4+4/4-4=57
C4*4*4-4-4*4+4/4=57
たたいた回数: 8

NUMBER = 67

C4*4*4+4*4-4/4=67
C4*4*4*4-4/4+4=67
たたいた回数: 7

NUMBER = 77

C4*4+4*4*4+4/4-4=77
C4*4+4*4-4*4+4/4=77
たたいた回数: 8

NUMBER = 87

C4*4+4*4+4+4*4-4/4=87
C4*4+4*4+4*4-4/4+4=87
C4*4+4*4*4-4/4+4+4=87
たたいた回数: 9

NUMBER = 97

C4*4+4+4*4*4+4/4=97
たたいた回数: 8

【問題２】

唯一の数字キーを[ｎ]としたとき、ｎと*,/,+,-をたたいた結果を展開してｎの冪で整理すると、結果が整数の場合は以下のようになります。

N(k)*nk+N(k-1)*nK-2+・・・+N(2)*n+N(1)　（１式）
（ただしN(j)は整数）

逆にこの式を題意の電卓で実現するためには以下のようになります。

n(N(k)回),*,n,n(N(k-1)回),*,n,・・・・・,
n(N(2)回),*,n,n(N(1)回),/,n　　（２式）

ただし、n(N回)はnをN回加算（Nが正）もしくは減算（Nが負）することを示します。

Nが0のときは何もしません。

この時nをたたく回数は
|N(k)|+|N(k-1|+・・+|N(1)|+k　（３式）　　となります。

この回数を最小にすることを考えます。

ところで１式でN(3)以上の項がない場合は(２式）は
n(N(1)回),/,n,n(N(2)回)で実現した方が回数が１回少なくて済みます。

したがって１式は実現数≧n2+1　のときの一般式となります。

実現数≧n2+1　の時、

実現数を作るのに、nをたたく回数を最小で済ますためには

-(n-1) ≦N(j)≦n-1　（ただし最上位N(K)は常に正）

の範囲で３式を最小にするものを見つけることになります。

まず、n進数表示をつくります。

次に下の桁から順に
nが偶数のとき|N(j)|≧ n
2		+1、nが奇数のとき|N(j)|≧ n+1
2		 の場合、
桁上げをして補数をとる（-ｎする）ことにより回数を少なくすることができます。

この時、該当桁が１つ以上（ｎが奇数の時。偶数の場合は２つ以上）減って、桁上げで１つ増加。

ただし、最上位の場合、新しい桁ができるので桁上げでは２つ増加します。

したがってｎが奇数の時は最上位桁が
n+1
2		 となる時は補数をとらないようにします。（手順２）

次にnが偶数の場合は、下の桁から順にチェックし、
N(j)＝n/2の桁があるとき、すぐ上の桁が負の場合、桁上げをして補数をとることにより、桁上げで１つ減少させることができます。

また、n/2の桁が２桁続く時はそれぞれの桁を桁上げして補数をとることにより回数は変わりませんが、桁上げがされ、上の桁で回数を 減少させるチャンスができます。

ただし連続した桁の先頭が最上位の場合は新しい桁ができるため、桁上げで回数が増加してしまうので操作をしません。　　 （手順３）

手順３の後、上の桁へ手順２，手順３を適用することにより、回数を減少させることができます。

実現数≦n2-1　の時、

n(N(1)回),/,n,n(N(2)回)と
n(N(3)回),*,n,n(N(2)回),*,n,n(N(1)回),/,n (N(3)=1または0）

を比較して少ない方を採用します。

特に実現数＝n2-1　の時は、

n*n*n-n/n　が最小回数になります。（n≧3のとき）

●確認用のプログラム

アルゴリズムの確認用に１０進BASICでプログラムを作って
n2+1以上の場合のテストをしてみました。

●アルゴリズムの確認用プログラム（改訂版）

◆愛知県　Y.M.Ojisan さんからの解答

【問題１】

数値キー操作回数
７C4+4*4-4/4=7５
１７C4*4*4+4/4=17５
２７C4+4*4-4*4-4/4=27７
３７C4+4*4+4*4+4/4=37７
４７C4*4-4*4*4-4/4=47７
５７C4*4*4*4+4/4-4-4=57８
６７C4*4*4+4*4-4/4=67７
７７C4*4+4*4-4*4+4/4=77８
８７C4*4+4*4+4+4*4-4/4=87９
９７C4*4+4+4*4*4+4/4=97８

【問題２】

基本的にはｎ進数に表わして、各桁に対してはその値分ｎを加算ないし減算し、最後にｎで割る方法が考えられます。
ただし、各桁の数値は通常の０〜ｎ−１ではなく、
- n
2		〜n
2		 で考えます。

●（１） ｎが奇数の場合

＜作成手順＞

＜最小性の証明＞

　　まず（ ）がないので、*と/は桁移動としてのみ働く。
よって自然数をｎ進法で表記したときの各桁に対応する桁値は＋ｎまたは−ｎをその数入力する以外に方法はない。

ｎ2の位以上は±ｎで桁値相当を作成したあと、*nを作用させることで得ることが可能である。
しかし、１の位は./nを作用させなければならない。
一方ｎの位は最後に±ｎを作用させればよい。

一の位が負の場合は最初に「−」キーを押せないので０を作るためにn-nを余分に入れるか、ｎの位の数を前に持ち出すために*nを余分に入れる必要があり、後者でも通常より「ｎ」を２個損する。
従ってこの場合に限り、１の位を正にし、桁を減らした方が少なくなる場合がある。
即ちケース(b)である。

同様に最上位についても最上位の次の位を正にして桁数を減らしたほうが少なくなる。
即ちケース（ｃ）である。

桁数が固定されたとき、各位の数値の絶対値が(n-1)/2より大きければ、(n-1)/2以内に入るようにした方が、上位桁で１変化するのに対し、nが奇数の時はその桁で少なくとも１個減るので最小でない値を与えることはない。

●（２）ｎが偶数の場合

手順の基本は奇数の場合と同じである。
ただし、ある桁に対して-n/2を用いるべきかn/2を用いるべきか任意性があり、最小性が保証できない。
このため、全ての場合を探索する必要がある。

　◆ 問題へもどる

　◆ 今週の問題へ

数学の部屋へもどる