当前位置:首页 >> 学科竞赛 >>

专题五 初等数论与组合数学


鏊囊--i_誓__
专题五

初等数论与组合数学
谢广喜(江南大学理学院)

题意要求的)存在性问题、构造性问题、可能

~一、初等数论基础知识及有关问题
相关的常见知识和问题主要有:奇数的 平方被8除余1、质数与合数(2是唯一的偶 质数,其余质数都是奇数)、奇数与偶数(两 个整数的和与差的

奇偶性相同)、不定方程 的整数解、“对于任意一个有限大的自然数

情形有多少种(计数问题)、是否存在最“好” 情形(最优化情形),等等.当然,其中部分问 题(如染色问题等)也与其他内容(如图论、 规划理论等)有交叉,我们熟悉的数列、排列 与组合等都是组合数学的重要组成部分. 总而言之,求解自主招生考试中的组合 数学部分试题,通常不像我们求解其他数学 问题那样对背景、方法较为熟悉,而主要是 结合具体的问题,采取具体的手段和方法, 其中,抽屉原理等是必须要了解的.在解题 中,如何巧妙地构造“抽屉”往往是关键.

N,N!兰N?(N一1)…??2?1中含有素

因子户的方次为[鲁]+[笋]+[笋]+…
(rz]是取整函数,此式虽然无限加下去,但 是对于任意一个有限大的自然数N,从某一 项开始向后全部为0,表达式自动截断为有 限项)”,等等.

矽例1


(2012年北约试题)在1,2,…,

012中取一组数,使得任意两数之和不能

被其差整除,最多能取多少个数?

★二、组合数学初步
组合数学的研究对象主要包括:(满足 模的几何意义,即点Z到点(1,0)的距离是 点Z到点(一1,0)的距离的2倍,再利用阿 波罗尼斯圆的定义,直接得到复数z所对应 的点的轨迹是圆,无需任何运算过程.

解析

在1,2,…,2 012中取一组数,

记其中任意两数分别为a,b(a>6),若a一6 —1,显然此时必有两数之和能被其差整除,

考此题:点B、点D即为定点,罴一2为定
,1上/

值,故点A的轨迹即为一个阿波罗尼斯圆 (同学们自己思考如何建系求点A的轨迹方 程),且圆心在BD上,故以BD为底边的 △ABD的最大的高即为圆半径,所以所求 三角形ABC面积最大值为2. 以上题目充分说明,阿波罗尼斯圆对于 求解某些数学问题发挥着很大的作用.同学 们在理解阿波罗尼斯圆概念的同时,要体会 其中的数学思想和数学方法,融会贯通,在 实际解题中灵活运用,那么一些题目我们就 能轻松解决了.

参例7

在等腰三角形

ABC中(如图2),AB—

AC,BD是腰AC的中线, 且BD=√i,则S△船。的最 大值是






图2

本题旨在考查三角形面积公式、余弦定 理,可利用解三角形的知识去解决此题(同 学们可以思考一下怎么做).换个角度去思 峰——、

瀚黪k一 万方数据

liil嚣强臻纛j蠹≤。。j誊麓j1。,瓣;一≤¨j。。、x—j》:j。

-、



■■■■■■■■■■■■■■▲….≥{
不合要求,若n一6=2,而我们知道两个整数 的和与差的奇偶性相同,因此此时也必有两 数之和能被其差整除,仍不合要求,故a—b 至少为3(而&一b的最小值越大,最多能取 的数的个数越小). 于是下面针对a—b的最小值为3的情 况进行试探性设计,为此将1,2,…,2 012分 组(建立抽屉)如下:{1,2,3),{4,5,6),…,
{2
008,2 009,2

将S中所有的数分成以下117组:[1]: 18个元素(模117余1的同余类).[2]:18个 元素(模117余2的同余类)...?;[24]:18个 元素(模117余24的同余类);[25]:17个元 素(模117余25的同余类);E26]:17个元素 (模117余26的同余类);…;[116]:17个元 素(模117余116的同余类).[o]:17个元素 (模117余0的同余类). 要想满足题意,A中[o]组的元素最多 只能有一个,不能同时有[1]和[116]组的元 素,不能同时有[2]和[115]组的元素,…,不 能同时有[58]和[59]组的元素. 所以满足题意的是的最大值为14-18X
24+17×(58—24)一1 011.

010),{2

011,2

012),共671

组,为了满足题意要求,显然必须使得任意 两数均不来自同一“抽屉”(否则必导致盘一b 一1或2的情况发生),故满足要求的数的个 数至多为671.
下面构造性地给出一种取法:取1,4,7,
…,2

011这671个数,即从每个“抽屉”中取

评注

显然,有时初等数论与组合数

最小的数,也即形如3卵一2(72∈N+)的数,从 中任取两数a一3n1—2,b一3n2—2(行1,竹2∈
N’,卵l≠门2),显然有a—b一3(卵1一咒2)是3

学是交叉在一起,不易截然分开的.

多例3(2009年清华试题)问:m gin,--}.
抛物线以及它们的内部能否覆盖整个平面?

