平成１４年６月１６日
[流れ星]
第９９回数学的な応募問題解答
＜解答募集期間：６月１日〜６月１５日＞
［最長距離数］
太郎さんは、よく「図１のような碁盤の目になった町で、Ａ地点からＢ地点への最短距離で行く道順の総数を求めよ。」と言う問題に出合います。これは組み合わせの考え方で解くことができます。
では、Ａ地点からＢ地点へくねくねと遠回りをして行くと、最長距離数は幾つになるか。また、道順の総距離数は幾つになるかを考えました。ただし、同じ道を１回しか通れないものとし、小正方形の１辺の長さを１とする。
例えば、図２の１辺が２の正方形の場合は、総距離数Ｐは１２，最短距離数Ｓは４、最長距離数Ｌは８になります。
ここで、問題です。
問１．１辺が３の正方形の場合は、総距離数Ｐ，最短距離数Ｓ、最長距離数Ｌを求めよ。
問２．１辺が４の正方形の場合は、総距離数Ｐ，最短距離数Ｓ、最長距離数Ｌを求めよ。
問３．１辺が５の正方形の場合は、総距離数Ｐ，最短距離数Ｓ、最長距離数Ｌを求めよ。
問４．１辺がｎの正方形の場合は、総距離数Ｐ，最短距離数Ｓ、最長距離数Ｌを求めよ。
次に、長方形の碁盤の目を考え、１辺の長さがｍとｎの長方形を考えます。
問５．（１）ｍ、ｎがともに偶数のとき、総距離数Ｐ，最短距離数Ｓ、最長距離数Ｌを求めよ。
（２）ｍ、ｎがともに奇数のとき、総距離数Ｐ，最短距離数Ｓ、最長距離数Ｌを求めよ。
（３）ｍが奇数、ｎが偶数のとき、総距離数Ｐ，最短距離数Ｓ、最長距離数Ｌを求めよ。
＜問題の出典は、数研出版が出している数研通信ＮＯ２４の中にあったものです。＞
ＮＯ１＜Ｈ７Ｋ＞さん 1回目の解答 6月2日 17：12受信 更新６月16日
今度の問題はかなり難しいですね。問1-4についてですが、
P=2n(n+1) S=2n は明らか。
しかし、Lが予想段階を抜けていません。L=2n^2となるような気がします。証明ができたらまた書きます。<以上の一報は６月１日の報告＞
さっき横になって考えていましたら、「n*nの正方形のとき、L=2n^2」が示せました。
今から、それを書きます。メモとして書いているので、ちゃんとした説明は後日書きます。
A->Bの道は当然一筆なので、A,B以外の全ての点は偶点である。
端の4n点をA,B以外偶点にするには、そこの点から出ている線は常に二本でなければならない。
よって、L<=2n^2+2n-2n=2n^2(2n本の線をなくせば端についてA,B以外偶点にできる)
一方、2n^2での行き方は存在するので、L=2n^2.
<以上は６月１日の２回目報告＞
1回目の解答 6月2日 17：12受信
問5関連で、ちょっと考えてみました。
n*mの長方形において、
P(n,m)=(n+1)m+(m+1)n=2mn+m+n
S(n,m)=m+n
は明らか。
さて、L(n,m)についてだがm>=nとしても一般性を失わない。(以下、L(n,m)をU(n,m)と表す。
U(1,m)=2*m(m;奇数)
U(1,m)=2*m+1(m;偶数)
であるが、また
U(n+1,m+1)>=U(n,m)+2+4*([(n+1)/2]+[(m+1)/2]-1) ((n奇数,m偶数)or(m奇数,n偶数))
=U(n,m)+2*(n+m)
>=U(n,m)+2+4*([(n+1)/2]+[(m+1)/2]) (n,m奇数)
=U(n,m)+2*(n+m+1)
>=U(n,m)+2+4*([(n+1)/2]+[(m+1)/2]-1) (n,m偶数)
=U(n,m)+2*(n+m+1)
が成立するので、
U(n,m) >=U(n-1,m-1)+2*(n+m-1) (n,m奇数 or n,m偶数)
=U(n-2,m-2)+2*(2n+2m-4)
=U(n-k,m-k)+2*(kn+km-k^2)
=U(1,m-n+1)+2*(n^2-n+mn-m-n^2+2n-1)
=U(1,m-n+1)+2*(mn-m+n-1)
=2mn
U(n,m) >=U(n-1,m-1)+2*(n+m-2) ((n奇数,m偶数)or(m奇数,n偶数))
=U(n-2,m-2)+2*(2n+2m-6)
=U(n-k,m-k)+2*(kn+km-k^2-k)
=U(1,m-n+1)+2*(n^2-n+mn-m-n^2+2n-1-n+1)
=U(1,m-n+1)+2*(mn-m)
=2*(m-n)+3+2*(mn-m)
=2mn-2n+3
である。
一方、一筆書きの話より
U(n,m)<=P(n,m)-(n-1)-(m-1)-2=2mn (n,m奇数 or n,m偶数)
U(n,m)<=P(n,m)-(n-1)-(m-1)-2=2mn (n,m奇数 or n,m偶数)
現在はここまでしか.. たぶんL(n,m)<=2mn-2n+2が示せると思うのですが...
＜水の流れ：コメント＞ ｍが奇数、ｎが偶数のとき、L(n,m)の結果が私の解と異なっていますが・・・・
ＮＯ２＜kashiwagi＞さん 1回目の解答 6月3日 7：54受信 更新６月16日
第９９回解答
問１〜４
題意に沿って一辺の長さが３や４の正方形で試みると、縦横とも３や４づつ通らない道がある場合に最長距離になることが分かる。総数や最短距離は自明であるので、以下の表に整理する。又、P＝S＋Lである。
|
一辺の長さ |
P |
S |
L |
|
３ |
２４ |
６ |
１８ |
|
４ |
４０ |
８ |
３２ |
|
５ |
６０ |
１０ |
５０ |
|
ｎ |
２ｎ(ｎ＋１) |
２ｎ |
２ｎ＾２ |
問５
長方形の場合も（ｍ、ｎ）＝（３，１）、（４，２）の場合を試みると、上記と同様であることが分かる。但し、ｍ、ｎが偶数と奇数が混じる場合は最長距離のみ異なる。以下の表に整理する。
|
CASE |
P |
S |
L |
|
ｍ、ｎが偶数 |
２ｍｎ＋ｍ＋ｎ |
ｍ＋ｎ |
２ｍｎ |
|
ｍ、ｎが奇数 |
２ｍｎ＋ｍ＋ｎ |
ｍ＋ｎ |
２ｍｎ |
|
ｍが奇数、ｎが偶数 |
２ｍｎ＋ｍ＋ｎ |
ｍ＋ｎ |
２ｍｎ＋ｍ−ｎ |
＜水の流れ：コメント＞ｍが奇数、ｎが偶数のとき、L＝２ｍｎ＋ｍ−ｎに私の解と異なっていますが・・・・。
ＮＯ３＜Ｈ７Ｋ＞さん 2回目の解答 6月4日 19：19受信 更新６月16日
今までの解答をまとめてみました。
m*nの長方形での最少距離=S(m,n)、最長距離=L(m,n)、総距離数=P(m,n)とする。
P(m,n)=(m+1)n+(n+1)m=2mn+m+n、
S(m,n)=m+n
は明らか。
ここで、次の命題を示す。
「m≡n(mod 2)ならば、L(m,n)=2mn」「m-1≡n(mod 2)ならば、L(m,n)=2mn+1」
●L(1,n)>=2*n=2*1*n (n is odd)
L(1,n)>=2*n+1=2*1*n+1 (n is even)
であるので、m=1のときは両方とも成立。
●L(n+1,m+1)>=L(n,m)+2+4*([(n+1)/2]+[(m+1)/2]-1)=L(n,m)+2*(n+m) (m-1≡n(mod 2))
L(n+1,m+1)>=L(n,m)+2+4*([(n+1)/2]+[(m+1)/2])=L(n,m)+2*(n+m+1) (m≡n≡1(mod 2))
L(n+1,m+1)>=L(n,m)+2+4*([(n+1)/2]+[(m+1)/2]-1)=L(n,m)+2*(n+m+1) (m≡n≡0(mod 2))
が成立するので、m≡n(mod 2)のとき、「n=pの時成立すれば、n=p+1の時も成立。」
よって、m≡n(mod 2)のとき、L(n,m)>=2mn
●AからBへの道のりは一筆書きなので、縁に注目すると
m≡n(mod 2)のとき、L(n,m)<=P(n,m)-(n-1)-(m-1)-2=2mn
が成立。
よって、m≡n(mod 2)のとき、L(n,m)=2mn
一方、m-1≡n(mod 2)のとき、
●以下、m≡1としても一般性を失わない。
L(n+1,m+1)>=L(n,m+1)+1+4*[(m+1)/2]=2n(m+1)+2m+3=2nm+2n+2m+5=2(n+1)(m+1)+1
なので、m-1≡n(mod 2)のとき、L(n,m)>=2mn+1
●AからBへの道のりは一筆書きなので、縁に注目すると
m-1≡n(mod 2)のとき、L(n,m)<=P(n,m)-(n-1)-(m-1)-1=2mn+1
が成立。
よって、m-1≡n(mod 2)のとき、L(n,m)=2mn+1. //
以上より、
問1. P=24,S=6,L=18
問2. P=40,S=8,L=32
問3. P=60,S=10,L=50
問4. P=2(n^2+n),S=2n,L=2n^2
である。
＜水の流れ：コメント＞ L(n,m)の値が同じになりました。
ＮＯ４＜Ｉｇａ＞さん 解答 6月6日 18：19受信 更新６月16日
お久しぶりです、Igaです。またまたできそうだったのでやったらなんとかなりました。
よろしくお願いします。
総距離数Ｐ
まず、 縦の道(｜)の合計＝縦の長さ×本数
＝縦の長さ×｛横の道(−)の数＋１｝
同様に、横の道(−)の合計＝横の長さ×本数
＝横の長さ×｛縦の道(｜)の数＋１｝
よって、総距離数Ｐ＝縦の長さ×｛横の道の数＋１｝＋横の長さ×｛縦の道の数＋１｝
正方形の場合、縦の長さと横の長さは同じだから、１辺の長さをｎとすると
総距離数Ｐ＝ｎ×（ｎ＋１）×２
最短距離数Ｓ
経路は他にも考えられるが、一番外枠の道を選んだ場合が最短になることは明らか。
よって、最短距離数Ｓ＝縦の長さ＋横の長さ
正方形の場合、縦の長さと横の長さは同じだから、１辺の長さをｎとすると、
最短距離数Ｓ＝ｎ×２
最長距離数Ｌ
これは実際に図をかいて、数えてみました。
ｎ Ｐ Ｓ Ｌ
２ １２ ４ ８
３ ２４ ６ １８
４ ４０ ８ ３２
ここまでやってみて、Ｌ＝Ｐ−Ｓ という関係があることに気づいたので、
５ ６０ １０ ５０
ｎのときはＰ＝２ｎ（ｎ＋１）、Ｓ＝２ｎを代入して、
Ｌ＝Ｐ−Ｓ
＝２ｎ（ｎ＋１）−２ｎ
＝２ｎ＾２
以上のようになりました。
次に、長方形の碁盤の目を考え、１辺の長さがｍとｎの長方形を考えます。
問５
（１）ｍ、ｎがともに偶数のとき、総距離数Ｐ，最短距離数Ｓ、最長距離数Ｌを求めよ。
ｍ＝２，ｎ＝４のときを例にして数えてみました。
総距離数Ｐ＝２２ 、最短距離数Ｓ＝６はすぐに求められました。
最長距離数Ｌは図をかいて求めたら、１６となりました。
よって、正方形のときと同じように考えて、
Ｐ＝ｎ（ｍ＋１）＋ｍ（ｎ＋１） 、Ｓ＝ｍ＋ｎ
であるから、最長距離数Ｌは、
Ｌ＝Ｐ−Ｓ
＝ｎ（ｍ＋１）＋ｍ（ｎ＋１）−（ｍ＋ｎ）
＝２ｍｎ
（２）ｍ、ｎがともに奇数のとき、総距離数Ｐ，最短距離数Ｓ、最長距離数Ｌを求めよ。
ｍ＝３，ｎ＝５のときを例にして数えてみました。
総距離数Ｐ＝３８ 、最短距離数Ｓ＝８はすぐに求められました。
最長距離数Ｌは図をかいて求めたら、３０となりました。
よって、（１）と同様に、
Ｌ＝２ｍｎ
（３）ｍが奇数、ｎが偶数のとき、総距離数Ｐ，最短距離数Ｓ、最長距離数Ｌを求めよ。
ｍ＝３，ｎ＝２のときを例にして数えてみました。
総距離数Ｐ＝１７ 、最短距離数Ｓ＝５はすぐに求められました。
最長距離数Ｌは図をかいて求めたら、１３となりました。
今までと同じ関係があるなら、Ｌ＝１７−５で、１２となるはずなので数え間違いかと思い、何度も確認しましたが、最長距離数は１３でした。
何が違うのかいろいろと考えているうちに、同じ道を通らないということから、一筆書きを思いつきました。一筆書きができるかどうかを判断するのに、奇数本の線の集まる奇点の個数をかぞえるというやつです。
●−○−○−Ｇ 左の図で、Ｓはスタートで、Ｇはゴール、
｜ ｜ ｜ ｜ ●は偶点、 ○は奇点を表しています。
○−●−●−○Ｄ
｜ ｜ ｜ ｜
○−●−●−○Ｃ
｜ ｜ ｜ ｜
Ｓ −○−○−●
Ａ Ｂ
ＳとＧはその性質上、奇点扱いになります。（Ｓからは２本の道がありますが、
Ｓから横へいったら、Ｓから縦につながっている道を通ることはできません。Ｇも同様）
ここで、最長距離数となるには、通らない道をできるだけ減らす必要があります。
奇点につながっている道のうちの一つは、通らない道となるので、そのままでは単純に奇点の数だけ通らない道ができてしまいます。通らない道を減らすためには、隣り合った奇点と奇点の間の道を通らない道とすることにより、半減します。（上の図のＡＢ間、ＣＤ間）
しかし、この図のような奇点の配置だと、１０個の奇点のうちＡＢ間のような組み合わせは４組しか作ることができず、２個の奇点は孤立してしまいます。
そのため通らない道の数は、この図の場合で１０−４＝６本ということになります。
１辺長さがｎの正方形の場合、奇点の数は（ｎ−１）×４個、孤立する２個を仮にＳとＧとすれば、
半減できる道の数は（（ｎ−１）×４）÷２となるので、通らない道の数は
（ｎ−１）×４−（ｎ−１）×２＋２＝２ｎ となります。
この数が最短距離数Ｓと一致するので、問い５（３）以外はＬ＝Ｐ−Ｓという関係が成り立ちます。
●−○−○−Ｇ
｜ ｜ ｜ ｜
○−●−●−○
｜ ｜ ｜ ｜
Ｓ −○−○−●
ｍが奇数、ｎが偶数のときは、その他の場合にあったように奇点を孤立させることなく、
隣り合った奇点の組を作ることができます。
その結果、奇点の数は （ｍ−１）×２＋（ｎ−１）×２個、
ＳとＧの２個を加えて、奇点の２個組の数は ｍ＋ｎ＋１組、
したがって通らない道の数も（ｍ＋ｎ＋１）本となり、総距離数Ｌから引くと最長距離数Ｌ
が求められます。
Ｌ＝Ｐ−（ｍ＋ｎ＋１）
＝ｎ（ｍ＋１）＋ｍ（ｎ＋１）−（ｍ＋ｎ＋１）
＝２ｍｎ＋１
以上です。何とか自分なりに納得行く解答が出せたので満足しています。
またよろしくお願いします。
＜水の流れ：コメント＞ 当初、ｍ、ｎが奇数であろうが偶数であろうが、Ｐ＝Ｓ＋Ｌが成り立つと考えていましたが、この解答で自分の間違いに気がつきました。これまで、ご迷惑をおかけしたことの お詫びします。
で、ｍが奇数、ｎが偶数のときは、Ｐ＝Ｓ＋Ｌ―１になっていました。
ＮＯ５＜kashiwagi＞さん２回目の解答 6月10日 7：46受信 更新６月16日
問５の（３）のＳ，Ｌが違うとの事でしたが、Ｌは理論式の導出で計算ミスをしておりました。
長方形の場合も（ｍ、ｎ）＝（３，１）、（４，２）の場合を試みると、上記と同様であることが分かる。但し、ｍ、ｎが偶数と奇数が混じる場合は最長距離のみ異なる。以下の表に整理する。
|
CASE |
P |
S |
L |
|
ｍ、ｎが偶数 |
２ｍｎ＋ｍ＋ｎ |
ｍ＋ｎ |
２ｍｎ |
|
ｍ、ｎが奇数 |
２ｍｎ＋ｍ＋ｎ |
ｍ＋ｎ |
２ｍｎ |
|
ｍが奇数、ｎが偶数 |
２ｍｎ＋ｍ＋ｎ |
ｍ＋ｎ |
２ｍｎ＋１ |
関係式はｍ、ｎのどちらも偶数か奇数の時はP＝S＋L
ｍ、ｎの片方が偶数、もう一方が奇数の時はP＝S＋L−１
＜水の流れ：コメント＞ 当初、ｍ、ｎが奇数であろうが偶数であろうが、Ｐ＝Ｓ＋Ｌが成り立つと考えていましたが、この解答で自分の間違いに気がつきました。これまで、ご迷惑をおかけしたことの お詫びします。
で、ｍが奇数、ｎが偶数のときは、Ｐ＝Ｓ＋Ｌ―１になっていました。
