Fussy's Diary

昨日はちょっとしたイベントがあって参加してきたのですが。

夕方に到着後しばらく外を眺めていたら大量のカラスが近くに集まってきました。これほどたくさんのカラスが集まっているところを見たことがなかったのでかなり驚きました。写真撮ってみたんですけど、写真ではあまりすごそうには見えないですね。



大きな公園が近くにあって緑も多いので、カラスにとっては天国なんでしょう。車が通ると逃げたりしていたものの、近くを歩いて通ろうものなら集団で襲われるんじゃないかと思いました。ちなみに、うちの父親は以前カラスに襲撃されたことがあります。一度襲った人間は忘れないそうです。

カラスを眺めていたら、ふと桜が咲いているのに気づきました。いい季節になってきました。  

今週は春分の日がありますね。いよいよ春到来ですか。

今回も名大の入試問題を解いてみたいと思います。今年ではなく去年の問題から選んでみました。
ちなみに、たいていは問題文の短いものを選択しています。図入りのものなんかは画像を作らなきゃならないのでよほどのことがない限りパスしてます。

-----

■ p を素数、a, b を整数とする。このとき、次の問に答えよ ( 2018 年 名大 )。
(1) ( a + b )^p - a^p - b^p は p で割り切れることを示せ。
(2) ( a + 2 )^p - a^p は偶数であることを示せ。
(3) ( a + 2 )^p - a^p を 2p で割ったときの余りを求めよ。

(1) 二項定理より

( a + b )^p - a^p - b^p = Σ_k{1→p-1}( _pC_ka^kb^p-k )

なので、_pC_k ( k = 1, 2, ... p - 1 ) が p で割り切れることを示せば十分です。_pC_k = p! / k!( p - k )! より分子は p を素因数に持ちますが、分母は持ちません。p は素数なので分母にあるすべての素因数と互いに素です。_pC_k は整数なので、_pC_k は p で割り切れることになります。

(2) ( a + 2 )^p - a^p = 2Σ_k{0→p-1}( _pC_ka^k2^p-k-1 )

より、偶数であることが示されます。

(3) (2) で示した式と (1) の結果より、k が 1 から p - 1 までの項は 2p で割り切れるので、2_pC₀a⁰2^p-1 = 2^p を 2p で割ったときの余りを求めればよいことになります。p = 2 のときは明らかに 0 なので、奇素数の場合を考えます。

2^p = ( 1 + 1 )^p

と表せることから、( 1 + 1 )^p - 1 - 1 は (1) より p で割り切れ、かつ偶数であるので、2^p - 2 は 2p で割り切れることになり、2^p を 2p で割った余りは 2 となります。
  

このところ雨が多くなってきました。季節も春に移りつつあるようです。

新聞に載っていた今年の名大の入試問題をいくつか解いてみました。久々に紹介してみたいと思います。

-----

正の整数 n の正の平方根 √n は整数ではなく、それを 10 進法で表すと、小数第 1 位は 0 であり、第 2 位は 0 以外の数であるとする ( 2019 年 名大 )。
(1) このような n の中で最小のものを求めよ。
(2) このような n を小さいものから順に並べたときに 10 番目にくるものを求めよ。

(1) √n は整数ではなく、小数第 1 位が 0 なので、ある整数 m を使って m.01 以上で m.1 より小さい数として表すことができます。

m = 1 のとき、1.1² = 1.21 < 2 なので、2, 3 は非該当です。
m = 2 のとき、2.1² = 4.41 < 5 なので、5, 6, 7, 8 は非該当です。
m = 3 のとき、3.1² = 9.61 < 10 なので、10～15 は非該当です。
m = 4 のとき、4.1² = 16.81 < 17 なので、17～24 は非該当です。
m = 5 のとき、5.1² = 26.01 > 26 で、5.01² = 25.1001 < 26 なので 26 が最小となります。

m.1 の平方値の増え方には規則性があります。実際、

( m + 0.1 )² = m² + 0.2m + 0.01
( m + 1.1 )² = m² + 2.2m + 1.21

なので、m が 1 増えることに m.1² は 2m + 1.2 ずつ増えます。また

( m + 0.01 )² = m² + 0.02m + 0.0001

なので、分解して計算すると計算が少し楽になります。

(2) 5.1² < 27 なので、27～35 は非該当です。

m = 6 のとき、6.1² = 37.21 > 37 で、6.01² = 36.1201 < 37 なので 37 が 2 番目となります。
m = 7 のとき、7.1² = 50.41 > 50 で、7.01² = 49.1401 < 50 なので 50 が 3 番目となります。
m = 8 のとき、8.1² = 65.61 > 65 で、8.01² = 64.1601 < 65 なので 65 が 4 番目となります。
m = 9 のとき、9.1² = 82.81 > 82 で、9.01² = 81.1801 < 82 なので 82 が 5 番目となります。
m = 10 のとき、10.1² = 102.01 > 102 で、10.01² = 100.2001 < 101 なので 101, 102 で 6, 7 番目となります。
m = 11 のとき、11.1² = 123.21 > 123 で、11.01² = 121.2201 < 122 なので 122, 123 で 8, 9 番目となります。
m = 12 のとき、12.1² = 146.41 > 146 で、12.01² = 144.2401 < 145 なので 145 が 10 番目となります。


計算さえ間違えなければ割と簡単に解ける問題だと思います。新聞の解答はもう少し凝った方法で解いているようでした。  

私用で出かけてたんですが、あいにくの雨でした。曇の予報だったのに。
しかし、久々に鉄板ナポリタンが食べられたので満足です。

アルゴリズムのコーナーを更新しました。今回は「決定木」がテーマです。サンプル・プログラムがかなり多めになりました。
次回は画像関連で「コーナー検出」を取り上げる予定です。その後のテーマは全く決めてません。まあ、のんびりと探そうかと思います。