Math 板


LINE

写了一个略嫌(?)粗糙的证明,待高手检验 以下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







like.gif 您可能会有兴趣的文章
icon.png[问题/行为] 猫晚上进房间会不会有憋尿问题
icon.pngRe: [闲聊] 选了错误的女孩成为魔法少女 XDDDDDDDDDD
icon.png[正妹] 瑞典 一张
icon.png[心得] EMS高领长版毛衣.墨小楼MC1002
icon.png[分享] 丹龙隔热纸GE55+33+22
icon.png[问题] 清洗洗衣机
icon.png[寻物] 窗台下的空间
icon.png[闲聊] 双极の女神1 木魔爵
icon.png[售车] 新竹 1997 march 1297cc 白色 四门
icon.png[讨论] 能从照片感受到摄影者心情吗
icon.png[狂贺] 贺贺贺贺 贺!岛村卯月!总选举NO.1
icon.png[难过] 羡慕白皮肤的女生
icon.png阅读文章
icon.png[黑特]
icon.png[问题] SBK S1安装於安全帽位置
icon.png[分享] 旧woo100绝版开箱!!
icon.pngRe: [无言] 关於小包卫生纸
icon.png[开箱] E5-2683V3 RX480Strix 快睿C1 简单测试
icon.png[心得] 苍の海贼龙 地狱 执行者16PT
icon.png[售车] 1999年Virage iO 1.8EXi
icon.png[心得] 挑战33 LV10 狮子座pt solo
icon.png[闲聊] 手把手教你不被桶之新手主购教学
icon.png[分享] Civic Type R 量产版官方照无预警流出
icon.png[售车] Golf 4 2.0 银色 自排
icon.png[出售] Graco提篮汽座(有底座)2000元诚可议
icon.png[问题] 请问补牙材质掉了还能再补吗?(台中半年内
icon.png[问题] 44th 单曲 生写竟然都给重复的啊啊!
icon.png[心得] 华南红卡/icash 核卡
icon.png[问题] 拔牙矫正这样正常吗
icon.png[赠送] 老莫高业 初业 102年版
icon.png[情报] 三大行动支付 本季掀战火
icon.png[宝宝] 博客来Amos水蜡笔5/1特价五折
icon.pngRe: [心得] 新鲜人一些面试分享
icon.png[心得] 苍の海贼龙 地狱 麒麟25PT
icon.pngRe: [闲聊] (君の名は。雷慎入) 君名二创漫画翻译
icon.pngRe: [闲聊] OGN中场影片:失踪人口局 (英文字幕)
icon.png[问题] 台湾大哥大4G讯号差
icon.png[出售] [全国]全新千寻侘草LED灯, 水草

请输入看板名称,例如:Gossiping 或 站内搜寻

TOP