AMC day25の問題だけ

196

この記事の内容

この記事は Advent Math Calendar2022 の $25$ 日目の記事として書いた組み合わせ典型(主客転倒, 包除原理, 二項係数etc) の問題のみを抜き出した記事です. 例題, 演習問題等を全ていっしょくたにしているので難易度のばらつきは激しいです.
記事の内容より先に問題だけチャレンジしてみたいという方はご活用ください.

また, さらにこの中から抜き出した $6$ 問は google form で解答が可能です.
コンテストっぽく問題を解きたい方は是非チャレンジしてみてください.

問題

例題

$\sum_{i = 1}^{1000} \sum_{j = 1}^{1000} \frac{1}{1000 - | i - j |}$
を計算してください.

解答

\begin{aligned} \sum_{i = 1}^{1000} \sum_{j = 1}^{1000} \frac{1}{1000 - | i - j |} \\ = \sum_{k = 0}^{999} \frac{1}{1000 - k} \times (| i - j | = k の登場回数) \\ = \frac{1000}{1000} \+ \sum_{k = 1}^{999} \frac{2 \times (1000 - k)}{1000 - k} \\ = 1 + \sum_{k = 1}^{999} 2 \\ = 1999 \end{aligned}

例題

正整数 $n$ に対し, $10000$ を $n$ で割った余りを $M (n)$ , $n$ の正の約数の総和を $S (n)$ とします.
$\sum_{n = 1}^{10000} (M (n) + S (n))$ を求めてください.

解答

