cmasterの独り言(´・ω・｀)

2ちゃんねるのコテが気ままにつぶやきます(´・ω・｀)ﾉｼ

数学！！「1次独立」という事の面白さ！！(´・ω・｀)

どうも(´・ω・｀)ﾉｼ

(　＾ω＾)小話

久々な投稿になりますね～
最近は受験勉強そっちのけで漫画を読んだり数学をやったりしています(；・∀・)
他の最近の楽しみの一つに、2chで数学の問題を募集して解く、というのがあります(整数問題が中心です)
数学が好きな人が身近にいないので、クイズ感覚で数学を楽しみ、語り合える場として大切にしています
そんな中ですね(´・ω・｀)
昨日出された問題でとても面白い問題があったので紹介したいです
備忘録も兼ねて書きたいと思います
今回のテーマは一次独立ということです
前提知識を必要とする大学数学は使わずに証明するので、気軽に読んでくだしあ(´・ω・｀)
写像の単射、全射くらいは使います。

経緯をざっくり紹介(｀･ω･)b

問題が出されたスレはこれ↓です

[数学・整数]ウィルソンの定理って至極当たり前だよな ･
http://hebi.5ch.net/test/read.cgi/news4vip/1522637910/

元々このスレは考えた事を述べただけのスレだったのですが、途中から問題を募集したところ、今回のメインテーマとなる問題が出されました(´・ω・｀)
いつもに増してボリューミーなスレです
得られたものが多い！
途中に出てくる「ココナッツの問題」と「条件を満たす点を構成する問題」も面白いので、気が向いたら見てください
では、メインテーマに移りますv(｡･ω･｡)

問題(´・ω・｀)

[問]
内角が全て等しく、辺の長さが全て整数の素数角形は必ず正多角形となることを示せ

是非皆さんも答えを見る前にチャレンジしてみて下さいﾍ(ﾟ∀ﾟﾍ)ｱﾋｬ

問題を解く手がかり(´・ω・｀)

自力でチャレンジする方にヒントを…
必要ない、という方はスクロールストップ！(；・∀・)

