回 8-2 分野 8 考え方
偶奇 (ぐうき) は、整数が偶数か奇数かという性質です。偶奇で考えるとは、数が偶数か奇数かだけを見て、操作の前後で変わらない性質を探すことです。表のコイン 7 枚 を、1 回 に 2 枚 ずつ裏返して全部裏にすることはできません。1 回 の操作で表の枚数は 2 増えるか 2 減るか変わらないので、表の枚数が奇数のまま、0 (偶数) にはならないからです。
偶数と奇数の計算の決まりから、変わらない量を使って「できない」を示す考え方まで、全部の場合を 数えて確かめます。
文 ゆめさくコード編集部 公開 2026年10月30日 更新 2026年10月30日 出典を確かめた日 2026年10月30日
2 できません。何回試しても、何通りの順で裏返しても、全部裏にはなりません。
7 枚 のコインが全部表で並んでいます。1 回 の操作では、好きな 2 枚 を選んで、両方を裏返します (表は裏に、裏は表に)。これを繰り返して全部を裏にできるかを考えます。
試す順は無数にあるので、試して「できなかった」を積み上げても、できない理由にはなりません。ここで効くのが、数が偶数か奇数か (偶奇、英語ではパリティ) だけを見る考え方です。操作の前後で変わらない量を見つけると、探さずに「できない」と言えます。
偶奇の 偶数と 偶数は 2 で割り切れる整数、奇数は 2 で割ると 1 余る整数です。0 も偶数です。足し算と掛け算の偶奇は、元の数の偶奇だけで決まります。
計算 偶数と偶数 偶数と奇数 奇数と奇数 足し算、引き算 偶数 奇数 偶数 掛け算 偶数 偶数 奇数
表から、2 つ の整数の和と差は、いつも同じ偶奇になることも分かります。a − b = (a + b) − 2b で、2b は偶数なので、偶数を引いても偶奇は変わらないからです。隣り合う 2 つ の整数は、片方が偶数で片方が奇数です。奇数を足すたびに偶奇が入れ替わり、偶数を足しても偶奇は変わりません。だから、整数をいくつ足しても、和の偶奇は「奇数がいくつ入っているか」の偶奇で決まります。
変わらない 操作を何回しても変わらない量を、不変量と呼びます。不変量が見つかれば、始めと目標で不変量が違うとき、目標には届かないと言えます。
コインの問題では、表の枚数の偶奇が不変量です。2 枚 を裏返すとき、選んだ 2 枚 の組み合わせで表の枚数は次のように変わります。
選んだ 2 枚 表の 偶奇 表と表 2 減る 変わらない 裏と裏 2 増える 変わらない 表と裏 変わらない 変わらない
始めは表が 7 枚 (奇数)、目標は 0 枚 (偶数) です。偶奇が変わらない操作だけでは、奇数から偶数には移れません。
色を 8 × 8 の盤から、向かい合う 2 つ の角を除いた 62 マスを、1 × 2 のドミノ 31 枚 で敷き詰められるかを考えます。盤を市松模様に塗ると、ドミノ 1 枚 は必ず白 1 マスと黒 1 マスを覆います。向かい合う角は同じ色なので、残りは一方の色が 32 マス、他方が 30 マスです。31 枚 で両方の色を 31 マスずつ覆う必要があるので、敷き詰められません。
数ではない物も、色を塗ったり 0 と 1 を割り当てたりすると、偶奇で考えられます。
ビットの 整数を 2 進数で書くと、一番右の桁 (最下位ビット) は、偶数なら 0、奇数なら 1 です。だから x & 1 (最下位ビットだけを取り出す計算) で偶奇が分かります。2 進数の桁の重みは CS 1-1 で扱います。
動かして確かめる 1 本 目は、コインの問題を全部の状態で調べます。表と裏を 1 と 0 で表すと、7 枚 の並びは 2^7 = 128 通りです。全部表の状態から、操作でたどり着ける状態を、幅優先探索 (近い所から順に広げる探し方) で全部数えます。
動かす 2 枚ずつ裏返す全部の状態
実行すると、次の通りに出ます
届く状態 64
全部裏 False
表の数がどれも奇数 True届く状態は 128 通りの半分の 64 通りで、どれも表の枚数が奇数でした。全部裏 (表 0 枚 ) は入っていません。表の枚数の偶奇という不変量が、全部の場合を数えた結果と合います。
2 本 目は、コインが 6 枚 のときです。始めの表の枚数が偶数になるので、結果が変わるかを確かめます。
動かす 6 枚なら全部裏にできるか
実行すると、次の通りに出ます
6 枚 3
7 枚 None6 枚 なら 3 回 で全部裏にでき、7 枚 では届きません (None は届かないという意味)。不変量は「できない」を示す道具で、偶奇が合っているときに「できる」までは言いません。6 枚 で届くことは、実際に手順 (2 枚 ずつ 3 回 ) を作って確かめます。
3 本 目は、ドミノの問題の色の数を数えます。マス (r, c) の色を (r + c) の偶奇で決めます。
動かす 角を除いた盤の色を数える
実行すると、次の通りに出ます
マス 62
白 30 黒 32
要るのは白黒 31 ずつ白が 30、黒が 32 で、ドミノ 31 枚 で覆うには白黒が 31 ずつ要ります。色の数が合わないので、敷き詰めはできません。
4 本 目は、偶奇の判定の書き方と、負の数での違いです。
動かす 偶奇の判定と負の数
実行すると、次の通りに出ます
6 0 0
7 1 1
0 0 0
-3 1 1
0b1011001 1 の数 4 偶奇 0
0b1011000 1 の数 3 偶奇 13 % 2 は 1 で、x & 1 と同じ答えです。最後の 2 行 は、7 ビットのデータに含まれる 1 の数の偶奇 (パリティ) です。1 ビットだけ変わると、パリティが入れ替わります。
偶奇で 言語に % は、割る数と同じ符号の余りを返すので、-3 % 2 は 1 です。C (C99 以降)、 % は、割られる数と同じ符号の余りを返すので、-3 % 2 は -1 になります。これらの言語で x % 2 == 1 と書くと、負の奇数を奇数と判定しません。x % 2 != 0 か、2 の補数で整数を持つ言語なら x & 1 と書くと、負の数でも外れません。
偶奇が 不変量が合っていることは、届くための必要条件にすぎません。15 パズル (4 × 4 の枠で 15 枚 の札を滑らせる遊び) は、並びの偶奇が合わない配置には届かないことが知られています。けれど偶奇が合う配置に本当に届くことは、偶奇とは別に示す必要があります。
パリティビットは 送るデータに、1 の数を偶数 (または奇数) にそろえる 1 ビット (パリティビット) を足すと、1 ビットの誤りは見つかります。けれど 2 ビットが同時に変わると、1 の数の偶奇は元に戻るので見逃します。誤りを直したり、多くの誤りを見つけたりするには、CRC やハミング符号のような別の方法を使います。
仕事と 偶奇で考える場面は、次の通りです。
誤りの検出。通信や記憶のパリティビットは、1 の数の偶奇で 1 ビットの誤りを見つける できない証明。パズルやゲームで「この状態には絶対に届かない」を、全部を探す前に言える。コーディングテストで、答えが -1 (不可能) になる場合を見分けるのに効く グラフ。どのグラフでも、頂点の次数 (つながる辺の数) の合計は辺の数の 2 倍で偶数になる。だから次数が奇数の頂点は偶数個ある (分野 6 のグラフの回で扱う予定) 並べ替え。2 つ の要素を入れ替える操作は、並びの偶奇 (置換の偶奇) を毎回入れ替える。ある並びに何回の入れ替えで届くかの偶奇は決まっている 表示。表の行を交互に色分けするときの i % 2、交互に処理を振り分けるときの偶奇 よくある問い 偶奇とは何ですか 整数が偶数か奇数かという性質です。2 で割った余りが 0 なら偶数、1 なら奇数です。英語ではパリティ (parity) と呼び、パリティビットのパリティも同じ意味です。
0 は 偶数です。0 は 2 × 0 で、2 で割り切れます。プログラムでも 0 % 2 は 0、0 & 1 も 0 です。
不変量は 操作を 1 回 したとき、何が変わって何が変わらないかを表にします。数そのものが変わっても、その偶奇、合計、余りなどは変わらないことがあります。コインなら、表の枚数は変わっても、偶奇は変わりませんでした。
偶奇の どちらでも同じ答えです。C、負の数の余りが -1 になるので、x % 2 == 1 は負の奇数で外れます。x % 2 != 0 と書けば、どの言語でも負の数を含めて奇数を判定できます。
確認クイズ 答えだと
1 問目
1 から 100 までの整数を全部足した和の偶奇はどれですか。
ア 偶数。 イ 奇数。 ウ 偶数。 エ 決められない 2 問目
黒板に 1 から 10 までの整数が 1 つ ずつ書いてあります。2 つ の数を消して、その和を 1 つ 書く操作を 9 回 すると、最後に 1 つ 残ります。残る数の偶奇はどれですか。
3 問目
-5 % 2 を計算すると、どの値になりますか。
説明課題 「全部表の 7 枚 のコインを、2 枚 ずつ裏返して全部裏にできない理由」を、不変量という言葉を使って 3 文で説明してください。書いたら、下の模範解答を開いて比べてください。
あなたの説明
模範解答 模範解答を開く 自分の
2 枚 を裏返す操作では、表の枚数は 2 減るか、2 増えるか、変わらないかのどれかなので、表の枚数の偶奇は変わらない不変量になる。始めは表が 7 枚 で奇数、全部裏は表が 0 枚 で偶数なので、偶奇が違う。偶奇の変わらない操作をいくら繰り返しても、奇数から偶数には移れないので、全部裏にはできない。
「何回試しても
もっと深く この
一次資料 どれも 2026年 10月 30日 に開いて、題と中身を確かめました。
