この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

整数の性質の問題

難易度 5最難関大の二次・数学オリンピック予選レベル数学A 整数の性質

$0$ 以上の整数 $n$ に対して、方程式 $7 x + 11 y = n$ を満たす $0$ 以上の整数の組 $(x, y)$ の個数を $f (n)$ とする。 $f (n) = 3$ となる $0$ 以上の整数 $n$ は有限個である。それらすべての和を求めよ。

この問題で使うもの

1 次不定方程式の整数解（説明と入口の問題）
不定方程式の正の整数解の個数と選び出し（説明と入口の問題）
合同式（説明と入口の問題）

この問題を解けるようになるまで（23 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$n$ を $77$ だけ増やすと解の個数がどう変わるかを調べましょう。 $77 = 7 \cdot 11$ です。

ヒント 2

解 $(x, y)$ から $(x, y + 7)$ をつくる対応を考えると、 $f (n + 77) = f (n) + 1$ が示せます。また、 $0 ≦ r ≦ 76$ では $f (r)$ は $0$ か $1$ です。

ヒント 3

$n = 77 k + r$ とおくと $f (n) = k + f (r)$ です。 $f (n) = 3$ となるのは「 $k = 2$ かつ $f (r) = 1$ 」または「 $k = 3$ かつ $f (r) = 0$ 」のときです。 $7 x + 11 y ≦ 76$ を満たす組を数えて、 $f (r) = 1$ となる $r$ の個数を求めましょう。

答えと解説

答えを見る

17094

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

(i) $f (n + 77) = f (n) + 1$ であること

$n$ を $0$ 以上の整数とする。 $7 x + 11 y = n$ の $0$ 以上の整数解 $(x, y)$ に対し、 $(x, y + 7)$ は $7 x + 11 y = n + 77$ の $0$ 以上の整数解である。この対応は異なる解を異なる解に移す。 $7 x + 11 y = n + 77$ の $0$ 以上の整数解のうち、こうして得られないのは $0 ≦ y ≦ 6$ のものだけである。

$7 x + 11 y = n + 77$ の 2 つの整数解 $(x_{1}, y_{1}), (x_{2}, y_{2})$ について、 $7 (x_{1} - x_{2}) = - 11 (y_{1} - y_{2})$ である。 $7$ と $11$ は互いに素なので $y_{1} - y_{2}$ は $7$ の倍数になる。よって $0 ≦ y ≦ 6$ を満たす解は高々 $1$ つである。

一方、 $11 y \equiv n + 77 (mod 7)$ を満たす $y$ で $0 ≦ y ≦ 6$ のものはちょうど $1$ つある（ $11 \equiv 4$ は $7$ を法として逆数をもつ）。この $y$ について $x = \frac{n + 77 - 11 y}{7}$ は整数であり、 $11 y ≦ 66 < 77$ より $x > 0$ である。したがって $0 ≦ y ≦ 6$ の解はちょうど $1$ つ存在し、 $f (n + 77) = f (n) + 1$ が成り立つ。

(ii) $0 ≦ r ≦ 76$ のとき $f (r) ≦ 1$ であること

$7 x + 11 y = r$ の 2 つの異なる $0$ 以上の整数解があるとする。(i) と同様に $x$ の差は $11$ の倍数なので、一方の解では $x ≧ 11$ である。すると $r ≧ 7 \cdot 11 = 77$ となり矛盾する。よって $f (r) \in {0, 1}$ である。

以上より、 $n = 77 k + r$ （ $k ≧ 0$ , $0 ≦ r ≦ 76$ ）と表すと $f (n) = k + f (r), f (r) \in {0, 1}$ となる。

(iii) $f (r) = 1$ となる $r$ （ $0 ≦ r ≦ 76$ ）の個数

