プロフィール

mathnegi

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

カレンダー

07 | 2017/08 | 09
- - 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年日本数学オリンピック予選 第11問

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

いよいよ今年の日本数学オリンピック予選の問題も残すところあと2問です。
どちらもしんどいです~

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

問題はこちらから~箱ドットおにおんmini
http://www.imojp.org/challenge/old/jmo23yq.html

立方体がn^3個重なってるような状態の3次元空間内の格子を考えて
1つ1つの格子線分に向きをつけていくのだそうです。
格子内にある全ての格子正方形が合同になるような向き付の仕方の総数を求めてにゃんneko(1).gif
というハードなことを要求しています~


幸いにも,解答欄には答えの数値だけ書けばいいので
途中の検証をすっ飛ばして直感に頼って答えを出していくことが許されるのですが
きちんと議論しようとすればとっても大変ですよコレbuta.gif
まぁ部分点が入らないという事で言えば,
答えの数値だけ書くシステムは残酷でもありますが~

それでは地道な検証を重ねながら答えを求めていきたいと思います~



まず物凄い基本的なこととして,各辺が向きを持った格子正方形は
合同なものは同一視することにすると,一体何種類あるんでしょうかcar2_tank.gif

一番わかり易いのは格子正方形ABCDに対して
(A→B→C→D→A) のように渦を巻いているパターンですね~

あとはこの渦の和を乱してる辺がいくつあるかで分類できます。
1辺だけ和を乱しているものが1種類,
2辺が和を乱しているものが2種類あります。

r1_20130125015933.jpg

空間内の回転と平行移動で重なるものが合同の定義とされています。
平面上での回転だけではなくて空間上での回転も許されます。
つまり,表裏をひっくり返すと重なるようなもの(鏡像になってるようなもの)も
同じものとみなされてしまいます~cat_1.gif


r2_20130125015933.jpg



いきなり一般のnで考えるとなかなか難しいので,
まずはn=1の場合について考えてみたいと思います~
すなわち1つの立方体の向き付けですね~
n=1の場合だけでも結構難しいですよ~dog_angry.gif


まずは各面がタイプ①のものと合同になっている場合が何通りあるか考えてみます。

実は,全ての面が綺麗に渦を巻いているようにしようとすると
どうしても流れの向きが一意に定まらない辺が出てきてしまいます。
よって,各面がタイプ①という事象は起きません。

下の図では辺DHの向きは(D→H)とも(D←H)とも定まりません。

r3_20130125015934.jpg


続いて各面がタイプ②の場合を考えてみます~
こいつが一番厄介で複雑なんですよね~
逆にそれ以外の場合は簡単なので,頑張ってこのパターンを乗り切りましょう~dolphin.gif


まず,基本考察として,隣り合う面との関係性について調べてみます。

1直線上に連続する3格子点P,Q,Rがこの順に並んでいるとき
(P→Q→R)または(P←Q←R)の向き付けがされている時
PQR間は同向であると呼ぶことにしますよー。
(P→Q←R)または(P←Q→R)の向き付けがされている時
PQR間は異向であると呼ぶことにしますよー。



下の図のように2つの格子正方形が隣り合っていて,
(B→A)の向き付けだけがされていると仮定しましょう~
この2つの格子正方形が共にタイプ②のものになるように
他の辺の向き付けをしてみます~drink_juice.gif


r4_20130125015934.jpg

r5_20130125015935.jpg

正方形ABCDについて,和を乱している辺の選択が4通り,
正方形CDEFについて,和を乱している辺の選択が4通りですので
選択のペアは16通りあります。
どのペアに対してもうまく向き付けができるとすれば,
それは各ペアにつき1通りずつで,
計16パターン存在することになります。


同様に,(A→B)の向きが付いているものも16パターンあるとすれば
全部で32パターンが存在することになります。
ちなみに,実際32パターン全部起こり得ます~eto_i.gif


