幾何学問題

質問

横線m本、縦線n本の方眼紙を切る直線は最大限何個のマスを通るか。
また、この問題の３次元版はどうか。

回答No.4

aster · ベストアンサー

一般的な話をしたので分かりにくかったのだと思います。具体的な例に沿って説明しますから、こういう風に考えているのだということを理解できましたら、先に述べたことも、何を述べていたのか分かると思います。

具体的な例として、縦線４本横線４本の正方形の形になる場合を考えてみましょう。
この例は、次のような図になりますね。

□□□
□□□
□□□

この図に、線を引いて、その線が横切る小さな四角形の数を最大にするというのが問題です。そこで、試しに、横線４本だけを通る線を考えてみます。

縦三段、横三段に積まれて、合計９個の四角形がありますが、このなかの一番右の三段の四角形を上から下に通る線を引いてみます（実際に絵に描いて考えるとよく分かります）。

最初に通るのは、「上端」の横線です。次に、第二の横線、第三の横線、そして、最後に「下端」の横線を通ります。この時、通過した四角形は３個です。

通り方をよく考えてみます。最初、上端つまり最初の横線を通った時、第一の四角形の内部に入りました。次の第二の横線を通過する時、第一の四角形から出て、第二の四角形に入りました。

第三の横線を通過する時は、第二の四角形から出て、第三の四角形に入ります。そして、第四の横線、つまり下端の横線を通過する時、第三の四角形を出ますが、その先に入る四角形はありません。

これだけで考えると、最後の下端の横線の場合を除いて、横線を一本通過すると、新しい四角形に入り、いままでいた四角形を出ることになるので、「少なくとも、四角形が隣接して、重なっている場合」は、横線を一本通過するごとに、通過する四角形の数は一つ増えることになります。

しかし、例外が、下端の横線です。この横線を通過しても、下に横線がもうないので、四角形を通過することになりません。そこで横線の数を、ｍとすると、この場合の通過した、四角形の数の式は、ｍ－１になります。実際、４－１で、３個になり、数が合います。

しかし、横線も通過すると同時に、縦線も通過すると、もっと通過する四角形の数は増えるのです。

上の例で、引いた、右の三段の四角形をまっすぐ上から下に通過する線を、上の点は固定して、下の点を、左に動かして行きます。すると、下段にならぶ三つの四角形の真ん中の四角形の右下角に触れ、やがて、この四角形のなかを横切ることになるでしょう。

この時、この新しい四角形を横切る線は、最初の三段の四角形の一番下の四角形の左の端線から、下段の真ん中の四角形の右端の線に入って行くことが分かるでしょう（実は、この二つの線は一本の線です）。

横線を横切る時に起こったのと、同じことが起こっています。つまり、境界の線を通過すると同時に、新しい四角形のなかに入っているので、これで通過四角形の数は一個増えることになります。

しかし、この場合、更に進むと、やはり、第四の横線つまり下端の横線に達します。そして、この第四の横線を通過しても、その先には、新しい四角形はありません。この場合、横線を四本通り、縦線を一本通過したことになります。

４（ｍ）＋１－１＝４　……これが、通過した四角形の数です。

何故、－２が出てくるのか、ここまででは分かりません。しかし、まだ、最大数には達していないのです。

以上の話で、縦線または横線を通過するたびに、通過する四角形が１増えるという規則があることが分かります。

従って、もっともたくさん縦線と横線を通過すると、通過する四角形の数も最大になるということが出てきます。理論的には上限は、ｍ＋ｎで、この場合は、４＋４です。

どうやると、８本の線を通過できるようになるか。一番簡単に考えると、大きな枠の四角形の右上の角から、左下の角へと、斜線を引くのがよいことが分かります。縦４，横４の場合は、この線は、小さな四角形の角を通過します。四角形内部は通過しません。これは、縦線と横線が同じ場合の特別なケースです。