この問題で与えられている条件は、
・素数個の角度
・有理数の長さ
この２つです(´・ω・｀)
初等幾何で示すのはまず無理だという事はすぐに分かるので、何らかの座標系に落とし込んで考える事になるでしょう
では最適な座標系は何か？と考えた時に、角度の条件を生かせそうな複素数平面に辿り着くのはさほど難しくないように思います
しかし、複素数平面を使うことを発想として予め持っていないとキツいかも知れません…( -ω- `)

メインテーマを明確にしておく！(´・ω・｀)

皆さんも「一次独立」という言葉は知っているでしょう
説明せよ、と言われたときに、次のように答えると思います

n個のベクトルv_1,v_2,\cdots ,v_nが、\lambda_1,\lambda_2,\cdots \lambda_n \in Aに対して
\displaystyle \lambda_1 v_1+\lambda_2 v_2+\cdots +\lambda_n v_n=0\\ \Rightarrow \lambda_1=\lambda_2=\cdots =\lambda_n=0
を満たすとき、ベクトルv_iはA上一次独立であるという。

これは正しいのですが、これの指し示す意味をきちんと理解しているでしょうか？
私は最近まで気にせず一次独立とかのたまって来たのですが、この問題で一次独立と向き合うことでその本質を確認することが出来ました(´・ω・｀)
一次独立とは、ずばり単射です

f(\lambda_1,\lambda_2,\cdots ,\lambda_n)=\lambda_1 v_1+\lambda_2 v_2+\cdots +\lambda_n v_n
なるn個のベクトルの線型結合f:A^n\to \mathbb{C}が単射ならば、各ベクトルv_iはA上一次独立であるという。

これは最初の定義と同値です(´・ω・｀)
証明はとても簡単なので省略しますが、この単射が一次独立の本質なのです！
一次独立とか言わずに単射って言えよ…(^ω^#)
はい、一次独立の確認も済んだところで解答の方に移ります(｀･ω･)b

問題の解答はこちら(´・ω・｀)

下記中の補題は後に示す。

qを素数とする。
全ての内角が等しいq角形であって、全ての辺の長さが有理数であるものをGとする。
Gの頂点の一つをp_0とし、そこから反時計回りに各頂点をp_1,p_2,\cdots とする。
複素数平面の原点にp_0、正の実軸上にp_1が来るようにGを配置する。
以後、p_iで頂点p_iの座標を表す。
また、\displaystyle \xi =e^{\frac{2\pi i}{q}}とする。
Gの外角は全て\displaystyle \frac{2\pi}{q}であるから、各頂点の座標は次の漸化式で表される。
\displaystyle p_{n+1}=p_n+\lambda_n p_1 \xi^n(ただし、\lambda_i \in \mathbb{Q})
よって、p_q=p_0であるから、
\displaystyle p_1+\lambda_1 p_1 \xi+\lambda_2 p_1 \xi^2+\cdots +\lambda_{q-1} p_1 \xi^{q-1}=0\\ \displaystyle \Leftrightarrow 1+\sum_{k=1}^{q-1} \lambda_k \xi^k=0\ \cdots (*)
ここで、補題2より、各ベクトル\xi_iは\mathbb{Q}上一次独立*1であるから、
組(\lambda_1,\lambda_2,\cdots ,\lambda_{q-1})は存在しても高々1組である。(「単射」に注意せよ)
\displaystyle \xi^q-1=0\\ \Leftrightarrow (\xi-1)(\xi^{q-1}+\xi^{q-2}+\cdots +\xi+1)=0\\ \Leftrightarrow \xi^{q-1}+\xi^{q-2}+\cdots +\xi+1=0
であるので、\lambda_1=\lambda_2=\cdots=\lambda_{q-1}=1のとき(*)は満たされ、これが唯一の組である。
このとき、Gは正q角形になるので、題意は示された。//

続いて、補題1を示す。

[補題1]
多項式
x^{q-1}+x^{q-2}+\cdots +x+1
は\mathbb{Q}上既約である。
[証明]
与式が既約であるかどうかは、x\to x+1という変換において不変である。
よって、以後変換後の多項式について考える。
\displaystyle (x+1)^{q-1}+(x+1)^{q-2}+\cdots +(x+1)+1\\ \displaystyle =\sum_{n=0}^{q-1} \sum_{k=0}^{n} {}_n \mathrm{C}_k x^k
であるから、定数項はq、最高次係数は1である。
その他のk次の項の係数が、全てqで割り切れる事を示す。
有名な恒等式を変形すると、
\displaystyle {}_n \mathrm{C}_r={}_{n-1} \mathrm{C}_r+{}_{n-1} \mathrm{C}_{r-1}\\ \Leftrightarrow {}_n \mathrm{C}_r-{}_{n-1} \mathrm{C}_r={}_{n-1} \mathrm{C}_{r-1}\\ \Leftrightarrow {}_{n+1} \mathrm{C}_{r+1}-{}_n \mathrm{C}_{r+1}={}_n \mathrm{C}_r
(ただし、n,r\geq 1)
となるので、k次の項の係数は
\displaystyle \sum_{n=k}^{q-1} {}_n \mathrm{C}_k\\ \displaystyle ={}_k \mathrm{C}_k+\sum_{n=k+1}^{q-1} {}_{n+1} \mathrm{C}_{k+1}-{}_n \mathrm{C}_{k+1}\\ ={}_k \mathrm{C}_k+{}_q \mathrm{C}_{k+1}-{}_{k+1} \mathrm{C}_{k+1}\\ ={}_q \mathrm{C}_{k+1}
となり、これはk\neq q-1のときqで割り切れる。*2
以上より、アイゼンシュタインの定理*3から題意は示された。//

最後に、補題2を示す。

[補題2]
各ベクトル\xi_i(i=1,2,\cdots ,q-1)は\mathbb{Q}上一次独立である。
[証明]
\displaystyle f(x)=x^{q-1}+x^{q-2}+\cdots +x+1
とおく。
次の同値な命題を、数学的帰納法で示す。
[命題]
t\leq q-1及び\lambda_1,\lambda_2,\cdots ,\lambda_t \in \mathbb{Q}のとき、
\displaystyle \sum_{k=1}^{t} \lambda_k \xi^k=0\Rightarrow \lambda_1=\lambda_2=\cdots =\lambda_t=0
(∵)t=1のときは明らか。
t\leq s-1で成立を仮定する。
\displaystyle g(x)=\lambda_s x^s+\lambda_{s-1} x^{s-1}+\cdots +\lambda_1 x
とおく。
g(\xi )=0\ \wedge \ \lambda_s\neq 0となったと仮定すると、多項式の除法の原理*4より
f(x)=P(x)g(x)+R(x)…(#)
なる有理数係数多項式P(x),R(x)(ただしR(x)の次数はs-1以下)が一意に定まる。
補題1より、f(x)は\mathbb{Q}上既約であるから、R(x)\not \equiv 0である。
f(\xi )=g(\xi )=0であるから、(#)にx=\xiを代入するとR(\xi )=0となるが、R(x)は高々s-1次であり、帰納法の仮定に矛盾する。
よって背理法より、t\leq sでも成り立つ。
以上より、数学的帰納法から示された。//
この命題で、特にt=p-1のとき補題2を得る。//

最後に(´・ω・｀)

いかがでしたでしょうか(´・ω・｀)
書く方も読む方もめちゃくちゃ疲れる問題でしたｗ*5
しかし、解き終えた後の嬉しさはすごい！
なんとこの問題はオリジナルなのだそうです
上記のスレの>69さんの自作です
どうやったらこんな良問を作れるんでしょうね…
皆さんの「一次独立」に対する考察が深まったのなら幸いです(´・ω・｀)ﾉｼ

*1:qが素数である事に注意されたい。素数でないと、補題1が成り立たず、したがって補題2も成り立たないので一次独立にはならない。

*2:有名な事実なので証明は省略するが、数学的帰納法で示す事が出来る。

*3:多項式の\mathbb{Q}上既約を示すのに便利な定理。完璧に1から証明を書くならこの定理も証明すべきであろうが、解答が冗長になるので省いた。有名な数学サイト「高校数学の美しい物語」で証明まで紹介されているので、興味を持たれた方はそこを訪れることをお勧めする。

*4:当たり前の事のように見えて、これもきちんと証明すべき事柄である。アイゼンシュタインの定理と同様の理由で、証明は省いた。

*5:現にこの記事を書き終えるのに4時間以上かかった。

数学！！「空港に直行便を開設する」例の問題を知っていますか？(´・ω・｀)

数学

(。・ω・)ﾉﾄﾞﾓ

前置き(´⊙ω⊙ˋ)

１週間ぶりくらいの投稿になります
もう2017年も終わりですね～(´・ω・｀)
時間が経つのが早く感じられて非常に焦っています((((;´･ω･`)))
ところで最近おもしろい問題を見かけたので、記事にしてみても良いかな、という事で「空港の問題」を取り上げます(ﾉ °ω° )ﾉ
例によって組み合わせ数学の問題です…はい(´･ω･`)
皆さんの中にも聞いたことがある人はいると思います
では見ていきましょう(((っ･ω･)っ

問題ですお(　＾ω＾)

[問題]
n(\geq 3)個の空港の間に以下の⑴,⑵,⑶の条件を満たすように直行便を開設するとき、開設の仕方は何通りあるか。
⑴ どの相異なる2つの空港A,Bの間にも直行便を開設する。
⑵ AよりBへの直行便と、BよりAへの直行便が両方開設されるような2つの空港A,Bは存在しない。また、どの空港Aでも、AよりAへの直行便はない。
⑶ ある空港Cより出発し、直行便を乗り継いで、またCに戻って来られる空港Cが少なくとも1つ存在する。

どうでしょうか(´・ω・｀)
なかなかヤバい雰囲気を醸し出していますね…
この問題は1999年の日本数学オリンピック予選の12問目だそうです
とりあえずこの記事の目的は私自身の記憶の定着でもあるので、何も見ずに解答を書いて行きます
でもその前にちょっとした小話を…(´^p^`)

