Archive

Posts Tagged ‘数学’

NOIP2010提高组初赛问题求解第三题推广

October 27, 2010 Leave a comment

我们很自然地想求解下面的问题:

题目:记T为一队列,初始时为空,现有k个总和不超过n的正整数依次入列。如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为m,那么k的最小值是___________。

显然当m<=0或n<=0或n<m时此题无解,否则:

类似地我们构建下面的图:

0—m—2m—…—m*[n/m]
1—m+1—2m+1—..—m*[n/m]+1
……
n%m—m+n%m—…—n

n%m+1—n%m+1+m—…—n-m+1

m-1—2m-1—…—n-n%m+1
第0行至第n%m行最多总共选([[n/m]/2]+1)(n%m+1)个
第n%m+1行至第m-1行最多总共选[([n/m]+1)/2](m-1-n%m)个
所以总共最多选([[n/m]/2]+1)(n%m+1)+[([n/m]+1)/2](m-1-n%m)个
注意到,我们计算的时候包含了S0,所以k的最小值就是([[n/m]/2]+1)(n%m+1)+[([n/m]+1)/2](m-1-n%m)

以原题n=32, m=9代入,得

k=([32/9]/2+1)*(32%9+1)+[(32/9]+1)/2]*(9-1-32%9)=2*6+2*3=18

Advertisements
Categories: OI Tags: , , , , ,

《微积分学教程》笔记续

October 11, 2010 Leave a comment

第五章 多元函数

多元函数 单纯形 聚点 开域 闭域

多元函数极限严格定义 对应的整序变量情形 P307一道极限题

累次极限 有关连续函数的几个定理

偏导数 偏微分 全增量 全微分 沿给定方向的导数

欧拉公式【188 混合导数可交换条件 高阶微分(类似于多项式定理)

泰勒公式 多元函数极值的充分条件

 

第六章 函数行列式

雅可比式及相应记号

单值连续隐函数的存在条件

隐函数的可微性

相对极值

换元法 勒让德变换(此章实在看得很晕,只能回头再弄了……)

 

第七章 微分在几何学上的应用(果断先跳过)

 

第八章 原函数(不定积分)

一些积分的具体例子(换元法 分部积分)

二项式积分【279】 递推公式【280】

二次根式积分【281】 几何解释【282】 例题【283】 其它计算方法【284】

三角式【285】 椭圆积分【291】

 

第九章 定积分

函数可积条件

达布和

三类可积函数

推广中值定理【304】

积分上限函数

第二中值定理【306】

泊松积分的计算【307】

例题【312】

定积分的换元公式【313】

数e的超越性【319】

勒让德多项式【320】

积分不等式【321】

积分近似计算

 

第十章 积分学在几何学、力学与物理学中的应用(果断先看几何学,不过还是先跳过吧,和之前微分在几何学上的应用有关系..)

 

第十一章 常数项无穷级数

 

第十二章 函数序列与函数级数(这两章内容以前了解较多,也先跳过)

 

第十三章 反常积分

反常积分审敛

例题【489】

几个有名的积分【492】

伏汝兰尼积分【495】

有理函数在无穷间的积分【496】

杂例和习题【497】

反常积分的近似计算

 

第十四章 依赖于参数的积分(先跳过)

 

第十五章 曲线积分 斯蒂尔切斯积分

只看了第一、二类曲线积分 扫看了斯蒂尔切斯积分

需要弄清的概念 可积 黎曼可积 绝对可积 收敛 绝对收敛 一致收敛

还需再看 一些定理 比如斯蒂尔切斯积分的中值定理 以及斯蒂尔切斯积分的可积判定等等

 

第十六章 二重积分

几个不等式(112页开始的)

先只看前两节

 

第十七章 曲面面积 曲面积分(先跳过)

 

第十八章 三重积分及多重积分

先只看了一些基础的东西

以及:

场论 纯量 向量 纯量场 向量场 等量面(只简单看了一下 有涉及之前没看的内容 只能先跳过)

多重积分

变量变换略去(需从二重积分开始看)

例题也照例跳过

 

第十九章&第二十章 傅里叶级数

正交函数系

三角插值法

——只简单看了一下,得开始从头补一些东西了

A math problem concerned about monotonicity

October 10, 2010 Leave a comment

Given that f(x) is a monotonously increasing function and g(x)=f(x)-f(1-x). Now if for certain real numbers x_1, x_2, g(x_1)+g(x_2)>0, compare x_1+x_2 and 1.

Here we will prove that $latex  x_1+x_2>1$.

