プロフィール

mathnegi

Author:mathnegi
ゆる~い人間です(*´ヮ`*)
宮城県在住~

カレンダー

09 | 2017/10 | 11
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 - - - -

最新記事

全記事リスト

全ての記事を表示する

最新コメント

月別アーカイブ

カテゴリ

閲覧者数

検索フォーム

RSSリンクの表示

リンク

ブロとも申請フォーム

この人とブロともになる

QRコード

QR

電卓だよん♪

電 卓

お問い合わせはこちらまで~♪

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

受験ブログ 大学受験(指導・勉強法)へ

スポンサーサイト

--.--.-- --:--|スポンサー広告
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2013年日本数学オリンピック予選 第10問

2013.01.29 00:00|数学
どもども。

今回はこの間の日本数学オリンピック予選の第10問をやりますよ~
残り3問になりましたね~
今回のもめっさしんどいです~
骨の折れる解法になってしまったので,恐らくもっと見事な解法があるのでしょうねbakezouri.gif


何かミスがあったら教えて下さいね~

問題はこちらから~くりmini
http://www.imojp.org/challenge/old/jmo23yq.html


第9問に続いての2013絡みの問題です~
2012絡みでもありますね~

そして,ややこしい事態を引き起こしそうなガウス記号が出てきてます~
嫌な予感がしますね~

操作1から操作2013までのよく分からない操作をするんだそうです~
各操作につき条件に該当するカードをひっくり返していきます~
操作が進むにつれて,各カードが表になったり裏になったりを繰り返すわけですね~
最終的に表向きになってるカードは何枚ありますか~~ということを聞いていますeto_ushi.gif


何だかよく分からないので
具体的に操作3くらいまで見てみましょうか。

q1_20130123202653.jpg

操作1では [2013×0/1]=0 より,0のカードだけが裏から表になります

q2_20130123202654.jpg

操作2では0と1006のカードがひっくり返ります。
0のカードは再び裏向きに戻ってしまいますね。

操作3では0,671,1342の3枚がひっくり返ります~
0は再び表向きになります~
操作2でひっくり返った1006のカードはここでは変化ありません。

この要領でどんどん操作が進んでいくというわけですね~m_0030.gif
0のカードは毎回ひっくり返されるようですね~
2013回ひっくり返されると最終的には表になっていますね。

カードごとにひっくり返される回数は変わってきます。
kのカードがひっくり返される回数を N(k) とおきましょう。
N(k) が奇数になるkの数が,最終的に表になっているカードの枚数ですm_0054.gif


今回は N(k)を実際に求めて,それが奇数になるkの数を数えてみたいと思います~


N(k) は, [2013×j/i]=k を満たす(i,j)の組の個数に等しいです。
[2013×j/i]=k であるとは, 2013×j/i=k+r (0≦r<1)の形で
書けるということです。
すなわち j=(k+r)i/2013 と書けるということです。

xy平面を考え,(i,j)をこの平面上の格子点(x座標,y座標が共に整数である点)に
対応させてみますね~m_0049.gif

[2013×j/i]=k を満たす(i,j)の数N(k)というのは,

(k/2013)x≦y<{(k+1)/2013}x 
かつ 1≦x≦2013 かつ 0≦y≦x-1


が表す領域上にある格子点の数だと思うことができますm_0100.gif


q3_20130123202654.jpg
q4_20130123202655.jpg
q5_20130123202655.jpg

上の図の斜線部分にある格子点の数を数えればいいわけですね~m_0151.gif
AD上の点は数えないので注意です。
k=2012の時は y=(k+1)x/2013=x となり,
y=x-1と平行になってしまうので図が特殊です。
一応,あとで別に取り扱うことにしますね~


さて,多角形とその上の格子点…
と聞いてピンとくる定理があります。
ピックの定理です~~zashiki.gif


なんぞや?と申しますと以下のようなものです~

q6_20130123202656.jpg

頂点が全て格子点だったら,内部と周上の格子点の数を数えるだけで面積が分かるという
とても面白い定理なんです~aicon156.gif

この定理を少し発想を変えて使うと,
面積と周上の格子点数が分かっている多角形の,
内部の格子点数を求めることが出来ますね~

その発想を取り入れてみます~aicon343.gif



C(2013,k),D(2013,k+1)は格子点ですがA,Bは一般には
格子点ではありません。代わりに△OCDを考えます。
これは3頂点とも格子点ですし,面積も容易に出せます。
△OCDにピックの定理を適用して,その結果を四角形ABCDに反映させますよー


まず△OABに着目してみましょう~
この三角形は2直線 y=x-1,y=x で囲まれた帯状領域上に
あるのが分かりますか?
そのため,△OABの内部には格子点はありません
周上だと原点は確定ですが,それ以外はもしあるとすればAB上です~

q7_20130129032405.jpg


したがって,
(△OCDの内部の格子点数)=(四角形ABCD内部の格子点数)+(線分AB上の端点以外の格子点数)
が成り立ちます~

また,CD=1なのでCD上の格子点はC,Dのみです~
よって△OCDの内部の格子点数にBC上の格子点数を加えれば,
ちょうどN(k)になりますね~aicon_bbs17.gif


(OC上の格子点の数)=(BC上の格子点数)+1
(OD上の格子点の数)=(AD上の格子点数)+1

が成り立ちます。「+1」は原点の分ですよー

2013とkの最大公約数をg_1,2013とk+1の最大公約数をg_2とおくと,
BC上の格子点数はg_1個,AD上の格子点数はg_2個になります


これらを踏まえてN(k)を求めてみましょーaomushi02.gif



q8_20130123202722.jpg
q9_20130123202723_201504121144451f6.jpg

q10_20130123202723.jpg


これは,一旦置いておいたk=2012の場合にも成り立ちます~bear.gif


q11_20130129033022.jpg




さて,次はN(k)が奇数になるkの個数を数えなければいけません。
N(k)が奇数になることは, g_1-g_2 が4の倍数になることと同値ですkinkan.gif


q12_20130123202724.jpg

g_1,g_2は2013の約数なので, 1,3,11,33,61,183,671,2013 の
いずれかですね~。 mod 4で考えると

1≡1
3≡3
11≡3
33≡1
61≡1
183≡3
671≡3
2013≡1


になっています。どれも1か3と合同ですね~
g_1-g_2≡0 となるのは, g_1≡g_2≡1 または g_1≡g_2≡3
となる時であることが分かります08.gif


そのような(g_1,g_2)の組み合わせは(1,33)や(671,3)など
たくさんあって考察が大変ですー

考察を楽にする工夫を考えましょー10(1).gif


各約数を4で割った余りが上の方に列挙した合同式の右辺に並んでいます。
1,3,3,1,1,3,3,1
「1,3,3,1」の塊が2つ並んでいる,この周期性に着目してください~
後半の方は, 61×1,61×3,61×11,61×33 を4で割った余りです。

≡61× (mod 4)

になっています。これは 61≡1 であるせいですね~8190575.gif
mod 4 で考えると61という素因数は無視が出来るということが分かりますが
これはつまり,2013=61×33の61を無視して,
33とkの最大公約数をG_1,33とk+1の最大公約数をG_2とおくと
g_1≡G_1 と g_2≡G_2 が成り立つということです。
よって, G_1-G_2≡0 (mod 4)
となるkを数えればいいとい話に置き換えることができます~Mushroom01.gif


q13.jpg


また,33と 33m+ℓ の形の整数との最大公約数は
33と ℓ との最大公約数と等しいです。
これは, G_1-G_2 を4で割った時の余りをR_kとおくと
数列{R_k}は周期33の周期数列になっていることを意味します~8257410.gif



q14.jpg


ということは R_0,R_1,…,R_32 までに R_k=0 を満たすkが
M個あるとすれば,R_2012までには61M個あるということになりますよね
この61MがN(k)を奇数にするkの数,すなわち最終的に表向きになっているカードの枚数です~bye03.gif



q15.jpg
q16.jpg






    
関連記事
スポンサーサイト

テーマ:算数・数学の学習
ジャンル:学校・教育

タグ:2013 日本数学オリンピック 予選 ピックの定理 ガウス記号 格子点

コメント

管理人のみ閲覧できます

このコメントは管理人のみ閲覧できます

No title

コメントありがとうございます~

確かにk=0のところは若干の具合悪さがありますね。
というわけでひとこと触れておくことにしました~

気掛かりな点を見つけたらまた教えてください~
非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。