とりあえずは(B→A)の向きを仮定しているので,
まずはADE間とBCF間が共に同向になっているものを考えてみると
これは以下の4パターンがあります~

ADE間とBCF間の向き付けを与えてしまうと残り2辺の向きは決まってしまいますeto_tatsu.gif


r6_20130125015935.jpg

4パターンとも辺ABとEFは上向きになっていることを覚えておいてください~gp08.gif

次はADE間とBCF間が共に異向になっているものを考えます。
やはり4パターンあります。
またまた辺ABとEFは常に上向きになっていることを確認してください~gp11.gif


r7_20130125020005.jpg


一方,(A→B)の向きが付いているときは,ADE間とBCF間が共に同向または共に異向
であるものは上記の8パターンをいじくれば全部出てきます



r8_20130125020005.jpg

正確には名称を入れ替えた後に表裏をひっくり返さなきゃいけないですが
それはただの合同変換なので特にこだわる必要はないです~


次はADE間は同向,BCF間は異向の場合を考えてみましょう~
(B→A)の向きがついたものは4パターンあります~
どれも(E→F)の向きになっていることに注目です~hiyo_ang2.gif


r9_20130125020006.jpg

(A→B)の向きがついたものも上にあるように4パターンなんですね~

ADE間は異向,BCF間が同向であるものは今得られた8パターンにおいて
頂点の入れ替えをすればやはり全部出てきます。

r10_20130125020006.jpg


これで32パターン全てが出てきました~
そしてこれらに関して言えることを以下にまとめてあります~kaeru_en1.gif


r11_20130125020007.jpg

要するに,右端と左端の辺(ABとEF)の向きが,同じ方向か逆向きかによって
ADE間とBCF間の関係性(同向か異向か)がある程度決まってしまうということです~kaeru_en2.gif


例えば,(A→B),(E→F)の向きがついていれば
ADE間とBCF間は,共に同向かまたは共に異向かのどちらかに限られることがわかります~


これを踏まえて,立方体の各辺の向き付けを考えていきます~

r12_20130125020009.jpg

正面の4辺を決めた後に左隣りの正方形の残り3辺,次に上面・下面の残り2辺,
そして最後にGHを決めるという手順です~

r13_20130125020035.jpg

辺ABの向き,正方形ABCDの4辺の中で和を乱してる辺,
正方形ABFEの4辺の中で和を乱している辺。
この3つの選択が計2×4×4=32通りあります。
これで作られる32パターンというのは,さっき求めた32パターンのことですね~kojika.gif


次に上面と下面を見てみますが,
辺EFと辺CDに付けられた向きが同じか逆かによって
EAD間とFBC間の向き付け方が変わってきます~
ただ,以下に示すように,どのようなパターンになっていたとしても
EAD間とFBC間の向き付け方は2×2=4通りあることが分かります~ladybug.gif
そしてGHは自動的に向きが決まってしまいます~


r14_20130125020036.jpg
r15_20130125020036.jpg


というわけで,タイプ①の場合のように,向き付けに不備が生じるという事は
ないようですね。これで各面がタイプ②型になっているものの総数が分かります~

r16_20130125020037.jpg


次は各面がタイプ③になっている場合です~
これは割と簡単ですよ~

辺AB,BC,AEの向きを決めてしまえば残りの辺の向きが全部決まってしまうからです~m_0243.gif
そしてどのように向きを決めても何も不合理は起こりません~

r17_20130125020037.jpg


最後は各面がタイプ④になっている場合です~
これは下の図の2パターンしかありません~

以上より,今まで出てきたものを全て足せばn=1の場合の
格子線分の向き付け方の総数になります~panda_1.gif



r18_20130125020038.jpg


n=1の場合だけでもかなり疲れましたね
しかもこれを一般のnの場合で求めろって言うんだから
なんとも鬼畜です~rabi_angry.gif
先はまだ長そうですね~~

