AMC day25の問題だけ
この記事の内容
この記事は
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 \text{の登場回数})\ \ \ \ \ \ \ \\ &=\frac{1000}{1000}\+\sum_{k=1}^{999}\frac{2\times(1000-k)}{1000-k}\\ &=1+\sum_{k=1}^{999}2\\ &=\mathbf{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%m=0?m:0)\\ &=\sum_{m=1}^{10000}\sum_{n=1}^{10000}(n%m=0?m:0)\\ &=\sum_{m=1}^{10000}m\left\lfloor\dfrac{10000}{m}\right\rfloor\\ &=\sum_{m=1}^{10000}m\dfrac{10000-M(m)}{m}\\ &=10^8-\sum_{m=1}^{10000}M(m)\\ \end{aligned}$
よって求める答えは $10^8$
$272$ 項からなる整数列 $\{a_i\}_{i=1,\ldots,272}$ のスコアを以下で定めます.
$$\sum_{i=1}^{256} |a_i-a_{i+16}|$$
$1,2,\ldots,272$ を並べ替えてできる整数列は $272!$ 通り考えられますが, それらのスコアの平均値を求めてください.
ただし, この平均値は整数値になることが証明できます.
問題へのリンク
ヒント
問題文の素直に解釈すると, 各数列に対して$256$個の値の総和を求める→全ての数列に対してスコアの総和を求める
という流れになります. 足す順番を変えましょう.
正整数 $N$ が増加的であるとは，$N$ を $10$ 進法で表記した際に各位の数が上位から狭義単調増加となることをいいます．例えば，$157$ や $5$ は増加的ですが，$804$ や $421$ や $334$ は増加的ではありません．
増加的な正整数は有限個しか存在しません．それらすべてについて総和を求めてください．
問題へのリンク
$120$ 以下の正整数のうち, $2$ の倍数または $3$ の倍数であるものはいくつありますか?
略解
$\dfrac{120}{2}+\dfrac{120}{3}-\dfrac{120}{6}=80$
$120$ 以下の正整数のうち, $2$ の倍数または $3$ の倍数または $5$ の倍数であるものはいくつありますか?
略解
$\dfrac{120}{2}+\dfrac{120}{3}+\dfrac{120}{5}-\dfrac{120}{6}-\dfrac{120}{10}-\dfrac{120}{15}+\dfrac{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(=\text{20以下の素数の総乗}=2*3*5*7*11*13*17*19)$ 未満の非負整数のうち, $20$ 以下の素因数をもつ数の総和を求めてください.
解答
$20$ 以下の素数で割り切れる非負整数を良い数と呼ぶことにする.
この時, $n$ が良い数$\Leftrightarrow 9699690-n$ が良い数 という, 先ほどの問題と似た性質が現れます.
つまり, $9699690$ 未満の良い数のうち $0$ でない数の平均値は $\dfrac{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)*\dfrac{9699690}{2}=38996677324605$$
$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)$ としてあり得るものは何通りありますか？
問題へのリンク
ヒント
いくつかの "各箱の各玉の数"の組から同じ "各玉の数の和"の組が現れます.
よって, 前者を考えるのは遠回りのようですが, 扱い易いのは圧倒的に前者です.
まずは前者について考えて, どのような条件の前者の組が, 同一の後者の組となるかを考えてみましょう.
$x$ を $\tan{x}$ が定義される実数とします.
$$\frac{\cos{nx}}{\cos^{n}{x}}=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^k\tan^{2k}{x}\binom{n}{2k}$$
を示してください.
解答の概略
$(\cos{x}+i\sin{x})^n$ に二項定理を用いる.
$$\sum_{k=0}^{15}\dfrac{(-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}\left(\frac{(x+1)^{n+3}-1}{n+3}-\frac{(x+1)^{n+2}-1}{n+2}-\frac{x^2}{2}\right)=\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}\dfrac{(-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$ 人を選出する方法は何通りありますか.
解答略
$xy$ 平面上の点 $(0,0)$ に点 $P$ があります. この点は $(x,y)$ にいる時に $(x+1,y)$ または $(x,y+1)$ に移動することを繰り返します.
$(0,0)$ から $(n-k,k+1)\ (n\ge 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\le k\le 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}=5a_{i}+b_{i},\ b_{i+1}=a_{i}+5_{i+1}$ という漸化式がたつ.
これを解くと, $2a_i=6^{i+1}+4^{i+1},\ 2b_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$ を代入して和や積を取ることで漸化式を陽に解かずに解を求められる.
この記事を高評価した人
この記事に送られたバッジ
投稿者
