组合数学鸽巢原理那一章的习题证明对于任意给定的52个整数,存在其中的两个整数,要么两者的和能被100整除,要么两者的差能

gj2112022-10-04 11:39:541条回答

组合数学鸽巢原理那一章的习题
证明对于任意给定的52个整数,存在其中的两个整数,要么两者的和能被100整除,要么两者的差能被100整除.

已提交,审核后显示!提交回复

共1条回复
whskssd 共回答了18个问题 | 采纳率88.9%
这题目有个假设,其实就是0可以被100整除
1:分51个盒子.第一是尾数是00,第二个是尾数01或99,第三个是尾数02或98.第51个是尾数50.
2:必定有一个盒子中有2个数.
3:如果尾数相同,则差被100整除,如果尾数不同,则和被100整除
1年前

相关推荐

组合数学递推关系看不懂...下了好几份课件, 看了很久依然看不懂怎么由特征根方程求得a(n)通项公式,现在只会从a(n)
组合数学递推关系看不懂...
下了好几份课件, 看了很久依然看不懂怎么由特征根方程求得a(n)通项公式,
现在只会从a(n)+C(1)a(n-1)+C(2)a(n-2)+...+C(k)a(n-k)=0得到特征多项式C(x)=x^k+C1x^(k-1)+...+C(k-1)x+C(k)
之后母函数G(x)=P(x)/(1+C(1)x+...+C(k)x^k)的P(x)是什么东西, 分母那堆东西怎么求就看不懂了... 跳到了G(x)=A1/(1-a1x)+...则不知道A1~Ak要怎么求
再之后怎么由G(x)得到a(n)也更搞不懂... 课件没找到一个明确的公式能套进去解...
请问有谁能直接地提供一下从特征多项式求得an通项式的明确步骤? 不求证明, 只需要算法步骤和公式 谢谢`
iamxuzj1年前1
我是一个销售 共回答了22个问题 | 采纳率100%
设特征多项式C(x)=x^k+C1x^(k-1)+...+C(k-1)x+C(k)的根为{r1,r2,.,rk}
这里P(x)=a1x+(a1c1+a2)x²+.+(a1c(k-1)+a2c(k-2)+.a(k-1)c1+ak)x^k
其中a1,a2,...,ak是数列an的初始条件值
然后母函数G(x)=P(x)/(1+C(1)x+...+C(k)x^k)=P(x)/[(1-r1x)(1-r2x)...(1-rkx)]
则可将有理函数G(x)分解为A1/(1-r1x)+.+Ak/(1-rkx)
其中A1,A2.Ak的求法可以设G(x)=A1/(1-r1x)+.+Ak/(1-rkx),
则A1/(1-r1x)+.+Ak/(1-rkx)=P(x)/[(1-r1x)(1-r2x)...(1-rkx)],等式两边同乘(1-r1x)
得A1+A2(1-r1x)/(1-r2x)+.+Ak(1-r1x)/(1-rkx)=P(x)/[(1-r2x)...(1-rkx)],然后再令x=1/r1
得A1=P(1/r1)/[(1-r2/r1)...(1-rk/r1)],类似等式两边同乘(1-rix),然后再令x=1/ri,便可得Ai
然后利用1/(1-rx)=1+rx+(rx)²+...,将G(x)中每一项写成这种形式
整理后便可以求得G(X)=f(0)+f(1)x+f(2)x²+.f(n)x^n+.
其中x^n的系数f(n)=A1(r1)^n+A2(r2)^n+...+Ak(rk)^n便为an的通项公式
即an=A1(r1)^n+A2(r2)^n+...+Ak(rk)^n
组合数学第四版(RichardA.Brualdi)第11章的几道课后题(8、20、21).被采纳的一定追加分数.一共3道
组合数学第四版(RichardA.Brualdi)第11章的几道课后题(8、20、21).被采纳的一定追加分数.一共3道题:
liud1an1年前1
yzwolf 共回答了24个问题 | 采纳率95.8%
首先核对一下术语,题目里的"图"应该是指简单图,即每一对顶点间至多有一条边.
21题中的"一般图"才是一般意义上的图,允许多条边和起点终点重合的边.
8.将G的顶点分为两个子集:由前k个顶点组成的集合A,和后n-k个顶点组成的集合B.
在和式∑{1 ≤ i ≤ k} di中,A中顶点之间的边被计数两次,A中顶点与B中顶点之间的边被计数1次.
因此有不等式∑{1 ≤ i ≤ k} di ≤ 2·A内部的边数+A到B的边数,两部饭分别估计.
①因为G是简单图,A有k个顶点,故A内部的边数 ≤ C(k,2) = k(k-1)/2.
②A到B的边数 = ∑{k+1 ≤ i ≤ n} 第i个顶点到A的边数.
易见,第i个顶点到A的边数 ≤ di,且第i个顶点到A的边数 ≤ k.
故A到B的边数 ≤ ∑{k+1 ≤ i ≤ n} min{k,di}.
综合得∑{1 ≤ i ≤ k} di ≤ k(k-1)+∑{k+1 ≤ i ≤ n} min{k,di},即所求证.
20.用反证法,假设图不连通,则可将图分成两个子图的无交并.
设两个子图分别为k阶和n-k阶,1 ≤ k ≤ n-1.
作为简单图,二者的边数分别至多为C(k,2)和C(n-k,2).
因此原图边数 ≤ C(k,2)+C(n-k,2)
= (k²-k+(n-k)²-(n-k))/2
= (k²+(n-k)²-n)/2
= (n²+(n-2k)²-2n)/4
≤ (n²+(n-2)²-2n)/4 (1 ≤ k ≤ n-1)
= (n-1)(n-2)/2,
与至少有(n-1)(n-2)/2+1条边矛盾.
例子:一个n-1阶完全图恰有(n-1)(n-2)/2条边,添加一个孤立点即可.
21.基本事实:一个图中奇顶点的个数必为偶数.
设G中包含x的连通分支为H,由H包含奇顶点x,H至少还包含一个奇顶点.
但G中只有两个奇顶点x和y,故H包含y.
G中已存在x到y的路径,因此添加新边{x,y}不改变G的连通性.
即G连通当且仅当G*连通.