1.
证明由 k 个 1 组成的数 111…1 中存在 2023 的倍数。
› 答案 / 解析
由 k 个 1 构成的正整数即为 910k−1,欲证明题中命题,即证 ∃k,使得 910k−1≡0(mod2023)。
计算得 2023mod3=1,即 3∤2023,从而 gcd(2023,9)=1,有 910k−1≡0(mod2023) 等价于 10k−1≡0(mod2023),即 10k≡1(mod2023)。
计算得 2023mod2=1 且 2023mod5=3,即 2∤2023 且 5∤2023,从而 gcd(2023,10)=1。
由 gcd(2023,10)=1,根据 Euler 定理,有 10φ(2023)≡1(mod2023),取 k=φ(2023) 即可使得命题成立,证毕。
2.
A 和 B 比赛,规定没有平局,先胜 5 局者胜出并结束比赛。问:有多少种可能的情况?
› 答案 / 解析
不妨设 A 为胜者,则计算得出 A 胜的情况数对应翻倍即为答案。
考虑 B 的胜利次数为 i,则 i∈{0,1,⋯,n−1}(其中 n 表示胜利者的游戏次数),游戏共进行 n+i 局,且最后一局一定是 A 胜,而前 n+i−1 局任意排布,对应方案数为 (in+i−1)。
故答案为 2∑i=0n−1(in+i−1)=2×(n2n−1),代入 n=5,得方案数为 252。
3.
求 ∑k=0n(kn)k+21。
› 答案 / 解析
注意到 dxd(n1xn)=xn−1,故不妨设 f(x)=∑k=0n(kn)k+21xk+2,则所求即为 f(1),下面尝试求解 f(x) 的闭式。
先对 f(x) 求导,得 dxdf=∑k=0n(kn)xk+1,从而有 dxdf=x∑k=0n(kn)xk=x(x+1)n。
即得微分方程 dxdf=x(x+1)n,边界条件为 f(0)=0,从而有 f(x)=∫0xt(t+1)ndt=n+21(x+1)n+2−n+11(x+1)n+1+(n+1)(n+2)1。
代入 x=1,即得所求为 f(1)=(n+1)(n+2)n2n+1+1。
4.
有 a、b、c、d 四个人要到 P1,P2,P3,P4 四个地方去。
- a 不去 P1。
- b 不去 P3 和 P4。
- c 不去 P2。
- d 不去 P1。
求可能的方法数。
› 答案 / 解析
我们将此问题模型化为一个 n×n 的棋盘。棋盘的行代表人物,列代表地方。一个“不允许”的分配方案,我们称之为禁区,在棋盘上用 ■ 标记。
问题的解,等价于在这个 n×n 棋盘上放置 n 个“车”,要求任意两个车不能在同一行或同一列,并且没有任何一个车落在禁区(■)中。
首先计算禁区的棋盘多项式 R(x)=∑k=0nrkxk。其中,系数 rk 是指在禁区棋盘上放置 k 个互不攻击(不同行不同列)的车的方法数。
计算可得
r0=1,
r1=5,
r2=8,
r3=4,
r4=0。
因此,禁区的棋盘多项式为 R(x)=1+5x+8x2+4x3。
利用容斥原理,满足条件的排列总数可以通过公式 ∑k=0n(−1)krk(n−k)! 计算,代入 n=4 和 rk 的值,得到可能的分配方法总数为 6 种。
5.
有 1 元、2 元、5 元面值的钞票若干,要组成 20 元,有多少种方法?
› 答案 / 解析
不妨设 fi,j 表示用前 i 种货币组成 j 元的方案数,则有 f0,0=1,以及 fi,j=fi−1,j+fi,j−vi,其中 vi 表示第 i 种货币的面值。
从而列表递推 fi,j,可知答案为 f3,20=29。
6.
递推关系:an=6an−1−5an−2+2n+3n,
已知 a0=1,a1=7,求 an。
› 答案 / 解析
整理此式可得:
an−an−1+312n+1+213n+1=5(an−1−an−2+312n+213n)所以 {an−an−1+312n+1+213n+1} 是一个等比数列,且 a1−a0+3122+2132=671
因此
an−an−1+312n+1+213n+1=6715n−1整理得:
an==a0+k=1∑n(6715k−1−312k+1−213k+1)813+24715n−413n+2−312n+2