グラフ理論m9( ﾟДﾟ) ﾄﾞｰﾝ!

この問題は有向グラフというグラフで言い換えることが出来ます
組み合わせの問題で、「ある2人が友達」とか「どこからどこへ行く」といった言葉が出てくる問題では、グラフ理論の道具を使って言い換えると見通しが良くなることがあります
今回の解答ではグラフ理論の言葉は使いませんが、ざっとグラフについて書いておきます(´・ω・｀)
私の備忘録も兼ねております
(読み飛ばしても構いません)

グラフ(∩´∀｀)∩ﾜｰｲ

・グラフ…有限個の頂点と、そのうちの何組かの2頂点を結ぶ辺からなる図形
・次数…ある頂点Pについて、Pを端点とする辺の本数のこと
・彩色グラフ…辺や頂点に色をつけたグラフ
・無向グラフ…辺に向きが無いもの
・有向グラフ…辺に向きを定め、矢印で置き換えたもの
・道(パス)…グラフにおいて、辺をたどって頂点aから頂点bへ行くことが出来るとき、「aからbへの道が存在する」という
・有向道…有向グラフにおいて、向きを加味した道
・半道(セミパス)…有向グラフにおいて、向きを無視した道
・連結…どの2頂点をとっても、その2点がグラフの辺をたどってできる折れ線で結べる状態
・強連結…有向グラフの任意の頂点a,bにおいてaからbへの有向道が存在する状態
・弱連結…有向グラフの任意の頂点a,bにおいてaからbへの半道が存在する状態
・ループ(閉路)…aからaへの道(有向グラフであれば有向道)が存在するとき、それをループという
・有向閉路…有向グラフにおけるループをこのように呼ぶことがある
・DAG(directed acyclic graph)…閉路(有向閉路)のない有向グラフ、有向非巡回グラフとも呼ぶ
・完全グラフ…任意の2頂点間に辺があるグラフ、連結なのは言わずもがな

