- 面白い問題おしえて～な 30問目
144 ：１３２人目の素数さん[sage]：2019/12/03(火) 19:02:30.44 ID:PHS8a67O - >>113
まず以下の証明の図の読み方の説明。
生命体を虫と呼ぶ。
◯は虫のいる点。
ーは虫を駆除する必要のある点、
㊀はその駆除する必要がある点に虫が現時点でいる状態である。
この虫を分裂させて㊀を消去する手順の有無を議論する。
コレらを格子状にならべた図式でAにおいて、そのような手順があるとき、その手順の最小値を最小駆除手数と呼ぶ。
存在しないときは無限大とする。
そのような図式X,A,B,C,‥においてXの最小駆除手数がA,B,C,‥の最小駆除手数の最小値以上のときXはA,B,Cに還元されると呼び、X|A,B,C,‥と表す。
左辺の最小駆除手数が右辺のそれの最小値より真に大きいとき強還元と呼ぶ。
|
- 面白い問題おしえて～な 30問目
145 ：１３２人目の素数さん[sage]：2019/12/03(火) 19:03:18.66 ID:PHS8a67O - 証明に現れる還元を全て列挙する。
コレらが還元になっている事は後で示す。
⑦以外は全て強還元である。
A～Gの図の定義も兼ねている。
①A|B (初手実行)
ーー ｜ ㊀ー
㊀ーー ｜ ー㊀ー
②B|C,D(初手実行)
｜ ◯
㊀ー ｜ ー㊀ ㊀㊀
㊀ー ｜ ー㊀ー、 ー㊀
③C|E(初手実行)
ー ｜ ー◯
㊀㊀ ｜ ㊀ー◯
④E|B(終端優先)
ー ◯ ｜ ㊀◯
㊀ー◯ ｜ ー㊀◯
⑤D|F,G(初手実行)
｜ ◯
㊀㊀ ｜ ㊀ー◯ ㊀㊀◯
㊀ ｜ ㊀、 ー◯
⑥F|B(終端優先)
◯ ｜ ◯ ◯
㊀ー◯ ｜ ー㊀◯
㊀ ｜ ㊀
⑦G|B(終端除去)
｜ ㊀◯
㊀㊀◯ ｜ ー㊀◯
|
- 面白い問題おしえて～な 30問目
146 ：１３２人目の素数さん[sage]：2019/12/03(火) 19:05:10.16 ID:PHS8a67O - >>144のリストが還元になっている事を示す。
・初手実行の還元は実際に初手として可能な全ての分裂を行った結果の図を右辺に列挙する事によって得られる。
右辺に並ぶ図の最小駆除手数は全て左辺の手数+１であるから還元図になる。
ー例ー
②B|C,D(初手実行)
｜ ◯
㊀ー ｜ ー㊀ ㊀㊀
㊀ー ｜ ー㊀ー、 ー㊀
・終端優先の還元は左辺図内のある生物を分裂させてもその子が他の全ての生物の分裂を阻害しないとき、その分裂を優先する最小手順解があることから、その分裂を実行した図を右辺に書く事によって得られる。
やはり右辺の図の最小駆除手数は左辺の手数+１であるから還元図となる。
ー例ー
④E|B(終端優先)
◯ ｜ ㊀◯
㊀ー◯ ｜ ー㊀◯
・終端除去の還元は⑦のみである。
⑦左辺の虫を除去する最小手順において左の虫をA、それが分裂したときに現れる上の虫をB、右の虫をCとする。
Bは要駆除点でなく、Bは以降のたの分裂を邪魔しないため最小手順においては分裂しない。
Cは要駆除地点にいるのでいくらか後に分裂し、その上の虫をD、右の虫をEとするとBが分裂しないのと同じ理由でD、Eも分裂しない。
よって⑦左辺の最小駆除手順においてAとその子孫が分裂する回数は高々二回である。
よってその手順からAとその子孫を取り除けば図
ーー
ー㊀㊀
の駆除手順が得られ、その手順数は⑦左辺のものよりちょうど2小さい。
逆に⑦左辺の図において、上図の除去を行った後、AとCの分裂を行えば⑦右辺の図の駆除手順となるので⑦左辺の最小駆除手数は上図のそれ+2以下である。
以上により上図の最小駆除手数は⑦左辺のそれよりちょうど2小さい。
さらに上図に初手還元と終端優先を行えば
㊀◯
ー㊀◯
が得られ、その最小駆除手数は上図のそれよりちょうど2だけ大きい。
以上により⑦の左辺と右辺の最小駆除手数はちょうど等しいので⑦は弱還元である。
ー例ー
⑦G|H(終端除去)
｜ ㊀◯
㊀㊀◯ ｜ ー㊀◯
|
- 面白い問題おしえて～な 30問目
147 ：１３２人目の素数さん[sage]：2019/12/03(火) 19:06:07.74 ID:PHS8a67O - 証明を完成させる。
Aの図の最小駆除手数が有限とする。
①によってAはBに還元されるらBのそれも有限である。
還元を"合成"することにより②～⑦によってBはB自身に還元される。
すなわち
B|B
なる形の還元を得る。
当然左辺の最小駆除手数と右辺の最小駆除手数は等しい。
しかし先の"合成"において右辺のBへの還元は少なくとも⑦以外の還元を一回以上含むので強還元である。
よって左辺の最小駆除手数は右辺の最小駆除手順より真に大きい。
これは矛盾である。
|
- 面白い問題おしえて～な 30問目
148 ：１３２人目の素数さん[sage]：2019/12/03(火) 19:07:39.90 ID:PHS8a67O - 後は全ての要駆除地点数が4か所以下の場合駆除可能を示せば>>113の(2)は終わり。
それはさほど難しくない。
|
- 【未解決問題】奇数の完全数が存在しないことの証明6
32 ：１３２人目の素数さん[sage]：2019/12/03(火) 19:16:03.07 ID:PHS8a67O - もうテレビ見るのやめたら？
|
- 高校数学の質問スレPart402
434 ：１３２人目の素数さん[sage]：2019/12/03(火) 21:35:31.32 ID:PHS8a67O - 漸化式
a(n+1)+4a(n-1)=6a(n)
a(0)=2、a(1)=6
によって与えられる数列について
a(n)-1を1000で割ったあまりが答え。
周期p求めてn÷pのあまりを求める問題。
桁数はlog(n)オーダーでしか増えないので計算量もlog(n)オーダーでしか増えない。
同じ事だけどZ(√5)の整数環Rにおいての(3+√5)^nのR/1000Rの類だからどこか以降必ずループする。
|
- 面白い問題おしえて～な 30問目
151 ：１３２人目の素数さん[sage]：2019/12/03(火) 22:00:25.13 ID:PHS8a67O - >>146
訂正
>>145のリストは全部強還元だね
｜ ーー
㊀㊀◯ ｜ ー㊀㊀
が強還元だ。
左辺の最小駆除手数＝右辺の最小駆除手数+2でした。
なので
⑦左辺の最小駆除手数＝⑦右辺の最小駆除手数+４。
|