大学入試数学 非負整数解と総量の境界—解が存在する範囲をパラメータで説明する｜武蔵野個別指導塾

4個と7個の組合せを例に、0を含む条件と整数区間の端点から読み解く総量の境界。

よくあるのは、高校生が演習の解き直しで、個数の非負条件を正の条件に読み替えてしまう場面です。片方を1個も使わない組合せは、総量の端に現れる大事な候補です。0を含むかどうかを先に定め、文字で表した総量について、解がある場合とない場合を同じ手順で判定しましょう。

総量が文字のとき、何を答えるのか

例えば4個入りと7個入りの箱を、それぞれ x 箱、y 箱使うとします。x、y は0以上の整数です。総数を N 個とすると、条件は 4x + 7y = N です。ここで N が与えられた数なら解の組を求められますが、N が文字なら、どの N で解が存在するかまで説明しなければなりません。

問いには、指定された総量について全組を求める型と、解が存在する総量を特徴づける型があります。さらに、ある値以上の総量なら必ず実現できることと、その境目の直前が実現できないことを両方示す型もあります。単に大きな数で数例を試しても、途中に穴がない証明にはなりません。

まず見るのは、変数が整数か、0を含むか、総量がどの範囲の整数かです。以下で自然数は1以上の整数とし、0を含む場合は非負整数と呼びます。個数という場面では、0箱を明示的に許すことが重要です。非負の和は負にならないので、負の総量には解がありません。この入口の確認は、計算に入る前に済ませます。

整数の区間に候補が入るか

一般に正の整数 a、b に対して ax + by = N を考えます。まず整数解が1組 (x₀, y₀) 見つかり、a と b が互いに素なら、整数解は整数 t を用いて次の形です。

x = x₀ + bt
y = y₀ - at

実際、代入すると増加分 abt と減少分 -abt が消えます。逆に別の整数解との差を u、v とすると au + bv = 0 です。a と b は互いに素なので b は u を割り、u = bt と書けます。これを戻すと v = -at です。したがって、この表示は漏れも余分もない整数解の表示です。

非負条件を加えると、x₀ + bt ≥ 0、y₀ − at ≥ 0 です。a、b は正なので、それぞれ t の下限と上限になり、区間を得ます。図1のように、その区間に整数が入るかが存在判定です。区間に実数が入るだけでは足りません。例えば 1/3 ≤ t ≤ 2/3 は空でない区間ですが、整数は含みません。

図1の両端の等号は、x または y が0になる候補を残すために必要です。下限が整数ならその値を採用し、整数でなければそれより大きい最小の整数を採用します。上限も同様に、それ以下の最大の整数へ直します。下限側の整数が上限側の整数以下なら解があり、逆ならありません。区間が一点だけの場合も、その点が整数なら解が1組あります。

a と b が互いに素でない場合には、この表示を無条件で使えません。共通の正の約数 d が N を割らなければ整数解は存在しません。d が N を割る場合には、式全体を d で割ってから係数が互いに素な式に直せます。割り算の前に整除条件を確かめるのは、存在しない解を作らないためです。

区間の両端が等しい場合、その共通値が整数なら1組であり、整数でなければ0組です。下限が上限より大きければ整数解もありません。反対に下限が上限より小さくても、その差が小さければ整数が入らないことがあります。不等式を解いた後、最後に整数を拾う段階を省けません。

総量の境界を述べるときは、すべての非負整数を対象にするのか、ある倍数に限るのかを明記します。小さい値の表は予想を立てる助けですが、表の最後より先の値には、そのままでは何も保証しません。先へ進む仕組みを示し、境界の直前の失敗も確かめます。

基本例題：余りごとに最小の総量を置く

【例題1・標準】N を非負整数とします。4個入りの箱を x 箱、7個入りの箱を y 箱使います。x、y は非負整数です。総数 N を実現できる条件を、N を4で割った余りごとに述べ、最小の境界から先はすべて実現できることを示してください。

7を4で割った余りは3です。y を4で割った余りを r として 0 ≤ r ≤ 3 と置くと、y = r + 4t です。y が非負整数であることから t は非負整数です。代入すると次のようになります。

N = 4x + 7(r + 4t)
N = 7r + 4(x + 7t)

