Fussy's Diary

今日は鏡開き。ということで、昼はぜんざいを食べました。

鏡餅は鏡開きの日に食べるわけですが、昔は固くなった餅を割って食べたのでずいぶんと硬かった思い出があります。今では餅がパックに入ったものが売られているので餅が硬くなることもなく、しかも取り出して調理するだけで済むというのは便利な世の中になったものだと思います。
餅を使った料理というと、雑煮・ぜんざい・焼き餅くらいが定番でしょうか。「餅 レシピ」でググってみたら、オニオンスープとチーズでグラタン風にしたり、ホットケーキに入れたり、牛乳やココアと合わせてみたりといろんなレシピが見つかりました。こういうアイデアが浮かぶというのはすごいものだと思います。

さて、今回は「数学問題bot」のこんな問題を解いてみました。

-----

1) 自然数 n を 2 つの自然数 p, q の和 ( n = p + q ) に分解した時、常に p, q が互いに素であるならば、n は素数であることを示せ。
2) 1000を 2 つの互いに素な自然数の和に分解する方法は何通りか。ただし和の順番を入れ替えたものは同じとみなす。( nyoki1007 様 )

1) n が合成数ならば、2 以上の二つの因数 k, m に分解できるので、m = p' + q' とすれば

n = km = k( p' + q' ) = kp' + kq'

と表すことができます。従って、p = kp', q = kq' とすれば、互いに素でない二つの数 p, q の和で表すことができます。

従ってその対偶として、常に p, q が互いに素ならば n は素数であることになります。

2) 合成数 N が素因数 p1^r1p2^r2 ... pm^rm ( rk ( k = 1, 2, ... m ) > 0 ) に分解できるとします。N > L を満たす L が N の中の素因数で構成され、

L = p1^s1p2^s2 ... pm^sm・Q ( sk ≥ 0 )

で表されるならば、rk, sk のうち最小値を tk として

N - L = p1^t1p2^t2 ... pm^tm( p1^r1-t1p2^r2-t2 ... pm^rm-tm - p1^s1-t1p2^s2-t2 ... pm^sm-tmQ )

となります。p1^t1p2^t2 ... pm^tm は L も共有する因数なので、N - L と L は互いに素ではない数であり、その和は N になります。逆に、L が N と共通な因数を一つも持たなければ、N - L とも共通の因子を持たないことになり、L と N - L は互いに素になります。

1000 = 2³5³ なので、素因数として 2 と 5 を持ちます。1 から 500 の間で素因数 2 を持つ数は 250 個、5 を持つ数は 100 個あります。しかし、2, 5 の両方を持つ数は 10 の倍数で 50 個あるので、2, 5 のいずれかを素因数に持つ数は 250 + 100 - 50 = 300 個あります。よって、500 - 300 = 200 個の数は 2, 5 のいずれも素因数として持たず、この数との和が 100 になる組み合わせ全てが互いに素になります。従って、答えは 200 個になります。
  

あっという間の正月休み。明日から仕事です。

正月明けからはダラダラと毎日過ごしていたので、明日からちゃんと仕事できるか非常に心配です。心なしか、頭の方もあまり回っていないようなので、過去にストックしておいた中で軽めの問題を解いてみました。今回は「数学問題bot」からの出題です。

-----

■ a > b > c > d > e > f を満たし a + f = b + e = c + d = 22 となるような正の整数の組 ( a, b, c, d, e, f )はいくつあるか。(10数オリ予選)

6 つの数は正値でなので a の最大値は 21 でなければなりません。よって、b の最大値は 20、c の最大値は 19 です。また、c > d を満たす c の最小値は 12 です。よって、c は 12 から 19 までの値を取りえます。
a, b, c の値が決まれば d, e, f の値は自動的に決まり、a > b > c なら必ず d > e > f が成り立つので、a, b, c の組み合わせだけ考えれば十分です。c = 19 の時は a = 21, b = 20 の組み合わせしかありません。c = 18 のとき、( a, b ) の取りうる値は

( a, b ) = ( 21, 20 ) ( 21, 19 ) ( 20, 19 )

であり、c = 17 ならば

( a, b ) = ( 21, 20 ) ( 21, 19 ) ( 20, 19 ) ( 21, 18 ) ( 20, 18 ) ( 19, 18 )

です。よくみると、一つ前に求めた組み合わせは必ず含まれ、b = c + 1 のときの組み合わせが新たに追加されていることがこの結果からわかります。前に求めた組み合わせは、c が一つ小さくなっても必ず含まれることは明らかで、しかもそれは b > c + 1 の場合全てを含みます。従って、b = c + 1 のときの組み合わせの数を計算しさえすれば、前の結果を加算することで求める答えを得ることができます。その数は、a > b = c + 1 になる場合の数であり、21 - ( c + 1 ) です。c = 16 のとき、その数は 4 であり、実際に組み合わせを求めてみると

( a, b ) = ( 21, 20 ) ( 21, 19 ) ( 20, 19 ) ( 21, 18 ) ( 20, 18 ) ( 19, 18 ) ( 21, 17 ) ( 20, 17 ) ( 19, 17 ) ( 18, 17 )

で確かに一致します。よって、組み合わせの数は

1 + ( 1 + 2 ) + ( 3 + 3 ) + ( 6 + 4 ) + ( 10 + 5 ) + ( 15 + 6 ) + ( 21 + 7 ) + ( 28 + 8 )
= 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 = 120 通り

になります。

例によって、正解である保証はありません。  

仕事納めの前日に録画しておいた「NHK オックスフォード白熱教室」を昨日見ていました。

「知の限界」というタイトルで「無理数」「カオス理論」「不完全性定理」の三つをテーマにした講演でした。一般者向けの講演というだけあって、非常に難解なテーマをうまくまとめていました。しかし、理解した気にはさせられるのですが、考えれば考えるほどわけが分からなくなるテーマでもあります。不完全性定理の話では非常に簡潔に説明をしていました。なんとなくボンヤリとわかったような気にはなったので、もう一度定理の理解にチャレンジしたいと思います(実は二回ほど理解しようとチャレンジしてことごとく玉砕しています)。
最後に、人間の頭脳に限界はあるのかという話がありました。個人的には何らかの限界はあると思っています。しかし、まだその限界まで至っているわけでないとも信じています。「数の理論の中では知ることができないものがある」ことが証明できてしまうなんて、「不完全性定理」が発表される前はだれも思いもしなかったことでしょうから、これからも驚異的な発見というのはあると思うし、それを楽しみにしていきたいですね。

ということで、これが本当に今年最後の数学の問題になりそうです。今回は「数論bot ( @N_problem_bot )」からの出題です。

-----

■ n を 2 以上の整数とし、p を素数とする。n | p - 1 かつ p | n³ - 1 ならば 4p - 3 は平方数であることを示せ(出典:mathlinks)

n³ - 1 = ( n - 1 )( n² + n + 1 ) より p | n³ - 1 ならば p | n - 1 または p | n² + n + 1 が成り立ちます ( ちなみにこれは p が素数だから成り立ちます )。

p | n - 1 かつ n | p - 1 ならば p ≤ n - 1 かつ n ≤ p - 1 でありこれは成り立たちません。よって、p | n² + n + 1 かつ n | p - 1 が成り立つことになります。。

n | p - 1 より p - 1 = Kn とすれば、p = Kn + 1 なので、Kn + 1 | n² + n + 1 が成り立ちます。任意の n に対してこれを満たす K として n + 1 があり、このときは n² + n + 1 = Kn + 1 なので、K は n + 1 より大きくはなれません。また、K ≤ 0 のとき p は 1 以下の数となるので無視できます。そこで、1 ≤ K ≤ n + 1 に対して、n + 1 以外に Kn + 1 | n² + n + 1 を満たす K を考えます。
K = n のときは、Kn + 1 = n² + 1 で、n² + n + 1 との剰余は n になります。K = n - 1 の場合、Kn + 1 = ( n - 1 )n + 1 = n² - n + 1 で、剰余は 2n です。このように、剰余は n ずつ大きくなり、やがて Kn + 1 を超えるのでさらに割ることができますが、剰余が n の倍数であるのに対し、Kn + 1 は n の倍数ではなりえないので、割り切ることができません。従って、Kn + 1 | n² + n + 1 を満たす K は n + 1 以外にはありません。
最後に、K = n + 1 のとき p = n² + n + 1 なので、4p - 3 = 4( n² + n + 1 ) - 3 = 4n² + 4n + 1 = ( 2n + 1 )² であり、平方数であることが示されました。

