足跡-sokuseki-

りかの日進月歩の記録

エクセルでの乱数発生のメモ

この春休みは計算力を上げることを目標として頑張っているので、さまざまなことに取り組んでいる。その一環として使うプリントを作成した。その際の「１から１００までの整数をランダムに（重複なしで）表示させる方法」をメモしておく。難しくはなく、簡単にできるので大量にプリントを作ることができた。

以下その方法。

 

①エクセルを起動させる

ここは気合いでなんとかなる。

 

②A1に「=RAND()」を入力する

RAND関数は0以上1未満の小数の乱数を作る関数である。

 

③A100までコピーする

これで、0以上1未満の小数の乱数がA1からA100まで100個作成できた。

 

④B1に「=RANK(A1,$A$1:$A$100,0)」を入力

RANK関数はRANK(数値,参照範囲,順序)で入力すると、[数値]が[参照範囲]の中で[順序]で何番目かを返す。[順序]は0か1を入力でき、0ならば降順（大きい数字の方が順位が高い）、1ならば昇順（小さい数字の方が順位が高い）である。

あとでこの式をコピーするので、[数値]は相対参照、[参照範囲]は絶対参照(「＄」をつける)にしておく。

 

⑤B100までコピーする

これで、A1からA100に書いてある数字の順位がB1からB100に表示される。乱数の順番を表示させているので、重複を避けることができる。

 

 

証明を書いていたら循環論法になってしまいましたよという話

数学 証明

簡単なはずの証明問題にやたら時間がかかっていたことの弁明をしたいと思います(弁明にはならない)。

今日の夕方に投稿した記事の証明問題の話です。

「aのn乗がpの倍数であること」と「aがpの倍数であること」は同値である - 足跡-sokuseki-


これの⑵の証明の際に、対偶を帰納法ではなくそのまま証明できないかと奮闘していました。

以下がその証明部分です。

『 a^n が p の倍数 \Longrightarrow a が p の倍数 』を示すために、その対偶である

『 a が p の倍数でない \Longrightarrow a^n が p の倍数でない 』を示すことにします。


t,qを正の整数として、 a=pt+q とおきます。

ただし、 q については 0 < q < p とします。

このとき

a^n = (pt+q)^n

となりますが、ここで二項定理を使います。二項定理は

(x+y)^n = \sum_{k=0}^{n} {}_n C _{k} x^k y^{n-k}

というものです。これを利用すると

(pt+q)^n = \sum_{k=0}^{n} {}_n C _{k} (pt)^k q^{n-k} = \sum_{k=1}^{n} {}_n C _{k} p^k t^k q^{n-k} + q^n

となります。ここで、 k>0 のとき {}_n C _{k} p^k t^k q^{n-k} は p の倍数であり、

p の倍数を足し合わせたものである \sum_{k=1}^{n} {}_n C _{k} p^k t^k q^{n-k} も

p の倍数になります。

また、 0 < q < p より、 q は p の倍数ではないので、

q^n も p の倍数ではありません。

よって、 a^n = (pt+q)^n は p の倍数ではありません。

以上より、対偶を示すことができたので、十分条件が成り立つことがわかりました。

色を変えたところが循環論法になっています。

これをどうしようか……と悩んでいて時間が経ってしまったわけです。

なお、当該記事では帰納法を使っていますが、これは、どうしてもうまくいかなくて、数学の先生に

「『 a が p の倍数でない \Longrightarrow a^n が p の倍数でない』はどうやって示せばいいですか」

と質問したところ、帰納法を使えばいいよというアドバイスをいただいたので、帰納法でやってみた次第です。

私が自力で思いついたわけではないです。はい。

(帰納法ということを教えてもらっただけで中身の証明は自分で考えたのですが、そのせいで無駄に長い証明になってしまいました……)

なお、さきほど短いver.を追記しました。


以上、弁明にもならない弁解でした。

「aのn乗がpの倍数であること」と「aがpの倍数であること」は同値である

数学 証明

根号のついた様々な数が無理数であることを示すのが最近の趣味です。
その証明に使う補題(のようなもの)を証明したいと思います。

証明内容はタイトルにも書いた通り、

『 a,n が正の整数、 p が素数のとき、

a^n が p の倍数 \Longleftrightarrow a が p の倍数 』

です。必要条件と十分条件に分けて証明していきたいと思います。


⑴『 a^n が p の倍数 \Longleftarrow a が p の倍数 』を示す

t を整数として、 a=pt とおきます。このとき

