利用递推数列巧解圆环涂色问题

一、问题如图1在圆中,将圆分n等份得到n个区域M1,M2,M3,…,Mn（n≥2）.现取k（k≥2）种颜色对这n个区域涂色,要求每相邻的两个区域涂不同的两种颜色,试求涂色的方案有多少种？解设涂色方案总数为an（n≥2）,当n=2时,显然知：a2=k（k-1）.现探求{an}的递推公式：     

综合题新编选登

题188有一种摇奖盘是将一单位圆分成n（n≥3）个均匀的扇形区域构成的（如图1所示），现需将这n个扇形区域用三种不同颜色涂色，并要求三种颜色都要使用，且相邻的区域不能同色，如果把含有n（n≥3）价扇形区域摇奖盘的涂色方法数记为an（图1），     

一个涂色问题的推广

文[1],[2]讨论了这样一个涂色问题(为了问题的严谨与简洁,这里对原题作了改写):题目将图1中n(n≥3)个扇形区域用三种不同颜色涂色,要求相邻的区域不能够同色,且三种颜色都要使用,求所有的涂色方法总数an.     

完全多部图K_(1*r,3*(k-2))的m数

如果对一个图G的每个顶点v,任给一个k-列表L(v),使得G要么没有正常列表染色,要么至少有两种正常列表染色,则称图G具有M(k)性质.定义图G的m数为使得图G具有M(k)性质的最小整数k,记为m(G).已有研究表明,当k=3,4时,图K_(1*r,3*(k-2))具有M(k)性质,且当r≥2时,m(K_(1*r,3*(k-2)))=k.本文将上述结论推广到每一个k,证明了对任意r∈N~+,k≥3,图K_(1*r,3*(k-2))具有M(k)性质,且当k≥4,r≥(k-2)时,m(K_(1*r,3*(k-2)))=k.此外,得到图K_(1,3,3,3)的m数为4,该图是图K_(1*r,3*(k-2))中r=1,k=5时的特殊情况,同时也是现有研究中尚未解决的一个问题.     

一道高考压轴题的加强

2005年高考重庆卷(理)压轴题为:数列{an}满足a1=1,且an 1=(1 1/(n2 n))an 1/2n(n≥1).(Ⅰ)用数学归纳法证明:an≥2(n≥2).(Ⅱ)已知不等式ln(1 x)0成立,证明:an0(k∈N*),∴由已知ln(1 x)0)有ln(1 1k2 k)<1k2 k,∴1 1k2 k相似文献   

“传球”问题可看作“种植”问题的一个应用

文[1]把“传球”问题推广到一般情况:m(m≥2,m∈N*)个人互相传球,甲先发球作为第一次传球,经过n(n≥2,m∈N*)次传球后,球仍回到甲手中,则不同的传球方法有多少种?并推得一般结论an=mm-1[(m-1)n-1-(-1)n-1].图1圆文[2]把“种植”问题推广到一般情况:如图1,一个圆形花坛分为n(n≥3,n∈N*)个扇形,种植m(m≥3,m∈N*)种不同颜色的花,要求相邻两部分种植不同颜色的花,有多少种不同的种植方法?也推得一般结论:an=(m-1)n (-1)n(m-1).文[1]的结论难记,随手整理一下:an=1m[(m-1)n (-1)n(m-1)].这是文[2]的结论的m分之一!这激起了我的好奇心!经过探索…     

具有固定行列和k的阶为2k-2的(0,1)-矩阵的最大跳跃数

1992年Brualdi与Jung首次引出了最大跳跃数M(n,k),即每行每列均含k个1的阶为n的(0,1)-矩阵的跳跃数的极大数,给出了满足条件1≤k ≤n ≤10的(0,1)-矩阵的最大跳跃数M(n,k)的一个表,并提出了几个猜想,其中包括猜想M(2k-2,k)=3k-4 [k-2/2].本文证明了当k≥11时,对每个A∈∧(2k-2,k)有b(A)≥4.还得到了该猜想的另一个反例.     

一个猜想的证明