K = n - L としたとき、剰余は ( L + 1 )n と表されます。K = L = n / 2 ( n | p - 1 より p が奇素数なら n はかならず偶数です ) のときに剰余が n² / 2 + n となり、Kn + 1 = n² / 2 + 1 より剰余は初めてさらに割ることができるようになります。K = 1 のとき Kn + 1 = n なので、剰余は必ず 1 になります。n = 10 を例にすると、n² + n + 1 = 111 なので、剰余は以下のように変化します。

K	Kn + 1	剰余
11	111	0
10	101	10
9	91	20
8	81	30
7	71	40
6	61	50
5	51	9
4	41	29
3	31	18
2	21	6
1	11	1

例によって合っている保証はなく、他にもっとエレガントな解法もあると思います。これでも結構悩んだんですけどね。  

今年もあと 10 日ほどとなりました。

年末になると大掃除と同時に不要品の整理なんかをします。いつも思いますが、普段からやっておけば慌てる必要もないんですよね。しかし、なぜかそれができない。そろそろ、なんとかしなければ。PCのバックアップもこの頃に行います。これも普段からしておけばいいんですけど、それをしないのでもしものときに慌てふためく事になるわけです。で、RAID付きの外付けディスクでも買おうかと悩んでいます。結構高いんですよね。

今年最後になるかもしれない数学の問題へのチャレンジです。結構前から悩んでいた問題で、ようやく一つの解き方を見つけたといった感じです。しかし、解き方は完全ではないし、他にもっとエレガントな解き方があるのではないかと思います。出題は「数学問題bot」からです。

-----

■ √2 + √3 + √5 + √7 が無理数であることを証明せよ (近畿大学第12回数学コンテスト)

まず、q を有理数として √2＋√3＋√5＋√7 = q が成り立つとします。この両辺の二乗を計算します。

( √2＋√3＋√5＋√7 )²
= 2 + 3 + 5 + 7 + 2_2:3 + 2_2:5 + 2_2:7 + 2_3:5 + 2_3:7 + 2_5:7
= 17 + 2_2:3 + 2_2:5 + 2_2:7 + 2_3:5 + 2_3:7 + 2_5:7 = q² より

2:3 + 2:5 + 2:7 + 3:5 + 3:7 + 5:7 = q² / 2 - 17 / 2

となります。但し、2_2:3 = 2√2√3 を表しています。このとき、右辺はやはり有理数となります。これをもう一度二乗します。

( 2:3 + 2:5 + 2:7 + 3:5 + 3:7 + 5:7 )²
= 6 + 10 + 14 + 15 + 21 + 35 + 24_2:3 + 20_2:5 + 16_2:7 + 18_3:5 + 14_3:7 + 10_5:7 + 6_2:3:5:7
= ( q² / 2 - 17 / 2 )² より

24_2:3 + 20_2:5 + 16_2:7 + 18_3:5 + 14_3:7 + 10_5:7 + 6_2:3:5:7 = ( q² / 2 - 17 / 2 )² - 101

となります。ここでも右辺はやはり有理数です。これを繰り返すと、左辺は常に 2:3, 2:5, 2:7, 3:5, 3:7, 5:7, 2:3:5:7 の線形結合で表され、右辺は常に有理数です。

左辺が ( K1_2:3 + K2_2:5 + K3_2:7 + K4_3:5 + K5_3:7 + K6_5:7 + K7_2:3:5:7 )² のとき、これを展開すると

( 6K1² + 10K2² + 14K3² + 15K4² + 21K5² + 35K6² + 210K7² ) +
( 10K2K4 + 14K3K5 + 70K6K7 )_2:3 + ( 6K1K4 + 14K3K6 + 42K5K7 )_2:5 +
( 6K1K5 + 10K2K6 + 30K4K7 )_2:7 + ( 4K1K2 + 28K3K7 + 14K5K6 )_3:5 +
( 4K1K3 + 20K2K7 + 10K4K6 )_3:7 + ( 12K1K7 + 4K2K3 + 6K4K5 )_5:7 +
( 2K1K6 + 2K2K5 + 2K3K4 )_2:3:5:7

となるので、( K1, K2, K3, K4, K5, K6, K7 ) = ( 1, 1, 1, 1, 1, 1, 0 ) を初期値として二乗したときの式を無限に作成することができます。その中の 7 つの式を使って連立方程式を計算すれば、2:3 から 2:3:5:7 までの値を求めることができます。ところが、右辺は有理数なので、その解はやはり有理数になります。これは、2:3 から 2:3:5:7 までの値が全て有理数であることを意味します。しかし、これらは無理数であるため、最初の仮定に矛盾します。従って、√2＋√3＋√5＋√7 は無理数です。

次に、この連立方程式が解を持つことを示さなければなりません。が、これは証明することができなかったので、実際に数値計算をしてみることにしました。まず、連立方程式の係数を求めるプログラムを作成します。

template<class T> void calcK( const std::vector<T>& k, std::vector<T>* res )
{
  if ( k.size() != 8 ) return;

  res->resize( k.size() );

  (*res)[0] = 6 * k[1] * k[1] + 10 * k[2] * k[2] + 14 * k[3] * k[3] +
  15 * k[4] * k[4] + 21 * k[5] * k[5] + 35 * k[6] * k[6] +
  210 * k[7] * k[7];
  (*res)[1] = 10 * k[2] * k[4] + 14 * k[3] * k[5] + 70 * k[6] * k[7];
  (*res)[2] = 6 * k[1] * k[4] + 14 * k[3] * k[6] + 42 * k[5] * k[7];
  (*res)[3] = 6 * k[1] * k[5] + 10 * k[2] * k[6] + 30 * k[4] * k[7];
  (*res)[4] = 4 * k[1] * k[2] + 28 * k[3] * k[7] + 14 * k[5] * k[6];
  (*res)[5] = 4 * k[1] * k[3] + 20 * k[2] * k[7] + 10 * k[4] * k[6];
  (*res)[6] = 12 * k[1] * k[7] + 4 * k[2] * k[3] + 6 * k[4] * k[5];
  (*res)[7] = 2 * k[1] * k[6] + 2 * k[2] * k[5] + 2 * k[3] * k[4];
}

int main( int argc, char* argv[] )
{
  std::vector<double> k( 8, 1 );
  k[0] = 8.5;
  k[7] = 0;
  std::vector<double> res;

  for ( unsigned int i = 0 ; i < 7 ; ++i ) {
    for ( std::vector<double>::const_iterator cit = k.begin() ;
          cit != k.end() ; ++cit )
      printf( "%f ", *cit );
    std::cout << std::endl;
    calcK( k, &res );
    k = res;
  }
}

初期値を 定数項 17 / 2、2:3:5:7 の係数をゼロ、その他を全て 1 として、( √2＋√3＋√5＋√7 )² をスタートとして最初の 7 つの方程式を求めます。すると、定数項を含めた係数行列は次のようになります。

( 定数項, K1, K2, K3, K4, K5, K6, K7 ) =
( 8.50000E+00, 1.00000E+00, 1.00000E+00, 1.00000E+00, 1.00000E+00, 1.00000E+00, 1.00000E+00, 0.00000E+00 )
( 1.01000E+02, 2.40000E+01, 2.00000E+01, 1.60000E+01, 1.80000E+01, 1.40000E+01, 1.00000E+01, 6.00000E+00 )
( 3.10760E+04, 1.09360E+04, 8.36000E+03, 7.25600E+03, 6.56800E+03, 5.73600E+03, 4.52000E+03, 1.61600E+03 )
( 4.75505E+09, 1.64307E+09, 1.27944E+09, 1.07266E+09, 1.05699E+09, 8.84475E+08, 6.80756E+08, 2.90082E+08 )
( 1.15754E+20, 4.06293E+19, 3.14194E+19, 2.66279E+19, 2.55509E+19, 2.16682E+19, 1.68184E+19, 6.76792E+18 )
( 6.88744E+40, 2.40734E+40, 1.86577E+40, 1.57542E+40, 1.52542E+40, 1.28776E+40, 9.96809E+39, 4.08898E+39 )
( 2.43947E+82, 8.53950E+81, 6.61344E+81, 5.59108E+81, 5.39745E+81, 4.56340E+81, 3.53560E+81, 1.44110E+81 )

