受験数学わんこらスクール
京大理学部で数学をやったわんこらが中学生や高校生、受験生に数学の公式や問題を解説します。

整数問題、東京工業大学2007年度数学第1問の解説
こめかみが痛いわ。

さて、東京工業大学の2007年度の第1問の整数問題いきます。


[問題]
090125_m3.jpg
pを素数、nを0以上の整数とする。
(1)mは整数で0≦m≦nとする。1からp^(n+1)までの整数の中で、p^mで割り切れp^(m+1)で割り切れないものの個数を求めよ。

(2)1からp^(n+1)までの2つの整数x,yに対しその積がp^(n+1)で割り切れるような組(x,y)の個数を求めよ。


[解答と解説]
(1)
090125_m4.jpg
例えば、1から3^2=9までに3で割り切れるのは何個あるか?つまりは3の倍数は何個あるか言うと
9/3=3です。
3,6,9で確かに3個です。

同じように考えて1からp^n+1までにp^mで割り切れるのは
p^(n+1)/p^m=p^(n-m+1)
個あります。

これには、p^(m+1)やp^(m+2)で割り切れるものも含まれています。
だからp^(m+1)で割り切れるものの個数を引けばp^(m+1)で割り切れないがp^mで割り切れる個数がでます。

p^(m+1)で割り切れるものの個数は
p^(n+1)/p^(m+1)=p^(n-m)
個だから求める個数は
p^(n-m+1)-p^(n-m)
個です。

このやり方は、お決まりなので覚えていてください。


(2)
090125_m5.jpg
(1)を利用することが予想されます。
しかし、(1)は0≦m≦nだったのでx,yがp^(n+1)である場合を別に考えなければなりません。
x=p^(n+1)の時、xyはp^(n+1)で必ず割り切れるからyは任意でp^(n+1)個です。
同様にy=p^(n+1)もxは任意でp^(n+1)です。

これを足すとx=y=p^(n+1)を二重にカウントしてしまってるからx=y=p^(n+1)になる組み合わせはもちろん1個なので1を引きます。

だからx=p^(n+1)またはy=p^(n+1)になるのは
2p^(n+1)-1
個です。


後はi,jを0以上n以下の整数として、xがp^iで割り切れてp^(i+1)で割り切れなくて、yがp^jで割り切れてp^(j+1)で割り切れない場合は

(p^(n-i+1)-p^(n-i))(p^(n-j+1)-p^(n-j))

個あって、xyがp^(n+1)で割りきれるにはi+j≧n+1になればいいから、

n+1≦i+j,1≦i≦n,1≦j≦nを満たすi,jで(p^(n-i+1)-p^(n-i))(p^(n-j+1)-p^(n-j))を足し上げます。


∑(n+1≦i+j,1≦i≦n,1≦j≦n)(p^(n-i+1)-p^(n-i))(p^(n-j+1)-p^(n-j))
を計算します。

090125_m6.jpg

変数が二つあるときは、図を書いて格子点を考えるのが定石ですがこの場合は単純にiを固定してjで足し上げて、iで足し上げられます。

iを固定するとjの範囲は

n+1≦i+j⇔n+1-i≦j

で1≦i≦nよりn+1-i≧1だから

n+1≦i+j,1≦i≦n,1≦j≦n)

n+1-i≦j≦n,1≦i≦n

と整理できました。

まず

∑(n+1-i≦j≦n)(p^(n-i+1)-p^(n-i))(p^(n-j+1)-p^(n-j))

ですが∑計算に関係するp^(n-j+1)-p^(n-j)は階差数列です。

だから端だけが残って、そこの部分は

p^i-1

になります。


これはxがp^iで割り切れてp^(i+1)で割り切れない時、xyがp^(n+1)で割り切れるにはyがp^(n+1-i)で割り切れる必要がありますが、そういうyは

p^(n+1)/p^(n+1-i)=p^i

通りで、y=p^(n+1)の場合を取り除いて

p^i-1

って言う意味です。


それに気づけば、わざわざさっきの∑計算はする必要ありません。
と言っても、階差数列の和だから別にあんま計算してないかもしれんけど。

後は1≦i≦nでたします。


∑(1≦i≦n)(p^(n-i+1)-p^(n-i))(p^i-1)
=∑(1≦i≦n){(p^(n+1)-p^n) + (p^(n-i+1)-p^(n-i))}
でp^(n-i+1)-p^(n-i)も階差数列だからこの部分の和も端だけが残って
p^n-1
になるから結局
n(p^(n+1)-p^n)-p^n+1
になります。

よって2p^(n+1)-1を足して求める個数は

n(p^(n+1)-p^n)-p^n+1+2p^(n+1)-1
=(n+2)p^(n+1)-(n+1)p^n

になりました。


もっと追求すればp^i-1の-1があるから、計算がややこしくなってるので
x=p^(n+1)の時は、yは任意でp^(n+1)通り
xがp^mで割り切れてp^(m+1)で割り切れないとき(0≦m≦n)、xはp^(n-m+1)-p^(n-m)通りで、
yはn+1-(m+1)=n-mよりp^(n-m)で割り切れなければならないから、その個数は
p^(n)/p^(n-m)=p^m
個。
よって
∑(0≦m≦n)(p^(n-m+1)-p^(n-m))p^m
=∑(0≦m≦n)(p^(n+1)-p^n)
=(n+1)(p^(n+1)-p^n)

だから結局

(n+1)(p^(n+1)-p^n)+p^(n+1)
=(n+2)p^(n+1)-(n+1)p^n
とかなり簡単に求まりました


だからxだけp^(n+1)を別個に考えた方が上手くいくってことです。
でもこれはxもyも両方p^(n+1)を別個に考えるのもそこそこ自然な考えなのでそうやってしまった時でもばりばり計算して解いてしまう力があれば強いと思います。

東京工業大学の入試の数学の過去問の解説

高校数学の入試問題などの解説

整数問題の解法の解説と問題演習




テーマ:大学受験 - ジャンル:学校・教育

▲ページトップへ
この記事に対するトラックバック
トラックバックURL
→http://kazuschool.blog94.fc2.com/tb.php/161-570f07d2
この記事にトラックバックする(FC2ブログユーザー)
▲ページトップへ
プロフィール

Author:わんこら
京都大学理学部で数学と物理を勉強し、数学を専攻しました。
東京で数学と物理の講師やってます

わんこら日記で日記とか勉強の仕方とか書いています

わんこら式数学の勉強法

メール
迷惑メールにされる危険性があるので出来るだけ
kazuyuki_ht○guitar.ocn.ne.jp
(○を@にしてください)に送ってください
勉強とかでどんな悩み持ってるかなど色々と教えてくれると嬉しいです。
わんこら式のやり方についてのメールはわんこら式診断プログラムを参考にしてください

詳しいプロフィール

人気blogランキングへ



にほんブログ村 受験ブログへ



学生広場

相互リンクも募集してます。

何かあれば
kazuschool_ht★yahoo.co.jp
かメールフォームからメールください。
(★を@にしてください)

カテゴリー

メールフォーム

名前:
メール:
件名:
本文:

FC2カウンター

リンク

このブログをリンクに追加する

お勧めの参考書、ノート

数学でお勧めのノートは
KOKUYOの無地
理由




センター試験は過去問が大切


チャートが終わったらお勧め
大学への数学1対1シリーズ
数学1


数学A


数学2


数学B


数学3


数学C

月別アーカイブ

ブログ内検索

RSSフィード

最近のトラックバック

ブロとも申請フォーム

この人とブロともになる

  1. 無料アクセス解析