よって N を4で割った余りが 7r を4で割った余りに等しいとき、その余りの中で実現できる総量は 7r 以上です。逆に、その余りで N ≥ 7r なら、y = r、x = (N − 7r)/4 は非負整数です。したがって必要条件だけでなく十分条件も得られます。

図2のように、r = 0、1、2、3 に対応する総量の余りは順に 0、3、2、1 です。余り0では0以上、余り1では21以上、余り2では14以上、余り3では7以上が条件です。例えば21は x = 0、y = 3 で実現でき、境界そのものを含みます。

この表から実現できない非負整数は、余り1の1、5、9、13、17、余り2の2、6、10、余り3の3です。余り0にはありません。最大の実現できない数は17で、18以上はすべて実現できます。18、19、20、21がそれぞれ実現でき、以後は4個入りを加えれば同じ余りの総量を4ずつ増やせる、と考えても証明できます。17が実現できない確認を欠くと、18が最小の境界だとは言えません。

この方法で大事なのは、余りの候補を並べるだけで終わらないことです。各余りで最小の y を選ぶと、残りは4の倍数として x で補えます。一方、4つ多い y は総量を28増やすため、最小値より小さい総量を作れません。非負性がこの下限の根拠です。

解の個数と境界をどう扱うか

【例題2・やや難】N を非負整数とします。5x + 8y = N を満たす非負整数の順序対 (x, y) がちょうど2組存在する N の条件を、N を5で割った余りを用いて述べてください。

まず r を 0、1、2、3、4 のうち、8r と N の差が5の倍数となる唯一の数とします。8r の余りは順に0、3、1、4、2なので、各余りに対応する r は確かに1つです。任意の解では y と r の差が5の倍数です。y ≥ 0 と 0 ≤ r ≤ 4 から、整数 t を用いて y = r + 5t、t ≥ 0 と書けます。

5x + 8(r + 5t) = N
5x = N - 8r - 40t
x = (N - 8r)/5 - 8t

ここで q = (N − 8r)/5 は整数です。x ≥ 0 は 8t ≤ q です。q < 0 なら候補はなく、q ≥ 0 なら t は0から q/8 以下の最大の整数まで動きます。ちょうど2組となるのは t = 0、1 が可能で t = 2 が不可能なときです。

8 ≤ q < 16
40 ≤ N - 8r < 80
8r + 40 ≤ N < 8r + 80

これが求める条件です。ただし r は N の余りから上で定めた値です。下端では t = 1 の x が0となるので含み、上端では t = 2 が新たに可能となるので含みません。例えば r = 0、N = 40 では (8, 0)、(0, 5) の2組です。原式に戻すとどちらも総量40です。N = 80 ではさらに (0, 10) が加わり、2組という条件から外れます。

別の見方では、y を5ずつ増やすと x は8ずつ減ります。非負の範囲に残る点の数を数える方法です。ただし、実数区間の長さだけを見て2組と断定することはできません。端点が整数かどうかで、同じ長さでも含まれる整数の個数が変わるからです。

【例題3・難】N を非負整数とします。6x + 9y = N を満たす非負整数 x、y が存在する N の条件を求め、存在する N のうち、以後の3の倍数がすべて実現できる最小の N を求めてください。

左辺は3の倍数なので、まず N が3の倍数である必要があります。N = 3M と置けば、M は非負整数で、式は次のようになります。

6x + 9y = 3M
2x + 3y = M

M が偶数なら y = 0、x = M/2 とできます。M が奇数なら、非負の奇数で最小の1は作れません。M ≥ 3 なら y = 1、x = (M − 3)/2 とできます。これらの x はいずれも非負整数です。したがって条件は、N が非負の3の倍数で、N ≠ 3 です。

実際、N = 0 では (0, 0)、N = 6 では (1, 0)、N = 9 では (0, 1) です。6以上の3の倍数は、対応する M が2以上なので実現できます。0から始めると次の3が実現できず、3自身も実現できません。よって求める最小の N は6です。3の倍数でない総量はどれほど大きくても作れないため、「すべての整数がある境界から実現できる」と言い換えてはいけません。

この例では共通因子を取り除いた後に偶奇を使いました。元の係数が互いに素でないまま、例題1と同じように余りが一巡すると考える方法は使えません。先に割り切れる条件を確認すれば、存在しない余りを調べ続ける失敗も避けられます。

0を消す誤答をどう直すか

