2020年の数学ジュニアオリンピックで出題された問題12番は、1≦a<b<c<d≦9を満たす正の整数の組(a,b,c,d)について、a,b,c,dを一つずつ並べて作る4桁の整数24個がどれも7の倍数にならない組を求める問題です。ここでは、答えの(1,2,3,8)、(1,3,8,9)、(2,4,6,9)に至る解法を解説します。
ステップ1：問題の整理
まず、条件を整理します。
- 整数の順序：1≦a<b<c<d≦9
- 4桁整数を作る：a,b,c,dを並べ替えて24個の整数
- 7の倍数にならない：24個すべてが7の倍数でない
ポイントは、7の倍数チェックを効率よく行うことです。
ステップ2：7の倍数の判定の工夫
7の倍数かどうかを逐一計算するのは大変です。ここでは、mod7(7で割った余り)を利用します。4桁の整数を
a*1000+b*100+c*10+dとしたとき、10^k mod 7の周期性を利用できます。
- 10^1 ≡ 3 (mod7)
- 10^2 ≡ 2 (mod7)
- 10^3 ≡ 6 (mod7)
- 10^4 ≡ 4 (mod7)
これにより、4桁整数が7の倍数かどうかをmod7で判定できます。
ステップ3：候補の絞り込み
整数1～9の4つの組み合わせは合計9C4=126通りあります。それぞれをmod7でチェックし、どの組でも7で割り切れないものを抽出します。
この計算を効率的にするには、組の数の総和やmod7の分布を考慮して候補を絞り込むことができます。
ステップ4：最終的な答えの確認
計算の結果、24個すべての4桁整数が7で割り切れない組は以下の3つとなります。
- (1,2,3,8)
- (1,3,8,9)
- (2,4,6,9)
これらの組以外は、どれか1つ以上の並べ替えで7の倍数になる整数が存在します。
まとめ
この問題は、mod7による効率的な判定と組み合わせの絞り込みで解くことができます。計算を工夫することで、全通りを確認せずとも答えを導けます。最終的に求められる組は(1,2,3,8)、(1,3,8,9)、(2,4,6,9)の3つです。
コメント