大学入試数学 境界を越えない経路—初めて境界を越える位置を使って除く経路を対応させる｜武蔵野個別指導塾

格子上で初めて対角線を越えた点に着目し、除く経路を別の始点からの経路へ移す境界の数え方をたどります。

よくあるのは、高校生が格子の終点だけを見て、途中で境界を越えた経路も残してしまう場面です。右か上に1目盛りずつ進む道では、終点が対角線の下にあっても、途中で上へ出てから戻ることがあります。例えば右へ2回、上へ2回進む道のうち、上を先に選ぶ道は終点が対角線上でも条件を満たしません。

問われ方には、境界を越えない道の総数を求める型、途中の点を通る道を数える型、始点と終点を文字で置いて一般に示す型があります。どれも終点だけでなく、出発点を含む各格子点で不等式を調べることが必要です。ここでは有限回の右上移動を扱い、境界線上に乗ることは許します。

要点（結論から）

• 境界上を許すかを不等号で確定します。
• 始点と終点、右上移動の実現可能性を先に調べます。
• 違反経路は初めて y=x+1 に着く点で切ります。

道の条件と最初の違反

格子点を(x,y)と書き、右への1歩をR、上への1歩をUとします。境界を直線 y=x とし、許される領域を y≤x とします。等号があるので、対角線上に触れても違反ではありません。違反は y>x となったときです。右上移動なので、直線を初めて越える点では必ず y=x+1 となります。

始点を(a,b)、終点を(c,d)とし、a、b、c、dは整数とします。まず右と上だけで到着できるには c≥a、d≥b が必要です。さらに条件を満たす道があるには始点と終点も y≤x を満たす必要があります。この条件があれば、右へ必要回数進んでから上へ進む道が存在するので、条件は十分でもあります。距離が0の道も、始点と終点が一致し許される領域内なら1本です。

C(n,k)を、n個からk個を選ぶ組合せの数とします。nが0以上の整数、kが0以上n以下の整数のとき、右への歩数を決めた位置に置けば、制限なしの道は C(c-a+d-b,d-b) 本です。順序が違えば別の道です。範囲外のkについては、実現する選び方がないので0と考えます。

図1のように、違反した道は最初に y=x+1 へ着く点を目印にできます。最初の点を使う理由は、1本の道に目印が必ず1つ決まるからです。始点からその点までを直線 y=x+1 に関して反射し、目印より先は元のままにします。反射した部分ではRとUが交換され、始点(a,b)は(b-1,a+1)へ移ります。

逆向きも必要です。元の始点と終点が許される領域にあるとします。反射後の始点から終点への道を考え、最初に y=x+1 に達した点までを反射して元に戻します。

この移し方なら、新しい始点は y-x=a-b+2≥2、終点は y-x≤0 です。右上移動の1歩ごとに y-x は1ずつ変わるため、反射後の道は必ず y=x+1 に達します。その最初の到達点までを同じ直線で反射すれば、元の始点からの道が得られ、その点が元の道の初めての違反点になります。往復で元に戻るので、違反した道と新しい始点から終点への道は一対一です。反射は直線 y=x+1 に関して (x,y) を(y-1,x+1)へ移す操作です。

したがって、始点と終点が許される領域内で、右上移動が可能なとき、違反した道は C(c-a+d-b,d-a-1) 本です。新しい始点から終点までの上の歩数が d-a-1 だからです。これは範囲外なら0本とします。求める道は全体からこの数を引きます。始点を対角線に映すだけでは反射線が違い、初めて違反する点を固定できない点に注意します。

一般式を使う前の点検

反射後の始点から終点までの総歩数は、元の総歩数と同じです。右と上を入れ替えるのは途中までの部分だけで、その部分の歩数自体は変わらないからです。計算上も、右の歩数は c-b+1、上の歩数は d-a-1 となり、和は c-a+d-b です。この2つがいずれも0以上なら、その順序を選んで反射後の道を作れます。上の歩数が負なら、そのような道はなく、違反もありません。