定数項は右辺に移行すると、係数行列は 7 行 7 列の正方行列になります。Excel 等でこの行列式を計算すると、-7.97570E+135 という値になります。つまり、係数行列は非特異なので、この連立方程式は解くことができることになります。ちなみに、√2＋√3＋√5＋√7 = 8.02808 を使って右辺の値を求めると

( 2.37251E+01, 4.61879E+02, 1.82256E+05, 2.84622E+10, 6.94340E+20, 4.13234E+41, 1.46368E+83 )

となり、係数行列の逆行列は

( -3.46178E-01, 8.39753E+00, -4.03202E+00, -6.10160E-04, 2.46200E-13, 1.08539E-33, -4.10863E-75 )
( -1.03701E+00, -3.55841E+01, 1.34416E+01, 2.11717E-03, -8.41981E-13, -3.72926E-33, 1.40945E-74 )
( 1.27076E-03, 1.74473E+01, -2.33385E+00, -5.04553E-04, 1.80766E-13, 8.28950E-34, -3.09690E-75 )
( -1.00712E-01, 1.20718E+01, 4.56727E-01, -5.46006E-05, 1.35736E-15, 3.40899E-35, -9.26729E-77 )
( 1.91843E+00, 4.77461E-01, -1.50246E+01, -1.83415E-03, 8.06807E-13, 3.46302E-33, -1.32290E-74 )
( 5.64193E-01, -2.80997E+00, 7.49210E+00, 8.86292E-04, -3.93149E-13, -1.68219E-33, 6.43262E-75 )
( -2.76518E-01, 6.01798E+00, -1.25341E+00, -3.04790E-04, 1.08388E-13, 4.99769E-34, -1.86434E-75 )

なので、逆行列と右辺の積から √6, √10, √14, √15, √21, √35, √210 の値が計算できます。

最後に、二つの ( 一つだけ 4 つのものもありますが ) 異なる素数の積の平方根が無理数になることの証明ですが、これは √2 が無理数であることの証明法を応用すれば簡単に求められます。

二つの異なる素数の積の平方根 √pq が有理数 m / n ( 但し m, n は互いに素 ) と等しいとします。両辺を二乗すると

pq = m² / n² より

n²pq = m²

なので、m は p, q の両方を素因数に持ちます。m = m'pq とすると、

n²pq = m'²p²q² より

n² = m'²pq

となります。ところが、これが成り立つためには n が p, q の両方を素因数に持たなければなりません。これは最初の仮定 ( m, n が互いに素である ) に反します。従って、 √pq は無理数であることになります。4 つの異なる素数の積の平方根が無理数であることも同様に証明できますし、任意の数の異なる素数の積の平方根について成り立つことも理解できると思います。

-----

例によって、合っているという保証は全くありません。気になるのが、素数の平方根を任意の数だけ加算したとき、それは必ず無理数になるのかどうかというところです。これが証明できれば上の問題も自明になるのですけどね。  

今夜は猛烈に寒いですね。

今日から「NHK 白熱教室」で「オックスフォード白熱教室」が始まりました。最初のテーマは「素数」。ガウスの時代に予想された素数定理が、リーマンによって精度の高い式になる様子が音楽を使って説明されていました。非常にわかりやすい講義で、数学嫌いの方にもお勧めできる内容です。次回もぜひ見たいですね。

リーマン予想をテーマとした本に「素数に憑かれた人たち」というものがあります。これもなかなか面白い本でした。専門書の類ではないので内容もそれほど難しいことはなく、素数定理とゼータ関数の関係についてもわかりやすく説明してあります。もし興味のある方はぜひ読んでみてください。  

今日は「小雪」。雪が少し降り始める頃だそうですが、北海道などでは結構降ってますよね。北国ではあれでも少ない方なのでしょうかね。名古屋だったら確実に交通マヒしてしまう量です。

「Poisson Blending」という、画像の重ね合わせを自然に行うための手法について、サンプル・プログラムを見つけたのでそれを利用して簡単なツールを作成してみました。うまくいく場合があればダメな場合もあって、どこかに不具合がある可能性もあるので、もう少しテストが必要そうですが、それでも面白い結果が得られるのでなかなか楽しめます。サンプル・プログラムを公開して下さった方に感謝。

そして、恒例の大学入試問題ですが、今回は「数学問題bot(個人用)」から名古屋大の問題を取り上げました。例によって合っている保証はないです。一週間ほど、暇を見つけてはチャレンジしていました。

-----

■ a ≥ b > 0 とする。自然数 n に対して、次の不等式を証明せよ。
aⁿ - bⁿ ≤ ( n / 2 )( a - b )( a^n-1 + b^n-1 )　(1982年名大)

a > 0 なので、両辺を aⁿ で割ると、

(左辺) = 1 - ( b / a )ⁿ

(右辺) = ( n / 2 )( 1 - b / a )[ 1 + ( b / a )^n-1 ]

そこで、b / a = x とすると 0 < x ≤ 1 で、(左辺) と (右辺) は

(左辺) = 1 - xⁿ

(右辺) = ( n / 2 )( 1 - x )( 1 + x^n-1 )

となります。(左辺) は

(左辺) = ( 1 - x )( 1 + x + x² + ... + x^n-1 )

なので、1 - x = 0 ( つまり a = b ) なら両辺は等しくなり成り立ちます。それ以外なら 1 - x > 0 なので、両辺を 1 - x で割って

(左辺) = 1 + x + x² + ... + x^n-1

(右辺) = n( 1 + x^n-1 ) / 2

の大小関係を調べればよいことになります。n = 1 のとき、(左辺) = 1、(右辺) = 1 で成り立ちます。

1 + x + x² + ... + x^n-1 ≤ n( 1 + x^n-1 ) / 2

が成り立つと仮定したとき、

1 + x + x² + ... + xⁿ
= 1 + x( 1 + x + ... + x^n-1 )
≤ 1 + nx( 1 + x^n-1 ) / 2

で、n + 1 のときの (右辺) = ( n + 1 )( 1 + xⁿ ) / 2 と 1 + nx( 1 + x^n-1 ) / 2 との差は

( n + 1 )( 1 + xⁿ ) / 2 - [ 1 + nx( 1 + x^n-1 ) / 2 ]
= ( n + nxⁿ + 1 + xⁿ - 2 - nx - nxⁿ ) / 2
= [ n( 1 - x ) + xⁿ - 1 ] / 2

となります。これを f(x) とすると f(0) = ( n - 1 ) / 2 ≥ 0、f(1) = 0 です。f'(x) は

f'(x) = ( -n + nx^n-1 ) / 2 = n( x^n-1 - 1 ) / 2

で、0 < x < 1 において f'(x) < 0 なので、f(x) は 0 < x < 1 の範囲で単調減少で極値を持ちません。

従って、f(x) ≥ 0 ( 0 < x ≤ 1 ) が成り立ち、

1 + x + x² + ... + xⁿ ≤ 1 + nx( 1 + x^n-1 ) / 2 ≤ ( n + 1 )( 1 + xⁿ ) / 2

となることが示されるので、帰納法により不等式が成り立つことが証明されました。

-----

(補足) 元のサイトでは、(右辺) が ( n / 2 )( a - b )( a^n-1 - b^n-1 ) となっていました。しかし、この場合 n = 1 のときはゼロになってしまうので、不等式が成り立たず、他のサイトで符号が違うことを確認しました。作者さんへは返信をしていますが、今のところはまだ修正されていないようです。  

AI を使って東大入試に合格させようというプロジェクトが話題になってます。

