数学オリンピック事典を一日一問以上解くスレ
■ このスレッドは過去ログ倉庫に格納されています
整数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, 組合せ34
Sの元の個数は5以下である。4個以下とすると和は56。鳩の巣原理。{15,14,13,11,8}とする。61。
組合せ35
帰納法。全て0004状態に帰着させられる。
一つ特別扱いをする。アルゴリズム。
組合せ36
帰納法。2のべきとそれ以外に場合分け。構成する。 組合せ37
前と異なるように塗っていき、最後は題意を満たせばOKで、満たさなければ一個少ないものの題意を満たす。
531444。
組合せ38
奇数人と仮定して矛盾を導く。
別解。背理法無しでも行ける。
組合せ39
実際に調べると、90通り。 組合せ40
一番下以外は題意を満たしていると仮定する。帰納法みたいなもの。2^(n+1)-2。
組合せ41
2のべきなら可能。64はOK。
組合せ42
L以外の数の総和Sを考える。Sは操作回数の減少関数である。これを無限回繰り返すことはできない。 組合せ43
書かれた数の和をmとする。2^m -1。
組合せ44
帰納法。場合分け。裏返しの回数は奇数回であることが必要だが、実際には偶数回なので矛盾。
組合せ45
交代和。n×2^(n-1)。448。 組合せ46
広義単調減少数列。必要条件かつ十分条件でもある。
12C5=11×9×8=792。
組合せ47
偶奇性。R(odd)+C(even)-2S(B)は偶数。
組合せ48
周期性。905。ブロック分けの正当性。 組合せ49
14!×15!(2^15-1)。
組合せ50
背理法。偶奇性。
組合せ51
握手の回数関数を定義する。これは減少回数となる。いつかは0に到達する。 整数
1
(1)mod3で2なので平方数にならない。
mod4で2なので平方数にならない。
mod4で2または 3なので平方数にならない。
mod4で3なので平方数にならない。
平方数はmod3で0,1。mod4で0,1。
(2)n^2≡1より、絞れる。当てはめる。
2
等号が成立するので最良である。繰り上がり。
有界でない例を作る。
3
n=2^kと表せる。3以上の奇数を因数に持たない。 整数
4
合成数の個数と素数の個数を求める。鳩の巣原理。6個自力で作れれば良い。
5
mod4で考える。
6
背理法。
別解。mod16で考える。表を作って見てみると平方数に成り得ない部分が出来る。 幾何
1
加法定理。
2
対称性から大小関係を設定して進める。因数分解。チェビシェフの不等式。問題27(2)。
別解。並べ替えの不等式。
3
問題20(1)。問題28(3)。
問題19(1)。問題20(2)。
4
積和変換。
5
相加相乗平均の不等式。問題24(4)。
6
全単射。解と係数の関係。 幾何
7
正弦定理。問題42(1)。
8
ドモアブルの公式。二項定理。
9
通分。加法定理。三角関数の合成。相加相乗平均の不等式。微分法では困難。
10
半角の公式。
11
背理法。加法定理。
12
二倍角の公式。全単射。区間の分割。鳩の巣原理。
13
恒等式を用いる。
14
二倍角の公式。単位円を描いて考える。
15
問題27(1)。和積変換。
16
題意を満たす三角形を描く。三角不等式。正弦定理。
17
置き換え。コーシー・シュワルツの不等式。
18
三角関数の変形。差の形に分解できる。
別解。複素数を用いると自然に解ける。
19
問題21。シューアの不等式。
20
平方完成。周期性。同値変形。個数を求める。 幾何
21
正弦定理。チェバの定理。和積変換。
整数
7
667, 667,666に分ける。一回で終わる。
8
全て奇素数である。構成する。
別解。mod3で考える。
9
背理法。2の冪を考える常套手段。
10
互いに素。相加相乗平均の不等式。
11
偶数と奇数で場合分け。
別解。より一般的に。連続する平方数の差は一次関数的に増加する。偶奇性。
12
因数分解。合成数。存在する。
別解。上手く置ければ一発。
13
帰納法。
14
背理法。modaで考える。完全剰余系。
別解。命題を同値な他の命題に変えると簡単に解ける。ベズーの恒等式。
15
三角不等式。mod10^4をmod2^4とmod5^4に分けて考える常套手段。二項定理。
16
背理法。最大の数を設定する。最小の数を設定するパターンが多い。矛盾を導く。必勝戦略。
17
一並び問題。どんな「互いに素数列」にも一項付け加えられる。
別解。(10^n - 1)/9 と見做す常套手段。gcd。
18
オイラー関数。オイラーの定理。素数ではないことが示される。
19
mは4乗数。約数の個数。これが奇数なのでmは奇数。ベルヌーイの不等式。
20
「各桁の和」問題。等差数列。場合分け。背理法。 整数
21
三乗根を整数で評価する。背理法。不等式評価。
組合せ
1
リーグ戦。得点と試合数の関係。
2
計算する。場合分け。置換の個数。
3
区別出来る球を区別出来ない箱に入れるパターン。組合せ。
4
入れ替え。加える。広義単調増加。上手く選べば良い。場合分け。置き換え。例として667,667,667がある。
5
背理法。最小のものを文字でおく常套手段。偶奇性。場合分け。
別解。行列を使うと一般化が可能。
6
余りで置き換えておく。
7
条件を順番に使っていくと絞れる。場合分け。
別解。二進法を用いる。フィボナッチ数列になる。
8
m≧4を示す。m= 4で成り立つ事を示す。
9
偶奇性。両端を取り替える。帰納法。
別解。グラフを用いる。対応を考える。線分の本数。完全グラフは一筆書き可能。オイラー周遊。グラフ理論。
10
母関数みたいなものを考える。複素数の利用。5乗根。 幾何
22
漸化式。2倍角の公式。半角の公式。帰納法。
23
加法定理。3倍角の公式。
24
多項式を設定する。一意性の証明。具体的に構成する。チェビシェフ多項式。
25
正弦定理。問題25(4)。和積変換。積和変換。2倍角の公式。正値性。
26
垂線の足。問題27(2)。射影。
27
場合分け。加法定理。二乗する。2倍角の公式。和積変換。積和変換。加法定理。二乗する。2倍角の公式。積和変換。
28
正弦定理。半角の公式。オイラーの公式。二乗する。加法定理。
別解。垂線の足。垂直二等分線。二等辺三角形。問題27。
29 幾何
29
問題18。積和変換。
30
対称性。問題19(1)。連立。文字消去。半角の公式。
31
積和変換。2倍角の公式。巡回的に入れ替える。シューアの不等式。
32
和積変換。単調増加関数。シューアの不等式。
別解。加法定理。和積変換。単調増加関数。単調減少関数。3つを足す。
33
チェビシェフ多項式。問題49。ラグランジュの補間公式。
34
冪平均不等式。
35
置き換え。コーシー・シュワルツの不等式。
36
相加相乗平均の不等式。
37
三角関数を利用する置き換えが可能である。問題21。正弦定理。三平方の定理。
38
冪平均不等式。足し合わせる。冪平均不等式。足し合わせる。
39
イェンセンの不等式。1番目の不等式の方が成立する。
40
1のn乗根。チェビシェフ多項式。最小多項式。平方数。問題49(6)。 幾何
41
鋭角三角形。垂線の足。問題26。射影。全部加える。正弦定理。
補題。巡回的な和に関する等式。2倍角の公式。加法定理。
42
(1)(2)に帰着される。
(2)移項する。平方完成。場合分け。偶奇。対称性。
別解。2次方程式。判別式。
(3)正弦定理。2倍角の公式。(2)に帰着される。
(4)問題25(1)。平方根。2倍角の公式。正弦定理。余弦定理。
43
この等式はある不等式の等号成立条件として得られる。内接円。展開する。加法定理。2つ足す。加法定理。
別解。余弦定理。辺々足す。平方完成。加法定理。積和変換。2倍角の公式。イェンセンの不等式。2倍角の公式。
別解。補題。相似になるように取る。トレミーの定理。相似。相加相乗平均の不等式。
44
問題22。相加相乗平均の不等式。和積変換。積和変換。2倍角の公式。
別解。問題24(4)。一般性を失うことなく条件を強められる。2倍角の公式。積和変換。2倍角の公式。積和変換。等号成立条件。
別解。2次方程式。解の公式。
45
加法定理。コーシー・シュワルツの不等式。
46
三角関数と逆三角関数で√x→√(x+1)を作れる。
x→ 1/xも同様に作れる。帰納法。
47
同値変形。二乗する。極限の議論を用いる。相加相乗平均の不等式。
48
和積変換。巡回的な和。問題24(1)。
別解。正弦定理。補題。垂線の足。円に内接。相似。2倍角の公式。和積変換。
別解。正弦定理。
49
補題。回転。正弦定理。垂線。単調減少関数。加法定理。単調増加関数。加法定理。
50
問題24(4)。重み付き相加相乗平均の不等式。問題28(1)。巡回的に入れ替えた式。
別解。問題42(1)。問題42(2)。
別解。補題。置き換え。並べ替えの不等式。
問題28(1)。
51
補題。和分。補題。アーベルの不等式。補題。積和変換。周期関数。凸性。 整数
22
強化帰納法。オイラーの定理。あるcが存在して、十分大きなiに対してai≡c modφnが成り立つ。中国剰余定理。
23
代入する。帰納法。ユークリッドの互除法。
24
恒等式を用意する。有理数に拡張出来る。
25
(1)小数部分の議論。狭義単調減少関数。
(2)立方数を1〜5まで用意する。
26
フェルマー数。問題49(2)。
27
ブロック分割。漸化式。
28
帰納法。
29
背理法。素数が無限にあることの証明と同じ。
30
帰納法。不等式。偶奇性。場合分け。
31
合同式の冪乗根。オイラー関数。
32
連立方程式。ピタゴラス数。フェルマーの小定理。p-1の倍数は条件を満たす。 整数
33
dとi/dの関係。平方数の逆数和。Σ1/n^2=π^2/6< 2。
34
二式を足し両辺に1を加える。mod19。フェルマーの小定理。表を作って一覧する。
別解。mod13。立方数。
35
三進法。三回で済む。
36
2次方程式。解の公式。帰納的に。
37
実例を構成する。四進法。39(3)。
38
直接扱わず、mod2で考える。それで矛盾が生じる。
39
恒等式。4が作れるので、小さい数に関して具体的に示せればある値以上では「+ 4」によりそれ以降永久に成り立つことが示せる。
40
最大値の定義。具体的に調べる。帰納法。
別解。mod6で場合分け。エルミートの恒等式。
41
例題1.74(1)。
42
(1)帰納法。場合分け。最小公倍数。
(2)より強い不等式が示せる。その方が簡単。 整数
43
余りの合計。2の冪乗。
44
(1)10,25の倍数。ユークリッドの互除法。オイラーの定理。九並び。2の冪乗。帰納法。 2の冪乗×奇数。10と互いに素。
(2) 20の倍数。2の冪乗。5の冪乗。帰納法。オイラーの定理。
45
帰納法。p進法。等差数列。
46
a^ 3を割り切るが、aは割り切らない数。因数分解。3で何回割り切れるか。帰納法。
47
巡回的かつ対称的。
(1)背理法。フェルマーの小定理。互いに素。
(2)問題49(1)を繰り返し適用する。
48
帰納法。問題 38(3)。
別解。帰納法。最小公倍数。
別解。帰納法。互いに素。
49
奇素数。漸化式。modp。
50
上界についての不等式。下界についての不等式。
51
素因数分解。強化帰納法。
別解。解を見つける。
52
フェルマー数。素因数分解。問題49。二項定理。 2の冪乗。 ■ このスレッドは過去ログ倉庫に格納されています