このブール代数の漸化式を誰か解いてください!
初期seedから日時を求める無謀な挑戦 - Plus Le Toolのために必要で、だけど自力ではどうしても解けそうにない問題があるので、それを解いていただきたい。
なお、以下で使う記号の定義については[id:plusletool:20130427:p2]を参照。
また、以下では独自に定義した関数 を使うが、これについては[id:plusletool:20130612:p1]を参照。
【!】この問題は解決しました。【!】
この問題は[id:plusletool:20130713:p1]の方法で解決しました。
皆様にご協力いただき、ありがとうございました。
解いてほしい漸化式はこれ。
(★1)
(※集合 は である。ただし、 のときは (空集合)とする。)
(※数列 は未知の数列であり、数列 , , , , は既知の数列である。初項はそれぞれ , , , , , である。)
(※変数 , , , , , はブール変数である。つまり、その値は または しかとらない。)
この(★1)を について解いていただきたい。
より正確に言うなら、 を の排他的論理和,論理積(,論理和,論理否定)の式で表していただきたい。
【追記】 がよく分からない人は、後述の「補足2」の(★3)が(★1)と等価なので、それを使ってください。
ちなみにこの漸化式の出処は補題:32bit符号なし整数変数間の算術和演算をブール関数で表す - Plus Le Toolの後半部分(試行錯誤で解いて失敗した例もここの最後に書いた)。
この漸化式はBW/BW2で初期seedから起動日時を直接計算するために必要な式の1番難しい部分なので、これが解ければ初期seedからの日時逆算が可能になる! ……かもしれない(実際にできるかどうかは解いてみないことには分からない)。
解けた方はもちろん、解けそうで失敗した方も考え方を教えてもらえればヒントになるかもしれないので、ぜひコメント欄(または自分のブログなどにでも)に書いていってください。
また、式や記号の意味などで分かりにくい点があれば質問に答えます。
数学が得意な人も苦手な人も、ぜひチャレンジしていただきたい。
どうかよろしくお願いします。
補足1
関数 が分かりにくい人のための補足。
(★1)では なので、 は実際には次の形の式である。
(*1)
■ のとき
[tex:\left\{\,\begin{array}{lcl}\mathfrak{C}_{r}\left(\Phi_{i}\right)&=&0\;\;\;\;\left(\,\mathrm{as}\;r<0\,,\,5
これを使って(★1)から を消去すると、(★2)のようになる。
(★2)
……見ての通り、変数が多すぎてわけがわからないよ。
この式は各括弧の中が , , , , の対称式になっており、その対称式部分を に置き換えたのが(★1)ということだ。
補足2
数列 , , , , を次のように定義すれば、(★1)でわざわざ独自関数 を使わなくてもいいことに気づいた。
(*2)
この , , , , を使うと、(★1)は次のように書き直せる。
(★3)
><
(※変数 は未知のブール変数であり、変数 , , , , は既知のブール変数である。)
(★1)と(★3)は等価なので、 がよく分からない場合は(★3)を使ってください。
なお、 の性質から、 , , , , の間には次の関係が成り立つ。
(*3)
(※論理積は交換則が成り立つ(つまり乗算する順序を変えても同じになる)ので省略した。)
その他の の性質は、今回は使えないので省略する。
更新履歴
- 13/06/17
- 漸化式の初期条件として , を追加。
数列の初項が , , , , , であることを追記。 - 13/06/18
- 補足1,補足2を追記。