例題1で「x > 0、y > 0 だから N = 21 は不可能」とした答案を考えます。確かに両方が正なら、21を作る組はありません。しかし問題は非負整数を指定しており、0を許しています。y = 3、x = 0 を代入すると 4・0 + 7・3 = 21 なので、元の条件を満たします。

図3のように、誤りの原因は不等号を厳しくしたことです。正の条件を用いた計算自体が正しくても、別の問題を解いたことになります。修正するときは、まず x ≥ 0、y ≥ 0 と書き、等号が成り立つ場合を残します。その後、得られた組を箱の個数と総数に戻して検査します。

逆に、実数の解があるだけで整数解があると結論するのも失敗です。例えば例題1の N = 1 では x = 1/4、y = 0 は実数として式を満たしますが、箱の個数にはできません。整数を含む区間か、余り別の最小値を確認してください。解がない場合にも、どの条件で候補が消えたかを説明すれば、調べ漏れとの違いが明確になります。

練習：存在しない場合も答える

次の各問で変数は非負整数、総量は非負整数とします。順序対を求める場合は (x, y) の順に書いてください。

1. 【標準】3x + 5y = 16 の非負整数解をすべて求めてください。
2. 【標準】4x + 9y = 11 に非負整数解があるか判定し、理由を示してください。
3. 【やや難】3x + 7y = N が解をもつ条件を、N を3で割った余りごとに示してください。
4. 【やや難】4x + 6y = N が解をもつ条件を求めてください。
5. 【難】2x + 5y = N の非負整数解がちょうど2組となる N の条件を、偶奇に分けて示してください。

練習の答えと道筋

1. y は 0 ≤ y ≤ 3 です。3x = 16 − 5y が3の倍数になるには y を3で割った余りが2です。この範囲では y = 2 で、x = 2 です。答えは (2, 2) です。戻すと 3・2 + 5・2 = 16 で、どちらも非負です。

2. y ≤ 1 なので y は0または1です。y = 0 では 4x = 11、y = 1 では 4x = 2 となり、どちらも整数 x はありません。したがって解はありません。候補の上限を先に出したので、2つの確認で尽くせています。

3. y を3で割った余り r は0、1、2です。7r を3で割った余りは r と同じです。y = r + 3t とすると t は非負整数で、N = 7r + 3(x + 7t) です。したがって余り0では N ≥ 0、余り1では N ≥ 7、余り2では N ≥ 14 が必要です。各条件の下で y = r、x = (N − 7r)/3 とすれば、元の総量に戻り十分です。

4. 左辺は偶数です。N = 2M と置いて 2x + 3y = M とします。M が偶数なら y = 0 で実現でき、奇数なら M ≥ 3 のとき y = 1 で実現できます。M = 1 は作れません。よって N は非負の偶数で N ≠ 2 です。構成した組を戻すとそれぞれ 4(M/2) = 2M、4((M − 3)/2) + 6 = 2M です。

5. y は N と同じ偶奇です。N が偶数なら y = 2t、x = N/2 − 5t です。ちょうど t = 0、1 が可能となる条件は 10 ≤ N < 20 です。N が奇数なら y = 1 + 2t、x = (N − 5)/2 − 5t です。ちょうど2組の条件は 15 ≤ N < 25 です。いずれも t は非負整数で、上端では t = 2 も可能となるため除きます。それぞれの式を元に戻すと 2x + 5y = N となり、条件内の2組はいずれも非負です。

答案に残す要点

• 非負整数は0を含み、正の整数とは区別します。
• 整数解を1つの整数パラメータで表し、非負条件から上下限を出します。
• 実数区間の有無ではなく、その中の整数の有無と個数を調べます。
• 余りごとの最小値を示し、構成した解を元の総量へ戻します。
• 境界の内側と外側を両方調べ、等号を検査します。

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

個別指導で答案を確かめるなら、まず0箱を許す理由を自分の言葉で説明できるかを見ます。次に、パラメータの区間を指して、その中の整数を実際に列挙してもらいます。端点を除いた理由が「いつも不等号を厳しくするから」なら、元の条件に戻って等号を調べ直します。

存在しないという答えには、候補の範囲を尽くした根拠が必要です。存在するという答えには、非負の整数の組を作り、元の総量に戻す確認が必要です。両方向の推論がそろうと、総量の境界が答案の中で明確になります。