Obviously, when x_1>=1-x_1, x_2>=1-x_2 while the equalities don’t hold simultaneously, we can easily deduce the condition; at the same time we can get x_1+x_2>1.

While if x_1<=1-x_1 and x_2<=1-x_2, apparently we have

f(x_1)<=f(1-x_1), f(x_2)<=f(1-x_2), so f(x_1)+f(x_2)<=f(1-x_1)+f(1-x_2), so g(x_1)+g(x_2)<=0.

Now consider if x_1>=1-x_1 and x_2<=1-x_2. Thus we have x_1>=1/2 and x_2<=1/2. So at the same time we have
x_2<=x_1 and x_2<=1-x_2

Now if x_1+x_2<=1, then x_1<=1-x_2, then x_2<=1-x_1.

So we have x_2<=1-x_1<=x_1<=1-x_2

So f(x_2)<=f(1-x_1)<=f(x_1)<=f(1-x_2)

So f(x_2)+f(x_1)<=f(1-x_1)+f(1-x_2)

Which indicates that the condition holds only if x_1+x_2>1.

Symmetrically we can prove the same when x_1<=1-x_1 and x_2>=1-x_2.

《微积分学教程》笔记•一

October 9, 2010 Leave a comment

第一章 极限论

整序变量极限的严格定义

无穷小量 无穷大量

斯托尔茨定理

有上界或有下界的单调整序变量的极限定理

等差-等比中项 等差-调和中项

数e的定义 无理性证明

区间套引理

整序变量收敛原理

部分数列 部分极限

上极限 下极限

第二章 一元函数

狄利克雷函数 克罗内克函数

反正弦函数加法定理

反正切函数加法定理

反正切和反正弦函数关系

函数极限:聚点 邻域 极限 右聚点 右极限 左聚点 左极限

函数极限和整序数列极限的转换(还需再看)

几个重要极限的导出

极限理论的拓广(还需再看)

单调函数的极限 布尔查诺-柯西一般判别法

函数上极限 下极限

同阶无穷小

无穷小阶数

等价无穷小

主部的分出

无穷大分阶(仿无穷小)

函数的连续性

左间断 右间断 间断的分类

几个函数方程的解(还需再看)

例题[79]

连续函数性质 零值定理 中值定理

一致连续

闭区间的一致连续性

第三章 导数及微分

费马定理【109

达布定理【110

罗尔定理【111

拉格朗日定理【112

柯西公式【114

勒让德多项式【118

差分

第四章 利用导数研究函数

高阶导数对函数极值的应用

方程近似解

数学趣题:铲雪机

October 6, 2010 Leave a comment

下雪了。雪花以恒定的速率落下。过了一会儿,一辆铲雪车开始铲雪。铲雪车在单位时间内所铲的雪的体积是固定的,也就是说,铲雪车前进的速度和雪的厚度成反比。已知这辆铲雪车在第一小时内行走的距离是第二小时内行走的距离的两倍,求铲雪车开始铲雪的时间距离开始下雪的时间有多久。

Read more…

一个十分简短的证明:e是无理数

October 4, 2010 Leave a comment

这个证明来自Steve Kifowit的一篇论文

首先我们不加证明地给出下面的定理(或这里):

定理. 若一交错级数收敛,那么第n项余项的绝对值不大于级数的第(n+1)项的绝对值。

根据微积分的知识,我们有

e^x=\sum_{i=0}^{\infty}\frac{x^i}{i!}

x=-1,则有

e^{-1}=\sum_{i=0}^{\infty}\frac{(-1)^i}{i!}

这是一个交错级数。同时,记S_n=\sum_{i=0}^{n}\frac{(-1)^i}{i!},显然S_n是一个有理数,且可以写成\frac{M}{n!}的形式,其中M是一个整数。根据上面的定理有

若n为偶数,则S_n-\frac{1}{(n+1)!}<e^{-1}<S_n

若n为奇数,则S_n<e^{-1}<S_n+\frac{1}{(n+1)!}

所以对任意自然数n,e^{-1}都严格地处在\frac{a}{(n+1)!}\frac{a+1}{(n+1)!}之间,其中a是一个整数。这意味着e^{-1}不能表示成\frac{M}{(n+1)!}的形式,其中M是一个整数,而这对任意的自然数n都成立。然而,如果e是一个有理数,那么一定存在某个自然数n,使得e^{-1}可以表为\frac{M}{(n+1)!}的形式。矛盾。所以e是无理数。