ここまで説明すれば、上記の問題は「n頂点からなる完全有向グラフがループを持つときのグラフの書き方」と言い換えられることが分かると思います
たしかにこれは簡潔に言い表せていますね(´・ω・｀)

初見では解けなかったお(´；ω；｀)

まぁ解けなくて当たり前だと思いますけどね…(´･ω･`)
こんなん解けるわけがない
ちょっとしたヒントを書いておきます(´・ω・｀)↓
nが小さい場合で書き出してみて下さい
何か気づくことがあるかも知れません
あとは、余事象を考えると良いです
受験数学では鉄板となっている「少なくとも～というタイプの問題は余事象を考える」というアレが役に立ちます
ちなみに私は余事象では議論が進まないかな〜と、ほぼ考えずに諦めてしまいました(；・∀・)
じゃあそろそろ解説に移ります(((っ･ω･)っ

解説(_´･д･`)_ﾊﾞﾝｯ

問題の⑶の余事象を考えると、グラフは完全なDAG(完全有向グラフで閉路を持たないもの)になります
「完全なDAGには、どの頂点にも矢印をたどって行く事が出来ない頂点がただひとつ存在する」という事実を利用します(´・ω・｀)
この事実から、頂点がただ１通りに「１列化」出来ることを導きます
(こんなん知らなきゃ出来ないです)
まぁ見ていてください(´・ω・｀)

[解答]
n個の空港間には直行便が\displaystyle {}_n C_2個あり、そのそれぞれに向きの定め方が2通りあるので、全ての直行便の定め方は\displaystyle 2^{{}_n C_2}通り…①

ある空港Pからほかの空港への直行便が一つも無いとき、空港Pを「どん詰まりの空港」と呼ぶことにする。
ここで、⑶の余事象を考える。
⑴⑵を満たし、⑶を満たさないように直行便を開設すると、どん詰まりの空港が必ずただひとつ存在することを示す。
(存在性)
どん詰まりの空港が無いと仮定すると、ある空港から一度も行ったことの無い他の空港へ移動することを無限に繰り返すことが出来る。(⑶を満たさないように空港を開設したため)
しかし、空港の数は有限個であるので矛盾。
よってどん詰まりの空港が存在する。
(唯一性)
どん詰まりの空港が2つ以上存在したとすると、どん詰まりの空港a,bが取れるが、そのふたつの間には直行便が開設されていてどん詰まりの空港であることに矛盾。
よってどん詰まりの空港は一つ以下。
以上より、どん詰まりの空港はただひとつ存在することが示された。

ここでどん詰まりの空港をA_1として、A_1及びA_1への直行便を除外する。
すると、同様の議論により、どん詰まりの空港がただひとつ出来る。
これをA_2とし、A_2及びA_2への直行便を除外する。
以上の議論を繰り返すことで、空港の列\{ A_1,A_2, \cdots ,A_n \}が得られる。
さらに、
\displaystyle i > j \Leftrightarrow A_iから\displaystyle A_jへの直行便が存在する…(*)
となっていることが容易に確認できる。
ある空港の列\{ B_i \}に対して(*)を満たすように直行便を開設してやると、これは⑴⑵を満たし、⑶を満たさないような直行便の開設の仕方になっていることも容易に確認できる。
(空港B_iから出発すると空港B_j\ (i > j)にしか移動出来ないが、B_iに戻ってくるためにはB_k\ (k > i)を経由しなければならないため)
以上より、⑴⑵を満たし、⑶を満たさないような空港の開設の仕方は\displaystyle n!通り
したがって、①とあわせて求める場合の数は
\displaystyle 2^{{}_n C_2}-n!通り//