そこで、この斜線を右か左に、ほんの少し平行移動します。すると、大きな四角形の枠の角からも外れますし、小さな四角形の角からも外れ、勘定すると分かりますが、これで、ｍ＋ｍ－２＝４＋４－２＝６本の縦線、横線を通過していることになります。

平行にずらすことで、通過する縦線が一本減り、同じように横線も一本経るのです。これは、どういう線を引いても、最大数を維持しようとすると、－２が付きます。引き方次第で、縦線４本、横線２本か、縦線２本、横線４本にできますが、結局、－２が出てきます。

そして、線がスタートする時は、その先に、下の横線、または左の縦線があるので、四角形は１個増えますが、こうして、縦線、横線を横切って、四角形の数を増やして行くと、最後に、下端の横線か、あるいは、左端の縦線を通過しなければならなくなります。

この時、線を一本、通過しているにも拘わらず、これによって、通過する四角形は増えません。何故なら、先に、更に横線または縦線がもうないからです。そこで、ｍ＋ｍ－２という通過線の式、これはまた、通過四角形の数を表しているのですが、この式から最後の線の通過は、四角形の増加にならないので、この分１を引くのです。

すると、ｍ＋ｍ－２－１　となります。

一般のｍ本の横線と、ｎ本の縦線の場合は、もう少し話が複雑になるのですが、上端、下端、左端、右端の四つの線のうち、通過できる線は、この四つのなかのどれか二つで、他の二つは通過できないのです。

だから、最大の通過線は、ｎ＋ｍの最大数から、通過できない２本の線の数を引き、ｎ＋ｍ－２となります。そして、最後に、線が、大きな四角形を出る時は、新しい小さな四角形は増えないので、やはり、－１となるのです。

その結果、式は、ｎ＋ｍ－２－１＝ｎ＋ｍ－３　になるのです。

縦４本、横４本の線を引いてみて、それに交差する線を引いて、図に描いて考えてみてください。絵に描くと簡単なことなのですが、文章では、なかなか分かりにくいのです。

三次元の場合は、これと同じ原理で考えて、式が出てきていますので、説明は省きます（頭のなかで、三次元イメージを造って、実際どうなるか、最初はイメージがうまく造れなかったのです。二回目は慣れたのか、イメージが見えたので、確信ができました。三次元の場合、図に描けない……非常に描きにくい……ので、難しいのです）。

回答No.3

aster

三次元の場合の立体升目についても、先の計算で、正しいという証明ができますので、追加で回答します。

三次元の場合は、ａ，ｂ，ｃという数の縦横高さに当たる三つの次元での平面で割られているのですが、これも、理論的に、直線が横切ることのできる面の最大数は、ａ＋ｂ＋ｃになります（実際は、ａ＋ｂ＋ｃ－４です）。

一つの面を貫通すると、その面が属する升目のなかを、線が通ることになります。

この時、全体が造る直方体を考え、その対称になる頂点から他の頂点へと斜線の直線を引きます。この斜線は、升目の立体的な角を通過する可能性があるのは二次元と同様です。

その場合、この立体的な角というのは、三本の線が交わっている点です（つまり縦横高さの三つの方向の直線が交わって、交点を造り、この交点の周りに、全部で八個の立体升目空間があります）。

こういう状態だと、三つの面を通過することにならず、交点を通過し、その時、斜線が通過するのは、当然、一つの立体升目になります。しかし、これも、斜線を、少し平行移動させると、高さで層をなしていると考えると、高い方の四つの升目の一つの横の面を通過するようにでき、また、同じ平行移動で、低い方の四つの升目の一つの横の面を通過できるようにすることができます。

こうすると、三線の交点で、最初の一つの面通過に加え、あと二つ面通過が可能となり、また同時に三つの立体升目を通過することになります。

