数学＠ふたば保管庫 [戻る]
|
チンカスって何だろう チンチンから滲み出る何かなの？ |
|
置換 |
|
配列の要素を{1, 2, 3, ...n}(長さn)とし、この並びを初期状態とする。 自分の位置より右にある自分より小さい要素の数をその要素の重さとする。 すべての要素の重さの合計を配列の重さとする。 (初期状態の配列の重さは0, 初期状態から任意の隣り合う要素を入れ替えると配列の重さは1になる) 1回の操作による配列の重さの変化について考える。 入れ替える2つの要素の左側をL, 右側をRとして Lより左側の要素をA, Rより右側の要素をB, LとRの間の要素をMとする。 Mを構成する1つの要素をMxとする。 A, Bはそれより右の要素の集まりが変化しないので重さは変わらない。 (重さが変化する可能性があるのはL, M, Rのみ) |
|
(LがRの位置へ移動することによる)Lの重さの変化は ①Mx<LであるMの要素の数だけ減る ②R<Lならば1減る (RがLの位置へ移動することによる)Rの重さの変化は ①Mx<RであるMの要素の数だけ増える ②L<Rならば1増える Mの重さの変化は ①L<MxであるMの要素の数だけ増える ②R<MxであるMの要素の数だけ減る |
|
L<MxであるMの要素の数=(Mの要素数)-Mx<LであるMの要素の数 R<MxであるMの要素の数=(Mの要素数)-Mx<RであるMの要素の数 なので、L, M, Rの重さの変化は ①-(Mx<LであるMの要素の数) ②L<Rならば-1 ③+(Mx<RであるMの要素の数) ④R<Lならば+1 ⑤+(Mの要素数)-(Mx<LであるMの要素の数) ⑥-(Mの要素数)+(Mx<RであるMの要素の数) の合計となる。整理すると ①2*((Mx<RであるMの要素の数)-(Mx<LであるMの要素の数)) ②L<Rならば-1そうでなければ+1 の合計となる。 |
|
①は偶数②は奇数なので合計は奇数になる。 つまり1回の操作による配列の重さの変化は奇数になる。 操作を何回か行って初期状態に戻るためには、 操作による重さの変化の合計が0(偶数)でなければならない。 奇数個の奇数の合計は奇数であるため、 奇数回の操作で初期状態に戻ることは有り得ない。 |
|
↑ 長たらしいから3行くらいでシンプルに証明したいの |
|
置換を行列で表現して 行列式を考えたらいい |
|
行列わかんないの |
|
それを思考停止と言い、もっとも忌むべき行為の一つ。帰れ。 |
|
sgnの一意性の証明でググれ |
|
>sgnの一意性の証明でググれ いや ググっても小難しい言い回しに翻弄されるだけなのでお前が髪を優しく撫でるノリで証明しろ |
|
>お前が髪を優しく撫でるノリで証明 それが存在するという根拠を先に証明してくれ。 |