1.

证明由 kk11 组成的数 1111111\ldots1 中存在 20232023 的倍数。

答案 / 解析

kk11 构成的正整数即为 10k19\frac{10^{k}-1}{9},欲证明题中命题,即证 k\exists k,使得 10k190(mod2023)\frac{10^{k}-1}{9}\equiv 0\pmod{2023}

计算得 2023mod3=12023 \bmod{3} = 1,即 320233\nmid 2023,从而 gcd(2023,9)=1\gcd(2023, 9)=1,有 10k190(mod2023)\frac{10^{k}-1}{9}\equiv 0\pmod{2023} 等价于 10k10(mod2023)10^{k}-1\equiv 0\pmod{2023},即 10k1(mod2023)10^{k}\equiv 1\pmod{2023}

计算得 2023mod2=12023 \bmod{2} = 12023mod5=32023 \bmod{5} = 3,即 220232\nmid 2023520235\nmid 2023,从而 gcd(2023,10)=1\gcd(2023, 10)=1

gcd(2023,10)=1\gcd(2023, 10)=1,根据 Euler 定理,有 10φ(2023)1(mod2023)10^{\varphi(2023)}\equiv 1\pmod{2023},取 k=φ(2023)k=\varphi(2023) 即可使得命题成立,证毕。

2.

A 和 B 比赛,规定没有平局,先胜 5 局者胜出并结束比赛。问:有多少种可能的情况?

答案 / 解析

不妨设 A 为胜者,则计算得出 A 胜的情况数对应翻倍即为答案。

考虑 B 的胜利次数为 ii,则 i{0,1,,n1}i \in \{0, 1, \cdots, n-1\}(其中 nn 表示胜利者的游戏次数),游戏共进行 n+in + i 局,且最后一局一定是 A 胜,而前 n+i1n+i-1 局任意排布,对应方案数为 (n+i1i)\binom{n+i-1}{i}

故答案为 2i=0n1(n+i1i)=2×(2n1n)2\sum_{i=0}^{n-1}\binom{n+i-1}{i}=2\times\binom{2n-1}{n},代入 n=5n=5,得方案数为 252252

3.

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

答案 / 解析

注意到 d(1nxn)dx=xn1\frac{\mathrm{d}\left(\frac{1}{n}x^n\right)}{\mathrm{d}x}=x^{n-1},故不妨设 f(x)=k=0n(nk)1k+2xk+2f(x)=\sum_{k=0}^{n}\binom{n}{k}\frac{1}{k+2}x^{k+2},则所求即为 f(1)f(1),下面尝试求解 f(x)f(x) 的闭式。

先对 f(x)f(x) 求导,得 dfdx=k=0n(nk)xk+1\frac{\mathrm{d}f}{\mathrm{d}x}=\sum_{k=0}^{n}\binom{n}{k}x^{k+1},从而有 dfdx=xk=0n(nk)xk=x(x+1)n\frac{\mathrm{d}f}{\mathrm{d}x}=x\sum_{k=0}^{n}\binom{n}{k}x^k=x(x+1)^n

即得微分方程 dfdx=x(x+1)n\frac{\mathrm{d}f}{\mathrm{d}x}=x(x+1)^n,边界条件为 f(0)=0f(0)=0,从而有 f(x)=0xt(t+1)ndt=1n+2(x+1)n+21n+1(x+1)n+1+1(n+1)(n+2)f(x)=\int_{0}^{x}t(t+1)^n\mathrm{d}t=\frac{1}{n+2}(x+1)^{n+2}-\frac{1}{n+1}(x+1)^{n+1}+\frac{1}{(n+1)(n+2)}

代入 x=1x=1,即得所求为 f(1)=n2n+1+1(n+1)(n+2)f(1)=\frac{n2^{n+1}+1}{(n+1)(n+2)}

4.

有 a、b、c、d 四个人要到 P1,P2,P3,P4P_{1},\,P_{2},\,P_{3},\,P_{4} 四个地方去。

  • a 不去 P1P_{1}
  • b 不去 P3P_{3}P4P_{4}
  • c 不去 P2P_{2}
  • d 不去 P1P_{1}

求可能的方法数。

答案 / 解析

我们将此问题模型化为一个 n×nn\times n 的棋盘。棋盘的行代表人物,列代表地方。一个“不允许”的分配方案,我们称之为禁区,在棋盘上用 标记。

问题的解,等价于在这个 n×nn\times n 棋盘上放置 nn 个“车”,要求任意两个车不能在同一行或同一列,并且没有任何一个车落在禁区()中。

首先计算禁区的棋盘多项式 R(x)=k=0nrkxkR(x) = \sum_{k=0}^{n} r_k x^k。其中,系数 rkr_k 是指在禁区棋盘上放置 kk 个互不攻击(不同行不同列)的车的方法数

计算可得 r0=1r_0 = 1r1=5r_1 = 5r2=8r_2 = 8r3=4r_3 = 4r4=0r_4 = 0。 因此,禁区的棋盘多项式为 R(x)=1+5x+8x2+4x3R(x) = 1 + 5x + 8x^2 + 4x^3

利用容斥原理,满足条件的排列总数可以通过公式 k=0n(1)krk(nk)!\sum_{k=0}^{n} (-1)^k r_k (n-k)! 计算,代入 n=4n=4rkr_k 的值,得到可能的分配方法总数为 66 种。

5.

有 1 元、2 元、5 元面值的钞票若干,要组成 20 元,有多少种方法?

答案 / 解析

不妨设 fi,jf_{i,j} 表示用前 ii 种货币组成 jj 元的方案数,则有 f0,0=1f_{0,0}=1,以及 fi,j=fi1,j+fi,jvif_{i,j}=f_{i-1,j}+f_{i,j-v_i},其中 viv_i 表示第 ii 种货币的面值。

从而列表递推 fi,jf_{i,j},可知答案为 f3,20=29f_{3,20}=29

6.

递推关系:an=6an15an2+2n+3na_{n}=6a_{n-1}-5a_{n-2}+2^{n}+3^{n}

已知 a0=1a_{0}=1a1=7a_{1}=7,求 ana_{n}

答案 / 解析

整理此式可得:

anan1+132n+1+123n+1=5(an1an2+132n+123n)a_n-a_{n-1}+\frac132^{n+1}+\frac123^{n+1}=5\left(a_{n-1}-a_{n-2}+\frac132^n+\frac123^n\right)

所以 {anan1+132n+1+123n+1}\left\{a_n-a_{n-1}+\frac132^{n+1}+\frac123^{n+1}\right\} 是一个等比数列,且 a1a0+1322+1232=716a_1-a_0+\frac132^2+\frac123^2=\frac{71}6

因此

anan1+132n+1+123n+1=7165n1a_n-a_{n-1}+\frac132^{n+1}+\frac123^{n+1}=\frac{71}65^{n-1}

整理得:

an=a0+k=1n(7165k1132k+1123k+1)=138+71245n143n+2132n+2\begin{align*} a_n=&{}a_0+\sum_{k=1}^n\left(\frac{71}65^{k-1}-\frac132^{k+1}-\frac123^{k+1}\right)\\ =&{}\frac{13}8+\frac{71}{24}5^n-\frac143^{n+2}-\frac132^{n+2} \end{align*}