グラフ理論でまとめよう(ΦωΦ)ﾌﾌﾌ…

いかがだったでしょうか(´・ω・｀)
かなり複雑に見えますが、実際はそうでもないです
最後の方は、

⑴⑵を満たし、⑶を満たさない
\displaystyle \Leftrightarrow [ i > j \Leftrightarrow A_iから\displaystyle A_jへの直行便が存在する\displaystyle ]

という事を主張しています。
この問題で得られた事実をグラフ理論の言葉を使ってまとめておきましょう(´・ω・｀)

[定理1]
完全なDAGには、ほかの頂点に矢印をたどって移動することが出来ない頂点がただひとつ存在する。

(証明)
主張のような頂点を「どん詰まりの頂点」と呼ぶ。
どん詰まりの頂点が存在しないとすると、ある頂点から矢印をたどって今までに通ったことの無い頂点に移動することを無限に繰り返すことが出来る。しかし、これは頂点が有限個であることに矛盾。(存在性)
どん詰まりの頂点が2つ以上存在したとすると、完全グラフであることから、その二点の間にも辺があり、どん詰まりの頂点であることに矛盾。(唯一性)
以上より、主張は正しい。//

[系]
完全なDAGは、頂点を次の同値な規則
・どん詰まりの頂点P及びPへの矢印を取り除いていく
・[\displaystyle i > j \Leftrightarrow A_iから\displaystyle A_jへの辺が存在する]
によってただ１通りに１列化出来る。

(証明)
主張の後者の規則で頂点を１列化するときのアルゴリズムは主張の前者そのものであるので２つの規則は同値。
主張の規則によって得られる頂点の列\{ A_1,A_2, \cdots ,A_n \}は上記の定理により一意に定まる。//

[定理2]
n個の頂点からなる完全なDAGの書き方はn!通りである。

(証明)
定理1の系より、完全なDAGを与えると頂点の列を返す写像fを考えることができる。
fはある有限集合Pからある有限集合Qへの写像である。
ここで、ある頂点の列から、規則
[\displaystyle i > j \Leftrightarrow A_iから\displaystyle A_jへの辺が存在する]
を満たすように完全なDAGを構成すると、ただ１通りのグラフが得られる。
よって、写像fは全単射であるので、|P|=|Q|=n!//

終わりに(；・∀・)

上の定理の証明は私が頑張って考えたものなので、不備があるかもしれません
申し訳ないです
もし不備を発見した方がいましたらコメントで伝えて下さると助かります
ちなみにこの記事書くのかなーり大変でした！！(´；ω；｀)

より理解が深まると思われる文献を貼っておきます
↓グラフの用語等
http://www.hongo.wide.ad.jp/~jo2lxq/dm/lecture/06.pdf
↓DAGについて、中盤に１列化の話題あり
http://www.i.kyushu-u.ac.jp/~algo/6.6-7.pdf

不備があったので訂正致しました。申し訳ございません。(2017/12/29 00:01:47)

LTEの補題について書きます！！備忘録(´・ω・｀)

どーも(´・ω・｀)ﾉｼ

独り言ドーン(ﾉ °ω° )ﾉ

昨日の記事が結構ヘビーな内容だったから何書いていいか迷ったんですけどね(；・∀・)
アレに匹敵するものだったら……整数問題の花形「LTEの補題」！！
これしかない！と思ったので書きます
思い立ったら即実行って事で…(´・ω・｀)
LTEの補題は一部のオタク気質な人たちの間では割りかし有名みたいで、ググれば記事を書いている人がちらほら見受けられます
なので今さら記事として取り上げる必要も無いかな〜とも思ったのですが、自力で証明を書き直すことで理解が深まるだろうし、備忘録として書いてみるのもいいかも！(´･∀･｀)
という訳で書きます

