問題161 バスの運行
図にように碁盤の目状の道があり、２つの道が出会う点を交差点と呼ぶことにします。
各行、各列に１台ずつ、合計９台のバスを走らせます。
それぞれのバスは同じ速さで走り、１つの行または列を往復しつづけます。
初めはどのバスもいずれかの交差点に置くものとします。
どの２台も往復の間にどこかの交差点で出会うことがないようにすることが可能でしょうか。
不可能であれば証明し、可能であればどのようなときかを示してください。
問題の出典
ジュニア数学オリンピック2003-2008
数学オリンピック財団編
日本評論社
答えと解説
解答・その1
（ペンネ－ム：転位反応）
下図の通り、交差点に1から20の番号を付け、
行を往復するバスをそれぞれＡ、Ｂ、Ｃ、Ｄ、列を往復するバスをＥ、Ｆ、Ｇ、Ｈ、Ⅰとする。
バスは行または列を往復し続け、通過する交差点の数は行を１往復すると８、列を１往復すると６なので、
それらの最小公倍数である２４が１サイクルに通過する交差点の数である。
各バスが通過する交差点を１サイクルについて整理すると表１のようになるので、これらのケースから
全てのバスが交差点で出会わないような組合せを選択すれば良い。
先ず、Ａを交差点１からスタートさせ、ＥがＡと出会うことがないようにＥがスタートする交差点を求める。
表１から、Ｅが交差点６、１６からスタートするとＡと交差点１で出会うことはない。
この場合、Ｅが交差点６からスタートする方向は、交差点１或いは１１の何れの方向でも良い。
同様にして、Ｂが交差点６でＥと出会わないように、Ｂがスタートする交差点を求める。
以下、既に決定したバスの経路に対して残りのバスがスタートする交差点を順次、求めて行けば良い。
表１
以上、Ａを交差点１からスタートさせ、全てのバスが交差点で出会わないように、他のバスがスタートする
交差点の位置を求めると下図の通りとなる。なお、バスが交差点からスタートする方向が２通りある場合は、
何れか１つを任意に選択できる。（表１の水色網掛けのケース）
ここで、表１より、Ａがスタートする交差点は、１の他に３、または５でも良いことが分かるので、追記すると
下図の通りとなる。（表１の黄色網掛けのケース）
また、Ａがスタートする交差点を２、４とした場合は、表１の色を付けていないケースが該当するので、
上図の●と▲を入れ替えれば良い。
よって、各バスが交差点で出会うことなく、往復することは可能である。
具体的方法は、図Ⅰ、または図Ⅱの何れかを選択して、各バスがスタートする交差点を１か所選定する。
但し、交差点からスタートする方向が２通りある場合は、何れの方向でも良い。
解答・その2
（ペンネ－ム：falcon@中学教師）
可能。
スタート時の配置は様々だが、一例は下図の通り。（矢印はバスの進行方向を表している。）
＜考え方＞
上下に動くバスは6回の移動で元の位置に戻る。
左右に動くバスは8回の移動で元の位置に戻る。
したがってこの9台のバスの位置は６と８の最小公倍数である24回の移動で元に戻る。
上記のことをもとにしながら、最も左で上下に動くバスの初期位置を固定し、
左右に動くバスの初期位置を、固定したバスと24回の移動の中で交差点で出会わないように調べることにした。
その結果ある程度の指針が立ったので、試しに設定した初期位置から24回の移動を実際に行い、
可能であることが判明した。
解答・その3
（ペンネ－ム：スモークマン）
重なるとき二つの座標の和は必ず偶数になるので...
そうならないような初期値に配置すればよい。
左下を(0,0) とする座標で考えると...
横に動くバス 縦に動くバス
(偶数、偶数(0))-(偶数(0)、奇数)
(奇数、奇数(1))-(奇数(1)、偶数)
(偶数、偶数(2))-(偶数(2)、奇数)
(奇数、奇数(3))-(奇数(3)、偶数)
-(偶数(4)、奇数)
たとえば...
(0,0)-(0,1)
(1,1)-(1,2)
(2,2)-(2,3)
(3,3)-(3,0)
-(4,1)
でもいいはず...?
解答・その4
（ペンネ－ム：オヤジ）
各交差点で出会うことが無い様にすることが可能
∵ 長方形の格子の左下の交差点を原点（０，０）とし、
右側を、Ｘ軸方向，上側をＹ軸方向とし各交差点に、（直交）座標を入れる。
各交差点Ｐ（a，b） （ a ＝０，１，２，３，４ b ＝０，１，２，３）
に対して，下記の様に色づけをする。
Ｃ｛Ｐ（a，b）｝＝ 赤 （ 但し a＋b ＝ 偶数）
Ｃ｛Ｐ（a，b）｝＝ 白 （ 但し a＋b ＝ 奇数）
ここで、横方向に走るバスを例えば 白色の交差点から出発させる。
同様に 縦方向に走るバスを例えば 赤色の交差点から同時に出発させると、
横：白→赤→白→赤→・・・→白→赤→・・・
縦：赤→白→赤→白→・・・→赤→白→・・・ となり
どの２台のバスも各交差点で出会うことが無い。
解答・その5
（ペンネ－ム：巷の夢）
道路の交差点を格子点と見て、その座標を以下の様に考える。
この様に表せば全ての交差点は座標で表せ、ｘとｙ座標の合計は必ず偶数か奇数となる。因って、横4本の道路各々に置く4台のバス全てを合計座標偶数に置いた場合は、縦5本の道路各々に置く5台のバスの座標を全て合計座標奇数箇所に割り振れば、交差点で2台がぶつかる事はない。
勿論、縦と横の座標合計を逆にしても良い。但し、縦の5台は全て奇数なら奇数、偶数なら偶数とせねばならない。
解答・その6
（ペンネ－ム：杖のおじさん）
答えは可能です。
交差点を○と●で図のように印をつけます。
縦のバスは○に配置する。横のバスは●に配置する。
配置する場所は列上に一台であれば何処に配置しても良いのです。
走る方向は縦のバスは上方向でも下方向でも良いのです。
横方向は右方向でも左方向でも良いのです。
理由は縦方向のバスは走りだすと白→黒→白→黒の順に通過します。
横の方向は黒→白→黒→白の順番に通過します。従って同じ時間には縦のバスと同じ印の交差点は通過しません。
縦が●であれば横が○、縦が○であれば横が●に配置します。従って配置場所の組合せは多くあります。
解答・その7
（ペンネ－ム：haya）
どこかの交差点で出会うことがないようにすることは可能です。
例えば、分かりやすくするために、列を上下するバスを●、行を左右に動くバスを○で表すとして、
のように。
【解き方】
列を上下するバスは6回目に、行を左右に行き来するバスは8回目に同じ場所に戻りますから、
最小公倍数は24で、25回目には同じ局面に戻ります。
一番左の列と一番下の行を行き来するバスに限定して、原点で出会った状況から動かし始めて、
0,0 （※左の数値が●の、右が○の原点からの距離を表します）
1,1
2,2
3,3
2,4
1,3
0,2
2,0
3,1
0,4
の都合9種類が使用不可の組合せだと分かります。 ここでの●と○の組合せの数は、
3+4*4=19
ですから、残りの使える組合せは10種類です。 仮に、使用可の 0,1 から始めるとして、
0,1
1,2
2,3
3,4
・・・
1,0
2,1
3,2
・・・
1,4
0,3
・・・
3,0
・・・
と言う具合に実際に残りの10種類で衝突せずに運行可能でした。
同じ手法で組合せを適当に按分したものが図の例なのですが、実際に衝突せずに運行できます。
解答・その8
（ペンネ－ム：ＲＹＵ1128）
次のような図を考えます。一つの交差点から次の交差点までの到達時間は、１単位時
間とします。白丸は出発（時刻０)か偶単位時刻です。黒丸は奇単位時刻です。
横軸上の丸は横の往復、縦軸上の丸は縦の往復です。
偶時刻と奇時刻は出会いませんので図に従って白丸を各出発点とすればよいことにな
ります。
黒丸と白丸を入れ替えても成り立ちます。
計算が面倒なので省きますが、出発点の場合の数から、全ての組み合わせが何通りに
なるかも計算できそうですね！
さらに補足ですが、左下を決めるとドミノ式に後のすべてが決まってしまうので、
白黒の組み合わせは、図と図の白黒を入れ替えたケースしかありません。
また任意の交差点で縦横いずれも白丸（遇時刻）またはいずれも黒丸（奇時刻）の場
合、各々の往復回数を適当にえらぶことにより周期的に必ず一致するのは自明です。
解答・その9
（ペンネ－ム：のっこん）
各交差点に白石と黒石を交互に置く
○●○●○ ●○●○● ○●○●○ ●○●○●
列を走るバスをＡ、行を走るバスをＢとする
すべてのＡ（５台）を○の上、
すべてのＢ（４台）を●の上に置くことができれば
どの２台も交差点で出会うことはない
※すべてのＡが●の上、すべてのＢが○の上でも構わない
例えば次のように置けばよいから、出会わないようにすることは可能である
（１） ＡＢ－－Ａ （２） －－－ＢＡ （３） －－ＡＢ－ －ＡＢ－－ －－ＢＡ－ －ＡＢＡ－ －－ＡＢ－ ＡＢＡ－－ ＡＢ－－Ａ －－－ＡＢ ＢＡ－－－ Ｂ－－－－ ・・・・・・
解答・その10
（ペンネ－ム：迷子の雄猫）
上下方向に移動するバスは上記の□の交差点に
左右方向に移動するバスは上記の■の交差点に配置する。（またはその逆）
上下方向のバスと左右方向のバスが交差点で出会うためには、
ある時点で同じ色の交差点に居なければいけない。
初期配置からは、上下方向のバスが■の交差点に移動するときには、
左右方向のバスは□の交差点に移動しているので、
どの２台も往復の間にどこかの交差点で出会うことがない。
解答・その11
（ペンネ－ム：夜ふかしのつらいおじさん）
碁盤の目状の道を図のように座標平面の中におくことにします。
バスが１区画進むのにかかる時間を単位時間とします。
ｙ軸上にあるバスがある行を左右に移動するとき、各列を通過する時間を調べます。
表１
| (0,*) | (1,*) | (2,*) | (3,*) | (4,*) |
|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 |
| 8 | 7 | 6 | 5 | |
| 9 | 10 | 11 | 12 | |
| 16 | 15 | 14 | 13 | |
| 17 | 18 | ・・・ | ・・・ |
ｘ軸上にあるバスがある列を上下に移動するとき各行を通過する時間を調べます。
表２
| (*,3) | 3 | 9 | 15 | |||
|---|---|---|---|---|---|---|
| (*,2) | 2 | 4 | 8 | 10 | 14 | 16 |
| (*,1) | 1 | 5 | 7 | 11 | 13 | ・・・ |
| (*,0) | 0 | 6 | 12 | ・・・ |
ここで、各座標点でバスが出会うかどうかを調べます。
「－」は出会わないこと、「×」は出会うことを表します。
例えば、(2,1)の地点は、
左右に移動するバスは、時間｛2,6,10,14,･･･｝に通過します。（表１の桃色）
上下に移動するバスは、時間｛1,5,7,11,13,･･･｝に通過します。（表２の水色）
これらの時間をみると、偶数と奇数なので同じ時間はなく、出会わないことが分かります。
| (0,*) | (1,*) | (2,*) | (3,*) | (4,*) | |
|---|---|---|---|---|---|
| (*,3) | － | × | － | × | － |
| (*,2) | × | － | × | － | × |
| (*,1) | － | × | － | × | － |
| (*,0) | × | － | × | － | × |
この結果から、次の図のようにまずバスを配置します。
漢字は、その色のバスが通過する時間の偶数、奇数を表します。
次に残りのバスを通過時間の偶数、奇数に注意して、例えば次のように配置します。
するとどの地点も偶数、奇数が同じにならないのでどの２台のバスも出会うことがありません。
つまり偶数、奇数が重ならなければよいので、
赤丸を行を左右に移動するバスの配置の候補地、青四角を列を上下に移動するバスの配置の候補地とすると、
この図では、
（３×２×３×２）×（２×２×２×２×２）
通りの配置があります。
また、赤丸と青四角を入れ替えてもよいのでさらに倍して、
２×（３×２×３×２）×（２×２×２×２×２）＝２３０４
通りの配置があります。
解答・その12
（ペンネ－ム：T_Tatekawa）
交差点を市松模様に塗ります．左下を黒，ここの交差点の隣を白というようにします．
□■□■□ ■□■□■ □■□■□ ■□■□■
次に，バスを配置します．縦に走るバスは黒の交差点，横に走るバスは白の
交差点に配置します．すると，バスは交差点で出会いません．
時間が経って一ブロック進むと，縦に走るバスは白の交差点，横に走るバスは
黒の交差点に居るので，縦に走るバスと横に走るバスは交差点で出会いません．
また時間が経って一ブロック進むと，縦に走るバスは黒の交差点，横に走るバスは
白の交差点に居るので，縦に走るバスと横に走るバスは交差点で出会いません．
この繰り返しにより，バスが交差点で出会わないようにする事は可能です．
つまり交差点を市松模様に塗り，縦に走るバス，横に走るバスを同じ色の交差点に配置すれば可能です．
正解者
| 夜ふかしのつらいおじさん | のっこん | 迷子の雄猫 |
| 巷の夢 | スモークマン | 杖のおじさん |
| haya | ＲＹＵ1128 | 転位反応 |
| falcon@中学教師 | オヤジ | T_Tatekawa |
コメント
可能ですね。皆さんの解答にあるように、交差点を白黒の市松模様に塗り分け、 例えば縦方向のバスは黒交差点から、横方向のバスは白交差点から出発させれば、 互いにぶつかることはないということがわかります。 パリティ（偶奇性）で考えるマス目の問題の類似問題ですね。
top