このブログは、旧・はてなダイアリー「檜山正幸のキマイラ飼育記 メモ編」(http://d.hatena.ne.jp/m-hiyama-memo/)のデータを移行・保存したものであり、今後(2019年1月以降)更新の予定はありません。

今後の更新は、新しいブログ http://m-hiyama-memo.hatenablog.com/ で行います。

スパイダーの構成不可能性定理を変更 (A18)

当初(2018-12-18)、「スパイダーパズル (A17P10)」において、「次の定理を証明せよ」という問題を出しました。

  • 構成不可能性定理: プロファイルの形が Γ → Δ で、リストΓ内に出現するBの個数が、リストΔ内に出現するBの個数より少ないとき、このプロファイルに対してスパイダーは構成できない。

この構成不可能性定理を出したのは、以下のプロファイルを持つスパイダーが構成不可能であることを示すことが目的です。

  • A → A, B
  • C → A, B

しかし、上記の定理(定理じゃないが)は、反例があって、B → B, B というプロファイルを持つスパイダーは構成できます。

     ☆
  ========= Ent
     B
   ------ dup
    B  B

間違いました。次のように変更します。

  • 構成不可能性定理: プロファイルの形が Γ → Δ で、リストΓ内にBが出現せず、リストΔ内にBが出現するとき、このプロファイルに対してスパイダーは構成できない。