MicDZ's blog

以NOIp2018初赛第7题为例:

1
2
3
4
5
 7. 在一条长度为1 的线段上随机取两个点,则以这两个点为端点的线段的期望长度是( )。
A. 1 / 2
B. 1 / 3
C. 2 / 3
D. 3 / 5

首先您需要理解期望是什么。

假设您买彩票,不中奖概率为5050%,得到1元的概率为3030%,得到5050%元的概率为1515%,得到10001000元的概率为55%,那么记 买彩票获得的奖金 这个事件为AA,那么获得的奖金期望值记做E(A)E(A)

那么E(A)=00.5+10.3+500.15+10000.05=57.8E(A)=0*0.5+1*0.3+50*0.15+1000*0.05=57.8 如您见,就是每一种可能乘上对应的概率之和

我们可以来看这道题了。

这道题要用的一点微积分的思想。把这个线段平均分成nn段,然后枚举左右端点,算出所有可能的值,再求平均值即可

可能广大初中生并不知道怎么算,我来写一下过程吧

下面先求总长度

i=0nj=0nijn\sum_{i=0}^n \sum_{j=0}^n \dfrac{\lvert i-j \rvert}{n} 考虑把第二层求和拆开

=i=0n(i0n+i1n+...+inn)=\sum_{i=0}^n (\dfrac{\lvert i-0 \rvert}{n}+\dfrac{\lvert i-1 \rvert}{n}+...+\dfrac{\lvert i-n \rvert}{n}) 分母相同,分子写到一起去

=i=0n(i0+i1+i2+...+inn)=\sum_{i=0}^n (\dfrac{\lvert i-0 \rvert+\lvert i-1\rvert+\lvert i-2 \rvert+...+|i-n|}{n}) 陷入瓶颈

如果右边这一坨东西是个等差数列就好了,但事实上不是,but……我们可以找一点规律

我们以n=4n=4为例子吧

ij4\frac{|i-j|}{4} 0 1 2 3 4
0 00 14\dfrac{1}{4} 24\dfrac{2}{4} 34\dfrac{3}{4} 44\dfrac{4}{4}
1 14\dfrac{1}{4} 00 14\dfrac{1}{4} 24\dfrac{2}{4} 34\dfrac{3}{4}
2 24\dfrac{2}{4} 14\dfrac{1}{4} 00 14\dfrac{1}{4} 24\dfrac{2}{4}
3 34\dfrac{3}{4} 24\dfrac{2}{4} 14\dfrac{1}{4} 00 14\dfrac{1}{4}
4 44\dfrac{4}{4} 34\dfrac{3}{4} 24\dfrac{2}{4} 14\dfrac{1}{4} 00

规律十分明显,每一行都** 以00为分界线拆成两个等差数列 **!于是我们可以愉快地往下面写了!

=i=0n((0+i)(i+1)+(0+ni)(ni+1)2n)=\sum_{i=0}^n (\dfrac{(0+i)*(i+1)+(0+n-i)*(n-i+1)}{2n}) 然后愉快的化简!

=i=0n(i2+i+n2ni+1ni+i2i2n)=\sum_{i=0}^n (\dfrac{i^2+i+n^2-ni+1-ni+i^2-i}{2n}) 合并同类项

=i=0n(2i22ni+n2+12n)=\sum_{i=0}^n (\dfrac{2i^2-2ni+n^2+1}{2n}) 分离常数

=i=0n(2i22n2ni2n+n2+n2n)=\sum_{i=0}^n (\dfrac{2i^2}{2n}-\dfrac{2ni}{2n}+\dfrac{n^2+n}{2n})

=i=0n(i2ni+n+12)=\sum_{i=0}^n (\dfrac{i^2}{n}-i+\dfrac{n+1}{2}) 然后可以愉快的拆开 \sum 了!

=02+12+22+32...+n2n(0+1+2...+n)+(n+1)(n+1)2=\dfrac{0^2+1^2+2^2+3^2...+n^2}{n}-(0+1+2...+n)+\dfrac{(n+1)(n+1)}{2}

=02+12+22+32...+n2n(0+n)(n+1)2+(n+1)22=\dfrac{0^2+1^2+2^2+3^2...+n^2}{n}-\dfrac{(0+n)*(n+1)}{2}+\dfrac{(n+1)^2}{2} 陷入瓶颈

