Fussy's Diary

3 月も今日で終わりです。桜は明日あたりが満開になるかな。しかし、雨の予報が。。。

3 月に間に合わせる形で「アルゴリズムのコーナー」を更新しました。過去に公開した「ウェーブレット変換」の内容を見直しています。過去に作ったドキュメントをみると変な箇所や説明不足の部分もいろいろとあったのでかなり手直ししています。メインは多重解像度解析なのに、連続ウェーブレット変換の方が見直しに時間がかかりました。

そして、過去に拾ったまま放置していた問題を気合入れて解きました。ようやく暗算で計算できる方法を思いついたので紹介しておきます。

-----

1) 2011²³ の下 4 桁を求めよ。
2) 2011^23! の下 4 桁を求めよ ( cruz__F 様 )

以下、合同式を多用するので、先に定義といくつかの定理だけ示しておきます。

整数 m, k, q, r に対して m = qk + r となるとき、「m は k を法として r と合同である」といい、m ≡ r ( mod k ) と表します。これを「合同式」または「モジュラー演算」といいます。「時計算」と呼ばれることもあります。合同式では、m ≡ r ( mod k ) かつ n ≡ s ( mod k ) であるとき、

m ± n ≡ r ± s ( mod k )
m・n ≡ r・s ( mod k )
mⁿ ≡ rⁿ ( mod k )

が成り立ちます。

1) 二項定理より

2011²³
= ( 2000 + 11 )²³
= 2000²³ + ₂₃C₁・2000²²・11 + ... + ₂₃C₂₂・2000・11²² + 11²³
≡ 23・2000・11²² + 11²³ ( mod 10000 )

となります。なぜなら、任意のゼロでない自然数 N と 1 より大きい自然数 a に対し、2000^a・N ≡ 0 ( mod 10000 ) となるため、そのような項は無視できるからです。

23・2000・11²² + 11²³ = 11²²( 23・2000 + 11 )

より、11²² と 23・2000 + 11 が 10000 を法いくつになるかがわかれば、求めたい数を見つけることができます。もう一度、二項定理を使って

11²²
= ( 10 + 1 )²²
= 10²² + ₂₂C₁・10²¹ + ... + ₂₂C₁₉・10³ + ₂₂C₂₀・10² + ₂₂C₂₁・10 + 1
≡ ₂₂C₃・1000 + ₂₂C₂・100 + ₂₂C₁・10 + 1 ( mod 10000 )
= ( 22・21・20 / 3・2 )・1000 + ( 22・21 / 2 )・100 + 220 + 1
= 1540000 + 23100 + 2201 + 1
≡ 3321 ( mod 10000 )

となり、

23・2000 + 11 = 46011 ≡ 6011 ( mod 10000 )

なので、

3321・6011 = 19962531 ≡ 2531 ( mod 10000 )

となって、求める数は 2531 となります。

2) オイラーの定理より、自然数 n と互いに素な数の個数を φ( n ) としたとき、整数 a と n が互いに素であれば、

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

が成り立ちます。n が素数の場合、φ(n) = n - 1 なので、これはフェルマーの小定理の一般化になります。φ(n) には以下の定理が成り立ちます。

素数 p に対し、

φ(p) = p - 1
φ(p^m) = p^m - p^m-1

m, n が互いに素であれば

φ(mn) = φ(m)・φ(n)

以下の説明ではこれらを利用します。

10000 = 2⁴・5⁴ より

φ(10000)
= φ(2⁴・5⁴)
= φ(2⁴)・φ(5⁴)
= ( 2⁴ - 2³ )( 5⁴ - 5³ )
= ( 16 - 8 )( 625 - 125 ) = 8・500 = 4000 = 20・10・5・4

2011 と 10000 は互いに素なので、オイラーの定理から

2011^{20・10・5・2} ≡ 1 ( mod 10000 )

となります。23! は 23 以下の全ての自然数の積なので、この結果から 2011^23! ≡ 1 ( mod 10000 ) となります。

-----

オイラーの定理は、フェルマーの小定理の場合とほぼ同じ方法で証明ができます。

まず、自然数 n と互いに素な自然数を b_j ( j = 1, 2, ... φ(n) ) とします。b_j の全てに、n と互いに素なある自然数 a を掛けた数 ab_j は、a, b_j のどちらも n と互いに素であることから ab_j も n と互いに素であり、ある k ( k = 1, 2, ... φ(n) ) に対して

ab_j ≡ b_k ( mod n )

が成り立ちます。なぜなら、n と互いに素で n 以下の数は φ(n) の b_k の中にしか存在しないからです。二数 b_j と b_k について

ab_j ≡ ab_k ( mod n )

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

a( b_j - b_k ) ≡ 0 ( mod n )

より a( b_j - b_k ) は n で割り切れます。しかし、a は n と互いに素なので、b_j - b_k が n で割り切れなければなりません。また、1 ≤ b_j < n より | b_j - b_k | < n なので、条件を満たす数はゼロのみとなります。つまり、a を掛けたときに合同になる数が等しくなる b_j は存在せず重複しないことから

ab_j ≡ b_k ( mod n )

を満たす 1 から φ(n) までの全ての b_k が存在することになります。すなわち

Π_j{1→φ(n)}( ab_j ) ≡ Π_k{1→φ(n)}( b_k ) ( mod n )

であり、左辺は