(ii) より、このような $r$ は $7 x + 11 y ≦ 76$ を満たす $0$ 以上の整数の組 $(x, y)$ と $1$ 対 $1$ に対応する。 $y$ ごとに $x$ の個数を数える。
- $y = 0$ ： $7 x ≦ 76$ より $0 ≦ x ≦ 10$ で $11$ 個
- $y = 1$ ： $7 x ≦ 65$ より $0 ≦ x ≦ 9$ で $10$ 個
- $y = 2$ ： $7 x ≦ 54$ より $0 ≦ x ≦ 7$ で $8$ 個
- $y = 3$ ： $7 x ≦ 43$ より $0 ≦ x ≦ 6$ で $7$ 個
- $y = 4$ ： $7 x ≦ 32$ より $0 ≦ x ≦ 4$ で $5$ 個
- $y = 5$ ： $7 x ≦ 21$ より $0 ≦ x ≦ 3$ で $4$ 個
- $y = 6$ ： $7 x ≦ 10$ より $0 ≦ x ≦ 1$ で $2$ 個
- $y ≧ 7$ ： $11 y ≧ 77$ となるので $0$ 個

合計は $11 + 10 + 8 + 7 + 5 + 4 + 2 = 47$ 個である。よって $f (r) = 1$ となる $r$ は $47$ 個、 $f (r) = 0$ となる $r$ は $77 - 47 = 30$ 個ある。

(iv) $f (n) = 3$ となる $n$

$k + f (r) = 3$ となるのは次の 2 つの場合である。
- $k = 2$ かつ $f (r) = 1$ ： $n = 154 + r$ で、 $47$ 個
- $k = 3$ かつ $f (r) = 0$ ： $n = 231 + r$ で、 $30$ 個

$k ≧ 4$ では $f (n) ≧ 4$ 、 $k ≦ 1$ では $f (n) ≦ 2$ である。よって条件を満たす $n$ は有限個である。

各 $r$ （ $0 ≦ r ≦ 76$ ）はどちらか一方の場合にちょうど $1$ 回ずつ現れる。したがって求める和は
$154 \cdot 47 + 231 \cdot 30 + r = 0 \sum 76 r = 7238 + 6930 + \frac{76 \cdot 77}{2} = 7238 + 6930 + 2926 = 17094$
である。

別解

$7 x + 11 y = n$ の解 $(x, y)$ について、 $7$ を法として $4 y \equiv n$ より $y \equiv 2 n (mod 7)$ である。そこで $y_{0} \in {0, 1, \dots, 6}$ を $y_{0} \equiv 2 n (mod 7)$ となる数とすると、解は $y = y_{0} + 7 k$ と書ける。

このとき $n - 11 y_{0}$ は $7$ の倍数なので、 $n - 11 y_{0} = 7 t$ とおく。解が存在するには $t \geq 0$ が必要である。

$y = y_{0} + 7 k$ のとき $x = t - 11 k$ となる。 $x \geq 0$ かつ $k \geq 0$ なので、 $0 \leq k \leq ⌊ t /11 ⌋$ である。よって $f (n) = ⌊ t /11 ⌋ + 1$ （ $t \geq 0$ のとき）。

$f (n) = 3$ となるのは $⌊ t /11 ⌋ = 2$ 、すなわち $22 \leq t \leq 32$ のときである。

したがって $n = 11 y_{0} + 7 t$ （ $y_{0} = 0, \dots, 6$ 、 $t = 22, \dots, 32$ ）。 $n$ から $y_{0}$ と $t$ が一意に決まるので、この $7 \times 11 = 77$ 個の $n$ はすべて異なる。

和を求める。
- $\sum 11 y_{0}$ の部分： $11 \times (0 + 1 + \dots + 6) \times 11 = 11 \times 21 \times 11 = 2541$
- $\sum 7 t$ の部分： $7 \times (22 + \dots + 32) \times 7 = 7 \times 297 \times 7 = 14553$

合計は $2541 + 14553 = 17094$ 。

検算：最小の $n = 7 \cdot 22 = 154$ について、 $154 = 7 \cdot 22 = 7 \cdot 11 + 11 \cdot 7 = 7 \cdot 0 + 11 \cdot 14$ なので $(22, 0), (11, 7), (0, 14)$ の $3$ 個。 $f (154) = 3$ で一致する。

整数の性質の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題