2014年04月20日
睡眠時間
今日も寒い一日でした。本当に四月中旬なんだろうか。
明日はいつもより 30 分ほど早く起きなければいけません。少々ヘコんでいます。ちなみにいつもは 6 時に起きてます。寝るのがだいたい 0 時頃になるので 6 時間は寝ていることになります。しかし、睡眠時間が足りないようで、昼食後は眠気に襲われて特につらいです。
適正な睡眠時間は人によってバラバラで、通常は 6 時間程度と言われていますが自分の場合はもう少し必要なようです。睡眠時間は 1.5 時間単位にするとよいという事もあって、6 時間で足りなければ 7.5 時間眠ればいいものの、そこまで増やすことはできそうにありません。なので、休みの日にゆっくり眠ることで補うようにはしてます。そうは言ってもなかなか難しいですけどね。
今日も「アルゴリズムのコーナー」の作成をしていました。しかし、同じ事ばかり考えていると頭が煮つまってくるので、途中で「数学問題 bot」から問題を選んで悩んでました。
---
任意に選ばれた 4 つの整数を一度ずつ使い、四則演算子によって数式を作る。この時必ず 10 の倍数が作れることを示せ(wand125様)
まず、10 の倍数になるためには一桁目がゼロになればよく、一桁目の数は各整数の一桁目だけで決まるので、二桁目以降は無視できます。よって、ここからは一桁目の数だけを考えます。ゼロが入ればその数を掛けることでゼロになるので除外できます。また、同じ数が含まれればその差はゼロになるのでやはり除外できます。すると、考えられる組み合わせは 1 から 9 までの数から 4 つを選択する場合に限定されます。その数は
9C4 = 126 通り
です。まだひとつずつチェックするには大変な数なのでもう少し絞り込みます。
5 と偶数の両方が含まれるとそれらを掛けあわせることでゼロにすることができます。また、( 1, 9 )( 2, 8 )( 3, 7 )( 4, 6 ) の組み合わせも和はゼロになります。5 と奇数だけの組み合わせにすると、1, 3, 7, 9 の中から三つ選ぶ必要があり、どの組み合わせをとっても和がゼロになるペアが含まれるので、5 を含む場合は必ず 10 の倍数にすることができます。1, 2, 3, 4, 6, 7, 8, 9 から 4 つ選択し、かつ和がゼロになるペアを含まないようにするためには、( 1, 2, 3, 4 ) と ( 9, 8, 7, 6 ) の二つの組み合わせに対し、同じ位置の数を反転させて作られる全ての組み合わせだけを考えなければなりません。それは 24 = 16 通りあります。それらを列挙して調べてみると、
1, 2, 3, 4 ... 3 - 2 - 1 = 0
1, 2, 3, 6 ... 3 - 2 - 1 = 0
1, 2, 7, 4 ... 7 + 2 + 1 = 10
1, 8, 3, 4 ... 4 - 3 - 1 = 0
9, 2, 3, 4 ... 9 - 4 - 3 - 2 = 0
1, 2, 7, 6 ... 7 + 2 + 1 = 10
1, 8, 3, 6 ... 6 + 3 + 1 = 10
9, 2, 3, 6 ... 9 - 6 - 3 = 0
1, 8, 7, 4 ... 8 - 7 - 1 = 0
9, 2, 7, 4 ... 9 - 7 - 2 = 0
9, 8, 3, 4 ... 9 + 4 - 3 = 10
1, 8, 7, 6 ... 1 + 6 - 7 = 0
9, 2, 7, 6 ... 9 - 7 - 2 = 0
9, 8, 3, 6 ... 9 - 6 - 3 = 0
9, 8, 7, 4 ... 9 + 8 - 7 = 10
9, 8, 7, 6 ... 9 + 8 - 7 = 10
従って、必ず 10 の倍数が作れることになります。
---
他の問題を考えると、煮詰まっていた頭が整理できたりするようですね。最後に、この問題を考案して下さった wand125 様に感謝します。
それにしても、今月中に更新できるのか不安になってきました。あと三つほどヤマを越さなければいけません...
明日はいつもより 30 分ほど早く起きなければいけません。少々ヘコんでいます。ちなみにいつもは 6 時に起きてます。寝るのがだいたい 0 時頃になるので 6 時間は寝ていることになります。しかし、睡眠時間が足りないようで、昼食後は眠気に襲われて特につらいです。
適正な睡眠時間は人によってバラバラで、通常は 6 時間程度と言われていますが自分の場合はもう少し必要なようです。睡眠時間は 1.5 時間単位にするとよいという事もあって、6 時間で足りなければ 7.5 時間眠ればいいものの、そこまで増やすことはできそうにありません。なので、休みの日にゆっくり眠ることで補うようにはしてます。そうは言ってもなかなか難しいですけどね。
今日も「アルゴリズムのコーナー」の作成をしていました。しかし、同じ事ばかり考えていると頭が煮つまってくるので、途中で「数学問題 bot」から問題を選んで悩んでました。
---
任意に選ばれた 4 つの整数を一度ずつ使い、四則演算子によって数式を作る。この時必ず 10 の倍数が作れることを示せ(wand125様)
まず、10 の倍数になるためには一桁目がゼロになればよく、一桁目の数は各整数の一桁目だけで決まるので、二桁目以降は無視できます。よって、ここからは一桁目の数だけを考えます。ゼロが入ればその数を掛けることでゼロになるので除外できます。また、同じ数が含まれればその差はゼロになるのでやはり除外できます。すると、考えられる組み合わせは 1 から 9 までの数から 4 つを選択する場合に限定されます。その数は
9C4 = 126 通り
です。まだひとつずつチェックするには大変な数なのでもう少し絞り込みます。
5 と偶数の両方が含まれるとそれらを掛けあわせることでゼロにすることができます。また、( 1, 9 )( 2, 8 )( 3, 7 )( 4, 6 ) の組み合わせも和はゼロになります。5 と奇数だけの組み合わせにすると、1, 3, 7, 9 の中から三つ選ぶ必要があり、どの組み合わせをとっても和がゼロになるペアが含まれるので、5 を含む場合は必ず 10 の倍数にすることができます。1, 2, 3, 4, 6, 7, 8, 9 から 4 つ選択し、かつ和がゼロになるペアを含まないようにするためには、( 1, 2, 3, 4 ) と ( 9, 8, 7, 6 ) の二つの組み合わせに対し、同じ位置の数を反転させて作られる全ての組み合わせだけを考えなければなりません。それは 24 = 16 通りあります。それらを列挙して調べてみると、
1, 2, 3, 4 ... 3 - 2 - 1 = 0
1, 2, 3, 6 ... 3 - 2 - 1 = 0
1, 2, 7, 4 ... 7 + 2 + 1 = 10
1, 8, 3, 4 ... 4 - 3 - 1 = 0
9, 2, 3, 4 ... 9 - 4 - 3 - 2 = 0
1, 2, 7, 6 ... 7 + 2 + 1 = 10
1, 8, 3, 6 ... 6 + 3 + 1 = 10
9, 2, 3, 6 ... 9 - 6 - 3 = 0
1, 8, 7, 4 ... 8 - 7 - 1 = 0
9, 2, 7, 4 ... 9 - 7 - 2 = 0
9, 8, 3, 4 ... 9 + 4 - 3 = 10
1, 8, 7, 6 ... 1 + 6 - 7 = 0
9, 2, 7, 6 ... 9 - 7 - 2 = 0
9, 8, 3, 6 ... 9 - 6 - 3 = 0
9, 8, 7, 4 ... 9 + 8 - 7 = 10
9, 8, 7, 6 ... 9 + 8 - 7 = 10
従って、必ず 10 の倍数が作れることになります。
---
他の問題を考えると、煮詰まっていた頭が整理できたりするようですね。最後に、この問題を考案して下さった wand125 様に感謝します。
それにしても、今月中に更新できるのか不安になってきました。あと三つほどヤマを越さなければいけません...
2014年04月20日
オイラーのφ関数
暑くなったり、寒くなったり。調子が悪くなりそうです。
金曜日に飲み会があり、今日はしんどい一日でした。いや、二日酔いになるほど飲んではないんですけど、終了後すぐに電車に飛び乗って、座ることもできなかったので体の方は相当まいっていた模様。それでも、飲み会のおかげで作成できなかった週報を帰宅後に家で書いていました。しかし、途中で休憩を入れたら眠ってしまい、気がついたら朝の 8 時過ぎ。とりあえず週報を作成するためそのまま起きることに。昼食・夕食後に仮眠をとったので、だいぶマシな状態にはなりました。
さて、「数学問題 bot」から 2003 年の名古屋大の問題を選択してみました。
---
n を自然数とするとき m ≤ n で m と n の最大公約数が 1 となる自然数の個数を f(n) とする。
(中略)
2) p, q を互いに異なる素数とする。このとき f(pq) を求めよ。
pq 以下の自然数で、pq と互いに素ではない (最大公約数が 1 でない) 数は、0 < n < p の範囲の自然数 n と q の積 nq と 0 < m < q の範囲の自然数 m と p の積 mp、最後に pq そのものの 3 種類あります。
nq の個数は q から ( p - 1 )q までの p - 1 個。
mp の個数は p から ( q - 1 )p までの q - 1 個。
よって、pq 以下の自然数で pq と互いに素でない数は ( p - 1 ) + ( q - 1 ) + 1 = p + q - 1 個あり、1 から pq までは pq 個の数があるので、pq 以下の自然数で pq と互いに素となる数の個数 f(pq) は
f(pq) = pq - ( p + q - 1 ) = ( p - 1 )( q - 1 )個
になります。
---
さらに、素数 p のべき乗に対して、f( pk ) を求めてみましょう。
pk 以下の自然数で pk と互いに素でない数は、0 < n ≤ pk-1 の範囲の自然数 n と p の積 np となる数なので、その数は pk-1 個です。したがって、pk 以下の自然数で pk と互いに素となる数の個数 f( pk ) は
f( pk ) = pk - pk-1
になります。実は、任意の自然数 m と n が互いに素であれば、
f(mn) = f(m)f(n)
が成り立ちます。また、この関数 f の正体は「オイラーのφ関数 φ(m)」で、数学者オイラー ( Leonhard Euler ) が最初に紹介したと言われています。
a と m が互いに素であれば、a の φ(m) 乗を m で割った時の余りは必ず 1 になります。これを
aφ(m) ≡ 1 ( mod m )
と表します。m が素数 p のとき φ(p) = p - 1 なので、上式は
ap-1 ≡ 1 ( mod p )
です。これは「フェルマーの小定理」という有名な定理です。
もし、詳細を知りたいという方は「はじめての数論」という書籍を紹介しておきます。大学入試にも出題される可能性があるので、受験生の方も読んでおいて損はないと思います。
はじめての数論 原著第3版 -- 発見と証明の大航海-ピタゴラスの定理から楕円曲線まで
金曜日に飲み会があり、今日はしんどい一日でした。いや、二日酔いになるほど飲んではないんですけど、終了後すぐに電車に飛び乗って、座ることもできなかったので体の方は相当まいっていた模様。それでも、飲み会のおかげで作成できなかった週報を帰宅後に家で書いていました。しかし、途中で休憩を入れたら眠ってしまい、気がついたら朝の 8 時過ぎ。とりあえず週報を作成するためそのまま起きることに。昼食・夕食後に仮眠をとったので、だいぶマシな状態にはなりました。
さて、「数学問題 bot」から 2003 年の名古屋大の問題を選択してみました。
---
n を自然数とするとき m ≤ n で m と n の最大公約数が 1 となる自然数の個数を f(n) とする。
(中略)
2) p, q を互いに異なる素数とする。このとき f(pq) を求めよ。
pq 以下の自然数で、pq と互いに素ではない (最大公約数が 1 でない) 数は、0 < n < p の範囲の自然数 n と q の積 nq と 0 < m < q の範囲の自然数 m と p の積 mp、最後に pq そのものの 3 種類あります。
nq の個数は q から ( p - 1 )q までの p - 1 個。
mp の個数は p から ( q - 1 )p までの q - 1 個。
よって、pq 以下の自然数で pq と互いに素でない数は ( p - 1 ) + ( q - 1 ) + 1 = p + q - 1 個あり、1 から pq までは pq 個の数があるので、pq 以下の自然数で pq と互いに素となる数の個数 f(pq) は
f(pq) = pq - ( p + q - 1 ) = ( p - 1 )( q - 1 )個
になります。
---
さらに、素数 p のべき乗に対して、f( pk ) を求めてみましょう。
pk 以下の自然数で pk と互いに素でない数は、0 < n ≤ pk-1 の範囲の自然数 n と p の積 np となる数なので、その数は pk-1 個です。したがって、pk 以下の自然数で pk と互いに素となる数の個数 f( pk ) は
f( pk ) = pk - pk-1
になります。実は、任意の自然数 m と n が互いに素であれば、
f(mn) = f(m)f(n)
が成り立ちます。また、この関数 f の正体は「オイラーのφ関数 φ(m)」で、数学者オイラー ( Leonhard Euler ) が最初に紹介したと言われています。
a と m が互いに素であれば、a の φ(m) 乗を m で割った時の余りは必ず 1 になります。これを
aφ(m) ≡ 1 ( mod m )
と表します。m が素数 p のとき φ(p) = p - 1 なので、上式は
ap-1 ≡ 1 ( mod p )
です。これは「フェルマーの小定理」という有名な定理です。
もし、詳細を知りたいという方は「はじめての数論」という書籍を紹介しておきます。大学入試にも出題される可能性があるので、受験生の方も読んでおいて損はないと思います。
はじめての数論 原著第3版 -- 発見と証明の大航海-ピタゴラスの定理から楕円曲線まで