Π_j{1→φ(n)}( ab_j ) = a^φ(n)Π_j{1→φ(n)}( b_j )

なので、両辺を Π_j{1→φ(n)}( b_j ) で割れば

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

となります。

-----

最後のところでさりげなく両辺を Π_j{1→φ(n)}( b_j ) で割りましたが、mc ≡ nc ( mod k ) のときに

m ≡ n ( mod k )

は必ずしも成り立つとは限りません。例えば、

30 ≡ 6 ( mod 8 )

は成り立ちますが、両辺を 2 で割った

15 ≡ 3 ( mod 8 )

は成り立ちません。しかし、c が k と互いに素であれば成り立ちます。b_j は全て n と互いに素なので問題はないというわけです。
  

昨日は 5 時に起床しました。

空はまだ真っ暗でしたが、月がキレイだったので撮影してみました。撮影すると何となくショボくなりますね。



そして今日は日曜日ですが、5 時半に目が覚めてしまいました。空はだいぶ明るくなっていましたが、まだ月は見えていたのでまたカメラで撮影。



こうやって見ると、月の満ち欠けって結構早いんですね。それにしても、明け方はまだ寒いです。

「数学問題bot(個人用)」から今回は東大の入試問題にチャレンジ。なぜか最初の問題で大苦戦して何日間か悩んでいました。なお、合っている保証なしです。

-----

p, q は実数の定数で、0 < p < 1, q > 0 を満たすとする。関数

f(x) = ( 1 - p )x + ( 1 - x )( 1 - e^-qx )

を考える。

以下の問いに答えよ。必要であれば、不等式 1 + x ≤ e^x が全ての実数 x に対して成り立つことを証明なしに用いてよい。

(1) 0 < x < 1 のとき、0 < f(x) < 1 であることを示せ。

(2) x₀ は 0 < x₀ < 1 を満たす実数とする。数列 {x_n} の各項 x_n ( n = 1, 2, ... ) を、

x_n = f(x_n-1)

によって順次定める。p > q であるとき、

lim{n→∞} x_n = 0

となることを示せ。

(3) p < q であるとき、

c = f(c), 0 < c < 1

を満たす実数 c が存在することを示せ。

(東京大・2014・前・理)

-----

(1) f(x) の変数を q として f(q) の軌跡を考えます。

f(0) = ( 1 - p )x で 0 < 1 - p < 1 かつ 0 < x < 1 なので 0 < f(0) < 1 となります。
また、q → ∞ のとき f(q) → ( 1 - p )x + ( 1 - x ) = 1 - px なのでやはり 0 < lim{q→∞} f(q) < 1 となります。

f'(q) = q( 1 - x )e^-qx で q > 0 より任意の q に対して f'(q) > 0 となり、f(q) は単調増加となります。従って、命題が成り立ちます。

(2) (1) より、0 < x₀ < 1 ならば任意の n に対して 0 < x_n < 1 が成り立ちます。
1 - qx ≤ e^-qx より 1 - e^-qx ≤ qx なので、x_n = f(x_n-1) ≤ ( 1 - p )x_n-1 + qx_n-1( 1 - x_n-1 ) が成り立ち、

x_n-1 - x_n ≥ x_n-1 - [ ( 1 - p )x_n-1 + qx_n-1( 1 - x_n-1 ) ]
= x_n-1( p - q + qx_n-1 )

より p > q ならば x_n-1 - x_n > 0 となるので { x_n } は単調減少となります。f(0) = 0 であることから { x_n } は必ず 0 に収束し、lim{n→∞} x_n = 0 が成り立ちます。

(3) g(x) = f(x) - x とします。このとき、

g(x) = -px + ( 1 - x )( 1 - e^-qx )

なので、g(0) = 0、g(1) = -p < 0 となります。従って、g'(0) > 0 になるなら、0 < c < 1 かつ g(0) = 0 を満たす実数 c が存在します。

g'(x) = -p - ( 1 - e^-qx ) + qe^-qx( 1 - x ) より g'(0) = -p + q なので、p ≤ q ならば g'(0) > 0 です。従って、g(0) = c を満たす実数 c が存在し、f(c) = g(c) + c = c より命題が成り立ちます。  

美味しいはちみつを求めて、通販限定のお試しセットを買ってみました。
いくつかある中で、フランス産のラベンダーはちみつがなかなかにおいしかったので追加で購入しました。パンやヨーグルトにかけて使ってます。それにしても、花の種類によって味や食感も様々ですね。モカコーヒーのはちみつはにおいにかなり癖があってちょっと無理でした。あと試していないのはそばのはちみつですが、これもいつか食べてみたいです。はちみつを使った簡単なレシピがあればそれも試してみたいですね。

「数学問題bot(個人用)」から昔に拾った問題を解いてみました。合っている保証なしです。

-----

4 つの正数 a, b, c, d について a = b = c = d でないならば、4 つの数 a( 1 - b ), b( 1 - c ), c( 1 - d ), d( 1 - a ) のうち少なくとも 1 つは 1 / 4 より小さいことを証明せよ ( 1978 年東京理科大 )

まず、4 つの数が 1 / 4 以上だと仮定します。このとき、a( 1 - b ) ≥ 1 / 4 > 0 で a > 0 なので、1 - b > 0 となり、0 < b < 1 が成り立ちます。
同様に他の数 a, c, d についてもこれは成り立ちます。
4 つの数の和を計算すると、