LTEの補題ってなんぞや(ﾟДﾟ#)ｱｧ？

[定理]
ある奇素数pがある整数x,yを割り切らず、(x-y)を割り切るとき、以下が成り立つ。
\displaystyle \mathcal{ord}_p {(x^n-y^n)}=\mathcal{ord}_p {(x-y)}+\mathcal{ord}_p n

Lifting The Exponent Lemmaとかいうのだったと思います(´・ω・｀)
\displaystyle \mathcal{ord}_p nというのは「素数pに関するnのオーダー」と言い、nが何回pで割り切れるか、を表したものです
p=2の場合も考えることが出来ます(後述)
ググれば誰が思いついたーとか出てくると思うので省略！！
|ω・`).｡oO(知らないとか言えない)

さっそく証明しようず(´^p^`)

帰納法でやるのが一般的だと思います
それ以外では出来ないんじゃない？知らないけど←ヾ(･Д･`)ｵｲ
方針としては、

  1. n=pの場合に成り立つことを示す
  2. nとpが互いに素の場合に成り立つことを示す
  3. n=ap^kの時に成り立つことを示す(ここで帰納法)

というステップを踏みます
最初は何も見ないで記憶をたよりに書きます(´・ω・｀)

[証明]

ある奇素数pがある整数x,yを割り切らず、(x-y)を割り切るとき、
\displaystyle \mathcal{ord}_p {(x^n-y^n)}=\mathcal{ord}_p {(x-y)}+\mathcal{ord}_p n
が成り立つことを示す。
⑴n=pの場合
\displaystyle x^p-y^p=(x-y)(x^{p-1}+x^{p-2} y+\cdots +y^{p-1})
ここで、\displaystyle y \equiv \ x+mp \ \mathcal{mod} \ p^2であり、
\displaystyle x^{p-1}+x^{p-2} y+\cdots +y^{p-1}\\ \displaystyle =\sum_{k=0}^{p-1}x^{p-1-k}y^k\\ \displaystyle \equiv \sum_{k=0}^{p-1}x^{p-1-k}\sum_{l=0}^{k}x^{k-l}p^l m^l {}_k \mathrm{C}_l\\ \displaystyle =\sum_{k=0}^{p-1} \sum_{l=0}^{k}x^{p-1-l}p^l m^l {}_k \mathrm{C}_l\\ \displaystyle = \sum_{l=0}^{p-1}\sum_{k=l}^{p-1}x^{p-1-l}p^l m^l {}_k \mathrm{C}_l\\ \displaystyle \equiv\sum_{k=0}^{p-1}x^{p-1}+\sum_{k=1}^{p-1}x^{p-2}pmk\\ \displaystyle \equiv\ p+pmx^{p-2}\cdot\frac{p(p-1)}{2}\\ \displaystyle =\ p+p^2 (\frac{p-1}{2}\cdot mx^{p-2})\\ \equiv \ p \ \mathcal{mod} \ p^2
であるので、与式のn=pの場合、すなわち\displaystyle \mathcal{ord}_p {(x^p-y^p)} =\mathcal{ord}_p {(x-y)}+1は成立する。
⑵nとpが互いに素である場合
\displaystyle x^n-y^n=(x-y)(x^{n-1}+x^{n-2} y+\cdots +y^{n-1})
ここで、\displaystyle y \ \equiv \ x \ \mathcal{mod} \ pであり、
\displaystyle x^{n-1}+x^{n-2} y+\cdots +y^{n-1}\ \equiv \ nx^{n-1} \ \not\equiv \ 0 \ \mathcal{mod} \ p
したがって与式は成立する。
⑶n=ap^kの場合(aはpと互いに素)
k=0のとき⑵より成立する。
k=mのとき成り立つと仮定すると、⑴が適用できて、
\displaystyle \mathcal{ord}_p {(x^{ap^{m+1}}-y^{ap^{m+1}})}\\ =\mathcal{ord}_p {({(x^{ap^m})}^p-{(y^{ap^m})}^p)}\\ =\mathcal{ord}_p {(x^{ap^m}-y^{ap^m})}+1\\ =\mathcal{ord}_p {(x-y)}+\mathcal{ord}_p {ap^m}+1\\ =\mathcal{ord}_p {(x-y)}+m+1\\ =\mathcal{ord}_p {(x-y)}+\mathcal{ord}_p {ap^{m+1}}
以上⑴⑵⑶より示された。//

p=2の場合にも考えてみる(((っ･ω･)っ

同様に考えていきましょう(´・ω・｀)
少し条件が複雑になります
x,yは2で割り切れず、(x-y)は2で割り切れるとします

[定理]
・2\not\mid nまたは2\mid n\ \wedge\ 4\mid (x-y)の場合
\displaystyle \mathcal{ord}_2 {(x^n-y^n)}=\mathcal{ord}_2 {(x-y)}+\mathcal{ord}_2 n
が成り立つ。
・2\mid n\ \wedge\ 4\not\mid (x-y)の場合
\displaystyle \mathcal{ord}_2 {(x^n-y^n)}=\mathcal{ord}_2 {(x^2-y^2)}+\mathcal{ord}_2 n -1
が成り立つ。

[証明]
nが奇数の場合は、上記の証明の⑵と同様の議論で証明される。
(x-y)が4で割り切れるとき、
\displaystyle y \ \equiv \ x \ \mathcal{mod} \ 4 \ \wedge \ x,y \ \not\equiv \ 0 \ \mathcal{mod} \ 2 \\ \Rightarrow x+y \ \equiv \ 2 \ \mathcal{mod} \ 4
に注意して、
\displaystyle \mathcal{ord}_2 {(x^2-y^2)}\\ =\mathcal{ord}_2 {(x-y)(x+y)}\\ =\mathcal{ord}_2 {(x-y)}+1
であり、n=2^ka(aは奇数)のときに主張が成り立つと仮定すると、
\displaystyle \mathcal{ord}_2 {(x^{2^{k+1}a}-y^{2^{k+1}a})}\\ =\mathcal{ord}_2 {({(x^{2^{k+1}})}^a-{(y^{2^{k+1}})}^a)}\\ =\mathcal{ord}_2 {({(x^{2^k})}^2-{(y^{2^k})}^2)}+\mathcal{ord}_2 a \\ =\mathcal{ord}_2 {(x^{2^k}-y^{2^k})}+1\\ =\mathcal{ord}_2 {(x-y)}+\mathcal{ord}_2 +\mathcal{ord}_2 2^k +1\\ =\mathcal{ord}_2 {(x-y)}+\mathcal{ord}_2 {2^{k+1}}
となり、帰納法より一つ目の主張は正しい。//
(x-y)が4で割り切れないとき、\displaystyle x^2-y^2\ \equiv \ 0 \ \mathcal{mod} \ 4より、一つ目の主張に、\displaystyle x^2,y^2,\frac{n}{2}を代入する事で、二つ目の主張を得る。//
このとき、\displaystyle \mathcal{ord}_2 {(x^2-y^2)}をこれ以上簡単に表すことは出来ない。*1

結論をまとめます( ﾟωﾟ )ゝ

ある素数pとある整数x,yが
\displaystyle x\ \equiv \ y \ \not\equiv \ 0 \ \mathcal{mod} \ p
を満たすとき、

⑴ \displaystyle p=2\ \wedge\ 2\mid n \ \wedge \ 4\not\mid (x-y)でない場合
\displaystyle \mathcal{ord}_p {(x^n-y^n)}=\mathcal{ord}_p {(x-y)}+\mathcal{ord}_p n
⑵ \displaystyle p=2\ \wedge\ 2\mid n \ \wedge \ 4\not\mid (x-y)である場合
\displaystyle \mathcal{ord}_2 {(x^n-y^n)}=\mathcal{ord}_2 {(x^2-y^2)}+\mathcal{ord}_2 n -1

証明を終えた感想(A；´･ω･)

なにも見ずに証明しよう！って事で、p=2よりも前の部分は自力でやったんですが、p=2はなかなか思いつかなかったので「獲得金メダル！国際数学オリンピック」という本を参考にしますた(´・ω・｀)
p=2よりも前の部分も正しい事を確認しました
他の方の証明と比較してみて、個性が出てる部分があるかどうか探してみたのですが、有名な証明方法では\displaystyle x^{p-1}+x^{p-2} y+\cdots +y^{p-1}の部分をさらに(x-y)で割るようです
私のやり方ではp^2で割った余りがpである事を示し、pで一度しか割ることが出来ない事を示しています
ここは割と大きな違いじゃないですかね…？(；・∀・)

※不備があったため修正しました。申し訳ございません(2017/12/23)
※修正していなかった不備を全て修正し、大幅リニューアル致しました！(2018/04/05)

*1:見つかっていないだけで、もしかしたら簡単に表せるかも知れません…

難しい組み合わせ数学の問題が解けました！！この感動を伝えたい！！(´・ω・｀)

数学

 

まずは問題をば(´・ω・｀)

はい問題+(0ﾟ・∀・)+

[問]

■■　■■

■■　■

上のような座席配置の教室で7人が席替えをする
元々隣同士だった2人は席替え後には隣同士にならないような席替えの仕方は何通りか？

 

はい(´・ω・｀)

解答は下の方に載っけときますので、自力で解きたい方はスクロールに気をつけてくだしあ

 

この問題の裏事情(；・∀・)

とりあえず世間話で長さを稼ぎます

この問題が出された経緯を話しますと、昨日2chのニュー速VIPという掲示板で数学の問題(特に組み合わせ論)を募集するスレを立ててみたんです↓↓

組み合わせ論 ･
http://hebi.2ch.net/test/read.cgi/news4vip/1513736523/

そこで、ある方が適当に作問したのがアレです

(ただし少し改題してあります、本家は上記のスレにあります)

作問された方も解法が思い浮かばないとの事で、出された側はたまったもんじゃありませんねｗｗｗ(´；ω；｀)

このスレの最後の方に来られた方がJavaでプログラムを組んで、７席の場合まで計算されています

そして今日、その方が再度スレを立てて解答を募集していました(´・ω・｀)↓

【至急】数学得意な奴これ解いてくれ！！
http://hebi.2ch.net/test/read.cgi/news4vip/1513849429/

私はこれを偶然(必然)見かけて、再度挑戦してみた所うまい解法が！！

感動で咽び泣くまである(´；ω；｀)

問題を見てから解くまでに１日かかってますからね…

皆さんも数十分で諦めずに一日お考えください( ´･ω･)ﾌﾋﾋﾋﾋ

一般化できます、答えは汚くなりますが。

では、答えを見ていきましょう(((っ･ω･)っ

※合ってる保証はありませんご了承下さい(´>ω∂`)

 

