難問
さて、今日職場で３年以上一緒に仕事してるのに名前をど忘れされたおねーちゃんと、一緒に考えてて答えが出なかった難問です。
助けて偉い人！
てことで、興味をそそる為に、イキナリ図を張りますが、とりあえずこの図を眺めてみてくだされ。
１．同じ大きさの小さい四角形を任意のＮ列×Ｍ行に並べて大きい四角を作ります。
（図の黒い直線で作られた四角形）
２．大きい四角の任意の一隅から小さい四角形の対角線に向けて直線を引き、その延長が大きい四角形の一辺に到達した時点で折り返し、常に小さい四角形の対角線を通るように線を引いて行きます。
（図の赤い線）
こうして描かれる図形に対して、
１）赤い線が全ての小四角形を通る際のＮ、Ｍの条件を示し、そのことを証明する
２）任意のＮ、Ｍに対して、赤い線が何本の直線になるかを計算する計算式を算出する
という二つの問題を考えたワケですが・・・。
考えたけど解けません・・・orz
１）に関しては条件はなーんとなく直感的に判ったんですが、その証明が出来ない。
２）に関してはなーんか判るようで全然正解に至れない。
とゆー状況で残業時間に無駄に２時間近く悩んでしまいました（笑）
てことで、もう暫く自分でも考えて見ますが、我こそは！って猛者、この問題解いてみません？
トラックバック URL :
折り返す＝鏡に反射する、というイメージで考えてみたらどうかな？
大きい四角形の辺を鏡だと捕らえ、45度に発した光が鏡に囲まれた長方形の中をぐるぐる動き回るんでしょ？
そのとき、鏡にうつった先を考えて、絵を拡張していけば、赤い線は直線になる。その直線の長さが、小さい四角の個数分になるための条件は？と考える。
うーん、うまく説明できないけど、そんな感じで絵を書いて説明するとすればどうかねぇ？
もうすこし自分で考えてみませんか？
答えとしては、１）は「ｎとｍが互いに素であること」
２）は「n+m-1」でどうかな？
何本の直線になるかは、何回反射するか、に置き換えてもいいんだよね？
コメント by しょうた — 2006/12/8 Fri @ 1:43:23
あ、ごめん
２）任意のＮ、Ｍに対して、線Ｎが何本の直線になるかを計算する計算式を算出する
この線Nって言うのが定義されてないような気がしたけど、勝手に赤い線の本数と判断しました。あってる？
コメント by しょうた — 2006/12/8 Fri @ 1:46:47
あーだめ。
ソロバンでやるような算数は得意だけど数学はダメｗ
といいつつ実は中学入試レベルの問題を小難しくデザインしなおしただけだったりするんだよなぁ、こーゆーのってｗ
コメント by ぺけの — 2006/12/8 Fri @ 1:54:38
けさ、寝起きで夢の中で？思いついた追加問題。
３）直線を左上隅から右下に引き始めたとき、
a)右下
b）左下
c)右上
の各隅に直線が到達する条件を求めよ！
コメント by しょうた — 2006/12/8 Fri @ 10:48:55
２）に関してですが、NとMが互いに素となる場合は、「線の数 = N + M - 1」で成り立つ気がしますけど、NとMが公約数を持つ場合は、成り立たないです。
（N = 2、M = 6の場合、線の数は3本）
やっぱり、公約数を持つ場合と持たない場合で、分けて考えないとだめなんですかね。。。
コメント by うさぽん — 2006/12/8 Fri @ 10:59:36
２）だけど、とりあえず
M>=Nとして、
・M/Nが整数の時、その整数
・M/Nが整数でない時、N+M-1
かな？
ちょっと証明してきます。
コメント by monmon — 2006/12/8 Fri @ 22:56:35
＞うさぽんさん
おおっと、まさにおっしゃるとおりですね。
すみません、問題をかってに取り違えて、
１）が成立したときの本数だけ数えてました。
で、考えていく際に場合わけは必要で、その考えていくときのヒントが、僕の提示した３）がそのひとつの考え方にならないですかね？
（１，３，２の順に出題されると難易度が下がるということ）
手元で証明もすみましたが、答えとしては、
NとMの最大公約数をPとするとき、求める本数は、N/P＋M/P-１
となります。
互いに素の時は、P＝１ですから、N+M-1になりますし、
monmonさんのおっしゃるようにM>=Nで、NとMの最大公約数がNのときはM/Nになります。
また、1以外の最大公約数が存在するがN自身じゃない、という場合もこの式で表せますね。
コメント by しょうた — 2006/12/9 Sat @ 10:30:56
＞しょうたさん
あー、線Ｎってミスですな・・・「赤い線」に直しておきました。
で、やっぱりあっさり解いちゃったのね・・・orz
週末アレだったのであんまりその後考えてないんですが、やっぱり１）の証明がさっぱり判らずｗ
赤い線を直線に置き換えたモデルってのも、ちょっと考えてみたんですが、赤い線の終了条件を上手く数式に起こせなくて・・・（汗）
そのヒントが問題３）に隠れてる気もしますがｗｗ
まぁ、もうちょっと考えてみます。
コメント by にこ — 2006/12/11 Mon @ 11:27:20
＞まぁ、もうちょっと考えてみます。
で、考えてみた。
とりあえず、赤い線が通過する小四角形の個数がＮとＭの最小公倍数になるので、
最小公倍数＝Ｎ×Ｍになる→ＮとＭが互いに素
ってトコまでは判った。
だけど、証明って話になると、赤い線が通過する小四角形の個数が最小公倍数ってのも証明しなきゃダメだよな・・・orz
で、折り返しの回数は最小公倍数Ｇとした時、
ａ．Ｎ方向の折り返し回数＝Ｇ／Ｎ－１
ｂ．Ｍ方向の折り返し回数＝Ｇ／Ｍ－１
ｃ．総折り返し回数＝ａ＋ｂ＝G/N+G/M-2
直線の本数＝ｃ．＋１で
G/N+G/M-1
かなぁ・・・と。
最大公約数Ｐとすると、ＮとＭの最大公約数Ｐと最小公約数Ｇの関係ＮＭ＝ＧＰから式を変形すると、しょう太さんの式と一致するので、コレでいいかなぁ・・・と。
で・・・しょう太さんの追加問題３）と、１）の証明がまだ終わってません・・・orz
コメント by にこ — 2006/12/12 Tue @ 15:01:14
＞だけど、証明って話になると、赤い線が通過する小四角形の個数が最小公倍数ってのも証明しなきゃダメだよな・・・orz
ってことですが、実は問題文が、
＞赤い線が全ての小四角形を通る際のＮ、Ｍの条件を示し、そのことを証明する
とのことなので、僕なら
「赤い線がすべての小四角形を通るならば、ＮとＭは互いに素である」と理解し、互いに素であることが必要条件であることを証明して、証明完了！としたい（笑
それだと、にこちゃんので正解！
まぁ、出題者（つか、にこちゃんじぶんで考えたのよね？）の意図は、
「赤い線がすべての小四角形を通ることがあることを示し、その時のＮ、Ｍの条件を求めよ」なんだよね？これだと十分条件を示さなきゃならなくて、ちょっと難しいんだよね。
赤い線が通過する個数が最小公倍数であることはすぐ証明できると思う。あとは、その通過した小四角形が、すべての小四角形を必ず1回だけ通過していることを証明すればいいんじゃないかな。
コメント by しょうた — 2006/12/13 Wed @ 22:30:35