的倍数,而n+6—3(九。4-r/。)一4不是3的倍 数,满足题意要求. 综上所述,满足要求的数的个数至多
为671.

(含焦点的区域称为抛物线的内部) 解析 假设存在竹条抛物线(门为某个

有限值),使得这押条抛物线及其内部覆盖 这是一道需要应用抽屉原理解 整个平面,现在我们任取一条与这订条抛物 线的对称轴均不平行的直线,则这行条抛物 线中任意一条与该直线或者相切、或者相交 (两个交点)、或者没有交点,换句话说,就是 这咒个抛物线及其内部区域中的每一个都 只能覆盖该直线的有限部分,所以这行个抛 物线及其内部区域一起也只能覆盖该直线 的有限部分,所以该直线上必存在未被覆盖 的区域,所以有限条抛物线及其内部不能覆
盖整个平面.

评注

决的问题,这类试题的求解往往具有一定的 构造性,关键是如何构造恰当的“抽屉”.对于 本题,如何构造“抽屉”并不是显然的,而是依
赖于前期分析,在分析中逐渐明朗的.当然,对 于本题,取2,5,8,…,2 012这671个数也满

足题意(而另一组{3m|研∈N‘}这671个数则 显然不满足题意).所以类似的问题往往只关 心实现方案的内容的最大(小)数目,而不太关 心具体的内容.2013年“北约”解答题第一题 也可用类似办法解决,此处从略.

多例4(2012年北约试题)求证:对于任
意的正整数,z,(1+√2)“必可表示成以+
 ̄/5—1的形式,其中s∈N。. 证明

矽例2


已知集合S一(押∈N

1≤”≤

013),A一{盘1,a2,…,a^)是S的子集,且具

有性质:A中任意两个元素之和不能被117
整除,试确定正整数是的最大值,并证明你 的结论.

显然,对于任意的正整数7"/,

(1+√2)“=M+N√2,其中M,N∈N“,于是 联想到其对偶式(1一√2)“一M—N√2,发现

筒解



013÷117—17……24.

它们的和的一半仍是自然数,于是构造数列

New U砒,ersity

Entra理ce'L币aminatioⅣ_一_

,…l?◆

万方数据

×2×3×…×2 012,为从1到2 012之间所

有整数的连乘积,则2
A.504

012

1的值的尾部(从

D.501

个位往前)连续的0的个数是
B.503 C.502



(1)当72为偶数2m(m∈N”)时,视X:。

4.(2008年中科大试题)一个平面由 红、蓝点组成,且既有红点,又有蓝点,对于 任意给定的长度a(&>o),证明: (1)存在两个同色点,距离为a; (2)存在两个异色点,距离为a.

三(1+√手)“为一个整体,进而可将b。一

盟±丝翌毒』型变形为x;。一2bzmXl,1


^,

/J

‘‘‘卅

。。 cm

+1—0,显然X:。。>1,于是可得X。。一b:。+

 ̄/6;。一1(另一根大于0而小于1,已舍去), 显然,此时取s一6;。即可满足题意; (2)当,2为奇数2m一1(m∈N。)时,视
1.假设它们都是奇数,然后已知等式两边同时

6。一盟±堑翌Ij型变形为x;m一。一
取S一6;一,+1即可满足题意.

X。。一,三(1+厄)“1为一个整体,于是可将

对8取余,可以发现左边余5,右边余1,显然不等,
故它们不可能都是奇数. 注:此处用到了一个重要结论:任意一个奇数的 平方被8除余1.

262。一。X:一。一I=0,显然X2。一。>1,于是可

2.由对称性,不妨令z≥y≥z≥1,则二+二+


解得X。。一。一b。。一,+ ̄/62。一。+1,显然,此时



二=1≤上,于是知z≤3,所以z只能为l,2,3.分
类讨论,可得所有的正整数解共十组,为(3,3,3)(一 个),(4,4,2)及其交换解(共三个),(6,3,2)及其交 换解(共六个). 注:2013年“华约”试题之一(见《专题二》,本刊 本版2013年11月刊)与本题完全类似.
3.2 012