このように、対称となる頂点と頂点を結んだ斜線は、通過する面の数が、（ａ－２）＋ｂ＋ｃ－４となります。従って、この数の立体升目を通過することになります。理論的に、直方体を通過する線は、ａ＋ｂ＋ｃ－４の面しか通過できませんから、（ａ－２）の－２が、通過直線の通過で、無効な立体升目分を引いている以上、この（ａ－２）＋ｂ＋ｃ－４が、理論的に最大な通過立体升目の数になります。

ただ、内部に線がない場合でも、最低で、立体升目は一つあるので、この数に１を加え、（ａ－２）＋ｂ＋ｃ－４＋１＝ａ＋ｂ＋ｃ－５が答えになります。

ａ，ｂ，ｃについて、直方体の外枠を造る六個の面については、直線が通過するかしないかに関係なく、立体升目の数の勘定では関係しないことからすれば、（ａ－２）＋（ｂ－２）＋（ｃ－２）と通過可能な面の数を計算し、これに初期状態で、一個の立体升目（つまり、直方体自体）の数が加わるとして、（ａ－２）＋（ｂ－２）＋（ｃ－２）＋１とする表現も間違いではないことになります。

二次元の場合も、同様なことが言えます。

以上は、証明を行っているのですが、図形が描けないと、どういう証明なのかが分かりにくいと思います。

このような直方体のなかを、直線が通過すると、その通過できる面の数の最大数は幾らかという計算と、他方、一個の面を通過すると、一個の立体升目を通過することになるということから、対角位置にある二つの頂点のあいだの斜線が、もっとも多数の面を通過するという事実からの証明です。

ただ、こういう対角線だと、立体升目の交点を通過することがあり、その時、線を、わずかに平行移動すれば、三面の交点をはずれて、三つの面を通過することができるようにできるので、「ａ＋ｂ＋ｃ－５」が、最終的な通過升目の数になるのです。

この関係は、一般ｎ次元の立体で、直線を通過させる時、ｎ次元升目を幾つ通過できるかという問題にも対応します。原理的に、同じ証明法が適用できるからです。ｎ－１次の超面数を、ａ，ｂ，ｃ，ｄ，ｅ……で表すと、「ａ＋ｂ＋ｃ＋ｄ＋ｅ＋……－２ｎ＋１」となります。

二次元では、ａ＋ｂ－４＋１＝ａ＋ｂ－３となり、三次元では、ａ＋ｂ＋ｃ－６＋１＝ａ＋ｂ＋ｃ－５となるのです。

回答No.2

aster

これは方眼紙で、当然、ますめの形は正方形で、ｍとｎは自然数で、違った数もありえるという問題だとします。

この場合、わたしなりに考えてみると、No.1 の方の回答と同じ答えになると思います。つまり、「ｍ＋ｎ－３」が答えです。

理由は、縦線または横線を横切るたびに、升目を一個横切ることになるからです。

ただし、上端、下端、左端、右端の線を横切っても、升目は増えないので、２を引きます（何故、２かというと、上端、下端、左端、右端の四つを同時に通るケースは、対角関係にある頂点を通る対角線の場合だけで、その他の場合、この四つを同時に通ることはないからです。頂点を通る場合は……一つの頂点だけの場合も……、実際は、一つの線を通るのと等価なので、結局－２になるのです）。

なかの縦線、横線を無視して枠だけ考えると、縦横合わせて４本あるので、横切る升目の数を、正しく計算しようとすると、更に－１としなければなりません。よって、ｍ＋ｎ－２－１＝ｍ＋ｎ－３となります。答えは同じですが、考え方が少し違います。

これを証明することですが、縦線も横線も最大ｍとｎしか通過できないということは明らかです。つまり、ｍ＋ｎ以上の通過線はありえないのです。では、ｍ＋ｎという通過が「可能か」どうかです。

これは、升目を考え、右上の角から、左下の角へ、対角線を引くと可能らしいと分かります（しかし、この場合、通過升目数計算のため、ｍ＋ｎ－２と計算するのであり、これが実は「最大の通過線数」なのです。対角線または半対角線でない場合、すでに述べたように、上端、下端、左端、右端の四つを同時に通る線は引けないのです。どれか二つを通過する線だけです）。