学習アルゴリズムや分散処理技術の発達で、今やかなり専門的な分野にまでコンピュータが利用できる範囲が及んでいるように思います。メディアで話題になっていたのが将棋プログラムで、あれもひと昔前までは人間に勝つことは不可能とまで言われていたのに、今ではプロの棋士も打ち負かしてしまうというのはすごいものです。SF の世界にあるような、人工知能が暴走して人間を襲うようになることが将来起こらないことを祈ります。いや、本当に。

人工知能に負けないよう、今回もちょっとした問題を解いてみました。「数学問題bot」から今回は千葉大の問題です。パズルを解くような感じの問題でした。

-----

■ 自然数 a, b, c, d は c = 4a + 7b, d = 3a + 4b を満たしているものとする。1) c + 3d が 5 の倍数ならば 2a + b も 5 の倍数であることを示せ。2) a と b が互いに素で、c と d がどちらも素数 p の倍数ならば p = 5 であることを示せ(09千葉大前期)

1)

c + 3d
= ( 4a + 7b ) + 3( 3a + 4b )
= 13a + 19b
= 5( 3a + 4b ) - ( 2a + b ) より

右辺がが 5 の倍数になるためには 2a + b が 5 の倍数にならなければなりません。

2)

3c - 4d = 5b
4c - 7d = -5a

で、c, d は p を共通因数にもつので、5b と -5a も p の倍数です。ところが a, b は互いに素なので、5b と 5a は 5 以外に共通因数を持ちません。従って p = 5 でなければなりません。

例によって合っているという保証なしです。  

今日はインフルエンザの予防接種のため病院まで行ってきました。

行ってきたのは内科の病院で最近は行くこともなかったので久々に先生にお会いしたわけですが、去年よりも少し太ったと指摘されました。最近気にはしてるんですよね。

小学校の時に習うのになぜそうなるのかは説明がされず、気が付くと疑問にも思わずに使っていたというものに負数どうしの掛け算というものがあります。なぜ、マイナスとマイナスを掛けるとプラスになるのでしょうか。

■ -1 x -1 = 1 の証明

まず、以下の三つは成り立つことを前提とします。

1) 0 にどんな数を掛けても結果は 0 になる。任意の整数 N に対して 0 x N = N x 0 = 0。
2) 1 にどんな数を掛けても結果は変わらない。任意の整数 N に対して 1 x N = N x 1 = N。
3) 任意の整数 K, M, N に対して、展開公式 K x ( M + N ) = ( M + N ) x K = K x M + K x N が成り立つ。

すると、1) より

0 x (-1) = 0

が成り立ちます。0 = 1 + (-1) なので、上式は

[ 1 + (-1) ] x (-1) = 0

で、3) の展開公式から

1 x (-1) + (-1) x (-1) = 0

となります。2) より 1 x (-1) = -1 なので、

-1 + (-1) x (-1) = 0

となって、この等式が成り立つためには

(-1) x (-1) = 1

でなければなりません。従って、(-1) x (-1) = 1 になります。

自然数どうしの掛け算は、ある数を他の数の回数だけ(ゼロに)加算するという意味です。3 x 2 なら、3 を 2 回加えるという意味なので結果は 6 になります。よって、0 を掛けるということは 0 回加算する意味になって結果は必ずゼロ、1 を掛けるということは 1 回加算することなので結果は変化しない事になります。
3 x 2 を逆の 2 x 3 にしても結果は変化しません。これはどう説明すればいいでしょうか。3 は 1 を 3 回加えたもので、2 は 1 を 2 回加えたものです。これをマッチ棒に例えると、マッチ棒三本のグループが二つの場合とマッチ棒二本のグループが三つの場合でマッチ棒の本数が等しいことを意味します。グループの中から一本ずつマッチ棒を抜き取ると、グループ数と等しいマッチ棒を持った異なるグループができて、抜き取られたグループは一本ずつマッチ棒が少なくなります。これを繰り返すと、元のグループ数と等しいマッチ棒を持ったグループが、元のグループにあったマッチ棒の数と等しい分だけ得られます。つまり、M 本のマッチ棒を持った N 個のグループが、N 本のマッチ棒を持った M 個のグループに変化するわけです。
展開公式は、M + N 本のマッチ棒を持ったグループを、M 本のマッチを持ったグループと N 本のマッチを持ったグループに分ける操作と同じ意味になります。このように、自然数だけを相手にすれば、掛け算の意味がきちんと説明できます。

負の数が加わるとどうなるでしょうか。-N を掛けるというのは、ある数を -N 回加える、逆に考えれば N 回引くことと解釈できます。すると、5 x -2 は 5 を 2 回引くと考えて -10 と求めることができます。-1 x -1 は、-1 を 1 回引く操作と解釈できます。ゼロから 1 回だけ -1 を引けば、それは 1 になります。こうやって考えると、先ほど示したように計算のつじつまが合うようになります。そもそも -1 回なにか行うといったことはできないわけで、逆のことをすると解釈するしかありません。 -1 回もらうなら 1 回与える、-1 歩東に進むのなら 1 歩西に進むといった具合に。  

週末の夜、いつもながらホッとします。

今まで Twitter から得た数学の問題、最近はあまりチャレンジしていませんでした。久々に一問解いてみたので紹介しておきます。問題は「数学問題bot」から選択しました。例によって正解している保証なしです。

-----

■ ある整数を 14 で割った商は整数、余りは 0 以上 14 未満の整数とする。a は 14 で割ると 6 余る整数、b は 14 で割ると 1 余る整数である。二次方程式 x² - 2ax + b = 0 が整数解を持つとき、整数解を 14 で割った余りを求めよ(06慶應)

二次方程式の解を m, n とすると

m + n = 2a
mn = b

で、a, b はともに整数なので、二次方程式の解の一つが整数なら両方とも整数解であることになります。

m = 14p + r
n = 14q + s

とすると、

m + n = 14( p + q ) + ( r + s ) = 2a
mn = 14²pq + 14( ps + qr ) + rs = b

なので、r + s と rs を 14 で割った余りはそれぞれ 12 と 1 です。r は 0 から 13 までの値を取りうるので、各 r に対応する s の値から rs を 14 で割った余りを求めると、

r x s → 余り
0 x 12 → 0
1 x 11 → 11
2 x 10 → 6
3 x 9 → 13
4 x 8 → 4
5 x 7 → 7
6 x 6 → 8
7 x 5 → 7
8 x 4 → 4
9 x 3 → 13
10 x 2 → 6
11 x 1 → 11
12 x 0 → 0
13 x 13 → 1

となって、余りが 1 になるのは r, s がともに 13 のときです。従って答えは 13 になります。

ちなみに、r, s がともに 13 であっても a, b の 14 で割った剰余がそれぞれ 6, 1 になるとは限りません。a の剰余が 6 ならば 2a の剰余は 12 ですが、その逆は成り立たないからです。例えば、m = n = 13 のとき a = 13, b = 169 となり、b の剰余は 1 ですが a の剰余は 6 ではありません。m と n を加算してはじめて剰余が 12 になります。  

台風が過ぎたら急に寒くなってきましたね。このまま冬に突入でしょうか。

少し前に「フェルマーの小定理」を紹介しましたが、同じ「フェルマー」つながりで「フェルマーの最終定理」というのがあります。フェルマーは 1600 年代に活躍した数学者です。彼が残した定理の多くは彼自身が証明したものではなく、後に他の数学者たちが証明 (誤りであったものも含めて) しました。最後に残った定理が「フェルマーの最終定理」で、証明されたのは 300 年以上もあとの 1995 年。アンドリュー・ワイルズによって証明が成し遂げられるまで多くの数学者達を悩ませてきたことになります。

----------------------------------
「フェルマーの最終定理」

3 以上の自然数 n に対し、xⁿ + yⁿ = zⁿ を満たすゼロでない自然数 x, y, z は存在しない。
----------------------------------

この定理がわかっていれば、次の問題を解くこともできます。

----------------------------------
大きさの等しい立方体の積み木 ( 角砂糖やサイコロでもOK ) を積み重ねた一つの大きな立方体に対し、これをバラバラにして二つの立方体にすることは可能か。
----------------------------------