\begin{aligned} \sum_{n = 1}^{10000} S (n) & = \sum_{n = 1}^{10000} \sum_{m = 1}^{10000} (n & = \sum_{m = 1}^{10000} \sum_{n = 1}^{10000} (n & = \sum_{m = 1}^{10000} m ⌊ \frac{10000}{m} ⌋ \\ = \sum_{m = 1}^{10000} m \frac{10000 - M (m)}{m} \\ = 10^{8} - \sum_{m = 1}^{10000} M (m) \end{aligned}

よって求める答えは

10^{8}

OMC095-E

　 $272$ 項からなる整数列 ${a_{i}}_{i = 1, \dots, 272}$ のスコアを以下で定めます.
$\sum_{i = 1}^{256} | a_{i} - a_{i + 16} |$
$1, 2, \dots, 272$ を並べ替えてできる整数列は $272!$ 通り考えられますが, それらのスコアの平均値を求めてください.
　ただし, この平均値は整数値になることが証明できます.
問題へのリンク

ヒント

問題文の素直に解釈すると, 各数列に対して

256

個の値の総和を求める→全ての数列に対してスコアの総和を求める
という流れになります. 足す順番を変えましょう.

解答

こちらをご覧ください(OMC上の解説)

OMC079-D

　正整数 $N$ が増加的であるとは， $N$ を $10$ 進法で表記した際に各位の数が上位から狭義単調増加となることをいいます．例えば， $157$ や $5$ は増加的ですが， $804$ や $421$ や $334$ は増加的ではありません．
　増加的な正整数は有限個しか存在しません．それらすべてについて総和を求めてください．
問題へのリンク

解答

こちらをご覧ください(OMC上の解説)

例題

$120$ 以下の正整数のうち, $2$ の倍数または $3$ の倍数であるものはいくつありますか?

略解

\frac{120}{2} + \frac{120}{3} - \frac{120}{6} = 80

例題

$120$ 以下の正整数のうち, $2$ の倍数または $3$ の倍数または $5$ の倍数であるものはいくつありますか?

略解

\frac{120}{2} + \frac{120}{3} + \frac{120}{5} - \frac{120}{6} - \frac{120}{10} - \frac{120}{15} + \frac{120}{30} = 88

演習問題

$120$ 以下の正整数で, $2$ の倍数または $3$ の倍数であるような数の総和を求めよ.

解答

X \subset {1, 2, \dots, 120}

に対し,

X

の要素の総和を

f (X)

とすると,

f

は加法的集合関数である.

120

以下の正整数で

2, 3, 6

の倍数であるものの集合をそれぞれ

A, B, C (= A \cap B)

とすると, 簡単な計算により,

f (A) = 3660, f (B) = 2460, f (C) = 1260

である.
よって, 求める値は

f (A \cup B) = f (A) + f (B) - f (C) = 4860

例題

　 $99999$ 以下の非負整数のうち, $10$ 進法表記で各位の数の和が $15$ の倍数である数の総和を求めてください.

略解

各位の数の和が

15

となる非負整数の個数は,

15

以下の

5

つの非負整数で和が

15

になる組み合わせ数から

15

以下の

5

つの非負整数で和が

15

になり, 少なくとも一つが

10

以上となる組み合わせ数を引くことで,

(\binom{19}{4}) - 5 * (\binom{9}{4}) = 3246

通り.

n

の各位の数の和が

15 \Leftrightarrow

99999 - n

の各位の数の和が

30

であるので,
各位の数の和が

0, 45

の場合と合わせて, 求める答えは

0 + 99999 + 99999 * 3246 = 324696753

例題

　 $9699690 (= 20以下の素数の総乗 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19)$ 未満の非負整数のうち, $20$ 以下の素因数をもつ数の総和を求めてください.

解答

20

以下の素数で割り切れる非負整数を良い数と呼ぶことにする.
この時,

n

が良い数

\Leftrightarrow 9699690 - n

が良い数という, 先ほどの問題と似た性質が現れます.
つまり,

9699690

未満の良い数のうち

0

でない数の平均値は

\frac{9699690}{2}

となる.

ここで,

9699690

未満の良い数でない数は,

9699690 * \frac{1}{2} * \frac{2}{3} * \frac{4}{5} * \frac{6}{7} * \frac{10}{11} * \frac{12}{13} * \frac{16}{17} * \frac{18}{19} = 2^{12} * 3^{4} * 5^{1} = 1658880

個ある.

よって

9699690

未満の良い数は

9699690 - 1658880 = 8040810

個あるので, 求める答えは

(8040810 - 1) * \frac{9699690}{2} = 38996677324605

OMC0110-E

　 $9$ つの箱 $1, 2, \dots, 9$ があり，これらに $9$ 種類の玉 $1, 2, \dots, 9$ を次をみたすように入れることを考えます．

各 $i = 1, 2, \dots, 9$ に対し箱 $i$ には玉 $i$ と玉 $i + 1$ が合わせて $10$ 個入っており，それ以外の種類の玉は1つも入っていない．

ただし玉 $10$ は玉 $1$ を表すものとし，また $1$ 種類の玉しか入っていない箱があっても構いません．箱に入っている玉 $i$ の総数を $a_{i}$ とするとき，組 $(a_{1}, a_{2}, \dots, a_{9})$ としてあり得るものは何通りありますか？
問題へのリンク

ヒント

いくつかの "各箱の各玉の数"の組から同じ "各玉の数の和"の組が現れます.
よって, 前者を考えるのは遠回りのようですが, 扱い易いのは圧倒的に前者です.
まずは前者について考えて, どのような条件の前者の組が, 同一の後者の組となるかを考えてみましょう.

解答

こちらをご覧ください(OMC上の解説)

観賞用?

$x$ を $\tan x$ が定義される実数とします.
$\frac{\cos n x}{\cos^{n} x} = \sum_{k = 0}^{⌊ \frac{n}{2} ⌋} (- 1)^{k} \tan^{2 k} x (\binom{n}{2 k})$
を示してください.

解答の概略

(\cos x + i \sin x)^{n}

に二項定理を用いる.

演習問題

$\sum_{k = 0}^{15} \frac{(- 1)^{k}}{(k + 1) (k + 3)} (\binom{n}{k}) = \frac{a}{b}$
を満たす互いに素な正整数 $a, b$ について $a + b$ を求めてください.

解答

(x + 1)^{n}

を

0

から

x

まで積分,

x

を掛ける,

0

から

x

まで積分をすると,

\frac{1}{n + 1} (\frac{(x + 1)^{n + 3} - 1}{n + 3} - \frac{(x + 1)^{n + 2} - 1}{n + 2} - \frac{x^{2}}{2}) = \sum_{k = 0}^{k} \frac{x^{k + 3}}{(k + 1) (k + 3)} (\binom{n}{k})

となる. (

x (x + 1)^{m} = (x + 1)^{m + 1} - (x + 1)^{m}

を使うと幾分か計算が楽である.)
特に,

x = - 1

を代入して,

\begin{aligned} \sum_{k = 0}^{15} \frac{(- 1)^{k}}{(k + 1) (k + 3)} (\binom{n}{k}) & = \frac{(n + 2) (n + 3) - 2}{2 (n + 1) (n + 2) (n + 3)} \\ = \frac{n + 4}{2 (n + 2) (n + 3)} \end{aligned}

である.

n = 15

で,

\frac{19}{612} = \frac{a}{b}

である. よって求める答えは

19 + 612 = 631

ヴァンデルモンドの畳み込みを示すための問題

AMC高校には $p$ 個のクラスがあり, $i$ 個目のクラスには $n_{i}$ 人の生徒が在籍しています.
計 $n_{1} + n_{2} + \dots + n_{p}$ 人の中から計 $m$ 人を選出する方法は何通りありますか.

解答略

ホッケースティック恒等式を示すための問題

$x y$ 平面上の点 $(0, 0)$ に点 $P$ があります. この点は $(x, y)$ にいる時に $(x + 1, y)$ または $(x, y + 1)$ に移動することを繰り返します.
$(0, 0)$ から $(n - k, k + 1) (n \geq k)$ へ移動する方法は何通りありますか.

解答略

演習問題

$N, M > m$ に対し,
$\sum_{i = 0}^{N} (\binom{i + m}{m}) (\binom{N + M - m - i - 1}{M - m - 1}) = (\binom{N + M}{N})$
を示してください.

解答の概略

(0, 0)

から

(N, M)

への移動経路を,

(i, m)

から

(i, m + 1)

へ移動するような

i

の値毎に足し合わせる.

演習問題

$0 \leq k \leq n < 3^{10007}$ を満たす整数 $(n, k)$ の組全てについて, $(\binom{n}{k})$ を $3$ で割った余りを足し合わせた値を $M$ とします.
$M$ を $10007$ で割った余りを求めてください. 但し, $10007$ は素数です.

解答

p = 10007

とする.
Lucasの定理より,

2

つの,

3

未満の非負整数からなる長さ

p

の数列

(n_{0}, n_{1}, \dots, n_{p - 1}), (k_{0}, k_{1}, \dots, k_{p - 1})

の組全てに対して

\prod_{i = 0}^{p - 1} (\binom{n_{i}}{k_{i}})

を足し合わせた値を求めればよい.

3

未満の非負整数の組

n_{0}, k_{0}

の組で

(\binom{n_{0}}{k_{0}}) = 1, 2

となる組の数はそれぞれ

5, 1

通りである.
よって,

a_{i}, b_{i}

をそれぞれ

(n_{0}, n_{1}, \dots, n_{i}), (k_{0}, k_{1}, \dots, k_{i})

の組で,

\prod_{j = 0}^{i} (\binom{n_{j}}{k_{j}})

の値が

1, 2

となるものの数と定めると,

a_{0} = 5, b_{0} = 1, a_{i + 1} = 5 a_{i} + b_{i}, b_{i + 1} = a_{i} + 5_{i + 1}

という漸化式がたつ.
これを解くと,

2 a_{i} = 6^{i + 1} + 4^{i + 1}, 2 b_{i} = 6^{i + 1} - 4^{i + 1}

を得る.
よって,

M = 3 * 6^{p - 1} + 2 * 4^{p - 1} + 2 (3 * 6^{p - 1} - 2 * 4^{p - 1}) = 9 * 6^{p - 1} - 2 * 4^{p - 1}

である.
Felmatの小定理より, 求める答えは

9 * 1 - 2 * 1 \equiv 7

なお,

a_{i}, b_{i}

はFPSを用いると, は

(5 + x)^{i + 1}

のそれぞれ偶数次, 奇数次の係数の和であるので,

x = 1, - 1

を代入して和や積を取ることで漸化式を陽に解かずに解を求められる.

投稿日：2022年12月25日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

karihito

2985

他の人のコメント

コメントはありません。

読み込み中

karihito

AMC day25の問題だけ

この記事の内容
問題