
武蔵野個別指導塾の特徴
共通テスト情報I 処理結果の一致と反例—一つの入力で同じ二処理を別の条件で見分ける|武蔵野個別指導塾

正数の列で一致した2種類の合計を負数で比べ、主張を崩す反例を探しましょう。
よくあるのは、高校生が記録の列を2種類の手順で集計し、たまたま同じ数が出たので、どんな列でも同じ結果になると考える場面です。例えば、全部の値を足す手順と、正の値だけを足す手順は、記録がすべて正なら区別できません。記録に負の値が入ったときも同じでしょうか。
ここでは整数の列を使い、2つの合計の違いを調べます。数値や場面はすべて自作の条件です。1回の一致を根拠に広い範囲を断定せず、どの入力で何が起きるかを追います。扱うのは処理とその結果であり、実際の調査結果ではありません。
一致を問う問題の型
1つ目は、同じ入力に2つの処理を適用し、それぞれの出力を求める型です。途中で同じ値になったとしても、最後の要素まで両方を追います。出力するのは繰返しが終わった後の合計であり、途中の合計ではありません。
2つ目は、「指定された範囲の入力なら常に結果が一致する」という主張の真偽を問う型です。すべての入力について述べた主張を否定するには、指定範囲内で結果が異なる入力を1つ示せば足ります。その入力が反例です。逆に、いくつかの入力で一致しただけでは、残りの入力でも一致することは示せません。
3つ目は、一致する条件を考える型です。値が全部正なら、どの値も2つの手順で足されます。ただし、正の値だけという条件は一致のための十分な条件であって、唯一の条件とは限りません。0が混ざっても、その値を足すか足さないかによって合計は変わらないからです。
試験の独自表記を読む際には、その問題に記された命令や添字の決まりを使います。以下はPythonで表した自作の手順です。別の表記でも同じ起点や端の扱いだと決めつけず、問題の説明に戻ってください。
足される値と足されない値
手順Aは列の全要素を足します。手順Bは値が0より大きい場合だけ足します。どちらも合計の初期値は0で、左から右に1要素ずつ調べ、最後に合計を出します。列の添字は0から始まり、長さがnなら最後の添字はn-1です。空の列には要素がなく、どちらも初期値0を出力します。
図1のように、正の値は両方に入ります。0はAに入ってBには入らないものの、足しても合計を変えません。負の値はAの合計を減らし、Bには入りません。したがって、整数の列では負の値が1つでもあれば、Aの結果はBより小さくなります。負の値同士が互いに打ち消し合うことはありません。

一般に、Aの結果はBの結果に、列中の負の値をすべて足した結果を加えたものです。0は差に影響しません。負の値がなければ差は0で一致し、1つでもあれば差は負です。ここでの結論は整数の列、初期値0、示した加算処理に限ります。別の初期値や別の判定条件まで同じと考えることはできません。
反例を探すときは、まず主張の対象を読みます。「正の整数だけを含む列」に負数を入れても、対象外なのでその主張の反例にはなりません。「整数の列」とあれば、負数を含む列も試せます。空の列が許されるか、出力は合計か途中経過かも確かめます。結果を比べる際に、片方だけ別の入力を使うと、処理の違いを検証できません。
基本例題:正の記録で一致した後
ある装置の増減を表す記録の列を、左から順に集計します。列は [3, 2, 4] です。全値の合計Aと、正の値だけの合計Bを整数で答え、繰返しの各回の判定と更新を示してください。添字0から末尾まで調べ、2つの合計はともに0から始めます。次のプログラムでは data が記録、a と b がそれぞれAとB、x がその回の値です。
data = [3, 2, 4]
a = 0
b = 0
for x in data:
a = a + x
if x > 0:
b = b + x
print(a, b)
| 時点 | x | x > 0 | Aの更新 | Bの更新 |
|---|---|---|---|---|
| 開始前 | なし | 未判定 | 0 | 0 |
| 添字0の処理後 | 3 | 真 | 0から3 | 0から3 |
| 添字1の処理後 | 2 | 真 | 3から5 | 3から5 |
| 添字2の処理後 | 4 | 真 | 5から9 | 5から9 |
| 終了後 | なし | 未判定 | 9 | 9 |
最初の回では3をAに足し、3が正なのでBにも足します。次は2をそれぞれに足し、最後は4をそれぞれに足します。図2のように、両方の経路が各値を受け取るため、終了後の出力は 9 9 です。記録に戻しても、3、2、4の全値が正なので、正の値の合計も全値の合計も9です。