大きな立方体の縦・横・高さが z 個分あったとすれば、使用した積み木の数は z³ 個です。これを、二つの立方体に分けたいわけだから、

x³ + y³ = z³

を満たすゼロより大きな自然数 x, y, z を見つけることを意味して、これは「できない」ということになります。立体ではなく平面で考えれば、これはピタゴラスの定理を満たす自然数の組を見つけることを意味するので、無数に見つけることができます。

似たような問題はいくらでも考えることができて、例えば

----------------------------------
大きさの等しい立方体の積み木 ( 角砂糖やサイコロでもOK ) を積み重ねた一つの大きな立方体に対し、これをバラバラにしていくつかの立方体にすることは可能か。但し、全ての立方体が積み木一つだけという場合を除く。
----------------------------------

----------------------------------
大きさの等しい正方形の紙をを並べた一つの大きな正方形に対し、これをバラバラにして三つ以上の正方形にすることは可能か。但し、全ての正方形が紙一枚だけという場合を除く。
----------------------------------

などというものも考えられます。暇つぶしにいかがでしょうか。  

先週から喉が痛く、今度は咳が止まらなくなりました。この時期になるといつもこうなるのですが、風邪というわけでもないんですよね。

以前、フェルマーの小定理の証明法を紹介したので、今度はこれを一般化したオイラーの定理を証明してみます。

-----------------------------------------------------------------------------
オイラーの定理

m を正の整数、a を m と互いに素な整数とするとき、

a^φ(m) ≡ 1 ( mod m )

が成り立つ。但し、φ(m) はオイラーの φ 関数で、1 から m の間で m と互いに素な数の個数
-----------------------------------------------------------------------------

(証明)

フェルマーの小定理の証明では、a が素数 p と互いに素ならば

a, 2a, 3a, ... ( p - 1 )a

を p で割った p - 1 個の剰余が、適当に順番を入れ替えることで重複なく

1, 2, 3, ... p - 1

と等しくなることを利用しました。これは、p が素数でなくても成り立つことは、証明の内容から容易に理解できます。さらに、a と b が互いに素なとき、a を b で割った剰余を r とすると、r と b も互いに素となります。もし、r と b に共通の因数があるとしたとき、その因数を k として r = kr', b = kb', a = qb + r とすれば、

a = qkb' + kr' より a = k( qb' + r' )

となるので、a が k を因数として持つことになり最初の仮定に反します。そこで、任意の(合成数も含めた)正数 m に対し、互いに素な数 a を選び、1 から m の中で m と互いに素な数だけを抽出し、先頭から順に連番 i を付けて b_i で表します。b_i は必ず 1 であり、その要素数はオイラーのΦ関数 φ(m) で表すことができます。このとき、

b₁a, b₂a, b₃a, ... b_φ(m)a

を m で割った φ(m) 個の剰余は重複がなく、しかも全て m と互いに素なので、適当に順番を入れ替えることで

b₁, b₂, b₃, ... b_φ(m)

と等しくなります。よって、

Π_i{1→φ(m)}( b_ia ) ≡ Π_i{1→φ(m)}( b_i ) ( mod m )

が成り立ち ( Π_i{1→φ(m)}(...) は ... の全要素の 1 から φ(m) までの積を表します )、左辺は a^φ(m)・Π_i{1→φ(m)}( b_i ) であり、Π_i{1→φ(m)}( b_i ) は m と互いに素なので

a^φ(m) ≡ 1 ( mod m )

となって、オイラーの定理が証明されました (証明終)

素数 p に対して φ(p) = p - 1 なので、オイラーの定理を素数に限定すればフェルマーの小定理と等しくなります。  

今日は「秋分の日」です。お彼岸ということで、おはぎやぼたもちを食べられた方も多いのではないでしょうか。

現在、対数線形モデルの勉強中です。それほど難しくないだろうと甘く考えていたら予想以上に奥が深く、さらに正規方程式から解を導き出してみようとチャレンジしたらかなりハマってしまいました。まあ、いつものことなんですけどね。頭を一度リセットするために、「数学問題bot」の中から一問選んでみました。例によって合っているかどうかは不明です。

-----

■ 0 でない複素数からなる集合 G は「G の任意の要素 z, w の積 zw は再び G の要素である」を満たしているとする。

1) ちょうど n 個の複素数からなる G の例を挙げよ。
2) ちょうど n 個の複素数からなる G は 1) の例以外にないことを示せ。

(01京都府立医科大)

1) cos( 2kπ / n ) + i sin( 2kπ / n ) ( 0 ≤ k ≤ n - 1 )

0 以上 n - 1 以下の整数 p, q を上式に代入して積を計算すると

[ cos( 2pπ / n ) + i sin( 2pπ / n ) ][ cos( 2qπ / n ) + i sin( 2qπ / n ) ]
= cos( 2pπ / n )cos( 2qπ / n ) - sin( 2pπ / n )sin( 2qπ / n ) + i [ sin( 2pπ / n )cos( 2qπ / n ) + cos( 2pπ / n )sin( 2qπ / n ) ]
= cos( 2( p + q )π / n ) + i sin( 2( p + q )π / n )

となり、p + q を n で割った剰余を r としたとき 0 ≤ r ≤ n - 1 なので

cos( 2( p + q )π / n ) + i sin( 2( p + q )π / n ) = cos( 2rπ / n ) + i sin( 2rπ / n )

で、これは G の要素です。

2) G の要素を z = a + bi, w = c + di としたとき、zw = ( ac - bd ) + ( da + bc )i が再び G の要素ならば

|z|² = a² + b²
|w|² = c² + d²
|zw|² = ( ac - bd )² + ( da + bc )²

は全て等しくなります。ところが、

( ac - bd )² + ( da + bc )²
= (ac)² + (bd)² + (da)² + (bc)²

( a² + b² )( c² + d² )
= (ac)² + (da)² + (bc)² + (bd)²

より |z|²|w|² = |zw|² なので、|z|², |w|², |zw|² が全て等しくなるためには

|z|² = |w|² = 1

である必要があります。すなわち、n 個すべての要素について実部と虚部の二乗和は 1 であり、複素平面内において原点を中心とした半径 1 の円周上に位置することになるので、G の要素は必ず

cosθ + i sinθ

の形で表されます。

z = cosα + i sinα
w = cosβ + i sinβ

に対して

zw = cos( α + β ) + i sin( α + β )

なので、任意の要素の偏角の和は 0 から 2π の範囲で他の要素の偏角と等しくならなければなりません。これを満たすためには、偏角が 2kπ / n ( 0 ≤ k ≤ n - 1 )、すなわち 0 を起点として 2π / n 刻みで要素を取ればよいので、1) の例のみが条件を満たすことになります。  

明後日は「秋分の日」ですが、明日も休みという方も多いのではないでしょうか。そうすると 4 連休ですね。

今回は「フェルマーの小定理」の証明方法を紹介したいと思います。もちろん自力で解いたわけではなく「はじめての数論 (ISBN 978-4-89471-421-2)」の内容そのままです。

前提知識としてまずは「合同式」を説明しておきます。

a - b が m で割り切れるとき、a は m を法として b に合同であるといい、

a ≡ b ( mod m )

で表します。これを「合同式」といいます。合同式では以下の式が成り立つので、フェルマーの小定理の証明でこれらを利用します。

a ≡ b ( mod m )
c ≡ d ( mod m )

ならば

a・c ≡ b・d ( mod m )

an ≡ bn ( mod m ) で n と m が互いに素なら a ≡ b ( mod m )

-----------------------------------------------------------------------------
フェルマーの小定理

p を素数、a を p と互いに素な整数とするとき、

a^p-1 ≡ 1 ( mod p )

が成り立つ。
-----------------------------------------------------------------------------

(証明)

p - 1 個の整数 a, 2a, 3a, ... ( p - 1 )a を p で割ったときの剰余を考えます。その中の任意の二つの整数 ja, ka ( 但し 0 < k ≤ j < p ) が

ja ≡ ka ( mod p )