综上,对于任意的正整数九,(1+√2)“必

可表示舭+ ̄/s一1的形式,其中S∈N+.

型巫婆业∈N:,(1一抠)”一
评注

以上解法充分注意到了

1质因数分解后,因子5出现的“密度”要
012 1的值的尾部连

i_÷鲁的特性,使分类讨论工作的产生自
(1+√2)“

比因子2出现的“密度”小,因此。2

然而然,而整体变量的引入将一个比较复杂 的整数探求问题转化为一个一元二次方程 的求根问题(但要注意细节),极大地降低了
解题的难度.

续的0的个数与其中因子5的个数相等,为j半l+

[半H半]+[半]=501,故选n
4.(1)在该平面上任作一个边长为a的等边三 角形,由抽屉原理,知必有两点同色,满足要求. (2)在该平面上任取两个异色点A,B,不妨具体 设点A是红色的,点B是蓝色的,讨论如下:①若AB =2a,取其中点,记为C,则点C不是红色。就是蓝色,

I.若al,a2,a 3,a4,aj和b是满足a:+ n;+n;+口;+口;一b2的整数,证明:它们不可 能都是奇数. 2.(2012年清华保送生试题)求方程土


必与A,B之一同色,满足要求;②若AB<2a.则以 AB为底边,。为腰长,作一个等腰三角形,记其顶点 为C,则点C不是红色,就是蓝色,必与A,B之一同 色,满足要求;③若AB>2a,则在线段AB上靠近某 一端(不妨具体令为A)找一点B,,使得AB。一a,若 B】是蓝色,则A,B。两点满足要求;若B,是红色,则 用考虑线段AB的方法考虑线段B,B。而线段AB的长

+土十土一1的所有正整数解



3.(2012年复旦千分考)记2

012 1一I

度(也即初始长度)是有限的,必然在有限步内终止.

■_。’

辫k一 万方数据


相关文章:
初等数论与中学数学
d=∣25x0-15y0+12∣/5 34 根据初等数论中的公...它是组合数学的一个重要原理,最先由德国数学 家狄...对于前者《课标》是这样要求的,该专题是为对数学有...
初等数论
经常用到的一个工具,那就是鸽巢原理,也就 是同等意义下的在组合数学中的抽屉...41页 5下载券 (精品)初等数论试题(整理... 11页 2下载券 ©2016 Baidu...
组合数学调研报告
关键词 初等数论;组合数学;递归;数学归纳法。 三、对本课程的调研 1、递归...盖伊 《数论中未解决的问题》 科学出版 社 第三版 2007 5.李凡长 编著《组合...
初等数论论文
初等数论在计算机科学、代数编码、密码学、组合数学、...[5] 利用初等变换求整数的最大公约数 命题设 ?a1...专题推荐 2014下半年教师资格...专题 2014教师资格...
初等数论课程教学大纲新
而且近年来初等数论在计算器科学、组合数学、密码学...第五章(一)教学目的与要求 连分数 1、掌握连分数...专题推荐 省一等奖教学设计《运动... 浅谈讨论法在...
初等数论在中学数学竞赛中的应用
涵盖了初等代数、初等数论、几何、组合数学等.竞赛往往是针对中学生的数 学活动,...1 ,且 a|bc ,则 a|c ;(5) 若 (a, b) ? 1 ,且 a|c, b | c...
初等数论中蕴含的数学思想
目前,初等数论在计算机科学、代数编码、密码学、组合数学、计算方法等 领域内得到...[5]陈碧琴.矩阵初等变换在初等数论中的应用[J].南通工学院学报.2004.3.3 (...
初等数论精品课程申请及大纲
(5) 针对高等教育新形势和五年制师范教育的实际情况...而且近年来初等数论在计算器科学、组合数学、密码学...专题推荐 2014教师资格材料分析辅... 2014小学教师资格...
组合数学在数论中的应用实例
参考文献 1 R.A.Brualdi.组合学导引.华中理工大学出版社,1988 2 3 4 5 ...组合数学方兴未艾.广西教育出版社,2000 闵嗣鹤,严士健.初等数论.高等教育出版社,...
初等数论论文
初等数论论文素数及其应用 摘要:质数又称素数。指在...) 100 以内的质数有 2,3,5,7,11,13,17,19,...Selberg-艾狄胥的证明正好表示, 看似初等的组合数学,...
更多相关标签:
高中数学竞赛初等数论 | 初等数论 | 初等数论第三版答案 | 初等数论 pdf | 初等数论难题集 | 初等数论 潘承洞 | 初等数论及其应用 pdf | 初等数论及其应用 |