怖いのはあくまで各面がタイプ②になってる場合です~
しかしながら,n=1のところでしっかり考察を加えておいたおかげで
n≧2の場合はだいぶ楽に計算できそうです~~tanuki.gif


一気にいきなり一般のnにするのも分かりづらかろうと思うので
要領をつかむためにn=2の場合を考察してみます~tankoro.gif


各面がタイプ①型になっているものは当然ありません~

というわけで各面がタイプ②になっているものを考えていきます~
まずは隣り合う立方体との関係性について考察してみましょう~teng.gif

既に各辺が向き付けされた立方体の隣に新しい立方体を置きます。

r19.jpg

立方体CDHGKLIJは初期段階で既に1面がどの辺も向き付けられています~
正面の正方形DCKLの残り3辺の向きを決めてしまいましょう。
DCの向きは決まっているので,あとはどの辺が和を乱しているかを選ぶだけで
向き付けは決まってしまいます~dog04.gif
どれを選んでも不都合は生じません~
したがって4通りありますね。

次に上面・下面のそれぞれ残り2辺の向きを考えます。
これはn=1のときと,もはや変わらないですね。

HIL間が2通り,GJK間が2通りです。
ついでにIJの向き付けは1通りです。

r20.jpg

n=2では2×2×2=8個の立方体が重なってるような状態になっています。
上段の4個について考えてみましょう~kujira.gif


r21.jpg


1番の向き付けが決まると2番と3番の向き付け方は
さっき見たようにそれぞれ16通りです15927445.gif

残るは4番の立方体ですが,2面が既に決まってしまっていますね~
残り5辺ありますが,これの決め方もn=1のときと同じです~
上面・下面の決め方はそれぞれ2通りですね~
残りの1辺は自動的に向きが決まります。

r22.jpg

さて上段4個が決まればあとは下段4個ですね15927443.gif


r23.jpg

5番の決め方は,2番3番と同様で16通りです~
6番7番は4番と一緒で4通り~

残るは8番ですが,初期段階で3面決まっています~
下面の向き付け方が2通りあって残りの1辺が1通りです~

以上をまとめるとn=2のときの各面がタイプ②になってるものの総数が出てきますね15927440.gif


r24.jpg



次は各面がタイプ③のものです~
これは図にある6辺の向きを決めてしまえば残りが全部決まってしまいます~
この6辺の向きは自由に決めていいです。何も不都合は起きません。

r25.jpg


各面がタイプ④のものは2通りです~

さあ,これでn=2のときの全体の向き付けパターン総数が出てきます15901723.gif


r26.jpg


n=2の時点で物凄い数ですね~~

いよいよ一般のnの場合をやっつけます~
n=2の場合を見たことでだいぶ要領は掴んできたはずです~

タイプ①のものはやっぱり存在しないのでタイプ②のものから考えましょう~

上段のn^2個の立方体をまず相手にします。
一番左下 → それの右1列と奥1列 → 残りの立方体の中で一番左下
→ それの右1列と奥1列 → 残りの立方体の中で一番左下
→ ……

の順番に見ていきますよ~

ここまでの考察でわかると思いますが

既に1面が決まっている立方体の向き付け方は16通り
既に2面が決まっている立方体の向き付け方は4通り
既に3面が決まっている立方体の向き付け方は2通り


あるのであとは機械的に数えていくことができます~~15901731.gif


r27.jpg

r28.jpg

では次は上から2段目を考えてみましょう~
やはり何面が決まっているかに着目して機械的に計算できてしまいます~

それが分かれば残りの段も同様です~16054011.gif


r29.jpg


各面がタイプ③のものは図の3n個の辺の向きを決めちゃえば全て決定されます。
また,タイプ④のものは2通りです~


r30.jpg


実に長かったですが,
何とか答えまで辿り着くことが出来ました~

お疲れ様でした~~~~8261165.gif






  






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

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

タグ:2013 日本数学オリンピック 予選 個数の処理 格子線分 格子正方形 格子点

コメント

非公開コメント

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