だとすると、( j - k )a は p で割り切れることになります。しかし a は p と互いに素なので、j - k が p で割り切れることになり、0 ≤ j - k < p なので j - k = 0 すなわち j = k であることになります。よって、a, 2a, 3a, ... ( p - 1 )a を p で割った時の剰余は全て異なることになります。ところが、これらの整数は p - 1 個あり、p で割った剰余も 1 から p - 1 までの p - 1 個なので、全てが相異なるためには 1 から p - 1 までの数を必ず含む必要があります。つまり、a, 2a, 3a, ... ( p - 1 )a を p で割った剰余は適当に順番を入れ替えることで 1 から p - 1 までの数となります。よって、

a・2a・3a・...・( p - 1 )a ≡ 1・2・3・...・( p - 1 ) ( mod p )

が成り立ちます。左辺は a^p-1( p - 1 )! であり、右辺は ( p - 1 )! です。( p - 1 )! は p と互いに素なので、両辺を ( p - 1 )! で割れば

a^p-1 ≡ 1 ( mod p )

となって、フェルマーの小定理が証明されました。
  

今日、8 月 2 日は「パンツの日」だそうです。語呂合わせでそうなったらしいです。あと、6 月 2 日が「カレーの日」で 7 月 2 日が「うどんの日」だから 8 月 2 日は「カレーうどんの日」。さらにこれも語呂合わせで「ハーブの日」でもあるようです。いったい、そんな日を決めて何をすればいいのでしょうか。

「数学問題集」からこんな問題をチョイス。相変わらずの逃避行動。

-----

■ 3000 枚のカードに 1 から 3000 まで番号が書かれており、1 を一番上として番号順に積み重なっている。『一番上のカードを一番下に挿入し、次に一番上になったカードを捨てる』 という作業を繰り返したとき、最後に残るカードの数字は何か（コマ大数学科第 6 回ヨセフスの問題・改）

最初の操作は、1 を一番下 ( 3000 の下 ) に挿入して 2 を捨てることになります。次は 3 を下に挿入して 4 を捨てる... ということを繰り返した結果、偶数のカードは全て捨てられることになり、3000 番のカードを捨てれば 1 が再び一番上になります。この時点で、カードは奇数が 1 から順に並んだ状態となります。1 を一番下に挿入して一番上に現れるカードは 3 で、これが捨てられます。以下、5 を下に挿入して 7 を捨てる... ということを繰り返した結果、4n + 1 ( n ≥ 0 ) のカードだけが残った状態で再び 1 が一番上になります。以下、次のようにカードが残ることになります。

一巡目終了 : 2n + 1 が残り、1 が一番上になる。残りの枚数は 1500 枚。
二巡目終了 : 4n + 1 が残り、1 が一番上になる。残りの枚数は 750 枚。
三巡目終了 : 8n + 1 が残り、1 が一番上になる。残りの枚数は 375 枚。

四巡目からは残りの枚数が奇数になります。このとき、四巡目が終了した時点で捨てられるカードが逆転する現象が発生します。四巡目は 16n + 1 が残って 16n + 9 が捨てられる事になりますが、末尾のカードを一番下にしたときに現れるカードは 1 であり、次に捨てられるのはこのカードで、その後に現れるカードは 1 に 16 を加算した 17 です。従って、

四巡目終了 : 16n + 1 が残り、17 が一番上になる。残りの枚数は 187 枚。

となります。1 を捨てたので、端数は消えることに注意してください。つまり、奇数なら増分を加算すればいいので、これを繰り返せば

五巡目終了 : 32n + 1 が残り、17 + 32 = 49 が一番上になる。残りの枚数は 93 枚。
六巡目終了 : 64n + 1 が残り、49 + 64 = 113 が一番上になる。残りの枚数は 46 枚。
七巡目終了 : 128n + 1 が残り、113 が一番上になる。残りの枚数は 23 枚。
八巡目終了 : 256n + 1 が残り、113 + 256 = 369 が一番上になる。残りの枚数は 11 枚。
九巡目終了 : 512n + 1 が残り、369 + 512 = 881 が一番上になる。残りの枚数は 5 枚。
十巡目終了 : 1024n + 1 が残り、881 + 1024 = 1905 が一番上になる。残りの枚数は 2 枚。
十一巡目終了 : 2048n + 1 が残り、1905 が一番上になる。残りの枚数は 1 枚。

よって、最後に残るのは 1905 となります。アルゴリズムとしては、

1. 増分 add を 2、最後に残る番号 head を 1 で初期化する。
2. 枚数を 2 で割り、1 余ったら head に add を加算する。
3. add に 2 を掛ける。
4. 枚数が 1 になるまで 1 から 3 の操作を繰り返す。

ということになります。以下に、実際に配列を使って操作を繰り返す場合と、上記アルゴリズムを使った場合のサンプル・プログラムを示しておきます( C++ で STL を使ってます)。

unsigned int size = 3000; // カードの枚数

// 配列 (vector) を使って実際に操作する

std::vector<unsigned int> data( size );
for ( unsigned int i = 0 ; i < data.size() ; ++i )
data[i] = i + 1;

while ( data.size() > 1 ) {
unsigned int i = data[0];
data.erase( data.begin() );
data.push_back( i );
data.erase( data.begin() );
}
std::cout << data[0] << std::endl;

// 枚数を使ったアルゴリズム

unsigned int add = 2;
unsigned int head = 1;
while ( size > 1 ) {
if ( size & 1 ) head += add;
size /= 2;
add *= 2;
}
std::cout << head << std::endl;
  

猛暑が続いています。

昼の二時頃から外出していたわけですが、日の当たるところにいるとめまいがするくらい強烈に暑くて大変でした。川沿いの木陰のあるところを選んで歩くようにしていたおかげでなんとか目的地には到達。あと、太陽が雲に隠れたりして多少日差しが和らいだのも幸いしたようです。それにしても、木陰の涼しさというものを改めて実感しました。

「数学問題bot(個人用)」というのを見つけました。京大の問題があったのでチャレンジ。最近、ややこしい計算処理をしているので、また逃避に走っているようです。

-----

■ a,b,c,d,e,f をいずれも 0 から 9 までの数字とする。6 ケタの整数 abcdef を適当に定めて，その 2 倍が cdefab となるような a,b,c,d,e,f を求めよ。(1957年京大)

ab = x , cdef = y とします。このとき、x は二桁の整数、y は 10000 より小さい整数でなければなりません。

このとき、

abcdef = 10000x + y
cdefab = 100y + x

であり、abcdef x 2 = cdefab なので

2( 10000x + y ) = 100y + x より y / x = 19999 / 98 = 2857 / 14 となります。すなわち、x と y の比は 14 : 2857 であることになります。これを満たす ( x, y ) の組み合わせは

( 14, 2857 ), ( 28, 5714 ), ( 42, 8571 )

の三つのみです。従って、( a,b,c,d,e,f ) は

( 1,4,2,8,5,7 ), ( 2,8,5,7,1,4 ), ( 4,2,8,5,7,1 )

となります。

-----

やけにあっさりと解けてしまったのですが、もしかしたら見落としがあるかも。  

去年も同じタイトルで投稿してました。そのとき買おうと思ってたサーキュレータは結局まだ持ってません。除湿機も同じ。
朝の 9 時頃に仕事で屋外にいたんですけど、短時間だったのにもかかわらず、あまりの暑さに頭がクラクラしました。明日もこんな感じなんでしょうか。

「数学問題bot」から今回はこの問題を選んでみました。

-----

■ コンビネーション C[40,20] = 40_C_20 を 41 で割った余りを求めよ。 ( 00 数オリ予選 )

これを解くのに以下の道具を使います。

整数 a と b について、その差 ( a - b ) が整数 n で割り切れるとき、「a と b は n を法として合同である」といい、a ≡ b ( mod n ) と表す。これを「合同式」という。

例えば、5 ≡ 1 ( mod 4 ) であり、19 ≡ 7 ( mod 6 ) です。負数のときも成り立つと考えることができて、例えば 1 ≡ -3 ( mod 4 ) になります。

合同式では以下の式が成り立ちます。