a^n = (pt)^n = p^n t^n

p^n t^n は p の倍数なので、 a^n が p の倍数であることがわかります。


よって必要条件は示すことができました。





⑵『 a^n が p の倍数 \Longrightarrow a が p の倍数 』を示す

これを直接証明することは難しいので、対偶を示すことにします。

『 a^n が p の倍数 \Longrightarrow a が p の倍数 』の対偶は

『 a が p の倍数でない \Longrightarrow a^n が p の倍数でない 』……(＊) です。

なので、(＊)を数学的帰納法を使って示します。



(i) まずは n=1 のとき

「 a が p の倍数でないならば a が p の倍数でない 」は自明なので(＊)は成り立ちます。



(ii) 次に、 n=k のときに(＊)が成り立つと仮定します。

このとき仮定より、「 a が p の倍数でないならば、 a^k が p の倍数でない」といえます。

またこのとき、

「 p の倍数でない数に、 p の倍数でない数をかけても p の倍数にはならない 」……(A)

ということがいえるならば、

p の倍数でない a^k に、 p の倍数でない a をかけた a^{k+1} も p の倍数ではありません。

よって(A)さえ示すことができれば、 n=k+1 のときも(＊)が成り立つといえます。



ここで(A)を示すために、 p の倍数でない2数の積を p で割ったあまりについて考えます。

(ここでは合同式を使って、整数 a を整数 p で割ったあまりと、整数 b を整数 p で割ったあまりが等しいとき
「 a \equiv b ( mod p ) 」と表すことにします。 )

整数 a, b, c, d を用いて、 p の倍数でない2数を

ap+b、 cp+d 　　(ただし、 0 \leq a, c かつ 0 < b, d < p )

とします。

この2数の積を p で割ったあまりは

(ap+b)(cp+d) \equiv acp^2 + ( ad+bc ) p + bd \equiv bd 　 ( mod p )

と表せます。


ここで、「 bd \equiv 0 　( mod p ) 」と仮定すると、

bd は p の倍数であり、 p は素数なので、

b と d の少なくとも片方が「 0 または p の倍数」である必要があります。

しかし、 0 < b, d < p より、

b と d の両方ともが 0 でも p の倍数でもないので、これは矛盾します。

よって 「 bd \equiv 0 　( mod p ) 」という仮定が間違っていることがわかります。


以上より bd \not\equiv 0 　( mod p ) となります。

よって、 (ap+b)(cp+d) \not\equiv 0 　( mod p ) となり、

p の倍数でない2数の積は p の倍数でないことが示せました。(A)の証明はこれで終了です。



これで、

(i) n=1 のとき(＊)が成り立つ

(ii) n=k のときに(＊)が成り立つならば、 n=k+1 のときに(＊)が成り立つ

を示すことができたので、数学的帰納法より(＊)を証明することができました。



対偶である(＊)を証明することができたので、

『 a^n が p の倍数 \Longrightarrow a が p の倍数 』が成り立つことが証明できたことになります。





よって、必要条件、十分条件ともに成り立つことがわかったので、

『 a,n が正の整数、 p が素数のとき、 a^n が p の倍数 \Longleftrightarrow a が p の倍数 』

を証明することができました。





ところでこの証明、名前ついてたりするんですかね……。有名な気がするんですが……。


参考サイト

合同式の意味とよく使う６つの性質 | 高校数学の美しい物語





追記

この記事を投稿した後に、@lvbourbakiさんに指摘していただいて気づいたのですが、(A)の証明の部分で合同式を使って式変形をする必要はありませんでした。
ということで、簡潔になった(A)の証明を以下に書きます。



p の倍数でない2つの自然数を a, b とします。

ここで、「 ab が p の倍数である 」と仮定すると、 p は素数なので、

a と b の少なくとも片方が「 0 または p の倍数」である必要があります。

しかし、 a と b の両方ともが 0 でも p の倍数でもないので、これは矛盾します。

よって 「 ab が p の倍数である 」という仮定が間違っていることがわかります。


以上より ab は p の倍数でないということがいえるので、

p の倍数でない2数の積は p の倍数でないことが示せました。

じ、自明だ……

ということで随分と短くなりました。

@lvbourbakiさん、どうもありがとうございました。

競技プログラミング2016総括

競技プログラミング

ということで競技プログラミング1年目のまとめをします。長くて面倒なので箇条書きスタイルでいきます。

 

4月

 

5月

  • RiPProに正式入部
  • AtCoder初AC
  • AtCoderのコンテストに初出場(ABC038)

 