ただし、この表はこの列の結果を示しただけです。Bの条件が偽になる回はありません。条件が偽になる入力でBの更新が省かれたとき、Aと差が生じるかを別に調べる必要があります。
標準例題:0を入れたら反例になるか
記録を [5, 0, 1] とし、同じAとBを使います。終了後の合計をそれぞれ整数で答え、0の回が反例になるか説明してください。初期値と走査順は基本例題と同じです。
| 処理した添字 | 値 | 条件 | A | B |
|---|---|---|---|---|
| 開始前 | なし | 未判定 | 0 | 0 |
| 0 | 5 | 真 | 5 | 5 |
| 1 | 0 | 偽 | 5 | 5 |
| 2 | 1 | 真 | 6 | 6 |
答えはAもBも6で、この列は結果の不一致を示す反例ではありません。0の回にAは0を足し、Bは何も足しません。実行した命令には違いがあっても、その回の合計は両方5のままです。全値を足す目的なら0を含めた合計は6であり、正の値5と1だけを足しても6です。目的に照らしても両方の答えは合っています。
「判定が偽になる」と「出力が異なる」は別の事柄です。処理の経路が違っても、指定された出力が同じになる場合があります。もし出力に加算した回数も含める別の問題なら、0の回はその回数に差を作ります。何を結果として比較するかによって、反例かどうかが変わります。
発展例題:負の記録を含む列
列を [6, -2, 3] とします。AとBの終了後の整数を求め、最初に合計が異なる添字を答えてください。全値の合計を求める目的に合うのはどちらかも判断します。
| 処理した添字 | 値 | 条件 | A | B |
|---|---|---|---|---|
| 開始前 | なし | 未判定 | 0 | 0 |
| 0 | 6 | 真 | 6 | 6 |
| 1 | -2 | 偽 | 4 | 6 |
| 2 | 3 | 真 | 7 | 9 |
最初の食い違いは添字1です。Aは-2を足して4、Bは条件が偽なので6のままです。次に両方へ3が足され、終了後はAが7、Bが9です。全値の合計は6から2を引いて3を足した7なので、全値の合計という目的に合うのはAです。正の記録だけの合計を求める目的ならBの9が合います。同じ出力を求める問題か、異なる目的の集計を比較する問題かを区別します。
この列から、負数の影響だけを残して短くすると [-2] です。Aは-2、Bは0を出すので、整数の列全体に対して常に一致するという主張の反例になります。空の列は両方0なので反例になりません。要素数という尺度では、負数1個の列が最小です。どの負数を選んでも反例になりますが、数値の大きさについて唯一の最小例があるという意味ではありません。
誤答を最初の差から直す
「正の列で同じ9だったから、どんな整数列でも同じ」という答えは、入力の範囲を広げたところに飛躍があります。基本例題の結果自体は正しいものの、正でない値を処理した証拠にはなりません。図3のように、負数1個を同じ入力として2つの処理へ渡すと、最初の回から差が現れます。

