範囲で絞る（不等式評価で有限化）
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
整数問題の手段は合同式・因数分解・評価の3つで、このうち評価は最も発想を要求する。やっていることは単純で、無限にある候補を不等式で有限個に閉じ込め、あとは全部調べるだけである。鍵になるのは、対称性のある方程式で『a ≦ b ≦ c としてよい』と大小を仮定し、最も小さい文字の上界を出すこと。この一言を置くかどうかで、調べる場合の数が数十分の一になる。逆にこれを置かないと、いつまでも場合が減らずに手が止まる。
こんなときに使う
- 1/x + 1/y + 1/z = 1 のような分数の和が整数 → 大小を仮定して最小の文字を絞る
- 『自然数解をすべて求めよ』で、因数分解も合同式も効かない
- 式が対称式（文字を入れ替えても変わらない）→ 大小関係を仮定してよい
- 『〜を満たす組は有限個であることを示せ』→ 評価そのものが答え
- 文字の一つが極端に大きいと成り立たない構造が見える → 上界が取れる
手順
- 1. 対称性があれば a ≦ b ≦ c と仮定する（一般性を失わない、と根拠つきで書く）
- 2. 最小の文字に注目し、不等式で上界を出す（最小のものが最も大きく効くことを使う）
- 3. 有限個に絞れたら、各値について全部調べる
- 4. 各場合で残りの文字を決定する
- 5. 最後に仮定を外し、並べ替えをすべて書き出す
例題
1/x + 1/y + 1/z = 1 を満たす自然数の組 (x, y, z) をすべて求めよ。
解答
- 式は x, y, z について対称なので、x ≦ y ≦ z としてよい（最後に並べ替えを考える）。
- 【x の範囲を絞る】
- x ≦ y ≦ z より 1/x ≧ 1/y ≧ 1/z だから、1 = 1/x + 1/y + 1/z ≦ 3/x。よって x ≦ 3。
- また 1/x < 1 が必要（他の項が正なので）だから x ≧ 2。∴ x = 2 または 3。
- 【x = 2 のとき】1/y + 1/z = 1/2。
- y ≦ z より 1/2 ≦ 2/y、よって y ≦ 4。また 1/y < 1/2 より y > 2。∴ y = 3 または 4。
- y = 3 → 1/z = 1/2 - 1/3 = 1/6、z = 6
- y = 4 → 1/z = 1/2 - 1/4 = 1/4、z = 4
- 【x = 3 のとき】1/y + 1/z = 2/3。
- y ≦ z より 2/3 ≦ 2/y、よって y ≦ 3。また y ≧ x = 3。∴ y = 3。
- 1/z = 2/3 - 1/3 = 1/3、z = 3
- ∴ x ≦ y ≦ z のもとで (x,y,z) = (2,3,6), (2,4,4), (3,3,3)
- 一般には、これらの並べ替えがすべて解。
- 検算：1/2+1/3+1/6 = 3/6+2/6+1/6 = 1 ○ 1/2+1/4+1/4 = 1 ○ 1/3×3 = 1 ○
別解・ほかの見方
- 因数分解で閉じ込める：1/x + 1/y = 1/n を (x-n)(y-n) = n² の形に変形すると、約数を調べるだけで済む
- 合同式で候補を減らしてから評価する（3手段は排他的ではなく、組み合わせて使う）
- 上界を出す不等式は複数ある。緩い評価だと調べる場合が増えるので、できるだけ強い評価を選ぶ
- 無限降下法：評価で最小の解を取り、そこからより小さい解を作って矛盾を出す
落とし穴
- 大小の仮定を置かず、場合が無限に増えて手が止まる（この単元の失敗のほぼ全て）
- 『一般性を失わない』と書ける根拠（式の対称性）を確認せずに使う
- 最後に並べ替えを書き忘れ、解を数え落とす
- 不等号の向きを取り違える（最小の文字だから 1/x が最大、という対応を間違える）
- 等号成立の場合（y = z など）を重複して数える
- 大小関係の仮定（対称性の利用）を置かずに無限に場合が増える
なぜ大事か
整数問題の三大手段（合同・因数分解・評価）の最後。東大はここを試す
東大での出方
東大の整数は誘導が薄く、3手段のどれを使うかの選択から問われる。評価は最も発想を要するため差がつきやすい。単独の大問として出るほか、確率や数列との融合問題で『有限個であること』を示す部分に埋め込まれることもある。
確認問題
- 1/x + 1/y = 1/3 を満たす自然数の組をすべて求めよ（因数分解でも評価でも解けるので、両方試すこと）
- x ≦ y ≦ z を満たす自然数で xyz = x + y + z となるものをすべて求めよ
- 上の問題で、大小の仮定を置かずに解こうとするとどうなるか試してみよ
発展
評価と無限降下の組み合わせ。『解が存在するとすれば、より小さい解が必ず作れる』という構造を見つけると、自然数の整列性から矛盾が出る。x²+y²=3z² の非存在証明がその典型。
前提になるノード
このノードを前提にするノード
「整数」のノード
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。