ところで、対角線の場合、「内部の升目の角」を線が通過することがあり、この時、縦線と横線を同時に通過して、しかし、通過する升目は一個ということになります。

しかし、線を、ごくわずか平行移動すると、升目の角を通過しないようにして、かつ、縦線ｍ－１本、横線ｎ－１本を通過するようにできます。

従って、最大で、縦線ｍ－１本、横線ｎ－１本を通過し、しかも、それが升目の角に来ないという斜線の引き方が可能であるとなり、通過升目の最大数は、「ｍ＋ｎ－３」になります。

ｍ＋ｎという通過線の引き方は実はできないのです。最大で、ｍ＋ｎ－２の通過線しか引けません。

-------------------------------------

三次元の場合は、直線としても、平面の通過の話になるので、いま分かりません。仮に軸に相当する区切り平面数をａ，ｂ，ｃとすると、ａ＋ｂ＋ｃ－２－３＝ａ＋ｂ＋ｃ－５になるような気がしますが、根拠が明確に分かりません。

ここで、－２は、六個の枠平面がありますが、直線はその二つの平面しか通らないからです。－３は、枠だけの場合の補正数です。この場合も対角線をずらすことで、考えられるのですが、見通しがよく分かりません。

二次元の場合と同じ説明で証明できるように思うのですが、三次元図形でどうなるのか、イメージできないのです。

二次元の場合だけで、「自信あり」とします。三次元は自信なしです。

補足

すみません。よくわからないのでもう一度質問します。

ただし、上端、下端、左端、右端の線を横切っても、升目は増えないので、２を引きます（何故、２かというと、上端、下端、左端、右端の四つを同時に通るケースは、対角関係にある頂点を通る対角線の場合だけで、その他の場合、この四つを同時に通ることはないからです。頂点を通る場合は……一つの頂点だけの場合も……、実際は、一つの線を通るのと等価なので、結局－２になるのです）。

＞どうして最初に２を引くのかがわかりません。
　「上端、下端、左端、右端の線を横切っても、升目が増えない」というのがわからないです。一つの線を横切るたびに升目が増えていくので、右上に線を引くとすると、最初に線が接している下端もしくは左端を升目が増えることとカウントしなければ、最後に接することになる上端もしくは右端は升目が増えたとカウントするのではないでしょうか？
　　また、縦m本、横n本が作る枠で考えて、それを横切るように考えた場合、

　　(1)始点も終点も頂点を通る
　　(2)始点だけ（終点だけ）頂点を通る
　　(3)始点も終点も頂点を通らない

このように場合わけできるってことですよね？

それから最後に－１をするのはさっき書いた「最初に接している線をカウントしな」かったからだと捉えていいのでしょうか？

回答No.1

wolv

1+(m-2)+(n-2)
つまり，m+n-3
だとは思うが，こういう簡単なことを厳密に証明しなければならないとすると，どこまで細かく話せばいいのかよくわかりません．

私の考え方：
------------------------------------------------------------
まず，左上のマスのみを通る直線を考える．この状態から，縦線でも横線でも，横切る直線が一本増えるごとに，通るマスも一つ増える．ただし，最上，最下，最右，最左の４つの線は横切ってもとおるマスの数は変わらない．よって，冒頭に数になる．
------------------------------------------------------------
どうでしょう．

------------------------------------------------------------

３次元版：

水平面L枚，垂直面M枚，さらに，その両方に垂直な面N枚によってできた「小立方体」群を切る＊＊＊は最大何個の「小立方体」を通るか？

＊＊＊は
直線ですか？
平面ですか？
------------------------------------------------------------
直線なら
1+(L-2)+(M-2)+(N-2)
= L+M+N-5
になりそう．

平面なら……？