a( 1 - b ) + b( 1 - c ) + c( 1 - d ) + d( 1 - a )
= ( a + b + c + d ) - ( ab + bc + cd + da )
= ( a + c ) + ( b + d ) - ( a + c )( b + d )
= ( a + c - 1 )( 1 - b - d ) + 1

で、これは仮定より 1 以上となるので、

( a + c - 1 )( b + d - 1 ) ≤ 0

が成り立ちます。これが成り立つためには、

i) a + c ≤ 1 かつ b + d ≥ 1
ii) a + c ≥ 1 かつ b + d ≤ 1

のいずれかを条件として満たす必要があります。i) のときは、a ≤ 1 - c かつ 1 - b ≤ d なので、設問の前提条件も併せれば

1 / 4 ≤ a( 1 - b ) ≤ d( 1 - c )

となります。また、c ≤ 1 - a かつ 1 - d ≤ b とも変形できるため、

1 / 4 ≤ c( 1 - d ) ≤ b( 1 - a )

ともなります。1 / 4 ≤ b( 1 - a ) より b ≥ 1 / 4( 1 - a ) を 1 / 4 ≤ a( 1 - b ) に適用して

1 / 4 ≤ a( 1 - b ) ≤ a[ 1 - 1 / 4( 1 - a ) ]

1 - a > より両辺に 4( 1 - a ) を掛ければ

1 - a ≤ a[ 4( 1 - a ) - 1 ] = -4a² + 3a

式を整理して 4a² - 4a + 1 ≤ 0 より ( 2a - 1 )² ≤ 0 なので、これを満たす実数は 1 / 2 しかありません。
このとき、1 / 4 ≤ ( 1- b ) / 2 かつ 1 / 4 ≤ b / 2 が成り立つ必要があるので b = 1 / 2 になります。さらに、ii) の条件から同様の手順で c = d = 1 / 2 となり、a = b = c = d = 1 / 2 となります。

従って、その対偶である設問の命題が証明されました。  

連休中はずっと外出していたわけですが、桜はまだのようです。

しかし、ソメイヨシノ以外の桜で咲いていたのを近所の公園で見つけたのでカメラで撮っておきました。



もう、葉が見えてしまっているということは、花も落ち始めているのかな。

最後の名古屋大入試問題。最後におまけも付けてあります。例によって合っている保証はありません。

-----

正の n に対して、その ( 1 と自分自身も含めた ) すべての正の約数の和を s(n) と書くことにする。このとき、次の問に答えよ。

(1) k を正の整数、p を 3 以上の素数とするとき、s(2^kp) を求めよ。
(2) s(2016) を求めよ。
(3) 2016 の正の約数 n で、s(n) = 2016 となるものをすべて求めよ。

(1) 2^kp の約数は、

1, 2, 2², ... 2^k
p, 2p, 2²p, ... 2^kp

なので、

s(2^kp)
= Σ_j{0→k}( 2^j ) + Σ_j{0→k}( 2^jp )
= Σ_j{0→k}( 2^j( p + 1 ) )
= ( 2^k+1 - 1 )( p + 1 )

となります。

(2) 2016 = 2⁵・3²・7 より、約数は

1	2	22	23	24	25
3	2・3	22・3	23・3	24・3	25・3
32	2・32	22・32	23・32	24・32	25・32
7	2・7	22・7	23・7	24・7	25・7
3・7	2・3・7	22・3・7	23・3・7	24・3・7	25・3・7
32・7	2・32・7	22・32・7	23・32・7	24・32・7	25・32・7

です。これをマジメに足しあわせて

s(2016)
= Σ_j{0→5}( 2^j( 1 + 3 + 3² + 7 + 3・7 + 3²・7 ) )
= ( 2⁶ - 1 )・104
= 63・104 = 6552

となります。

(3) m の約数の和を s(m) としたとき、s(m) に対して、s( 2^km ) は (1)(2) の結果から ( 2^k+1 - 1 )s(m) となることがわかります。2016 = 2⁵・3²・7 より、s(n) = 2016 となる n を求めるには ( 2⁶ - 1 )s(m) = 2016 を満たす m を見つければよいことになります。s(m) = 2016 / 63 = 32 なので、約数の和が 32 以下の数を n の中から調べると

s(1) = 1 s(3) = 4 s(3²) = 13 s(7) = 8 s(3・7) = 32

となって、3・7 が一つ見つかりました。残りの約数は全て上記 5 つの数に 2^k ( 1 ≤ k ≤ 5 ) を掛けあわせることで得られますが、その約数の和は上記で求めた約数の和に 2^k+1 - 1 を掛けた数に等しくなり、この数が奇数であることから 32 になるためには s(m) が偶数でなければなりません。それは s(3) と s(7) で、

s(2・3) = 12 s(2・3) = 28 でこれより大きな数は 32 より大きくなるため該当するものはなく、
s(2・7) = 24 でこれより大きな数は 32 より大きくなるためこちらも該当するものはありません。

従って、求める数は 2⁵・3・7 = 672 となります。

-----

約数の和 s(n) にはおもしろい性質があります。素数 p の約数は 1 と p だけなので、s(p) = p + 1 です。また、p のべき乗 p^m の約数は 1, p, p², ... p^m であり、

s(p^m) = Σ_j{0→m}( p^j ) = ( p^m+1 - ) / ( p - 1 )

となります。二つの素数の積 pq の約数は 1, p, q, pq であり、

