数学オリンピック事典を一日一問以上解くスレ
■ このスレッドは過去ログ倉庫に格納されています
>>5
数オリの問題が必ずしも面白い問題とは限ら無い 黒板に数字1と2が書かれている.次の方法で新しい数を黒板に書き足すことが許されるものとする.
黒板に数a,bがあるならばab+a+bを書くことができる.
このような方法で次の数を黒板に書くことができるか.
(1) 13121 (2) 12131 >>8
n回目に黒板から選ぶa,bをそれぞれan,bnとし、新たに黒板に追加する数をcn=an+bnとする。
(1) an=1で固定し、b1=2とする。b[n+1]=cnとなるようにとると、c[n+1]=cn+1+cn=2cn+1となり、cn=2×3^n-1となりn=7とするとcn=13121が黒板に追加される。 >>8
(2) c=ab+a+b=(a+1)(b+1)-1=12131とすると(a+1)(b+1)=2^2×3^2×337
対称性より、a+1が337の倍数として考えてよい
[1] a+1=337のとき黒板には336が書けなければならない
つまり新たに(a+1)(b+1)-1=336とすると337が素数なのでこれは成り立たない
よって黒板には336は追加できないので[1]は不成立
順次場合分けすれば、いずれも(a+1)(b+1)=素数が出てきて不成立になるので12131は黒板に書けない >>8
・ ab+a+b=(a+1)(b+1)−1
・ a と b から (a+1)(b+1)−1 が作れる
・ (a+1)−1 と (b+1)−1 から (a+1)(b+1)−1 が作れる
・ x−1 と y−1 から xy−1 が作れる
・ 最初に黒板に書いてあるのは 2−1 と 3−1
このことから、黒板に書けるのは 2^n3^m−1 (n,m≧0, (n,m)≠(0,0)) という形の数に限定される。
また、この形の数は必ず黒板に書ける。
(1) 13121=2^n3^m−1 (n,m≧0, (n,m)≠(0,0)) となるかを調べればよい。
(n,m)=(1,8) とすればよい。よって、この数は黒板に書ける。
(2) 12131=2^n3^m−1 (n,m≧0, (n,m)≠(0,0)) となるかを調べればよい。
12132=2^n3^m となるかを調べればよい。12132=4*9*337 であり、
337 は2でも3でも割り切れないので、12132=2^n3^m は起こらない。
よって、この数は黒板に書けない。 ゼータ関数のすべての非自明な零点の実部は 1/2 である。 整数 1
16+21k≦3×2003+1より、k≦285。
4008-286=3722。
整数2
a4<12である。すると
a1=1, a2=2, a3=4, a4=8と決まる。
8m+8mn=64。m+mn=8。a5=16, a6=48。
整数3
実際割ると、n+10|900。n=890。 整数 1
共通項16+21k≦3×2003+1よりk≦285。
4008-286=3722。
整数2
1, 2, 4, 8まできまり、8m, 8mnと置けて、
m=2, n=3。∴16, 48。
整数3
n+10|900より、nの最大値は890。 組合せ1
25C2=300。
組合せ2
13794/2=6897桁。9+180+2700=2889桁。
残り4008/4=1002個。全部で2001個。
組合せ3
与式/2=(2^n-2)/2=2^(n-1)-1は奇数である。 幾何1
(s-t)(s+t)=1より、s+t=1/2。
幾何2
底>1のとき指数関数は増加関数なのでt3<t4。
底<1のとき指数関数は減少関数なのでt2<t1。
t1<t3より、t4>t3>t1>t2。
幾何3
(√6±√2)/4。2±√3。
cosπ/12=√6+√2/4。
1/2。分母分子に掛ける。
8sin20をかけると、1/8。 数オリと大学への数学の宿題とでは、どちらの方が難しいのでしょうか? The IMO Compendium持ってる人いますか? 数オリって、才能ですか?
それとも、攻略法がありますか? 整数4
k/nと(n-k)/n。異なれば偶数個が示せた。
同じならばn=2kとなり、既約ではない。この場合はそれ以外を考えれば良いので示された。
ユークリッドの互除法による。
整数5
1001=(a+f)(b+d)(c+e)=7×11×13。31。
整数6
1〜999の中に
2の倍数は499個。3の倍数は333個。5の倍数は199個。
6は166個。10は99個。15は66個。30は33個。
包除原理により733個。999-733=266個。100個。 組合せ4
3は667個。4は500個。12は166個。
3または4は1001個。
15は133個。20は100個。60は33個。
15または20は200個。よって801個。
組合せ5
Aを一桁、Bを二桁、Cを三桁とする。
A=9, B=180, C=1794=3×598。697の7。
組合せ6
背理法。
女子ブロック:男女女男。男女男。13個以上。男子は26個以上。これは矛盾。
男子ブロック:女男男男女。女男男女。なので男子が取り合いになることはない。
別解。背理法。1人置きに2つに分ける。するとどちらも女子は12個以下となり合わせて24以下となるから矛盾。 幾何4
二乗の所のsinとcosを変える。
幾何5
sinとcosに変えて加法定理。
別解。cotの加法定理。因数分解して与式になる。
幾何6
π/12の値を使う。普通の三角方程式になる。
変域を押さえる。 >>31
秋山 仁 + P.フランクル「[完全攻略]数学オリンピック」日本評論社(1991)
という本が昔あったけど、今じゃ役に立たないだろうね。
http://www.nippyo.co.jp/shop/book/1495.html 整数7
鳩の巣原理によりk個の巣に類別される。素数は無限個あるので少なくとも1つの巣には無限個の素数が入っている。
それらは全てp+ka(n)の形をしている。
整数8
積の総和は(0+1+…+9)^3-0。0を1に読み替えて、
(1+1+…+9)^3-1=46^3-1より、最大の素因数は103。
整数9
L=Gabより、(a-1)(b-1)=0となり、成り立つ。
別解。2次方程式を考える。与式と 解と係数の関係を使うと
{L, G}={m,m}が示される。G|Lより成り立つ。 組合せ7
2^4=16通り。
組合せ8
16!/2^8通り。
組合せ9
最小でも20枚は必要。反例があれば上げて行く。
22枚の時、5,5,5,7とすると、2,2,2,3=9足となり不適。
23の時、少なくとも一色は偶数枚ある。すると無駄になるのは3枚以下になるので、23枚。
別解。2p+3であることを示す。
2p+2の時、1,1,1,2p-1はp-1足となり不適。
この組み合わせが作れない時でも4つの奇数で代用できる。
(4枚の無駄を発生させる)。
例えば解1において3,3,3,13とすると1,1,1,6=9で不適となる。
帰納法で2p+3が示せる。p+1の時、2p+5枚で、その5枚中一足作れる。残りの2p+3は帰納法の仮定により成り立つ。 幾何7
円盤の面積。帯状領域。点対称。50π。
幾何8
正弦定理で辺をsinに変える。
倍角公式と和積変換で不等式が示せる。
幾何9
関数方程式。2乗する。一対一に対応する。
f(t)=√(t+1), -1≦t≦1。f(tan^2x)=secx。 整数10
n^2の約数の個数。平方数なので奇数個。nより小は1を引いた半分。nの約数の個数。引くとrsになる。31×19=589。
別解。構成する。19×31=589。
整数11
2の冪乗×奇数と置く。1より大きな奇数の約数を持つ。
整数12
nの奇数の約数のうち最大のものをpとする。n=2^a×pと置ける。
pが等しい二数は一方が他方の二倍以上にならなければならない。矛盾。従って等しくなることはない。
集合として{1,3,…,4011}。2006^2+1003
=1003×4013=4025039。 組合せ10
分子と分母は互いに素。素因数は2,3,5,7,11,13,17,19の8個。分子と分母に割り振るから2^8=256。分母>分子はちょうど半分だから128個。
組合せ11
1≦a<<b<<c<<d<<e≦18⇔
1≦a<b-1<c-2<d-3<e-4≦14より、
14C5=14×13×12×11×10/120=14×13×11=2002。
組合せ12
Aは1人と握手をしていないとする。それをBとする。
他の(N-2)人同士は全員が握手をしているとしてよい。
その(N-2)人はAとBとも握手をしているとしてよい。
すなわち(N-2)人は他の(N-1)人全員と握手をしている。
AはB以外の全員と握手をしている。
BはA以外の全員と握手をしている。
答え(N-2)人。
AはN-2人と、BはN-2人と、その他の人々はN-1人と握手をしている。 幾何10
4と6を代入するだけ。次数下げ。
幾何11
15,36,39{5:12:13)の大三角形よりも1ずつ小さい相似な三角形を考える。内心。角の二等分線。面積比。相似比。
5/6倍なので、15×36×25/36 ÷13×34=15×25/13×34
=375/442。
幾何12
二乗して足す。C=30,150。150だと矛盾。
30で矛盾が生じないのかは不明だが答え30°。 整数13
27000=2^3×3^3×5^3。分数と整数の総和は、
(2^7-1)(3^7-1)(5^7-1)/2^6×3^3×5^3。
整数14
(1)どちらも2^a×5^の形なのでこの形を保存しなければならない。l=Max、g=Minとして調べる。慣れないとミスしやすい。4,3,それ以下。3,3,それ以下。それぞれの順列。
これらは独立なので7×10=70個。
(2)素因数分解しておく。l=Max、g=Minとして調べる。
対等性より大小を設定してよく、簡単に消去できる。
整数15
仮定を反映させて文字を設定する。互いに素を利用する。最終的にc=a'b'とg=b'-a'が示せる。 組合せ13
x=2y-1と置き換える。50C3=50×49×8=19600個。
組合せ14
人名の数に関する帰納法で示す。
n=1の時、シャッフルすれば良い。
nの時に成り立つと仮定するとn+1の時、
(1)aのみの人名が書かれたカードの枚数が左右で等しい時。
帰納法の仮定によりaを無視するシャッフルでa以外について成立する。両側にaを同数加えても成り立っている。
(2)左より右の方が多い場合も同様である。
(3)左の方が右よりも多い場合はaについてのシャッフルを一度だけ行う。その結果成り立てば終わり。
成り立たなければ(2)になっているのでaを無視するシャッフルで成り立たせることができる。(証明終)
組合せ15
繰り上がりが必ず発生するのは5,6,7,8の場合である。
その他の場合は、1999, 1a99, 1ab9, 1abc9として、
0,1,2,3,4を代入すると、1+5+5^2+5^3=156。 幾何13
移項してtanの加法定理。注も同様。
幾何14
1^2+8^2=4^2+7^2=65に注意する。
二乗して加えてcosの加法定理。
幾何15
和積変換+二倍角の公式→和積変換。注も同様。 整数16
p|aとするとp|bとなる。
そうでない場合、a^3≡b^3。フェルマーの小定理。
整数17
因数分解の公式。7×43×271×331より652。
整数18
n=5のみである。1〜9まで調べる。完全立方数ならば5の倍数であるから125の倍数である。n!は125の倍数なので5が125の倍数にならないといけない。矛盾。
別解。mod7で5になる。
mod7における立方剰余は0, ±1のみなので矛盾。 組合せ16
5×4×3=60。
組合せ17
二つのペアの差は16C2=120。悪いペアは高々16個。
悪いペアでないペアは少なくとも104個。
2数の差は1〜99なので鳩の巣原理により、差の等しい二つのペアが存在する。
ある数aについてaによる悪いペアが 2組以上存在すると証明は完結する。よって悪いペアは高々一つと仮定して良い。
組合せ18
材質2。大きさ3。色4。形4。
異なるのはそれぞれ1, 2, 3, 3。
2+3+3+6+6+9=29。 幾何16
3倍角の公式。
幾何17
展開する。相加相乗平均の不等式。 2倍角の公式。
使った不等式を二乗してまた使う。
幾何18
一般性を失うことなく大小関係を設定して良い。
正弦定理。A≧60°と合わせてA>150°。 整数19
p≠3の時。p^2+11=A。3|A。
p≠2の時、2|A。4|A。よってこの時、12| A。
12は約数を6個もつので不適。
p=2の時、4個。p=3の時、適する。
整数20
10進法と7進法。k=2、2a2-4a1-a0=0。
630。49×6+7×3=315。
整数21
設定して二項定理。
反例。3^4≡1^4 mod4^2であるが3≡1mod4ではない。 組合せ19
全て同じ場合。10個。
それ以外の場合。異なる二桁を持つ。2個ずつ対応するのて、
2×9990+10=19990。
別解。包除原理。1000×10×2-10=19990。
組合せ20
円順列。49C2=49×24=1176。
点対称の位置は中心を除いて24個ある。
1152/4 +24/2=288+12=300。
組合せ21
mod3で考えて良い。0,1,2,0,1,2,0。
a4≡0。a1≡a5。a2≡a6。a3≡a7。{0,1,2},0,{0,1,2}。
3×6×4×2=144。 幾何19
内角の和。加法定理。相加相乗平均の不等式。
同値な形。
幾何20
鋭角三角形。相加相乗平均の不等式。
注。定義されている範囲において三角形の内角でなくとも成り立つ。
幾何21
直角三角形の時。
それ以外の時。前問に帰着される。
全単射な関数であることを利用する。 整数22
帰納法。p-1以下での成立を仮定することに注意する。
二項係数の公式。
別解。互いに素。
整数23
フェルマーの小定理。n=(p-1)^2kとすれば良い。
整数24
n=4の時、成り立たない。
n≧5の時、mod10で3となり、完全平方数になることはなく
従って偶数乗になることはない。
n≦8を直接調べて成り立たないことを確かめられる。
n≧9に対して、27の倍数であるが
1+2+6+24+120+720+5040+40320
46233/3→15411/3=5137→×。
立方数になるためには素因数3に関しても立方数になっていなければならないがそれが不可能であることが示された。 組合せ22
少なくともA,Bのどちらか一方には属する。
3^n-1/2 +1=3^n+1/2より、365。
組合せ23
三角形の成立条件。
4,5,9,14,23,37,60,97,157,254
足して次の項にしている。
n=254は満たさない。これは必要条件なので逆にそれ以下だと満たしてしまう。フィボナッチ数列。n=253ならばOK。
組合せ24
集合Aが有限である場合。満たす数は無限集合Bに属する。
逆も同様である。
どちらも無限集合とする。
Aから3数xyz>nかつy-z>nを選ぶ。これは可能である。
y-zはA,Bどちらでも矛盾する。 幾何22
後半。xについて解く。yzは決まる。cosの加法定理。
三角形の内角の和。
前半は逆を辿ることで示される。
幾何23
(1)問題8と相加相乗平均の不等式。
別解。相加相乗平均の不等式。問題22。因数分解される。
(2)問題22と(1)より示される。
(3)基本公式と(2)。
(4)相加相乗平均の不等式と(3)。
(5)問題8と対等性。相加相乗平均の不等式。
幾何24
(3)(4)は(2)とcos2倍角。
(1)和積変換。三角形の内角の和。
(2)和積変換。三角形の内角の和。和積変換。
(4)の後半。増加関数。高々1つ。鋭角であることを示す。
別解。係数行列の行列式が0となること。 整数25
奇数と偶数で場合分け。x^k+y^kはkが奇数の時、x+yで割り切れる。(m+1, 2m+1)=(m+1, -1)=(0, -1) =1。互いに素。
nが偶数の時も同様。
整数26
p-4=q^4と置く。q≧2。(q+1)^2+1>(q-1)^2+1≧2。
これは素数であることに反する。合成数である。
整数27
縦のものを横に数える。Σk[n/k]≦Σn=n^2。 組合せ25
100(10)=1100100(2)→3^6+3^5+3^2=729+243+9=981。
組合せ26
2枚のカードを取り、固定する。ある1つの項目に関して2枚のカードが同じ場合3枚目も同じになる。2枚のカードが異なる場合3枚目は異なる。他の二項目に関しても同様である。
従ってどちらの場合でも1枚に決まってしまう。
27C2/3=117。
組合せ27
仮定より全ての参加者に友達が少なくとも1人存在する。
2≦k≦mのkで、k人のうちの任意の2人について友達であると仮定する。
他のm-k人を加えるとk人全てと友達である人間が存在する。
A(k+1)。「自分は自分と友達になれない」からこれはk人以外の人間である。これを繰り返すことにより、任意の2人が友達であるm+1人の組合せが作られる。もっと多くても良い。
m+1人より多くは存在しないことの証明。
他の人Bを取ってくる。Bには友達がいる。
(1)m+1人の中にBの友達が2人以上いると仮定する。その2人を除きBを加えたm人の集合についてこのm人は共通の友人(除かれた2人)を2人持つことになって仮定に反する。
(2)Bの友達が多くとも1人だけいると仮定する。それをA1とする。A1は友達の可能性もあるし友達でない可能性もある。
m人集合{B,A1,A3,…Am}は共通の友達Cを持つ。C≠Ai (i=1〜m+1)である。C=A1とするとA1はm-1人になってしまう。
Cの友達は{B,A1,A3,A4,…Am}である。m (≧3)人集合の最小値は{B,A1,A3}である。
Cは少なくとも友達{A1,A3}を持つので(1)に帰着され矛盾が導かれる。答えは、参加者はm+1人で友達の数の最大値はm人である。 幾何25
(1)正弦定理。
(2)正弦定理。
(3)正弦定理。
(4)余弦定理。半角の公式。三角形の周の長さの半分。
ヘロンの公式。
(5)正弦定理。問題24(1)。
幾何26
(1)内接円の半径と三角形の面積。問題25(2)(4)(1)。
2倍角の公式。
(2)(1)と問題23(4)。
幾何27
(1)和積変換。2倍角の公式。和積変換。
(2)問題25(3)。オイラーの公式。
別解。外接円。トレミーの定理。
組合せ27
別解。Pの友達の集合をSとする。|S|=n。
m-1個の元を持つSの任意の部分集合をS'とする。PをS'に加えてm人にする。このm人全員と友達であるQが存在する。Q∈Sである。
S1, S2∈S'を取る。QS1=QS2と仮定すると、QはS1∪S2である、m個の元を持つ集合の要素全員と友達である。またPとも友達であるからQは友達をm+1人以上持ち矛盾である。
よってQS1≠QS2である。任意のQは全て相異なる。
相異なる部分集合の個数はm≧3より、
nC(m-1)≧nC2>n (∵n≧4)。
よって全てのQの種類は、存在する人数よりも多くなってしまう。従って任意のQが相異なることはなくどれかは一致してしまい矛盾する。鳩の巣原理。 整数のbig ploblemは何行に収まるんだろうか 整数28
i=jとすると2i/i=2。
2以外の要素のうち最小のものをsとする。
sが奇数の時、(s+2)/1=s+2∈Sとなり、奇数が無限に続くので矛盾。
sが偶数の時、(s+2)/2=s/2 +1∈S。
s≧4>2、2<3≦s/2 +1<sとなり、sの最小性に反する。
注。異なっていなければならないという条件が加わると
{a+1, a(a+1)} (a=2,3,4,5,…)
整数29
2^3≡-1 mod9より、2^29≡5。答えは4。
実際に2^29=536870912であり、4以外は全て出現する。
整数30
n^5+n^4+1=(n^2+n+1)(n^3-n+1)>1 (∵n>1)
よって素数ではない。合成数である。 組合せ28
Ti=Hi=18!であり、Ni=(Ti+Hi)×7×13。
よって平均値はΣNi/20!=7×13×2/20=91/10。
別解。Ai=2× (n-2)C(k-1)/nCk。
(n-1)Ai= (n-1)×2× k(n-2)C(k-1)/n× (n-1)C(k-1)
=2k(n-k)/n。2×7×13/20=91/10。
組合せ29
ラベルの張り替え。n→2^(k-1) +1 -n/2と変わる。
1024→1、1022→2、…、2→512。
漸化式を解いて、L10=4^5/3 +2/3=342。
組合せ30
約数の個数。rs=31×19=589。
別解。2^a=3^bとなることはないので、31×19=589。 整数28
i=jとすると2i/i=2。
2以外の要素のうち最小のものをsとする。
sが奇数の時、(s+2)/1=s+2∈Sとなり、奇数が無限に続くので矛盾。
sが偶数の時、(s+2)/2=s/2 +1∈S。
s≧4>2、2<3≦s/2 +1<sとなり、sの最小性に反する。
注。異なっていなければならないという条件が加わると
{a+1, a(a+1)} (a=2,3,4,5,…)
整数29
2^3≡-1 mod9より、2^29≡5。答えは4。
実際に2^29=536870912であり、4以外は全て出現する。
整数30
n^5+n^4+1=(n^2+n+1)(n^3-n+1)>1 (∵n>1)
よって素数ではない。合成数である。 幾何28
(1)鋭角三角形。問題24(4)。問題23(1)(2)。問題22。
問題23注。
(2)(5)と相加相乗平均の不等式。
(3)コーシー・シュワルツの不等式と(5)。
(4)(1)と同様。
(5)⇔(4)
(6)(5)とcosの2倍角の公式。
(7)(2)と問題25(5)。
幾何29
tanの3倍角の公式。
幾何30
(1+tank)(1+tan(45-k))=2。与式=2^23となる。
別解。途中計算について。 幾何31
幾何的に考えつつ組合せ的に考える。
y座標が定まる。余弦定理と三平方の定理。
x座標が定まる。面積が求まる。
別解。三角関数を使う。x座標が簡単に求まる。
幾何32
cos^-1(sinθ)=π/2 -θより、
x>0の時、tancos^-1sintan^-1x=1/x。
x<0の時、tan sin^-1costan^-1x=1/x。
幾何33
問題25(4)。積和変換。 幾何34
正弦定理。和積変換。
幾何35
問題34。
幾何36
問題20(1)の注。2倍角の公式。問題20(1)。 幾何37
正弦定理。
問題15。
幾何38
sinを掛ける。
幾何39
置き換え。相加相乗平均の不等式。 幾何40
相加相乗平均の不等式。
幾何41
帰納法。和積変換。
幾何42
解析。置き換え。合成。 幾何43
コーシー・シュワルツの不等式。
幾何44
解析。加法定理。2次方程式の2解。取り得る値の範囲。
幾何45
置き換え。 幾何46
場合分け。置き換え。平方完成。
幾何47
帰納法。加法定理。
幾何48
要素が一致する条件。和積変換。 幾何49
チェビシェフ多項式。
(1)帰納法。偶関数、奇関数。
(2)帰納法。
(3)帰納法。積和変換。
(4)区間 [0, π/2] の上で一対一写像。
(5)奇関数または偶関数。場合分け。
幾何50
チェバの定理。三角比による表示。
幾何51
ブロカール点。
問題28(5)。コーシー・シュワルツの不等式。
別解。f(x)= logsinx。イェンセンの不等式。
別解。積和変換。2倍角の公式。
問題23(1)。
幾何52
(1)和積変換。2倍角の公式。
(2)和積変換。
(3)補題の証明。積和変換。
(4)(5)2倍角の公式。3倍角の公式。
ガウスの補題。
注。技巧的な変換により場合分けが減る。
(6)2倍角の公式。加法定理。
解と係数の関係。
注。一般化。解と係数の関係。cot^2の和。 整数31
2と5を含む必要がある。それ以外の素数を設定する。
x+y≦xy (整数2以上、実数1以上)を導く。重要。
これが拡張される。重要。
2,3,5,7に絞られる。
さらに5のみに絞られ、{2,3,5,5}を得る。
整数32
mod9で考えてn≡0。9と11111は互いに素なのでnは99999の倍数。0<x+y<99999×2より、x+y=99999に決まる。
繰り上がりを考える。
5!×2^5×(9/10)=12×32×9=3456。
整数33
背理法。1999/19<106。少なくとも1つは105以下であり、各桁の和は99の時の18以下である。
Sの総和≡Sの各桁の総和 mod9
これよりk≡1。k=1,10。
495。1495。1990。次に大きい数字を取ってくると208であり、総和は2008となり矛盾する。 整数34
3≦p≦qと仮定してよい。フェルマーの小定理。
p=3に決まる。q=3、13。
整数35
a(n)=11111(1が3^n個)とする。
a(n)≡0 mod3^nを帰納法で示す。
a(k+1)=11.…1 11…1 11…1=11…1(10^(2×3^k) +10^3^k +1)
=a(k)×100…0 100…0 1
≡a(k) mod 3
≡0 mod 3^k。
整数36
等比数列の和。因数分解。互いに素。
別解。mod p。 整数37
(1)aはmodbで逆元を持つ。ax≡1modbとする。
同一の素因数a,x,a+bからなる数列を構成する。s(n)=(a+b)(ax)^n。これらは与えられた等差数列に全て含まれる。
(2)全ての項がaとも互いに素となるような部分列を構成する。
別解。オイラーの定理を用いる。
(1)十分大きいnに対しては成り立つ。
(2)yiは問題の等差数列の項であるから、定めた数列は題意を満たす。
構成の仕方:yiの積を作る。オイラーの定理が使えるようにaの冪乗を作る。増加数列になるようにaの冪乗を作る。
すると全てのyiに対してyi≡a modbとできる。
整数38
(1)ユークリッドの互除法。
(2)指数のgcdを求めることに帰着される。重要。
別解。多項式の割り算→整数の割り算。互いに素。
(3)mが割り切ることを示す。mは2の約数であることと奇数であることによりm=1である。矛盾が導ける。
(4)ユークリッドの互除法。和が偶数の時gcdは12、和が奇数の時gcdは2。
整数39
(1)二進法。平面を2^0 x+2^1 y+2^2 z=0と定める。
(2)三進法。981。
(3)四進法。全ての桁は0または1。n=2^ a+2^0 bと置く。
どのように作ってもnには繰り上がりは生じない、
異なるai、biに対して作られたnは全て異なる。 >>85
分かりました。1日1題は「I MOの問題」にします。
それ以外は小問を進めさせてください。お願いします。 1959 IMO[1]
(21n+4, 14n+3)=(7n+1, 14n+3)=(7n+1, 1)=(0,1)=1。
よって分子と分母は互いに素なので、既約分数である。 整数40
(1)aは23!/13以外は13で割り切れる。
a=12!×23×22×21×…×14
≡12!×10×9×8×0…×1 mod13
=12!×10!=(12!)^2/11×12
≡(-1)^2/11×12 (ウィルソンの定理)
≡1/2≡7。
(2)((p-1)!)^2×m/nは整数である。{n^-1}≡{n}である。
ウィルソンの定理。互いに素。
(3)Σ(1/i +1/(p-1))。互いに素。
整数41
式の対称性。不等式で絞る。実際に調べる。
整数42
(1)最初の桁が1であるもの、23であるもの、4567であるものはそれぞれ603個ある。
1<x<2より、2<2x<4。4<4x<8。8<8x<16。
残りの195個は89である。この場合のみ最初の桁の数字が4となる。
別解。3個の要素からなる場合は12,35,67である。
4個の要素からなる場合は1,2,4,89である。
連立方程式が作れて、195個。
(2)ab=10に定まる。2^nと5^nの最初のk桁はどちらも√10の最初のk桁に一致する。 整数43
(1)9。mod4と7の関係。3。
(2)φ(1000)=1000×1/2 ×4/5=400。
オイラーの定理。逆元。二項定理。241。
(3)mod25。冪数計算。中国剰余定理。
9の倍数の見分け方。594。
別解。倍数の見分け方。9,11,7。
互いに素な分け方をしないと駄目。使えない。
(4)下一桁は2となることが必要。modの割り算。192。
整数44
既約剰余系。ウィルソンの定理。
全部の積が-1にならなければならない。
整数45
逆元。唯一性。問題44より、既約剰余系ではない。
問題45より、個数の最大値はp-2個である。 整数46
ak= n!/k!と置く。dはakの倍数。dはn!の約数。
次々に引いて行くと最後には0になる。
別解。帰納法。
整数47
nの最小の素因数をpとする。3^n≡-1 mod p
フェルマーの小定理。素因数pの最小性により
p-1とは互いに素。
整数48
格子点の個数に帰着させる。
互いに素とは限らない場合の数え方。
整数49
(1)d=ord(p,q)をmod pにおけるqの位数とする。
dは2rを割り切るがrを割り切らない。
フェルマーの小定理。
(2)フェルマーの小定理。フェルマー数。
ord(p,q)=2^(n+1)| p-1。
整数50
n=1〜6までを調べる。pを素数とする。
n=pの時。ウィルソンの定理。床関数。
n=p-1の時。ウィルソンの定理。床関数。
n, n+1の双方が合成数の時。互いに素。ルジャンドル関数により、偶数であることが分かる。
整数51
互いに素。一意性。m=8, p, 2p, 4p (pは奇素数)。
整数52
10の倍数の時は不適。
・n=2^k, 5^kの時。例題1.53。
・nが10と互いに素の時。オイラーの定理。
11111111(1をφ(9n )個並べたもの|n。
・n=a^s ×m (a=2, 5。gcd(m,10)=1)の時。
鳩の巣原理。 1959 IMO [2]
両辺を二乗する。
「√の中身は非負」に注意して変形する。
(1)1/2≦x≦1。
(2)解なし。
(3)x=3/2。 組合せ31
1990=79×25+15。この場合12列必要になる。
分断は高々9校である。
組合せ32
3816回桁数の増加がある。184回は桁数の増加が無い。
184。
組合せ33
総和が同じ時、最後の一つを除いた和は異なる。もし同じだと最後も同じになってしまうから。
ai=111111(n-1個)。n≦4と分かる。n= 1はOK。
n=2の時。m=1+2=3。
n=3の時。m=1+2+2=1+1+3。
n=4の時。m=1222, 1114, 1123, ■ このスレッドは過去ログ倉庫に格納されています