文[1]给出了:在任意△ABC中,A、B、C表示其三内角,则cos3A cos3B cos3C≥38.(当且仅当△ABC为正三角形时等号成立)并给出了如下猜想:cosnA cosnB cosnC≥32n.(n≥2,n∈N*)　(*)本文将利用著名的Jacobsthal不等式[2]:“设x≥0,y≥0,对任意正整数n,有xn (n-1)yn≥nxyn-1”的变形:“当x≥0,y>0时,有xnyn-1≥nx-(n-1)y”,以及相关的函数性质给出猜想的如下证明.证明　(1)若n=2k(k∈N*)时,　cosnA cosnB cosnC=cos2kA cos2kB cos2kC=(14)k-1[(cos2A)k(14)k-1 (cos2B)k(14)k-1 (cos2C)k(14)k-1]≥(14)k-1{[kcos2A-14(k-1)] [kcos2B-14…     

FUNDAMENTAL GROUPS OF CLOSED POSITIVELY CURVED MANIFOLDS WITH ALMOST DISCRETE ABELIAN GROUP ACTIONS

Let M be a closed n-manifold of positive sectional curvature.Assume that M admits an effiective isometrical T 1×Zkp-action with p prime.The main result of the article is that if k=1 for n=3 or k (n+1)/4 for n≥5,then there exists a positive constant p(n),depending only on n,such that π1(M) is cyclic if p≥p(n).     

综合题新编选登

题147设数列{an}满足:当n=2k-1(k∈N*)时,an=n;当n=2k(k∈N*)时,an=ak.1)求a2 a4 a6 a8 a10 a12 a14 a16;2)若Sn=a1 a2 a3 … a2n-1 a2n,证明:Sn=4n-1 Sn-1(n≥2);3)证明:S11 S12 … S1n<1-41n.解1)原式=a1 a2 a3 a4 a5 a6 a7 a8=a1 a1 a3 a1 a5 a3 a7 a1=4a1 2a3 a5 a7=4×1 2     

一道二项式证明题的证法研究与改造

在二项式内容中曾做到这样一题:例题证明C1n 2C2n 3C3n … nCnn=n·2n-1(n∈N*).1例题的证法研究本题一般常见的证明方法有3种.证明1(数学归纳法)n=1时,左边=C11=1,右边=1·21-1=1,等式成立;假设n=k(k≥1)时等式也成立,即C1k 2C2k 3C3k … kCkk=k·2k-1,则n=k 1时,C1k 1 2C2k 1     

隔项等比数列的研究

隔项等比数列的例子几次在高考题中出现 ,探讨隔项等比数列的性质很有必要 .为了便于研究 ,先给出隔项等比数列的定义 .定义　如果数列 { an}满足关系 :a2 n+ 1a2 n-1=q1,a2 n+ 2a2 n=q2 (n=1,2 ,3,… ) ,其中 q1,q2均为非零常数 ,则称数列 { an}为隔项等比数列 .定理 1　隔项等比数列 { an}的通项公式是an=1+(- 1) n-12 a1qn-121+1+(- 1) n2 a2 qn-222 .证　当 n为奇数时 ,令 n=2 k- 1(n∈ N) k=n+12 ,则有a2 k-1=a1qk-11 an=a1qn+ 12 -11=a1qn-121(1)当 n为偶数时 ,令 n=2 k k=n2 ,则有a2 k=a2 qk-12 an=a2 qn2 -12 =a2 qn-222 (2 )综…     

关于Erds-Jacobson-Lehel问题的门槛(英文)

设σ(k ,n)表示最小的正整数m ,使得对于每个n项正可图序列 ,当其项和至少为m时 ,有一个实现含k+ 1个顶点的团作为其子图 .Erd s等人猜想 :σ(k ,n) =(k - 1 ) ( 2n-k)+ 2 .Li等人证明了这个猜想对于k≥ 5,n≥ k2 + 3是对的 ,并且提出如下问题 :确定最小的整数N(k) ,使得这个猜想对于n≥N(k)成立 .他们同时指出 :当k≥ 5时 ,5k- 12 ≤N(k)≤ k2 + 3.Mubayi猜想 :当k≥ 5时 ,N(k) =5k - 12 .在本文中 ,我们证明了N( 8) =2 0 ,即Mubayi猜想对于k =8是成立的     

猜想M(2k,k+1)=3k-1+[(k-1)/2]的反例