s(pq) = 1 + p + q + pq = ( p + 1 )( q + 1 ) = s(p)s(q)

となり、さらに p^mqⁿ の約数は 0 ≤ j ≤ m, 0 ≤ k ≤ n を満たす任意の整数について p^jq^k で表わされるので、

s(p^mqⁿ)
= Σ_j{0→m}( Σ_k{0→n}( p^jq^k ) )
= Σ_j{0→m}( p^jΣ_k{0→n}( q^k ) )
= Σ_j{0→m}( p^js(qⁿ) )
= s(p^m)s(qⁿ)

となります。この結果は一般化して

s( Π_k( p_k^m_k ) ) = Π_k( s( p_k^m_k ) )

となるので、もし m と n が共通の素因数を持たない、つまり互いに素であれば

s(mn) = s(m)・s(n)

が成り立ちます。  

Tweet

今日は風の強い日ですね。

今更ながら God of War 2 のタイタンモードに挑戦しています。かなり昔にテセウス戦までは何とかクリアして、バーバリアン・キング前でやめてしまっていました。ちょっとやってみようかと思い、苦戦の末、バーバリアン・キングとエウリュアレまで何とか倒して、ロック・ミノタウロス + ハーピー極悪コンビに倒されまくってます。時間のあるときに少しずつ進めようと考えてます。このゲーム、イージーやノーマルなら戦闘は苦戦することなく、逆に謎解きが大変でした。ハード以降はガラリと変わり、戦闘が非常にきついです。特にタイタンモードはハードすら楽に思えるくらいきつく、何度死んだかわかりません。でも、攻略法などを参考にすればアクションが下手でも何とか進められます。後半はどうなるかわかりませんが。昔のゲームですが、今でもベストゲームの一つです。

今年の名古屋大入試から、今回は文系の問題です。なぜか個人的には文系の問題の方に苦戦しました。例によって合っている保証なしです。

-----

n を正の整数とし、k を 1 ≤ k ≤ n + 2 を満たす整数とする。n + 2 枚のカードがあり、そのうちの 1 枚には数字 0 が、他の 1 枚には数字 2 が、残りの n 枚には数字 1 が書かれている。この n + 2 枚のカードのうちから無作為に k 枚のカードを取り出すとする。このとき、次の問に答えよ。
(1) 取り出した k 枚のカードに書かれているすべての数字の積が 1 以上になる確率を求めよ。
(2) 取り出した k 枚のカードに書かれているすべての数字の積が 2 となる確率 Q_n(k) を求めよ。
(3) 与えられた n に対して、確率 Q_n(k) が最大となる k の値と、その最大値を求めよ。

(1) 積が 0 になるのは、0 のカードが k 枚の中に含まれた時で、その確率は

1 / ( n + 2 ) + [ ( n + 1 )( n + 2 ) ]・[ 1 / ( n + 1 ) ] + ... + [ ( n + 1 ) / ( n + 2 ) ]・[ n / ( n + 1 ) ]・ ... ・[ 1 / ( n - k + 3 ) ] = k / ( n + 2 )

となるので、その余事象である 1 以上となる確率は

1 - k ( n + 2 ) = ( n - k + 2 ) / ( n + 2 )

となります。

(2) 1 のカードだけが含まれる確率は、n + 2 枚のカードから k 枚を選択する場合の数 _n+2C_k で、0, 1 を除いた n 枚のカードから k 枚を選択する場合の数 _nC_k で割った値で、

_nC_k / _n+2C_k
= [ n! / k!・( n - k )! ] / [ ( n + 2 )! / k!・( n + 2 - k )! ]
= ( n - k + 2 )( n - k + 1 ) / ( n + 1 )( n + 2 )

となります。数字の積が 2 となるのは、1 以上になる事象から 1 になる事象、すなわち 1 のカードのみを含んだ事象を除けばよいので、

Q_n(k) = ( n - k + 2 ) / ( n + 2 ) - ( n - k + 2 )( n - k + 1 ) / ( n + 1 )( n + 2 ) = k( n - k +2 ) / ( n + 1 )( n + 2 )

となります。

(3) n は定数なので、f(k) = k( n - k +2 ) の最大値を求めれば十分です。

f(k) = -[ k - ( n + 2 ) / 2 ]² + ( n + 2 )² / 4 より、f(k) は k = ( n + 2 ) / 2 のとき最大となります。

n が偶数なら k = ( n + 2 ) / 2 のとき最大で、Q_n(k) = [ ( n + 2 )² / 4 ] / ( n + 1 )( n + 2 ) = ( n + 2 ) / 4( n + 1 )

n が奇数なら k = ( n + 1 ) / 2, ( n + 3 ) / 2 のとき最大で、

Q_n(k) = [ ( n + 1 )( n + 3 ) / 4 ] / ( n + 1 )( n + 2 ) = ( n + 3 ) / 4( n + 2 )

となります。  

昼からは暖かい一日でした。夜も寒くないというのは久しぶりのような気がします。

丸善出版の「パターン認識と機械学習」という書籍があります。以前、上巻だけを購入して読み進めていました。上巻は 6,500 円と高価でしたが、下巻はさらに高く 7,800 円もします。買うのはずっとためらっていたものの、上巻もだいぶ読み進めたので、本屋に立ち寄ったときに衝動買いしてしまいました。まだ上巻の残りを読んでいるところなので、もう少ししてから読もうと考えています。パターン認識関連の書籍はいろいろと買いましたが、高価なだけにこの本が一番まとまっている上に説明もある程度は細かく書かれていると思います。しかし、全部理解するにはあと 2, 3 冊、統計関係の書籍は必要になります。読むだけでもかなり苦労しました。