6月

  • 1年3人でチームを組んでICPC国内予選に出る(1完)

 

7月

  •  大学の期末テストで競プロできない日々が続く

 

8月

  • 夏休みだったので毎日AOJを目標にしてた(できたとは言ってない)

 

9月

  • ACPCに参加(初めてのオンサイトコンテスト&&初めての作問)
  • AtCoderで100solved達成！

 

10月

  •  KUPCに参加
  • AOJで100solved達成！
  • AtCoderのレートが1200突破！

 

11月

  • 何してたっけ……？

 

12月

  • 毎日AtCoderを目標にしていた
  • AtCoderで200solved達成！
  • Codefoces初AC

 

 

現在のAC状況(2016/12/30 17:00現在)

 

AOJ……133solved 

 

f:id:wk1080id:20161230165028p:plain

 (解いてるときと解いてないときの差が激しい)

 

AOJ-ICPC……47solved

 

f:id:wk1080id:20161230162354p:plain

 

 

AtCoder……253solved

 

f:id:wk1080id:20161230164102p:plain

(ABCのAB埋めが完了したので解ける問題が少なくなって進捗がなくなってきた)

 

f:id:wk1080id:20161230163753p:plain

 

 

 

最後に……

 

来年も競技プログラミング頑張ります！

たくさんのオンサイトコンテストに行けるといいな〜

 

 

 

今までに詠んだ和歌をまとめた

数学 和歌

 

和歌。それは少ない文字数に景色や心情を詠みこむ日本独自の歌。決まった文字数に様々な、時には二通りにも三通りにも読み取れる意味を込める和歌は、とても素晴らしい文化だと思います。

和歌を詠んだ経験は少ないのですが、イベントに関連してTwitterで和歌を募集していた際などに詠んだいろいろな和歌を一度まとめます。

 

愛と数学の短歌コンテスト

 

4月に理系彼女botさんが考案、横山明日希さん（数学のお兄さん）が主催して行われたコンテスト。

 

短歌も和歌の一種ということで。技法とか何もないのが多いですが。 

 

これは@mass_sawood さんのツイートが元ネタ。すべてローマ字にすると "I love U" になります。

 

 

ロマンティック数学俳句コンテスト

 

7月から8月にかけて、横山明日希さん（数学のお兄さん）主催で行われたコンテスト。

 

このコンテストについては、ツイートしてないのですが、スマホのメモに当時考えたものが残っていたので。 

関数で 君は一意に 僕とペア

「関数はある数を決めるとそれに対応して一つの数が決まる。関数のように、君と僕が一対一で対応する、っていうニュアンス」という解説まで残っていました(笑)

 

 

数学和歌を詠もう

 

8月末から、横山明日希さん（数学のお兄さん）と狡猾な狐さんが企画して行われたイベント。

 イベントまでに詠むことはできなかったのですが、その後行われたツイキャスで詠みました。

 

 

 そしてセルフ解説はこちら。

 

そしてこのハッシュタグを使って、その後もいくつかツイートしてます。

 これはただのネタです(笑)

 

 

古今和歌集の日

 

2016年11月11日の古今和歌集の日を記念して和歌を詠もうという企画（狡猾な狐さん発案）。

 

 これについてはセルフ解説を以下に。

 

 いくつかツイキャスで紹介もしていただいて、本当にありがとうございました！

 

最後に

 

古今和歌集からの良き節目を迎えて、せっかくだから、と今までの分もまとめました。もっと良い和歌を詠めるようになりたいです。

 

リーマンゼータ関数の収束条件

数学

大学の数学の授業で広義積分を習ってから、その魅力にとりつかれてしまったので、最近は広義積分のなかでも比較的有名な「リーマンゼータ関数」をいじってばかりいる。簡単に言えば、リーマンゼータ関数とは、

\zeta (s) = \sum_{n=1}^{\infty} \frac{1}{n^s}

で表される関数のことである。その他詳しくは下記参考サイトにて。



数学の授業で、広義積分 f(x) の極限を求めるために、

\sum^{\infty}_{n=1} f(x) が収束する \Longleftrightarrow \lim_{M \to \infty} \int_{1}^{M}f(x)dx が収束

を使えば良いと学んだので、これを使ってリーマンゼータ関数の収束発散を調べていた。

\int_{1}^{n} \frac{1}{ \sqrt{x} }dx = 2 ( \sqrt{n} - 1 ) \to \infty (n \to \infty)
よって \zeta ( \frac{1}{2} ) は発散

