プロフィール

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ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2014年日本数学オリンピック予選 第7問

2014.02.20 15:06|数学
どもども。


今回は今年のJMO予選第7問を考えてみます~

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


場合の数の問題です~
4人の委員と4つの係があって1人1係を担当するということらしいのですが~
1人あたり希望する係が2つあって,全員が希望通りの係に就ける配属方法が2通りあるそうなのです~
このときの4人の希望のあり方が何通りかという問題ですねー kero.gif


4つの係をA,B,C,Dとし,4人の委員をa,b,c,dとしてみましょう~
条件を満たす希望のあり方というと例えば次のようなものとかがあります~



m1_20140220151120cd5.jpg




この下側の表し方を参考にして,4つの○(委員を表す)と4つの■(係を表す)を頂点と見立てた
頂点数8のグラフ
を考えてみたいと思います~ rabi_smile.gif

それぞれの○から2本の辺が伸びていて,伸びた先には必ずどこかしらの■があるものを想定するんですね。



m2_20140220005822403.jpg
m3_20140220005823026.jpg



隣り合う○と■をペアにして,うまい具合に4つの○と4つの■の1対1対応が2種類作れる
ようなグラフのパターンを考えます~ cutlet.gif

どういう点に気をつけて見付けてみたらいいんでしょうか~

1対1対応が完成するためには,まず第一に全ての■に対して
どれかしらの○から辺が伸びていないといけません。
孤立している■があってはいけないのです~

そして,ある■に対してそれと辺で繋がっている○が1個しかなかったとすると
この■とペアになる○はもう確定してしまいます~

また,同数の○と■を含むループ構造が出来ていると,
時計回り,反時計回りで2種類の1対1対応が作れます~


あとはあれこれ手を動かして色んなパターンを描いて考察していくのですが,
どうもループ構造が複数存在するような辺の引き方では①は満たせても②を同時には満たせません。
それではループ構造を持たないような辺の引き方は出来るかと検証してみると,
3個の○と4個の■の間にならループを含まない辺の引き方があるのですが
最後の○を加えるとどうしてもループが生じてしまいます dog_smile.gif



m5_20140220005824747.jpg
m6_20140220005824f85.jpg

  (↑注:①だけ満たすパターンならこの3パターン以外にもあります)


  
    m4_201402200058236d9.jpg



どうやら必ずループを1個だけ含むようなので,
そのループが○と■を何個ずつ含んでいるかで分類しながら
起こり得るパターンを列挙してみたいと思います~ s2_sum_sunflower.gif




m7_20140220005902265.jpg



パターンの分類ができたので,
それぞれについてA~D,a~dの当てはめ方を考えていきましょう~

図形の対称性などに注意しながら考えていってください~
当てはめ方の重複カウントをしないようにしましょう~ dog_love.gif


例えば(ア)は以下のようになります~
ループ内の2個の○は対等ですが,残りの○と■は全部対等ではありません。

m8_20140220005902559.jpg


(イ)以降も同様に数えていきます~ clover.gif




m9_20140220005903a1c.jpg


m10_201402200059042e2.jpg


m11_201402200059048b9.jpg


m12_20140220005905002.jpg






          k7_2014021721391021b.jpgk20.jpg









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

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

コメント

非公開コメント

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