例えば、始点から終点までに使う上の歩が、初めの余裕を使い切って境界を越えるには足りない場合です。引く数を無理に正の数にせず、組合せの範囲外として0とします。終点が元の始点より左や下にある場合には、そもそも右上移動で到達できないため0本です。これらの判定を終えてから、全体と違反の差を取ります。

また、境界そのものを通ることを禁止する条件では、許される不等式が変わり、そのまま同じ式を使うことはできません。どの点を最初の違反点とするかも変わります。問題文の「越えない」と「触れない」を読み分け、出発点や到着点にも条件がかかるかを確かめます。文字を代入する前に図で1歩をたどると、等号の扱いを確実にできます。

基本例題：終点が対角線上にある道

【基本・標準】(0,0)から(3,3)まで右または上に1歩ずつ進みます。すべての途中点で y≤x を満たす道は何本ですか。整数で答えてください。

図2のように、全体は6歩中の上3歩の位置を選びます。違反した道の最初の違反点までを y=x+1 について反射すると、新しい始点は(-1,1)です。そこから終点へは右4歩、上2歩です。

全体 = C(6,3) = 20
違反 = C(6,2) = 15
条件を満たす道 = 20 - 15 = 5

答えは5本です。実際にRとUで書くと、RRRUUU、RRURUU、RRUURU、RURRUU、RURURUの5本です。各接頭部分でRの個数がU以上であり、最後にはそれぞれ3回です。逆に長さ6の列を先頭から調べれば、最初にUが多くなる列は除かれ、この5本が残ります。

標準例題：始点に余裕がある道

【標準・やや難】(2,0)から(5,3)へ右または上に進みます。各格子点で y≤x を満たす道の本数を整数で求めてください。

始点では x-y=2 なので、上への歩を先に選んでも直ちに違反するとは限りません。全体は右3歩、上3歩の20本です。反射後の始点は(-1,3)で、終点まで右6歩、上0歩です。よって違反は1本、答えは19本です。

全体 = C(6,3) = 20
違反 = C(6,0) = 1
条件を満たす道 = 20 - 1 = 19

別の見方では、6歩で違反するには、差 y-x が最初の-2から1へ上がらなければなりません。上がる歩が少なくとも3回必要であり、上の歩は全部で3回です。途中に右の歩を挟むと最初の違反までに4回以上の上が必要なので、違反する道はUUURRRの1本です。この列を元の座標に戻すと(2,3)で初めて越え、終点は(5,3)です。

発展例題：指定点を通る条件

【発展・難】(0,0)から(4,3)まで右または上へ進み、各格子点で y≤x を満たす道を考えます。そのうち(2,1)を通る道は何本ですか。整数で答えてください。

指定点に着くまでと着いてからで道を切ります。右上移動では指定点を2回通れず、前半と後半を1本ずつ選べば元の道が1本決まります。したがって積の法則が使えます。ただし後半にも境界条件を課す必要があります。

前半は右2歩、上1歩です。全体3本のうち、最初がUの1本は違反なので2本です。後半は(2,1)から(4,3)まで右2歩、上2歩です。全体6本、反射後の始点は(0,3)で、終点まで右4歩、上0歩なので違反は1本です。

前半 = C(3,1) - C(3,0) = 2
後半 = C(4,2) - C(4,0) = 5
指定点を通る道 = 2・5 = 10

答えは10本です。別解として、後半の4歩を列挙すると、UURRのみが最初の2歩で(2,3)に達して違反します。他の5列は、最初の差 x-y が1あることを使って各途中点を点検できます。前半の2列はRRUとRURです。それぞれに後半5列をつなげると、同じ完成経路が重なることはありません。

指定点が境界より上なら、そこを通る条件と境界条件は両立せず0本です。指定点が始点から右上に届かない、または指定点から終点に届かないときも0本です。先に実現可能性を判定すれば、存在しない歩数を組合せに入れる失敗を避けられます。

引く道が何を表すか

次の誤答を考えます。「(0,0)から(3,3)への全20本から、対角線上の点を通る道を引けばよい」。図3のように、対角線に触れることは許されています。例えばRURURUは途中で何度も触れますが、どの点でも y≤x です。この道を引くと必要な道まで失います。