いい本だと思うので、図書館などにあれば借りて読むというのもオススメです。

2016 年名古屋大入試の理系最後の問題です。まだ、文系問題がふたつ残ってます。例によって合っている保証はありません。

-----

次の問に答えよ。ただし 2 次方程式の重解は 2 つと数える。

(1) 次の条件 (*) を満たす整数 a, b, c, d, e, f の組をすべて求めよ。

(*)
・2 次方程式 x² + ax + b = 0 の 2 つの解が c, d である。
・2 次方程式 x² + cx + d = 0 の 2 つの解が e, f である。
・2 次方程式 x² + ex + f = 0 の 2 つの解が a, b である。

(2) 2 つの数列 { a_n }, { b_n } は、次の条件 (**) を満たすものとする。

(**) すべての正の整数 n について、a_n, b_n は整数であり、2 次方程式 x² + a_nx + b_n = 0 の 2 つの解が a_n+1, b_n+1 である。

このとき、

(i) 正の整数 m で、| b_m | = | b_m+1 | = | b_m+2 | = ... となるものが存在することを示せ。
(ii) 条件 (**) を満たす数列 { a_n }, { b_n } の組をすべて求めよ。

(1) 二次方程式の解と係数の関係から

a = -c - d --- (a)
b = cd --- (b)
c = -e - f --- (c)
d = ef --- (d)
e = -a - b --- (e)
f = ab --- (f)

が成り立ちます。(b) を (f) に代入して f = acd、さらに (d) を代入すれば f = acef になります。
f ≠ 0 のとき、ace = 1 であり、これを満たす整数は a, c, e が全て 1 か、ひとつが 1 で残りが -1 の場合のみです。また、f ≠ 0 なので (b)(d) から b ≠ 0, d ≠ 0 となります。
(a) + (c) + (e) より

a + c + e = -( a + b + c + d + e + f )
2( a + c + e ) = -( b + d + f )

となるので、a = c = e = 1 なら b + d + f = -6 であり、(b)(d)(f) から b = d = f になります。
従って、この場合は { a, b, c, d, e, f } = { 1, -2, 1, -2, 1, -2 } です。
a = c = -1, e = 1 の場合、(a)(c)(e) より b = 0, d = 2, f = 0 となり、f ≠ 0 に反します。対称性から c = e = -1 かつ a = 1 の場合と e = a = -1 かつ c = 1 の場合も b, d, f のいずれかにゼロを含むため仮定に反します。

f = 0 のとき、(d) より d = 0, (b) より b = 0 となり、(a)(c)(e) より a = -c, c = -e, e = -a なので

a = -c = e = -a

となります。これを満たすのは a = 0 のときしかありません。対称性から同様に c = 0, e = 0 となるので、{ a, b, c, d, e, f } = { 0, 0, 0, 0, 0, 0 } となります。組はこの二つとなります。

(2)(i) 二次方程式の解と係数の関係から

a_m = -a_m+1 - b_m+1 --- (a)
b_m = a_m+1b_m+1 --- (b)

が成り立つので、(b) より

b_m = a_m+1b_m+1 = a_m+1a_m+2b_m+2 = ...

となります。任意の k > m に対して a_k ≠ 0 ならば

b_m / b_m+1 = a_m+1
b_m / b_m+2 = a_m+1a_m+2
:

となるので、b_m に対して b_m+1 以降は全て約数とならなければなりません。また、

|a_m+1| ≤ |a_m+1a_m+2| ≤ ...

より

|b_m / b_m+1| ≤ |b_m / b_m+2| ≤ ...

なので

|b_m+1| ≥ |b_m+2| ≥ ...

となって、正の整数は有限なので必ずある値に収束します。最後に、a_m+1 = 0 となったとき、(b) より b_m = 0 で、(b) の添字を一つ前にずらすと

b_m-1 = a_mb_m

なので b_m-1 = 0 です。つまり、0 = b₁ = b₂= ... でありこの場合も成り立ちます。よて、命題が成り立つことが証明されました。

(2)(ii) (i) で証明した状態になったとき、(b) より b_m ≠ 0 なら a_m はすべて ±1 となります。(a) にこの値を代入することで ( a_m, b_m ) は ( b_m ≠ 0 であることに注意して )

( a_m, b_m ) = ( 1, -2 ), ( -1, 2 )

の二通りが得られます。( a_m, b_m ) は解を ( a_m+1, b_m+1 ) とする二次方程式の係数だったので、( 1, -2 ) のときは

x² + x - 2 = 0

の解が ( a_m+1, b_m+1 ) になります。その解は x = 1, -2 で、| a_m | = 1 という条件を満たすのは ( a_m+1, b_m+1 ) = ( 1, -2 ) です。逆に、( a_m+1, b_m+1 ) = ( 1, -2 ) なら (a)(b) より

a_m = -1 - ( -2 ) = 1
b_m = 1・( -2 ) = -2

なので、全ての m に対して ( a_m, b_m ) = ( 1, -2 ) ということになります。

( -1, 2 ) のときは

x² - x + 2 = 0