a ≡ b ( mod n ) かつ c ≡ d ( mod n ) なら

a ± c ≡ b ± d ( mod n ) ... (1)

a・c ≡ b・d ( mod n ) ... (2)

また、k と n が互いに素なら、

k・a ≡ k・b ( mod n ) ならば a ≡ k ( mod n ) ... (3)

も成り立ちます。これらを証明するのはそれほど難しくないので、ぜひともチャレンジしみてください。

さて、問題に戻ると、コンビネーション C[40,20] (以下 C と略記します) は

C = 40・39・ ... ・22・21 / 20!

で求めることができます。分子の部分を A とすると、これは 20! で割り切ることができます (組み合わせが必ず整数になることの証明もおもしろいテーマになると思いますがここでは省略します)。A の個々の数値を見ると

40 ≡ -1 ( mod 41 )、39 ≡ -2 ( mod 41 )、 ... 21 ≡ -20 ( mod 41 )

なので、先ほどの公式 (2) から

A = 40・39・ ... ・22・21 ≡ (-1)・(-2)・ ... (-19)・(-20) = 20! ( mod 41 )

となります。A は C に 20! を掛けたものであり 20!・C と等しいので、

A = 20!・C ≡ 20! ( mod 41 )

です。41 は素数で 20! と共通な因数は存在せず、これらは互いに素なので

C ≡ 1 ( mod 41 )

となり、答えは 1 になります。

-----

合同式、知ってると便利です。自分は学生時代習ったことがなくて後で知りました。大学受験でも利用できる場面があると思います。  

学校はもう夏休みに突入したのでしょうか。

今日から三連休なのに、初日はゲリラ豪雨と雷でいい休日とはいえなかったように感じます。多少暑さが和らいだかもしれませんが、雨で窓を閉め切ったので結局エアコンは必須でした。明日の天気はどうなんでしょうかね。予報では降水確率は低いようですが。

「数学問題 bot」を解いてみました。東大の入試問題です。

-----

■ n を 2 以上の整数とする。自然数 ( 1 以上の整数 ) の n 乗になる数を n 乗数と呼ぶことにする。
1) 連続する 2 個の自然数の積は n 乗数でないことを示せ。
2) 連続する n 個の自然数の積は n 乗数でないことを示せ。
( 12 東大理系 )

1) 2 個の自然数を M, M + 1 とします。M を素因数分解した結果を p₁^r₁・p₂^r₂・...・p_s^r_s としたとき、M + 1 は p₁^r₁・p₂^r₂・...・p_s^r_s + 1 なので、p₁ から p_s までのどの素数で割っても必ず 1 余ります。従って、M と M + 1 の間には共通な素因数が存在しないことになり、二数の積 M( M + 1 ) が n 乗数となるためには M と M + 1 がどちらも n 乗数でなければなりません。しかし、連続する 2 個の自然数がどちらも n 乗数となることはありえないので、連続する 2 個の自然数の積は n 乗数にはならないことが証明されます。

2) 連続する n 個の自然数の最小の数を M とすると、その積は M( M + 1 )...( M + n - 1 ) で表されます。この数が n 乗数 Aⁿ ( A は自然数 ) で表されるとした時、

Mⁿ < M( M + 1 )...( M + n - 1 ) < ( M + n - 1 )ⁿ

より A の取りうる値は M + 1 から M + n - 2 の間でなければなりません。但し、n ≥ 3 とします。すなわち、n 個の自然数の中のいずれかが A であるということになります。Aⁿ は、A が持つ素因数以外の素数を持ちません。しかし、A に連続する自然数は、1) で示したように A 以外の素因数を持ちます。従って最初の仮定が成り立たず、n ≥ 3 のとき、連続する n 個の自然数は n 乗数にはなりえないことになります。最後に 1) から連続する 2 個の自然数の積は 2 乗数にはなりえず、連続する n 個の自然数は n 乗数ではないことが示されました。

-----

さて、そうなると「連続する任意の個数の自然数の積で、 任意の n について n 乗数となる場合があるか」という疑問が出てきます。これについてはどうなんでしょうかね ? かなり大きな数になればありえそうにも思えるんですが。
それから、例によって上の回答で正解なのかはわかりません。  

今週も半分終わりました。残り二日。しかし、すでにヘトヘトです。
しかし、ここを乗り切れば連休ですね。

久々に「数学問題集」から問題を解いてみました。今回はわりと簡単 ?

-----

■ x は 0 でない実数。a を a ≤ x < a + 1 なる整数とし x = a + b とする。ab = 127( a + b ) が成立するとき、x の値を求めよ ( 09 早稲田・商 )

a = 0 ならば 0・b = 127( 0 + b ) より b = 0 で x = 0 となるので、a ≠ 0 になります。また b = 0 の時も同様のやり方で x = 0 となるので b ≠ 0 になります。よって ab ≠ 0 なので、両辺に 127 / ab を掛けると

1 / a + 1 / b = 1 / 127

です。0 < b < 1 より 1 / b > 1 なので、上式が成り立つためには a < 0 である必要があります。a = -n ( n は 1 以上の整数 ) として、上式を以下のように変形します。

1 / b = 1 / 127 + 1 / n = ( n + 127 ) / 127n

よって

b = 127n / ( n + 127 )

b < 1 が成り立つときの n は 1 の場合 ( つまり a = -1 ) のみであり、このとき b = 127 / 128 になります。従って、

x = a + b = -1 + 127 / 128 = -1 / 128

となります。

-----

検算すると正しいので正解とは思いますが、例によって保証はないです。  

「白と黒のとびら」という本を読み終えました。

副題は「オートマトンと形式言語をめぐる冒険」。オートマトンを一言で表すのはなかなか難しいですが(自分も厳密に理解しているわけではないですが)、状態がある条件に従って遷移してゆくシステムと考えればいいでしょうか。非常に難解なテーマのように感じますが、本自体は最後の方を除いてそれほど悩まずに読むことができます。パズルを解くような感じで読めばいいかと。
普通のファンタジー小説として読んでも十分楽しめるので、興味のある方は一読をお勧めします。

「数学問題 bot」から一問。高校生数学コンテストということで難易度は低いです。間違っていたら恥ずかしいですが。

-----

■ 3 / p + 2 / q = 1 を満たす自然数の組 ( p, q ) を全て求めよ (08京都高校生数学コンテスト)

3 / p > 0 かつ 2 / q > 0 なので、p ≥ 4, q ≥ 3 である必要があります。そうしないと、3 / p と 2 / q のいずれかが 1 以上になり、左辺は 1 より大きくなってしまうからです。p = 4 のとき q = 8 という結果が得られますが、q を 8 より大きくすると 2 / q は小さくなってゆくので、左辺が 1 になるためには 3 / p を大きく、すなわち p を小さくする必要があります。しかし、p は自然数なので、4 より小さい数は 3 以下であり、このときは左辺を 1 にすることができないのは先に述べた通りです。従って、q は 8 以下でなければなりません。同様に考えると p ≤ 9 であることがわかります。p が 4 から 9 までの自然数であるときの q の値を求めると

p = 4 , q = 8
p = 5 , q = 5
p = 6 , q = 4
p = 7 は成り立たない
p = 8 は成り立たない
p = 9 , q = 3

となるので、答えは ( p, q ) = ( 4, 8 ), ( 5, 5 ), ( 6, 4 ), ( 9, 3 ) となります。  

夕方頃から涼しくなって、今は涼しい風が流れています。昼間の暑さがウソのようです。

6/14 (土) はいよいよ石川智晶さんのライブなんですよね。しかし、チケットは結局入手できず、今回は断念です。来年の一月に渋谷でのライブが決定したそうで、次は名古屋でのライブが再び実現するのを期待したいと思います。ちょうど今週の木曜日から金曜日にかけて出張で東京まで行く予定なんですよね。チケットさえ持っていれば、そのままライブの時間まで東京をぶらつくこともできたんですけど、残念です。

「数学問題 bot」に面白そうな問題があったのでチャレンジしました。今回は非常に長いです。

---

■ { 1, 2, ..., n } の空でない部分集合のうち、隣り合う二つの数を含まないようなものはいくつあるか。(Marbel_NIKO様)

