32.スパイ達の接触


  • Global Moderator

    「自明」で久々に数学の言い回しを思い出しました。独特ですよね。

    例(笑):
    朝の卵かけごはんが美味いことは自明であり、我々は高々4万回程度でしかこれを味わうことはできない。任意の醤油が、ほとんど至るところで調味料として使用可能である。朝食を経て昼食に向かう気分は連続であるが、その微分可能性の証明はNP困難であるという予想がなされている。しかし、昼食への期待は有限であり、夕食への期待と双対関係にあるとしても一般性を失わない



  • ソムさん

    あー 自明って 数学でもよく使われるコトバでしたね。

    数学方面では「証明なんてわざわざする必要がないほどに明らか」みたいなニュアンスであったかと。

    ---- >8 ------- >8 ------- >8 --- チョッキン

    《朝食を経て昼食に向かう気分は連続であるが、その微分可能性の証明はNP困難であるという予想がなされている。》

    コトバのミックスサラダですね。
    むずがゆくてじたばたいたしました。

    野暮ですがマジレスいたしますと、

    いたるところ微分不可能な一変数実数関数で連続関数であるものが存在します。

    ■御参考:岡本による,いたるところ微分不可能な関数について(PDF)
    http://cm.hit-u.ac.jp/~kobayashi/topics/okamotofunc.pdf


  • Global Moderator

    32.スパイ達の接触で@Hannibalさんが発言 :

    野暮ですがマジレスいたしますと、
    いたるところ微分不可能な一変数実数関数で連続関数であるものが存在します。
    ■御参考:岡本による,いたるところ微分不可能な関数について(PDF)

    朝食を経て高まる昼食への期待は、確かにご紹介の岡本関数に似ているかもしれません(笑 ぎざぎざ変動しますし。

    実在のものでは、ブラウン運動をする粒子の軌跡なんかは、「連続でいたるところで微分不可能」というような雰囲気がありますね。



  • 2n-5問題、まだ考えています。
    オーバーヒートしている頭が夏バテです。

    次に書くような、こんなアイデアを思い付きましたが結実していません。

    諜報メモには以下のような事柄が書かれていてもパズルの本質を逸脱しません。

    【赤い字で】《発:A⇒B:着》

    これはAが調査した内容をメモにして 最終的に Bに渡されるべき諜報メモであるという意味です。

    Aが用意する諜報メモは、以下の5枚です。

    《発:A⇒B:着》
    《発:A⇒C:着》
    《発:A⇒D:着》
    《発:A⇒E:着》
    《発:A⇒F:着》

    同様にしてA以外の他のエージェントが用意する諜報メモにも【赤い字で】《発⇒着》が明記されているものとします。

    さて、諜報メモに赤い字で《発⇒着》が書かれている設定を追加しました。

    さらに設定を追加します。

    赤い字の《発⇒着》とは別に、発着を逆にした【青い字】の添え書きが以下のように記されているものとします。

    【赤い字で】《発:A⇒B:着》
    【青い字で】《発:B⇒A:着》

    ※他の諜報メモもすべて同じで、発着を逆にした【青い字】の添え書きがあります。
    たとえば
    【赤い字で】《発:C⇒F:着》
    【青い字で】《発:F⇒C:着》

    この【青い字】の添え書きは……

    (続く)



  • さて、
    各エージェントが諜報メモを作成し、互いに接触して諜報メモを手渡しし、最終的に全員の情報の同期を取る手順を問題にしていたのでした。

    最終的局面では、たとえばAの手元には、【赤い字】で

    《発:B⇒A:着》
    《発:C⇒A:着》
    《発:D⇒A:着》
    《発:E⇒A:着》
    《発:F⇒A:着》

    の【赤い字の】諜報メモがあります。

    そして同時に青い字の添え書き

    《発:A⇒B:着》
    《発:A⇒C:着》
    《発:A⇒D:着》
    《発:A⇒E:着》
    《発:A⇒F:着》

    の諜報メモがAの手元にあることになります。

    ===

    各エージェントの接触の様子を時系列順に全てビデオテープにとっておいて、今度は時間を逆転させてビデオを逆回しで見ることにします。

    すると青い字の添え書きに従って諜報メモが引き渡されているように見えるに違いありません。

    時系列について正順と逆順とについて両方考え、赤い字と青い字の諜報メモの引き渡しの手数をともにカウントしたときに、

    《最適手順をとっても手数は2n−4を下回らないこと》を示せるのではないか?

    と着想を得て、あれこれ場合分けをしてカウントいたしましたが、

    とうとう根を上げました。

    以上、ご報告でした。



  • 最初に試みたのは以下のようなものです。

    時系列正順で赤い字の発着を意識し、最初に全情報を集めた人物が2人いるケースのみを考えます。(双方向伝達では同時に2人発生することがあります)
    このとき、それよりも前に少なくともn−2回の接触があるはずです。
    また、時系列逆順で青い字の発着を意識し、最初に全情報を集めた人物が2人いるケースのみを考えます。このとき、それよりも前に少なくともn−2回の接触があるはずです。
    さて、あるひとつの接触が両者に含まれているようなことは絶対にない、……を示せれば、全体の手数は
    2n−4を下回らないのですが…… はてさて?


  • Global Moderator

    @Hannibal さん

    《最適手順をとっても手数は2n−4を下回らないこと》を示せるのではないか?

    ある n について、2 n -4 を下回らないことを証明

    n+1 について証明

    というやり方は可能でしょうか?(数学的帰納法)。1人増えると、伝達回数が最低2回は増えることが証明できればよいです。



  • @ソム さん
    昔取った杵柄で取り込み中【WEBやら書庫の本やら昔のノートやら・・・(^^♪】ですが、一言コメントです。
    2N-3から2N-4に変化する時(N=4)、2ルート増えて1ルート陳腐化しています。
    数学的帰納法で証明するためには、同様のルート陳腐化が生じないことも証明する必要があると思いますが、証明を考え付きません。逆に無限降下で証明できないかとも考えてみたのですがorz



  • ソムさん

    四色問題の証明は普通の数学的帰納法向きではありませんでしたがあんな感じ【どんな?】かもしれませんね。

    不可避集合を用意しておいて、どんな地図にもその部分には不可避集合に含まれるものがある⇒そこに放電手続きでもって手術すると元の地図からは様変わりした地図が生まれるけれど国の数は少なくなっている。【でしたっけ?】


  • Global Moderator

    @Hannibal さん

    四色問題の証明は普通の数学的帰納法向きではありませんでしたがあんな感じ【どんな?】かもしれませんね。

    地図の塗り分けにおける四色問題については、コンピューターを使った場合分けによって証明されたという、表面的なことしか知りません。

    最近、どこかでもう少し詳しい話を書籍で読んだ気がするのですが、どこだったか探してみましたが分かりませんでした。夢で見たのかもしれません(笑

    今、Wikipediaで調べると、証明の根幹のアイデアが説明してありましたが、それがまた、難しくて読むだけではちゃんと理解できなさそうです:

    以下、https://en.wikipedia.org/wiki/Four_color_theorem より引用


    The proof showed that such a minimal counterexample cannot exist, through the use of two technical concepts (Wilson 2014; Appel & Haken 1989; Thomas 1998, pp. 852–853):

    • An unavoidable set is a set of configurations such that every map that satisfies some necessary conditions for being a minimal non-4-colorable triangulation (such as having minimum degree 5) must have at least one configuration from this set.
    • A reducible configuration is an arrangement of countries that cannot occur in a minimal counterexample. If a map contains a reducible configuration, then the map can be reduced to a smaller map. This smaller map has the condition that if it can be colored with four colors, then the original map can also. This implies that if the original map cannot be colored with four colors the smaller map can't either and so the original map is not minimal.


Log in to reply
 

Looks like your connection to パズルハウス was lost, please wait while we try to reconnect.