の解が ( a_m+1, b_m+1 ) になりますが、この方程式は整数解はおろか実数解もないので除外できます。

最後に、m がある値以上になったときに b_m = 0 なら(a) より a_m = -a_m+1 なので、以降の a_m は絶対値の等しい値が符号だけ変化しながら続くことになります。その値を N としたとき、( a_m+1, b_m+1 ) = ( N, 0 ) なら (a)(b) より

a_m = -N - 0 = -N
b_m = N・0 = 0

であり、その前についても符号だけ変わって絶対値は変わりません。よって、任意の整数 N について { a_m } = { N, -N, N, ... } で { b_m } = { 0, 0, ... } となります。
  

バンダイが「必殺技」を密かに登録商標にしようとしていたそうです。

意図がよくわかりませんが、いっそのこと「クソゲー」を登録商標にすればいいんじゃないでしょうか。もしくは「抱き合わせ」とか「課金制」とか。
必殺技といえば、似たような言葉に奥義とかありますよね。「北斗百裂拳」とか、あの言葉は登録商標されているんでしょうか。他にもドラえもんの道具の名前だとか、ちょっと気にはなりますね。

今年の名古屋大の問題から三つ目です。例によって合っている保証なしです。

-----

玉が 2 個ずつ入った 2 つの袋 A, B があるとき、袋 B から玉を 1 個取り出して袋 A に入れ、次に袋 A から玉を 1 個取り出して袋 B に入れる、という操作を 1 回の操作と数えることにする。
A に赤玉が 2 個、B に白玉が 2 個入った状態から始め、この操作を n 回繰り返した後に袋 B に入っている赤玉の個数が k 個である確率を P_n(k) ( n = 1, 2, 3, ... ) とする。
このとき、k = 0, 1, 2 に対する P_n(k) を求めよ (途中の導出問題は省略) (名古屋大 2016)。

一回の試行で起こる事象とその確率は、A( 赤, 赤 ) B( 白, 白 ) に対して

B から白を A へ → A から赤を B へ ... 2 / 3
B から白を A へ → A から白を B へ ... 1 / 3

なので、P₁( 0 ) = 1 / 3, P₁( 1 ) = 2 / 3, P₁( 2 ) = 0 となります。n - 1 回の試行後の A, B の状態は

1. A( 赤, 赤 ) B( 白, 白 )
2. A( 赤, 白 ) B( 赤, 白 )
3. A( 白, 白 ) B( 赤, 赤 )

の 3 通りしかありません。この状態から試行を一回行ったときの事象とその確率は、1 の場合は先ほど求めたので 2, 3 について考えると

■ 2 の場合

B から赤を A へ ... 1 / 2 → A から赤を B へ ... 2 / 3 ( k = 1 )
B から赤を A へ ... 1 / 2 → A から白を B へ ... 1 / 3 ( k = 0 )
B から白を A へ ... 1 / 2 → A から赤を B へ ... 1 / 3 ( k = 2 )
B から白を A へ ... 1 / 2 → A から白を B へ ... 2 / 3 ( k = 1 )

■ 3 の場合

B から赤を A へ → A から赤を B へ ... 1 / 3 ( k = 2 )
B から赤を A へ → A から白を B へ ... 2 / 3 ( k = 1 )

1 の場合は k = 0 からのスタートなので、n - 1 回めの試行での確率は P_n-1( 0 ) です。同様に、2 の場合は P_n-1( 1 )、3 の場合は P_n-1( 2 ) となり、

P_n( 0 ) = ( 1 / 3 )P_n-1( 0 ) + ( 1 / 6 )P_n-1( 1 )
P_n( 1 ) = ( 2 / 3 )P_n-1( 0 ) + ( 2 / 3 )P_n-1( 1 ) + ( 2 / 3 )P_n-1( 2 )
P_n( 2 ) = ( 1 / 6 )P_n-1( 1 ) + ( 1 / 3 )P_n-1( 2 )

となります。P_n-1( 0 ) + P_n-1( 1 ) + P_n-1( 2 ) = 1 なので P_n-1( 2 ) = 1 - ( P_n-1( 0 ) + P_n-1( 1 ) ) を下側の 2 式に代入すると

P_n( 1 )
= ( 2 / 3 )P_n-1( 0 ) + ( 2 / 3 )P_n-1( 1 ) + ( 2 / 3 )[ 1 - ( P_n-1( 0 ) + P_n-1( 1 ) ) ]
= 2 / 3

P_n( 2 )
= ( 1 / 6 )P_n-1( 1 ) + ( 1 / 3 )[ 1 - ( P_n-1( 0 ) + P_n-1( 1 ) ) ]
= -( 1 / 3 )P_n-1( 0 ) - ( 1 / 6 )P_n-1( 1 ) + 1 / 3

となり、P_n( 1 ) は定数になります。従って、P_n-1( 1 ) = P_n( 1 ) = 2 / 3 であり、

P_n( 0 ) = ( 1 / 3 )P_n-1( 0 ) + 1 / 9
P_n( 2 ) = -( 1 / 3 )P_n-1( 0 ) + 2 / 9

という漸化式が得られます。

P_n( 0 ) - ( 1 / 3 )P_n-1( 0 ) = ( 1 / 3 )²
( 1 / 3 )P_n-1( 0 ) - ( 1 / 3 )²P_n-2( 0 ) = ( 1 / 3 )³
:
( 1 / 3 )^n-2P₂( 0 ) - ( 1 / 3 )^n-1P₁( 0 ) = ( 1 / 3 )ⁿ

