プロフィール

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年日本数学オリンピック予選 第6問

2014.02.19 15:11|数学
どもども。

今回は今年のJMO予選の第6問に挑戦です~

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



2つの黒板A,Bがあって数字を書き込んでいくらしいですよ~
書き込める数字は2~20の整数のうちの何個かで,1つの数字につき1回まで。
各数字ともどちらの黒板に書き込んでもよし。
全部の数字を書き込んでもいいし,一部だけ選んで書き込んでもいい。
ただし,黒板Aに書かれた数字 p と黒板Bに書かれた数字 q の組 (p,q) をどのように取ってきても
「p と q は互いに素」という関係性が成り立たなければいけませんよー
このとき,黒板Aに書き込まれた数字の数と黒板Bに書かれた数字の数の積は最大で幾つになるでしょうか
というお題なわけですー piman.gif


全部を書き込む必要はないという辺りが面倒さをかもしだしてますね~
書き込む個数で分類とかする必要が出てきそうです~

まずは具体例を考えてみましょう~。実験的考察です~。
例えば下図のような書き込み方をしてみると条件が満たされています hospital02.gif




l1_20140219111815703.jpg



2から20までの自然数たちを素因数分解したときに出現する素数たちは
2,3,5,7,11,13,17,19 なわけですね。
11,13,17,19の倍数は1個ずつしか含まれないのであまり気にする必要はないですが
2,3,5,7の倍数は複数存在します。

例えば黒板Aに「2」が書いてあったら,他の偶数が書き込めるのは黒板Aに限られます。
つまり,書き込む数字のうち偶数であるものは黒板A,Bのうちどちらか一方だけに集中するんですね~
これは3,5,7の倍数についても同様です~
したがって,書き込む数字の数が多いとかなりその書き込み方には制限を受けてしまうことが分かります~ pig01.gif

黒板AとBにそれぞれ書かれた数字の個数の積を考えるわけなので
それなりに多くの数字が書かれてたほうが多分いいはずなので
一番個数の多い場合,つまり全部の数字を書き込む場合から考察してみましょう~



全部を書き込むとしたら,2~18までの偶数は全てどちらか同じ側に書かれます~
3~18の3の倍数も全てどちらか同じ側に書かれます~
5~15の5の倍数,および7の倍数7,14も同様です~
このとき,偶数かつ3の倍数である「6」は偶数が含まれる側にも
3の倍数たちが含まれる側にも属してるわけだから,
結局偶数と3の倍数は全部同じ側に書かれていなければいけません。
偶数かつ5の倍数である「10」,偶数かつ7の倍数である「14」もあるので,
なんだかんだで偶数と3の倍数と5の倍数と7の倍数は全部同じ側に書かれているのです~ rajio05.gif

この時点で15個の数字が同じ側でもう確定してしまいました~
残っているのは11,13,17,19の4個ですが,
この子たちはどっちの側に含めても何も支障はありません~ hanaji01.gif
そんなわけで,個数の積は5通りしか無いんですね。


l2_201402191118152b6.jpg

  l3_201402191118167ea.jpg


ここまでのところでは,個数の積の最大値は60です。
これより大きくなることは果たしてあるのでしょうか。
次は18個の数字を書き込む場合について考えます~
1個だけ書かない数字があるというパターンですね。


(ア)で考えた書き込み方から何かしら1個の数字を消して出来るような書き込み方だと
個数の積は元の(ア)の状態だったときより小さくなるので最大にはなり得ません jitensya.gif
個数の積を大きくしたいんだから敢えて個数を減らす理由が無いですもんね。
したがって,そーいうパターンじゃないものに絞って考えれば十分なので
これでだいぶ手間が省けます~ s3_aut_momiji.gif

その「そーいうパターンじゃないもの」っていうのは,そんなに多くないです~
「偶数と3の倍数と5の倍数と7の倍数は全部同じ側に書かれている」もの以外のもの
ということなので,可能なのは「14」だけ書かずに「7」を解放させるものだけです~ kujira.gif


l10_20140219141055451.jpg
l8_20140219141056be2.jpg



おやおや,(ア)のときよりも個数の積が大きくなる65というのが出てきましたね。
現時点では暫定トップです。

次は17個の数字を書き込むパターンを調べてみましょう~
つまり書かない数字が2個あるというパターンです~

やはり(ア)で考えた書き込み方から2個の数字を消して出来るようなものは候補から外して構いません。
加えて,(イ)で考えたパターンから1個の数字を消して出来るようなものも対象外です~

そうでないものに絞って考えてみましょう~
そうすると,実はそんなものはないことに気づきます~kojika.gif
(注:はじめしばらくここミスってましたね。修正しました!すんません><)

l5_20140219111817bbb.jpg
l12_20140927085040d5a.jpg




ここまでの暫定トップは65です~

さて次は16個の数字を書き込む場合につて考える流れだとは思うのですが,
この調子で16個,15個,14個,… と続けていっても時間がかかりますね。
そろそろ65を越えるものは出てこないんじゃないかという予感もするので
書き込む数字の数が一般の k 個 (k≦16) の場合について考えてみましょう~ eto_hitsuji.gif

この k 個を, x 個と (k-x) 個に分けて
個数の積 x(k-x) を考えてみます。実は x(k-x)<65 という評価が出来ちゃいます。

このことから 65 が優勝ということが言えます~ ny_hatsuhinode.gif



l7_20140219111830e19.jpg












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

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

コメント

No title

数学オリンピックの問題に興味が出て、色々調べてたらこのサイトに出会いました。
問題の本質をとらえて、解説なさってるのでとても分かりやすいですね~!

記事を読んでいて気になったところがあったのでコメントさせていただきました。
「2014年日本数学オリンピック予選 第6問」にて、
17個の整数を使うパターンですが、グループAに20が入っていますので、
グループBに5が入れないのではないでしょうか。
17個のパターンは、単純に18個パターンにおいて、A、Bのいずれかから1個数字を消すしかなさそうです。
既にコメント・訂正等がありましたらゴメンなさい^^;

No title

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


あー!確かにそうですね!
ケアレスミスしてますね!
ご指摘ありがとうございます!
直ちに修正しておきます~
17個のパターンは18個または19個パターンで1つ数字消去を追加するしかなさそうですねー

こんな凡ミスがちょこちょこあるかもしれないので
見つけたら気兼ねなく教えて下さいませ~
非公開コメント

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