| 読み方 | [-2] のA |
[-2] のB |
判定 |
|---|---|---|---|
| どの整数列でも一致するという予想 | -2 | -2と予想 | 一致と誤答 |
| 条件を実際に追う | -2 | 0 | 不一致 |
原因は、Aに足した値をBにも必ず足すと考えたことです。修正すると、Bでは -2 > 0 が偽なので加算を実行せず、初期値0が残ります。Aが全値の合計、Bが正の値の合計という仕様なら、プログラムの一方を変える必要はありません。誤りは2つの仕様が常に同じだという主張です。
反対に、両方で全値の合計を求めることが目的なら、Bの条件を取り除いて各値を足す修正が必要です。その場合も正の列だけでは修正の効果を区別できません。負の列で修正前後を比べ、0や空の列でも初期値と出力を確認します。目的が正の値だけの合計なら、Aの側に正の値の判定を設けます。目的を先に決めてから、どの処理を直すか選びます。
条件を変えるときの確認
反例を作る操作では、何を固定し、何を変えたかが重要です。基本例題から負の値を含む列へ変えるとき、2つの初期値、走査順、出力時点はそのままにします。両処理に異なる列を渡したり、片方だけ途中で出力したりすると、差が入力や時点の違いから生じた可能性を除けません。1つの列を共通に使い、各回の値と条件を揃えて比べます。
また、反例を見つけた後も、主張のどの部分を否定したかに注意します。負数の列は「整数列ならいつも一致する」を否定しますが、「正数だけなら一致する」を否定しません。後者では各要素が両方に加わるので、初期値が同じなら各回の終了時にも同じ合計が残ります。0を許す範囲まで広げても、0を足すことは合計を変えないため、この一致は保たれます。負数を許すところで初めて、出力の一致が崩れる入力が可能になります。
練習:5つの入力を比べる
以下もすべて自作の整数列です。Aは全値を、Bは正の値だけを足し、初期値はともに0とします。添字は0から始め、左から末尾まで処理した後に合計を出します。各問の答えを求めた後、記録の意味に戻して確かめてください。
- 棚の移動量が
[7, 8]です。AとBの出力をそれぞれ整数で答えてください。 - 水位の変化が
[0]です。AとBの出力を答え、この列が両出力の一致を否定する反例か答えてください。 - 温度の変化が
[-4]です。AとBの出力と、両出力が初めて異なる添字を答えてください。 - 傾きの記録が
[2, -5, 10]です。AとBの出力を求め、全値の合計という目的に合う方を答えてください。 - 空の記録列
[]を処理します。AとBの出力を答え、整数列なら常に一致するという主張への反例になるか答えてください。
解答と追跡
-
AもBも15です。7を処理した後は両方7、8を処理した後は両方15です。棚の2つの移動量はどちらも正なので、全値の合計と正の値の合計に同じ2つが入ります。
-
AもBも0で、反例ではありません。Aは0を足し、Bは条件が偽なので足しませんが、どちらも0のままです。水位変化の全値は0で、正の値はありません。足す対象がないBも初期値0を出します。
-
Aは-4、Bは0で、最初に異なる添字は0です。Aは変化-4を合計に反映し、Bは正ではないので反映しません。温度の変化を全部足すと-4ですから、0を全値の合計とすることはできません。この1要素は、整数列全体を対象とする常時一致の反例です。
-
添字0の後はAもBも2、添字1の後はAが-3、Bが2、添字2の後はAが7、Bが12です。全値の合計は2から5を引き10を足した7なので、目的に合うのはAです。Bの12は正の記録2と10の合計としては正しい値です。
-
AもBも0で、反例ではありません。処理する要素がないので、条件の判定も加算も行わず、初期値を出します。空の記録に含まれる値はないため、ここで定めた初期値0が両方の結果です。空の入力で一致することも、負数を含む別の列の不一致を否定しません。
覚えておくこと
- 1つの入力での一致は、すべての入力での一致を意味しません。
- 反例は主張の入力範囲に入り、主張に反する結果を示す入力です。
- 0は加算の有無が違っても合計を変えません。
- 負数があれば全値の合計は正の値だけの合計より小さくなります。
- 出力の意味と目的を照らして修正先を決めます。
どこで判断がずれたか
お子さまが「同じ」と答えたときは、まずその言葉が1つの列についてなのか、許されたすべての列についてなのかを、解答の根拠とともに確かめます。次に追跡表の条件の真偽欄と、更新前後のAとBの欄を見ます。偽の回でもBを更新していれば条件の読み違い、0で出力が変わるとしていれば加算の影響の読み違いです。
個別指導では、同じ入力を両処理に渡したか、最初の差をどの行に記したか、出力を目的に戻したかを確かめます。正の列、0を含む列、負数1個の列を順に比べると、実行経路の違いと出力の違いを分けて説明できます。反例の強さは、短さだけでなく、主張の範囲に入り、異なる結果を実際に示していることにあります。
もう「日東駒専」を目標にしないでください。
武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。
まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。
本気になった日が、入塾の日。
お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。
電話は年中無休。365日、24時間、お電話可能。