を辺々加えて

P_n( 0 ) - ( 1 / 3 )^n-1P_n-1( 0 ) = Σ_k{2→n}( ( 1 / 3 )^k ) より

P_n( 0 ) = ( 1 / 6 ) - ( 3 / 2 )( 1 / 3 )ⁿ⁺¹ + ( 1 / 3 )ⁿ

となります。また、P_n( 2 ) = 1 - P_n( 0 ) - P_n( 1 ) なので、

P_n( 2 ) = ( 1 / 6 ) + ( 3 / 2 )( 1 / 3 )ⁿ⁺¹ - ( 1 / 3 )ⁿ

となります。
  

EL&P のキーボード奏者、キース・エマーソンの訃報を新聞で見たときはビックリしました。

亡くなったという知らせそのものというより、すでに亡くなっていたと勘違いしていたのが驚きの原因です。しかも自殺したというところまで記憶していたのは誰かと間違えたのか、予知能力でもあったのか :-)
EL&P といえば「展覧会の絵」が忘れられません。「タルカス」よりも好きな作品です。「展覧会の絵」と聞いて EL&P ですなと言ったらムソルグスキーでしょとつっこまれたこともあります。まあ、そんなんですけど少々恥ずかしかったです。

キーボード奏者はあまり記憶に残っている人がいないです。キース・エマーソンとジョン・ロードは超有名ですが、どちらも好きでしたね。そしてどちらも亡くなってしまい残念。ご冥福をお祈りします。  

震災から 5 年。今日はニュースでも特別枠が組まれ、復興の現状についてずっと放送されていました。

そして、それに埋もれるようにひっそりと、人工知能が囲碁界世界最強の棋士を二戦連勝で破るというニュースが流れ、さすがにゾッとしました。自分が思い浮かべる最悪の世界像は人工知能に支配されるというもの。しかし、人工知能が人間を超えてしまうのではなく、人間のほうが人工知能の利用で脳を退化させてしまうのが理由です。そうなると、もはや人工知能に頼らなければ生きてゆけなくなりますからね。

そうならないように、入試問題で脳のトレーニングをしました。合っている保証はありません。

-----

二つの円 C : ( x - 1 )² + y² = 1 と D : ( x + 2 )² + y² = 7² を考える。また原点を O( 0, 0 ) とする。このとき、次の問に答えよ。
円 C 上に、y 座標が正であるような点 P をとる。点 P が円 C 上を動き、点 Q が円 D 上を動くとき、ΔOPQ の面積の最大値を求めよ (途中の導出問題は省略) (名古屋大 2016)。

まず、x 軸の正の部分と線分 OP のなす角度を θ とします。点 P( px, py ) の座標を θ で表すと、

px = 1 - cos( π - 2θ ) = 1 + cos2θ
py = sin( π - 2θ ) = sin2θ

となります。また、OP の長さは 2cosθ となります。

点 P を固定したとき、ΔOPQが最大になるのは、OP を通る直線に円 D の中心 ( -2, 0 ) からひいた垂線が円 D と交差する点を Q としたときになります。これは、( -2, 0 ) を通り、ベクトル OP = ( 1 + cos2θ, sin2θ ) と直交する直線との交点を意味するので、まずはこの直線の方程式を求めると、

1 + cos2θ = 2cos²θ
sin2θ = 2sinθcosθ

より、求める直線の方向ベクトルを ( 1, t ) とすると

2cos²θ + 2tsinθcosθ = 0

を満たせばよく、0 < θ < π / 2 より cosθ ≠ 0 なので

t = -cosθ / sinθ = -1 / tanθ

となります。従って、直線の方程式は

y = ( -1 / tanθ )( x +2 )

となって、円 D との交点は

( x + 2 )² + ( x + 2 )² / tan²θ = 7²

を計算することによって

( x, y ) = ( 7sinθ - 2, -7cosθ ), ( -7sinθ - 2, 7cosθ )

となります。

直線 OP は y = x tanθ なので、先ほど求めた垂線 y = ( -1 / tanθ )( x +2 ) との交点は

( x, y ) = ( -2cos²θ, -2sinθcosθ )

となります。従って、ΔOPQ の高さは、( x, y ) = ( 7sinθ - 2, -7cosθ ) のとき

( -2cos²θ - 7sinθ + 2 )² + ( -2sinθcosθ + 7cosθ )²
= ( 2sinθ - 7 )²sin²θ + ( 2sinθ - 7 )²cos²θ
= ( 2sinθ - 7 )²

より ( 0 < sinθ < 1 なので ) 7 - 2sinθ であり、( -7sinθ - 2, 7cosθ ) の場合も同様に計算して 7 + 2sinθ となります。よって ΔOPQ の面積は

( 7 ± 2sinθ )cosθ = 7cosθ ± sin2θ

となり、0 < θ < π / 2 より sin2θ > 0 なので最大をとるのは 7cosθ + sin2θ の方です。これを θ に対して微分すると

f'(θ)
= -7sinθ + 2cos2θ
= -7sinθ + 2( 1 - 2sin²θ )
= -4sin²θ - 7sinθ + 2

なので、f'(θ) = 0 のとき

sinθ = [ -7 ± ( 7² + 4・4・2 )^1/2 ] / ( 2・4 ) = -2, 1 / 4