求めたい数を S(n) として、まずは、n = 1 から順に数えてみます。

n = 1 : {1}
n = 2 : {1} {2}
n = 3 : {1} {2} {1,3} {3}
n = 4 : {1} {2} {1,3} {3} {1,4} {2,4} {4}
n = 5 : {1} {2} {1,3} {3} {1,4} {2,4} {4} {1,5} {2,5} {1,3,5} {3,5} {5}
  :

よって、n = 5 までは S(1) = 1, S(2) = 2, S(3) = 4, S(4) = 7, S(5) = 12 となります。この結果からパターンを調べていきます。

n - 1 までに見つかった部分集合はそのまま n の部分集合になります。それらは n を要素に持たないので、残りは必ず n を要素に持つ部分集合になり、n - 1 までの部分集合に n を加えたものでなければなりません。なぜなら、それ以外の組み合わせは必ず隣り合う二つの数を含んでいるからです。さらに、部分集合の要素に n - 1 が含まれていると、n - 1 と n どうしが隣り合うのでこれらは除外する必要があります。例えば n = 5 のとき、その条件を満たす n = 4 までの部分集合は {1} {2} {1,3} {3} の 4 つなので、これらに 5 を加えた {1,5} {2,5} {1,3,5} {3,5} が求める部分集合になります。これは n = 3 での部分集合そのものに 5 を加えたものに相当します。最後に、n のみを要素とする部分集合 {n} を加える必要があります。
以上から、S(n) は n - 1 までの部分集合の数 S(n-1) に、その一つ前の n - 2 での部分集合の数 S(n-2) を加え、さらに 1 を加えた式

S(1) = 1
S(2) = 2
S(n) = S(n-1) + S(n-2) + 1 ( n > 2 )

で表されます。この漸化式に対して一般項を解けば、求めたい答えが得られます。

この漸化式は、フィボナッチ数列 F(1) = F(2) = 1, F(n) = F(n-1) + F(n-2) によく似ています。従って、フィボナッチ数列の一般項を求める方法を利用することができます。まず、数列 S(n) を xⁿ の係数とする多項式 (これを母関数といいます) を F(x) とすると、

F(x) = S(1)x + S(2)x² + S(3)x³ + S(4)x⁴ + ... + S(n)xⁿ + ...

となります。これに S(n) = S(n-1) + S(n-2) + 1 を代入すると、

F(x)
= S(1)x + S(2)x² + [ S(2) + S(1) + 1 ]x³ + [ S(3) + S(2) + 1 ]x⁴ + ... + [ S(n-1) + S(n-2) + 1 ]xⁿ + ...
= S(1)x + S(2)x²
 + [ S(2)x³ + S(3)x⁴ + ... + S(n-1)xⁿ + ... ]
 + [ S(1)x³ + S(2)x⁴ + ... + S(n-2)xⁿ + ... ]
 + [ x³ + x⁴ + ... + xⁿ + ... ]
= S(1)x + S(2)x²
 + x[ S(1)x + S(2)x² + S(3)x³ + ... + S(n-1)x^n-1 + ... ] - S(1)x²
 + x²[ S(1)x + S(2)x² + ... + S(n-2)x^n-2 + ... ]
 + x[ 1 + x + x² + x³ + ... + x^n-1 + ... ] - x - x²
= x + 2x² + xF(x) - x² + x²F(x) + xG(x) - x - x²
= xF(x) + x²F(x) + xG(x)

より

F(x) = xG(x) / ( 1 - x - x² )

となります。但し、G(x) は初項 1、公比 x の等比級数です。G(x) は

G(x) = 1 + x + x² + ...
xG(x) = x + x² + x³ + ...

の両式を辺々引いて

( 1 - x )G(x) = 1 より G(x) = 1 / ( 1 - x )

と求めることができるので、これを代入すれば

F(x) = x / ( 1 - x )( 1 - x - x² )

という結果が得られます。

次に得られた式を部分分数分解します。その前に、1 - x - x² を因数分解するため

1 - x - x² = ( 1 - ax )( 1 - bx )

とすると、(右辺) = 1 - ( a + b )x + abx² より a + b = 1, ab = -1 となります。b = 1 - a を ab = -1 に代入して

a( 1 - a ) = -1 より a² - a - 1 = 0

の解を求めると、二次方程式の解の公式から

a = ( 1 ± √5 ) / 2

となるので、a = ( 1 + √5 ) / 2, b = ( 1 - √5 ) / 2 とすれば

F(x) = x / ( 1 - x )( 1 - ax )( 1 - bx )

と表すことができます。これを

F(x) = A / ( 1 - ax ) + B / ( 1 - bx ) + C / ( 1 - x )

の形にすればいいので、この式をまた一つの分数に戻すと分子部分は

( 1 - bx )( 1 - x )A + ( 1 - ax )( 1 - x )B + ( 1 - ax )( 1 - bx )C
= [ 1 - ( b + 1 )x + bx² ]A + [ 1 - ( a + 1 )x + ax² ]B + [ 1 - ( a + b )x + abx² ]C
= ( A + B + C ) - [ ( b + 1 )A + ( a + 1 )B + C ]x + ( bA + aB - C )x²

となって、これが x と恒等的に等しいならば

A + B + C = 0 --- (1)
( b + 1 )A + ( a + 1 )B + C = -1 --- (2)
bA + aB - C = 0 --- (3)

が成り立ちます。(1) + (3) より

( b + 1 )A + ( a + 1 )B = 0

なので、これを (2) に代入すれば C = -1 が得られ、これを (1) (3) に代入して

A + B = 1 --- (1')
bA + aB = -1 --- (2')

(1') x a - (2') より

( a - b )A = a + 1

よって A = ( a + 1 ) / ( a - b ) で、同様にして B = ( b + 1 ) / ( b - a ) です。a, b の値を代入して

A = ( 5 + 3√5 ) / 10, B = ( 5 - 3√5 ) / 10

となり、これで F(x) を部分関数分解することができました。個々の分数を見ると、これらは G(ax), G(bx), G(x) と等しく、

1 / ( 1 - ax ) = 1 + (ax) + (ax)² + ...
1 / ( 1 - bx ) = 1 + (bx) + (bx)² + ...
1 / ( 1 - x ) = 1 + x + x² + ...

なので、

F(x)
= A[ 1 + (ax) + (ax)² + ... ] + B[ 1 + (bx) + (bx)² + ... ] - [ 1 + x + x² + ... ]
= ( A + B + C ) + ( Aa + Bb - 1 )x + ( Aa² + Bb² - 1 )x² + ...

と表せて、xⁿ の係数は

Aaⁿ + Bbⁿ - 1

となります。ところがこれは S(n) でもあることから

S(n) = Aaⁿ + Bbⁿ - 1
= [ ( 5 + 3√5 ) / 10 ][ ( 1 + √5 ) / 2 ]ⁿ + [ ( 5 - 3√5 ) / 10 ][ ( 1 - √5 ) / 2 ]ⁿ - 1

になります。これで S(n) の一般項が得られました。

ちなみにフィボナッチ数列の一般項は

F(n) = ( 1 / √5 )[ ( 1 + √5 ) / 2 ]ⁿ - ( 1 / √5 )[ ( 1 - √5 ) / 2 ]ⁿ

でこれは「ビネの公式」と呼ばれています。ビネはこの公式を 1843 年に発表しましたが、それより 100 年以上も前の 1730 年にド・モアブルによってすでに発見されていたそうです。S(n) も F(n) も [ ( 1 ± √5 ) / 2 ]ⁿ を項に持っていますが、( 1 + √5 ) / 2 > 1 に対して | 1 - √5 | / 2 < 1 なので [ ( 1 - √5 ) / 2 ]ⁿ 項は n が大きくなると無視できるほど小さくなります。よって、n が十分大きければ、S(n) も F(n) も n が 1 増加するたびにほぼ ( 1 + √5 ) / 2 倍ずつ大きくなるようになります。

■ 参考文献

「はじめての数論」 Joseph H. Silverman 著
ISBN 978-4-62106-620-1