我们被卡住关键在于Sn=02+12+22+32...+n2S_n=0^2+1^2+2^2+3^2...+n^2的计算(高中不必看这一段),那么我们不如来推一推公式吧?

怎么推公式?

玄学技巧-差分

n[0,5]n\in[0,5]SnS_n值列成一排

0        1        5        14        30        550~~~~~~~~1~~~~~~~~5~~~~~~~~14~~~~~~~~30~~~~~~~~55         ~~~~~~~~然后差分

    1        4        9        16        25~~~~1~~~~~~~~4~~~~~~~~9~~~~~~~~16~~~~~~~~25                 ~~~~~~~~~~~~~~~~继续

        3        5        7        9~~~~~~~~3~~~~~~~~5~~~~~~~~7~~~~~~~~9                           ~~~~~~~~~~~~~~~~~~~~~~~~~~继续

            2        2        2~~~~~~~~~~~~2~~~~~~~~2~~~~~~~~2                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~所有的数字竟然相等了!

这时候我们一共做了33次差分操作,那么我们可以得知SnS_n公式是一个33次整式!

玄学吧

此时设S=ax3+bx2+cx+dS=ax^3+bx^2+cx+d

{a+b+c+d=18a+4b+2c+d=527a+9b+3c+d=1464a+16b+4c+d=30\begin{cases} a+b+c+d=1 \\ 8a+4b+2c+d=5 \\ 27a+9b+3c+d=14 \\ 64a+16b+4c+d=30\end{cases}

然后解方程

{7a+3b+c=419a+5b+c=937a+7b+c=16\begin{cases} 7a+3b+c=4 \\ 19a+5b+c=9 \\ 37a+7b+c=16 \end{cases}

{12a+2b=518a+2b=7\begin{cases} 12a+2b=5 \\ 18a+2b=7 \end{cases}

6a=2       a=136a=2~~~~~~~\therefore a=\dfrac{1}{3}

b=12,c=16,d=0\therefore b=\dfrac{1}{2},c=\dfrac{1}{6},d=0

Sn=13n3+12n2+16n\therefore S_n=\dfrac{1}{3}n^3+\dfrac{1}{2}n^2+\dfrac{1}{6}n 化简一下

=16n(2n2+3n+1)=\dfrac{1}{6}n(2n^2+3n+1) 十字相乘分解

=16n(n+1)(2n+1)=\dfrac{1}{6}n(n+1)(2n+1)

然后就可以愉快的往下面写了

02+12+22+32...+n2n(0+n)(n+1)2+(n+1)22\dfrac{0^2+1^2+2^2+3^2...+n^2}{n}-\dfrac{(0+n)*(n+1)}{2}+\dfrac{(n+1)^2}{2}

=16n(n+1)(2n+1)n(0+n)(n+1)2+(n+1)22=\dfrac{\dfrac{1}{6}n(n+1)(2n+1)}{n}-\dfrac{(0+n)*(n+1)}{2}+\dfrac{(n+1)^2}{2}

=16(n+1)(2n+1)n2+n2+n2+2n+12=\dfrac{1}{6}(n+1)(2n+1)-\dfrac{n^2+n}{2}+\dfrac{n^2+2n+1}{2}

=(n+1)(2n+1)6+n+12=\dfrac{(n+1)(2n+1)}{6}+\dfrac{n+1}{2}

=2n2+3n+16+3n+36=\dfrac{2n^2+3n+1}{6}+\dfrac{3n+3}{6}

=2n2+6n+46=\dfrac{2n^2+6n+4}{6}

=n2+3n+23=\dfrac{n^2+3n+2}{3}

=(n+1)(n+2)3=\dfrac{(n+1)(n+2)}{3}

那么总长度算了出来,再除以情况数(n+1)2(n+1)^2

Ans=(n+1)(n+2)3(n+1)2Ans=\dfrac{(n+1)(n+2)}{3(n+1)^2}

=n+23n+3=\dfrac{n+2}{3n+3}​

limΔxAns=13\lim_{\Delta x\to \infty}Ans=\dfrac{1}{3}

至此,我们做出了这道题,答案选BB

By Imakf

https://www.luogu.org/blog/Imakf/noip-ti-gao-chu-sai-t7-xie-xi

 评论