となって、0 < sinθ < 1 より 1 / 4 が解となります。このとき cosθ = √15 / 4 なので、

7cosθ + sin2θ = 7cosθ + 2sinθcosθ ≤ 7√15 / 4 + 2・( 1 / 4 )・( √15 / 4 ) = 15√15 / 8 となります。

  

暖かくなったと思ったら寒くなったり。はっきりしない季節ですね。

「保育園落ちた」のブログが国会でも取り上げられたのがニュースになっていました。野党が利用しただけとかいろいろ言われてはいますが、ネットでのつぶやきが国会にまで影響を及ぼすというのは驚きです。前にも同じようなことってありましたっけ？今までは議員本人のつぶやきが取り上げられることしかなかったように記憶してます。
一応、前向きに検討しているみたいですけど、つぶやいた本人はすぐにでもなんとかしてほしいんじゃないでしょうか。

さて、今年の名古屋大の入試問題を一通り解いてみました。合っている保証なしですが、その中の一つを公開しておきます。

-----

曲線 y = x² 上に 2 点 A ( -2, 4 ), B ( b, b² ) をとる。ただし b > -2 とする。このとき、次の条件を満たす b の範囲を求めよ (名古屋大 2016)。
条件 : y = x² 上の点 T ( t, t² ) で、∠ATB が直角になるものが存在する。

A を任意の点 ( a, a² ) として解いてみます。まず、ベクトル TA と BT を求めると、

TA = ( t - a, t² - a² )
BT = ( b - t, b² - t² )

となります。∠ATB が直角ということは、この二つのベクトルが直交するということなので、内積 ( TA, BT ) = 0 となる点 T が a < t < b に存在すればいいことになります。この内積は

( t - a )( b - t ) + ( t² - a² )( b² - t² ) = ( t - a )( b - t )[ 1 + ( t + a )( b + t ) ]

となりますが、t - a > 0, b - t > 0 なので、

f(t) = 1 + ( t + a )( b + t ) = t² + ( a + b )t + ( ab + 1 )

に対し、f(t) = 0 が a < t < b の範囲で解を持つことが必要になります。判別式 D は

D = ( a + b )² - 4( ab + 1 ) = ( a - b )² - 4

より、f(t) = 0 が実数解を持つためには ( a - b )² ≥ 4 が成り立たなければなりません。まず、これがひとつ目の条件になります。

f(t) = 0 の解は { -( a + b ) ± [ ( a - b )² - 4 ]^1/2 } / 2 となることから、

2a < -( a + b ) + [ ( a - b )² - 4 ]^1/2 --- (1)
-( a + b ) - [ ( a - b )² - 4 ]^1/2 < 2b --- (2)

のいずれかとなれば、解は区間 ( a, b ) の間に入ります。(1) より

3a + b < [ ( a - b )² - 4 ]^1/2
( 3a + b )² = 9a² + 6ab + b² < a² - 2ab + b² - 4
8ab + 8a² + 4 < 0 を解いて

a < 0 のとき b > -( 2a² + 1 ) / 2a
a > 0 のとき b < -( 2a² + 1 ) / 2a

となります。また (2) より

[ ( a - b )² - 4 ]^1/2 > -a - 3b
( a - b )² - 4 = a² - 2ab + b² - 4 > ( -a - 3b )² = a² + 6ab + 9b²
2b² + 2ab + 1 < 0

b を変数とする (左辺) = 0 の解は [ -a ± ( a² - 2 )^1/2 ] / 2 なので、

[ -a - ( a² - 2 )^1/2 ] / 2 < b < [ -a + ( a² - 2 )^1/2 ] / 2

が求める範囲になります。これがふたつ目の条件です。

問いでは a = -2 なので、ひとつ目の条件から

( -2 - b )² ≥ 4 より b( b + 4 ) ≥ 0

が成り立てばよく、b > -2 から b + 4 > 0 なので、b ≥ 0 であればいいことになります。ふたつ目の条件から

b > 9 / 4

( 2 - √2 ) / 2 < b < ( 2 + √2 ) / 2

となって、全てを合わせれば

( 2 - √2 ) / 2 < b < ( 2 + √2 ) / 2 または b > 9 / 4

となります。文系では a = -1 だったようです。このときはひとつ目の条件から

( -1 - b )² ≥ 4 より ( b + 3 )( b - 1 ) ≥ 0 なので b < -3, 1 < b であり、ふたつ目の条件から

b > 3 / 2

( 1 - i ) / 2 < b < ( 1 + i ) / 2 [虚数解なので対象なし]

なので、b > 3 / 2 が求める解となります。  

ずいぶん前に買ったメタリック・ナノパズルをようやく一つだけ組み上げました。

今回は、一番簡単そうな「はやぶさ」です。鳥じゃなくて探査機の方。



「難しい」との評判だったのでできるかどうか心配でしたが、なんとか組み立てられました。しかし、パーツが小さすぎてよく見えないし落としたらどこにいったかわからなくなるし、結構大変でした。まだ二つストックがあります。こちらは難しそうなものばかり。。。
金属なので、折り曲げ方を間違えると折れてしまうのではないかと不安だったのが的中し、台座の足のところを逆に折ってしまったと勘違いして二回も曲げ直し、折れるなよという願いも虚しく一部が折れてしまいました。あまり目立たない、台座に近いところだったのが幸いです。

次のパズルはいつ組み上がるのでしょうか。。。