一般的な解法は？ ( 同じ数値をN回使用してMを表現する )

質問

すぐ下の q=830386 に触発されて便乗質問です。

同種の問題 (クイズ、数学パズル) は古来よりあるようですが、一般解 (N、Mがどんな値の場合でも、同じアプローチで解を導けるという意味です) は存在するのでしょうか？
私の知る限り、この種の問題のほとんどでは、解答しか記載されておらず、思考過程が示されていないように思います。
示された正解の検証は容易ですが、プロセスが示されていなければ、解決に到る手順を追体験することが困難に感じます。

偶然の「閃き」に頼る以外ない、ということでしょうか？

# 暗号解読やパスワードクラッキングでは、数学的、論理学的なアプローチばかりではなく、偶然の僥倖に頼る方法 (「辞書攻撃」、等) も少なくないようですが....。

整数論の専門家の方、コメントをお待ちしております。

回答No.3

stomachman · ベストアンサー

専門家では全然ないですが。
数xをN個と演算子を組み合わせて任意の整数Mを作れ、という問題を考えます。
二項演算子は二つの数をinputして一つの数をoutputする訳ですから、演算ひとつにつき数の個数がひとつ減っていきます。従って、二項演算子の組み合わせで作れる数は高々有限である。
ここはどうしても、単項演算子を使って、数の個数が目減りしないようにしなくちゃダメだとわかります。

で、q=830386 では単項演算子である√や!を使った解も出ていました。
そこでです。問題のご主旨からはいささかはずれますけれど、もし√とlogを使って良ければ、と考えますと：

xを1でも0でもない正の実数、log_x(y)をxを底とするyの対数とするとき、√√…√を√がM(M≧0)個重なったものとすると
-log_2(log_x(√√…√x))
=-log_2(log_x(x^((1/2)^M)))
=-log_2(2^(-M))
=M

(a) ですから、N=5のとき、
±log_((x+x)/x)(log_x(√√…√x))
とやれば、同じ数値xをN回使って任意の整数が作れます。（±は非負の整数を作るときは-、負の整数を作るときは+にする。）
(b) N=6なら、
±-log_((x+x)/x)(log_(x/√x)(√√…√x))
(ただし√はM+1個重ねる）によって、全ての整数Mが作れる。

一般にN≧5であれば、Nが奇数のときは(a)、Nが偶数のときは(b)に
+(x-x)+…+(x-x)
を追加すれば良い。

さらに、x=(2^k) (k＞1)のときには、たとえば
±log_(√…√x)(log_x(√√…√x))
（ここに、最初の(√…√x)は√をk個重ねたもの)ですとか、
±log_((√…√x)/(√…√x))(log_x(√√…√x))
（ここに、最初の(√…√x)は√をk-1個重ねたもの、二つ目の(√…√x)は√をk個重ねたもの）によって、N=3,4でも任意のMが作れます。

お礼

返信が遅くなりました。
コメントありがとうございます。
しかし、残念ながら、私の数学力では、上記内容の是非、妥当性が計りかねます。
学校時代に勉強していなかった結果ですので、自業自得としか言いようがありませんが、お恥ずかしい限りです....。

回答No.2

neKo_deux

同じく、解析的に解く方法は見当がつかないです。

シラミつぶしよりは効率的な解の探索方法として、遺伝的アルゴリズム及び遺伝的プログラミング(Genetic Programing:GP)というものがあります。

元ネタの質問の例ですと、「4を4つ使って表せる数」の式を、

(4-4)+(4*4)=16:
＋━－━４
┃□┗━４
┗━×━４
□□┗━４

((4*4)*4)-4=12:
－━×━×━４
┃□┃□┗━４
┃□┗━４
┗━４

4+((4-4)*(4/4))=4:※但し、4が５個なので０点
＋━４
┗━×━－━４
□□┃□┗━４
□□┗━÷━４
□□□□┗━４

のような２進木の構造として符号化(？)して、
・計算・評価結果に応じて不適応な個体を破棄する「選択」
・枝を交換する「交叉」
・数値や演算子を変更する「突然変異」
を繰り返して、解に近づこうとする方法です。

逆ポーランド記法を使うと、
44+44*-
44*4*4-
444-44/*+
のような表記？符号？

四則演算の演算子は２項演算。
カッコは演算順序の修飾なので上のような木の結合順序で吸収。
４４、√、階乗の扱いも、２項演算子や単項演算子として処理できる気もしますが、微妙かも。
(4!)!なんてのを認めると、解も有限でなくなりますし。

あまり見通し良くないかも。

お礼

コメントありがとうございます。
多忙のため、返信が遅くなりました。

> 遺伝的アルゴリズム
用語は聞いたことがあるものの、詳細はよく知りません。
そもそも、学術、研究分野以外で実用の域に達しているのかどうか......？
(本題から外れますが)

> (4!)!なんてのを認めると、解も有限でなくなりますし。
階乗だけに限って言えば、ネスト(入れ子)すればするほど計算値は大きくなりますので、「○○回以上の繰り返しは (他の箇所の演算内容如何を問わず) 目標値以内に収斂し得ない」と見做して探索を打ち切ればよいと思われます。
しかし、N乗根や対数、除算などと複合的に組み合せると、計算値は「大きくも小さくもなり得る」ので、有限回数の探索で収束するのがむずかしいかもしれません。
(残念ながら、私の数学力では、よくわからないのが正直なところです)

回答No.1

liar_adan

大学で整数論をやっていましたが、
この問題を一般的に解く方法はまるで見当つきませんし、
おそらく、そんな方法は存在しないと思います。

方法があるとすれば、
コンピュータでシラミつぶしに計算する方法です。
数字と、計算記号の組み合わせは、しょせん有限個なので、
計算する方法があるかないかは有限回の探索で出せます。

お礼

> この問題を一般的に解く方法はまるで見当つきませんし、
> おそらく、そんな方法は存在しないと思います。

予想通りのコメント、ありがとうございます。(^-^;
やはり、そうなのですね。

> 方法があるとすれば、
> コンピュータでシラミつぶしに計算する方法です。
初期の囲碁、将棋ソフトで使用されたアルゴリズムですね。
言わば、「ブルドーザ方式」とでも言いましょうか。(正しい呼び方なのか、わかりませんが....)

囲碁や将棋の世界では、組み合せの数が天文学的なため、この手法は効率が悪過ぎるということで、現在では廃れていますが、組み合せが比較的少ない場合 (オセロの終盤など) は、確かに有力な手法ですね。

人間が解く場合、すべての組み合せを検証するより、短い時間で解けてしまいます (時間が掛かる場合、解けずに「白旗」となる公算が大) が、どのような思考過程によるのか、興味深いところです。
(数学のテーマから逸脱してしまいますが)

ありがとうございました。

補足

> # 暗号解読やパスワードクラッキングでは、数学的、論理学的なアプローチばかりではなく

暗号はともかく、パスワードは数学的に生成するものではないし、平文を加工して作るものでもないので、数学的な解法など存在しませんね。
(ソーシャルエンジニアリングや通信傍受などは、数学、論理学とは別次元)
ここで引き合いに出すには不適切でした。

訂正致します。m(_ _)m