作者eminem2003 (强森)
看板Math
标题Re: [离散] 一题离散
时间Sun Mar 24 01:50:05 2019
写了一个略嫌(?)粗糙的证明,待高手检验
以下C(a,b)表示Ca取b
题目是说任意给两正整数n,k
若存在由小到大的k个正整数,上面是写m1~mk
依序放到 C( ,1)+C( ,2)+C( ,3)+....C( ,k)的那些空白处
也就是 C(m1,1)+C(m2,2)+C(m3,3)+....C(mk,k) 之值为n的话,
m1~mk的选择是唯一的
为了方便我假设 F(v,k)=C(v1,1)+C(v2,2)+C(v3,3)+....C(vk,k)
v是一个k维非负整数向量, vi表示第i个分量 而且v1<v2<...vk
用数学归纳法
x=1的时候显然(用x是因为不重复符号
难处在於
当x=k成立时,k+1怎麽也得到论证成立
x=k成立时,原命题的等价叙述是
一旦给定任何一个上述向量v=(v1,v2,...,vk),所得到F(v,k)的值
和任何另一个上述性质向量u=(u1,u2....,uk),得到的F(u,k)值必不相等
现在考虑x=k+1
比较以下两者的差值
F(v,k+1)=C(v1,1)+C(v2,2)+C(v3,3)+....C(vk,k)+C(vk+1,k+1)简称F1
F(u,k+1)=C(u1,1)+C(u2,2)+C(u3,3)+....C(uk,k)+C(uk+1,k+1)简称F2
先直接比最後项C(vk+1,k+1)和C(uk+1,k+1)
首先只需要讨论两者不相等的情况,
因为如果相等,F1和F2的前面k项总和是相等的,这个时候因为x=k成立
必然得到u=v
所以最後两项不相等,为了方便理解,我用实际数字示范
以下证明用到的关键是 C(n,k-1)+C(n,k)=C(n+1,k)的移项
C(n+1,k)-C(n,k)=C(n,k-1)
然後我的目的是要证明差值无法相等
WLOG, C(vk+1,k+1)>C(uk+1,k+1)
就假设前者是C(101,61) (数字乱掰的) 对应的总和是F1
也就是现在的情形k=60已经好了要证明k+1=61
我想要证明此时无论u怎麽给,F1永远大於F2
换句话说,两者最後一项之间的大小决定两者总值大小
本质上就是再算前面k项差值的估计值并且她无法大过最後一项之间的差
现在目标是想决定u使得F2的值可以追上目前和F1的差距
uk的最好选择(以下所说的最好选择都是使得差值最小的选择)
就是C(100,61) (因为61被定住了,比101小最大数字为100)
但是F1-F2目前只看最後一项差值是C(101,61)-C(100,61)=C(100,60)
所以目前F1比F2至少还大C(100,60)
uk-1的最好选择就是C(99,60) (因为60被定住了,比100小最大数字为99)
但是F1-F2目前差额变成了C(100,60)-C(99,60)=C(99,59)
所以目前F1比F2至少还大C(99,59)
好了有没有看出来即使每一次都选u让F2和F1的差值最小都还是永远追不上
可以继续玩下一个
uk-2的最好选择就是C(98,59) (因为59被定住了,比99小最大数字为98)
不罗嗦,差值变成了C(98,58)
所以继续再玩到没得玩,本例子的结局是
差额变成了C(41,1)
但是u1的最好选择只有C(40,1)
所以用这组数字得到的结果就是F1>F2无论u的选择
但是你把数字变成未知正整数可以得到一模一样结果,刚刚只是方便理解
真的要证明就把上面的101改成q,61改成p吧,然後依序减1做一模一样论证
记得要假设q>p
重新整理一下最终得到的结论就是:
若
当x=k时成立
x=k+1也会成立,根据上面的估计
因为只需要讨论两者最後一项不相等的情况
然而最後一项比较大的总值也会比较大,无论u向量的选择,
一旦v向量给定以後,换句话说就是总值F1,F2两者不会相等
会出现这样的情形是因为我们假设两者最後一项不相等,
一旦不相等,总值就会不相等,
不过若两者最後一项相等,根据一开始讨论,
u=v
因此选择m1,m2.....mk+1的选择只有唯一一种
数学归纳法结束
※ 引述《redcarp0702 (红鲤鱼)》之铭言:
: http://i.imgur.com/pl9Hz6j.jpg
: 目前学校刚教完计数原理,看完题目觉得跟二项式系数有关,但想了一个小时完全没头绪,m_k除了均为持续递增的自然数外,就完全没规律了,求解谢谢!!
: -----
: Sent from JPTT on my Sony E6853.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.137.157.39
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1553363409.A.B9B.html
1F:推 redcarp0702 : 十分感谢!!!! 03/24 12:39
※ 编辑: eminem2003 (101.137.253.123), 03/24/2019 19:05:57