Brualdi与Jung在[1]中研究了一类具有固定线和k的n×n矩阵上的最大跳跃数M(n,k),并提出猜想M(2k, k + 1) = 3k - 1 + [(k-1)/2].本文给出了这一猜想的两个反例．     

2006年中国数学奥林匹克试题(第1天)

1实数a1,a2,…,an满足a1 a2 … an=0,求证:max1≤k≤n(ak2)≤3nni∑-=11(ai-ai 1)2.证只需对任意1≤k≤n,证明不等式成立即可.记dk=ak-ak 1,k=1,2,…,n-1,则ak=ak,ak 1=ak-dk,ak 2=ak-dk-dk 1,…,an=ak-dk-dk 1-…-dn-1,ak-1=ak dk-1,ak-2=ak dk-1 dk-2,…,a1=ak dk-1 dk-2 … d1,把上面这n个等式相加,并利用a1 a2 … an=0可得nak-(n-k)dk-(n-k-1)dk 1-…-dn-1 (k-1)dk-1 (k-2)dk-2 … d1=0.由Cauchy不等式可得(nak)2=[(n-k)dk (n-k-1)dk 1 … dn-1-(k-1)dk-1-(k-2)dk-2-…-d1]2≤(∑k-1i=1i2 ∑n-ki=1i2)(∑n-1i=1di2)≤(∑n-1i=1i2)(n∑-…     

圆环染色问题的公式解法

一、圆环染色问题计算公式 如图1所示,把一个圆环（从圆环“中心”出发,以环“半径”为界）分成n（n≥2）个扇形区域A1A2…An,现有m（m≥2）种不同颜色为这n个区域染色,要求相邻两个区域An与An＋1颜色不同,则共有an=（m-1）^n＋（-1）^n（m-1）种不同的染色方法。     

着色问题的一种统一解法

有 n种颜色给 m个区域涂色 ,解决这样一类问题 ,比较容易产生“疑团”[1 ] .现介绍一种统一的方法 ,可以轻松地解决问题 ,疑团随之烟消云散 .图 1例 1　如图 1 ,用 5种颜色给图中的五个区域涂色 ,每个区域涂一种颜色 ,相邻区域不同颜色 ,那么共有多少种不同的涂色方法 ?解　我们把每一个区域画成一个小圆圈 ,相邻区域间用一条线段连接起来 ,就可以得到图 2 .图 2图 3用 5种颜色 ,有 A55种方法 ;用 4种颜色 (参见图 2 ) ,共有 3种情形 ,有 3A4 4种方法(相同的颜色打上同样的阴影 ,以下同 ) ;用 3种颜色 (参见图 3) ,有 A33种方法 ;所以共有…     

浅谈一类排列、组合问题的解法

1 基本模型。命题把一个圆面分成n个扇形区域，并把这n个扇区依次编以1-n的标号，若用m种不同的颜色去涂这n个扇区，要求每个扇区只涂一种颜色，且相邻的扇区不同色，则不同的涂色方法共有(m-1)[(m-1)^n-1 (-1)^n]种，其中m≥2，n≥2，m，n均是整数．     

一道国家集训题的导数证明

2005年国家集训题:从任意n(n≥2)个给定的正数a1,a2,…,an中,每项取k个数作乘积,所有这种乘积的算术平均值的k次方根,称为这n个数的k次对称平均,记为Bk.即Bk=a1a2…ak a1a3…ak 1 … an 1-k…an-1anCkn1k求证:若1≤k1相似文献   

Bounds for Two Classes of Graph Spectrum and Proof of Their Conjectures

Let λ_k be the kth greatest eigenvalue of forest F (or tree T) on n vertices, then λ_k=-λ_(n-k 1). Hong Yuan proposed the following conjecture: Conjecture 1. Suppose T is a tree with n vertices and edge independence number q. For k≤q, λ_k(T)≥λ_k(S_(n-2k 2)~(2h-2) with equality iff T≌S_(n-2k 2)~(2k-2), where S_(n-2k 2)~(2k-2) is formed from a K_(1,n-2k 1) and a path P_(2k-2) by joining with an edge a vertex of degree one of P_(2k-2) to the vertex of degree n-2k 1 of K_(1,n-2k 1).