一个不可证的定理-从一个数列说起

October 3, 2010 1 comment

我在这里看到了这个有趣的数列及由其引出的一些奇特的结论。

首先,选取任意一个正整数m_1,将之作为数列中的第一个数。比如,假设我们选取m_1=18

为计算数列中的第二项m_2,我们首先把m_1写成二进制形式,即m_1=\sum a_i2^i。接着把所有的指数项写成它们的二进制表示,接着把所有指数项的指数项写成它们的二进制表示,依此类推。因此m_1的相应形式是m_1=18=2^4+2^1=2^{2^2}+2^{2^0}。接下来,我们把所有2替换成3,并将得到的结果再减1。在这个例子中,m_2=3^{3^3}+3^{3^0}-1。显然m_2是一个非常大的数,大约7.63 \times 10^{12}

接着,用同样的方式得到其它数。为得到m_n,我们将m_{n-1}用n进制形式表示,再将所有n替换成n+1,再将最后的结果减一。

这样我们得到:

m_1=2^{2^2}+2^{2^0}=18

m_2=3^{3^3}+3^{3^0}-1=3^{3^3}+2^{3^0}\approx 7.63 \times 10^{12}

m_3=4^{4^4}+2^{4^0}-1=4^{4^4}+4^0\approx 1.34\times 10^{154}

m_4=5^{5^5}+5^0-1=5^{5^5}\approx 1.91\times 10^{2184}

m_5=6^{6^6}-1\approx 2.66\times 10^{36305}

为得到m_6,我们必须将m_5写成六进制表达形式。首先注意到

m_5=6^{6^6}-1=5\cdot 6^{6^6-1}+5\cdot 6^{6^6-2}+\ldots+5\cdot 6^1+5\cdot 6^0

但这还不是最终我们想要的形式,我们还要把所有指数项进一步展开。然后,我们把所有的6替换成7,再将得到的结果减1。不难想像最终我们将得到一个异常巨大的数。

对于这个数列(称为Goodstein数列),有两个十分深刻的定理:

定理(Goodstein定理). 存在一个k使m_k=0.

也就是说,尽管这个数列看起来会飞快地增长直至无穷大,仍旧会最终变为零并终止。这个定理的证明非常复杂,用到了序数定理。

通过上面的数列的例子我们可以看出写出前几项(或者甚至前几百万项)以决定这个数列的收敛性是相当不可取的……但实际上存在某个数字开头的数列,很快就结束到0。比如,若以m_1=3=2^1+1开始,则有

m_2=3^1+1-1=3^1=3

m_3=4^1-1=3

m_4=3-1=2

m_5=2-1=1

m_6=1-1=0

那么对于m_1=4呢?请看下表(或这里

Hereditary notation Value
22 4
 3^3 - 1 = 2 \cdot 3^2 + 2 \cdot 3 + 2 26
 2 \cdot 4^2 + 2 \cdot 4 + 1 41
 2 \cdot 5^2 + 2 \cdot 5 60
 2 \cdot 6^2 + 2 \cdot 6 - 1 = 2 \cdot 6^2 + 6 + 5 83
 2 \cdot 7^2 + 7 + 4 109
 \vdots  \vdots
 2 \cdot 11^2 + 11 253
 2 \cdot 12^2 + 12 - 1 = 2 \cdot 12^2 + 11 299
 \vdots  \vdots

它将继续增长,直至在3\times 2^{402653209}进制下,到达最大值3\times 2^{402653209}-1,然后再经过3\times 2^{402653209}步变为零!

更令人称奇的是,在1982年,Laurie Kirby和 Jeff Paris证明了下面的定理:

定理. Goodstein定理在皮阿诺算术公理下是不可证的。

也就是说,这正是哥德尔在1931年所描述的第一不完备性定理中的不可证的定理!

根据哥德尔不完备性定理,若有一个公理足以表示所有基本算术(比如由皮阿诺公理所导出),那么它一定是不完备的。也就是说,一定存在一个有关算术的命题,不能由这组公理所证明。在他的证明中哥德尔给出了一个正确但不可证的命题。但它相当难理解,更像是一个刻意构造的矛盾,而不是一个数学上的命题。

第一个让数学家们满意的命题由Paris和Harrington给出(和拉姆赛数有关)。接着在1982年有了上面的Goodstein定理不可证的结论。此外Laurie Kirby和 Jeff Paris还给出了另外一个例子,被称为“赫拉克勒斯大战九头蛇”(很喜感的名字),这与一种特定的树结构的增长有关。