直すには、除く条件を y>x と書き、その最初の点に注目します。境界上の点が複数ある道に対し、各点を通る道を個別に足しても、同じ道を何度も数えるおそれがあります。最初の違反点なら1本につき1つに定まり、反射後の道からも最初の到達点として復元できます。引く数が全体以下の非負整数になることも最後に点検します。

別の誤りは、始点と終点が領域内なら、間も自動的に領域内だとすることです。基本例題のUUURRRは両端が境界上ですが、最初の1歩で違反します。端点の条件は必要条件であり、途中の条件を省く根拠ではありません。点を1つ避ける問題ではその点を通る道を分けられますが、ここでは境界の上に出る場所が複数あるため、最初の違反を指定して重複を防ぎます。

練習問題

いずれも格子上を右または上に1歩ずつ進み、出発点と終点を含む各点で y≤x を満たすものとします。本数は整数で答えてください。

1. 【標準】(0,0)から(2,2)へ進む道は何本ですか。
2. 【標準】(1,0)から(3,2)へ進む道は何本ですか。
3. 【やや難】(0,0)から(4,2)へ進む道は何本ですか。
4. 【やや難】(1,0)から(4,2)へ進み、(2,0)を通る道は何本ですか。
5. 【難】(0,0)から(2,3)へ進む道は何本ですか。終点も条件に含めて判定してください。

練習問題の答えと道筋

1. 全体は C(4,2)=6 本です。反射後の始点は(-1,1)で、上1歩を含む4歩なので、違反は C(4,1)=4 本です。6 − 4 = 2 より2本です。RRUUとRURUを順にたどると、どちらも最後に(2,2)へ着きます。

2. 全体は C(4,2)=6 本です。反射後は(-1,2)から(3,2)へ右4歩ですから、違反は C(4,0)=1 本です。6 − 1 = 5 より5本です。除いたUURRは(1,2)で越え、残りの5列は各点で条件を満たします。

3. 全体は C(6,2)=15 本です。反射後は(-1,1)から(4,2)まで上1歩なので、違反は C(6,1)=6 本です。15 − 6 = 9 より9本です。最初の歩がUの5列と、最初がRで次の2歩がUUの1列が違反し、合わせて6列です。

4. 前半は右1歩の1本です。後半は(2,0)から(4,2)へ右2歩、上2歩で、上へ2回続けても境界に触れるだけです。最も上に寄るUURRも条件を満たすので、後半の C(4,2)=6 本はすべて有効です。1・6 = 6 より6本です。

5. 終点(2,3)では3>2です。終点を含めて条件を課すので、途中の選び方にかかわらず0本です。全体から反射先の道を引く式をそのまま使う前に、端点が条件を満たすかを調べます。

要点を持ち帰る

• 境界上を許すかを不等号で確定します。
• 始点と終点、右上移動の実現可能性を先に調べます。
• 違反経路は初めて y=x+1 に着く点で切ります。
• そこまでを直線 y=x+1 で反射し、逆操作も示します。
• 全体から違反を引き、歩数と答えを元の道へ戻します。

どこで止まったかを見分ける

図に許される側を塗れるのに式が作れないときは、最初に越える点の前後を別々の色でたどってみます。反射した始点と終点の間に必要な右と上の歩数を数えれば、何を組合せで選ぶかが見えます。逆に式は書けても、反射先の道が元へ戻る理由を言えない場合は、初めて境界に達する点が必ず存在するかを、両端の y-x の値から確認します。

個別指導で確かめるなら、まず短い道を実際に並べ、境界に触れる道と越える道を分類します。次に1本の違反経路を反射し、戻したときに同じ道になるかを説明してもらいます。一般式の数字を覚える前に、1歩ごとの変化と逆向きの対応を言葉にできれば、始点が変わっても自分で数え直せます。境界を越える最初の点が、道の数を結びます。反射の前後で、道を選ぶ順序も確かめましょう。