\int_{1}^{n} \frac{1}{x}dx = \log n \to \infty (n \to \infty )
よって \zeta ( 1 ) は発散

\int_{1}^{n} \frac{1}{x \sqrt{x} }dx = 2( 1 - \frac{1}{ \sqrt{n} } ) \to 2 (n \to \infty )
よって \zeta ( \frac{3}{2} ) は収束

\int_{1}^{n} \frac{1}{x^2}dx = 1 - \frac{1}{n} \to 1 ( n \to \infty )
よって \zeta (2) は収束
( \zeta (2) の収束値はバーゼル問題として有名 ( バーゼル問題 - Wikipedia ) )



ここからリーマンゼータ関数の収束条件をどこまで絞れるかと考えていたところ、Twitterにて「ゼータ関数に関する収束、発散の条件は定理としてまとめられている」と教えていただいたので、調べてみることに。
すると「複素数sの実部が１より大きいとき、 \zeta (s) は収束する」と書いてあった。

そういえば、と思って n \in \mathbb{R} のときの \int x^n dx の積分を思い出してみると、

n \neq -1 のとき \int x^n dx = \frac{ x^{n+1} }{ n+1 } + C
n = -1 のとき \int \frac{1}{x} dx= \log x +C

であり、 n=-1 のときは x \to \infty で発散するのは明らかで、
n \neq -1 のときの \frac{ x^{n+1} }{ n+1 } について x \to \infty で収束する条件は、
x の指数が負になること、つまり、 n+1 < 0 \Longleftrightarrow n < -1
よって、たしかに実数の場合でいえば、 s > 1 のとき \zeta(s) は収束する。

以上のように、 s \in \mathbb{R} における \zeta (s) の収束条件は比較的簡単にわかるんだなと実感。
s \in \mathbb{C} にまで拡張すると、おそらく複素数の積分の知識がいるはずなので、今の私には無理だと早々に諦めることにした。
いつか理解できるようになれたら、また記事を書きたいと思った。

参考サイト
リーマンゼータ関数 - Wikipedia
ゼータ関数の定義と基本的な話 | 高校数学の美しい物語

「爆笑」するのは誰なのか

思ったこと 日本語

Twitterのタイムラインで流れてきたツイートに驚いたので、私が思ったことと、それに関連して調べたことをメモしておく。

 

その内容は、「リツイートで回ってきたツイートを見て、電車の中なのに爆笑してしまった」というもので、私が引っかかったのは「爆笑」という言葉。

「爆笑」という単語の意味は「大勢のひとが同時に笑うこと」である。この人はもしかして電車の中で知人と同じツイートを見ながら盛り上がっていたのかとはじめは思ったけれど、前後のツイートからそれはないと確信したので、おそらく「誤用」なのだろうと結論づけた。

 

 

言葉の乱れや誤用という言葉をよく目にする(それは主にいわゆる若者言葉やら抜き言葉についての言及のときに使われている)が、私はあまりこれらの言葉が好きではなくて、それは私が「言葉は移り変わっていくもの」だという認識をしているという理由からくる(だから私がこれらの言葉をつかうときは、「」をつけたり、「いわゆる」という言葉をつけたりしている)。

「爆笑」という言葉を「一人で大笑いする」という意味で使われているのを「誤用」だと思うのは今だけで、もう少しすれば、人数の考慮なしにつかえるようになるかもしれない。それがいつになるかはぜんぜんわからないし、すでに辞書によっては一人で笑う場合も使えると書いてあるらしい(それでも未だほとんどの辞書は複数人で笑うことだとしている)。

 

「言葉は移り変わっていくもの」だとしても、その変遷の間は意味が錯綜して、意思疎通が困難になる。複数の意味を持っているわけだから、言葉の使用者がどの意味で使ったのかを正しく判断しなければ、誤解が生まれてしまう。言葉の移り変わりは、より意思疎通をしやすくするためにあるはずなのに、弊害がとても大きいということを再認識した出来事だった。

 

 

以下参考にしたサイト 

「失笑」と「爆笑」の笑い方の違いについて ～誤用の多い失笑と爆笑の正しい意味は | コトバノ

コラム −日本語の乱れ−

文化庁 | 国語施策・日本語教育 | 国語施策情報 | 第20期国語審議会 | 新しい時代に応じた国語施策について（審議経過報告） | Ｉ 言葉遣いに関すること

言葉の意味が時代と共に変わるのであれば - 日本語 解決済 | 教えて！goo