答え(っ＞ω＜c)

[解答]

{\displaystyle a_n}をn席の時に題意を満たす場合の数とする。
全ての席替えの場合の数はn!通り
元々の隣り合う組を{\displaystyle (p_1,p_2),(p_3,p_4),}…とする。
ここで、一組だけが隣り合う場合を考える。
その時、その一組の選び方は{\displaystyle {[\frac{n}{2}]}}通りあり、その一組の配置の仕方は{\displaystyle {[\frac{n}{2}]}}通りある。また、その二人の並び方は2通りある。さらに、他の人たちの席の決め方は{\displaystyle a_{n-2}}通りあり、他の人たちの中で、元々隣り合っていたペアが隣り合う、という事は無い。
同様に、二組が隣り合う場合、三組が隣り合う場合、…と考えていくと、その合計は

{\displaystyle \sum_{k=1}^{ [ \frac{n}{2} ]} {}_{[ \frac{n}{2} ]} \mathrm{C}_k \cdot {}_{[ \frac{n}{2} ]} \mathrm{P}_k \cdot 2^k \cdot a_{n-2k}}
となる事より、求める場合の数は

{\displaystyle a_n=n!-\sum_{k=1}^{ [ \frac{n}{2} ]} {}_{[ \frac{n}{2} ]} \mathrm{C}_k \cdot {}_{[ \frac{n}{2} ]} \mathrm{P}_k \cdot 2^k \cdot a_{n-2k}\\a_1=1,a_3=4 }

したがって、n=7のとき

{\displaystyle a_7=3264}

 

終わり

なにげにTeX初挑戦でした！(*´･ω･`)=3

漸化式解けんのかなこれ

解けたら教えて下さいm(_ _)m

 

何かお気づきの点がございましたら是非コメントしてくだしあ(´・ω・｀)

以上です！

今日からはてブロやります！(´・ω・｀)

雑記

どうも(´・ω・｀)

表題の通りですが、思い立ってはてなブログを始めることにしました

2ちゃんねるでコテをやっています(◆Cmaster.z.)

見かけたら声をかけてくだしあ(´･ω･`)

で、始めようと思ったきっかけはと言えば、たくさんの凄い方々がこぞってはてなブログをやっているからです

それで啓蒙とか触発？されてやりたいな〜と…(´・ω・｀)

まぁもともとネット依存みたいな感じで常に2chに張り付いて独り言を垂れ流していたので、ブログでもやって記録残してみたら面白いんじゃないかな、と思ったのもあります

日記みたいになると思いますが、どうぞよろしく(｡-人-｡)

カテゴリーはしっかり分けます

コメント頂いたらとても嬉しいです

返します