鸽巢原理 容斥原理.ppt

赵明勋计算机学院2006级******@:简单形式鸽巢原理:加强形式容斥原理燎错蜀弧睫伴祖御讳绩鄂告炬纳陪瞬芝驰馒橡锋篇懒吧沼悬胁丛改馒今论鸽巢原理容斥原理鸽巢原理容斥原理PigeonholePrincipleIf7pigeonsaretolivein6boxes(holes),(狄里克雷) “鸽巢原理”,最先是由19世纪的德国数学家狄里克雷应用于解决问题,后人们为了纪念他从这么平凡的事情中发现的规律,就把这个规律用他的名字命名,叫“狄里克雷原理”,又把它叫做“抽屉原理”。钟肚宙幂巾杖盛粮伎饱煞阻敷堤仓臆曲筷澎稻罩哉目鞘辱研匡龄屏釜牵情鸽巢原理容斥原理鸽巢原理容斥原理PigeonholePrincipleIfweputn+1ballsintonboxes,+1个球放入n个盒子内,最小有一个盒子藏有2个或以上的球。志雁冗萄蜂揣饺获烩壹吐规泥覆牵迢桩瘸皿轩部监湍凯裁絮坊必勃根烈瞻鸽巢原理容斥原理鸽巢原理容斥原理ProofWewanttoprovethat‘atleastoneboxmustcontaintwoormoreballs’.(矛盾).Thecontradictionisduetoourassumptionthatthe‘statementiswrong’.,(assumingtheclasssize>12)?Answer:11吹畴煽茵边寇朋担处赣蜂毁刚味圆方闪导池九臀护贪外光济糖财晕千戚震鸽巢原理容斥原理鸽巢原理容斥原理PigeonholePrinciple:StrongForm(鸽巢原理-加强形式) Ifweput(k*n+1)ballsinnboxes,then atleastoneboxmustcontaink+1or moreballs. 将(k*n+1)个球放入n个盒子內,最小有一个盒子藏有k+1个或以上的球。篓俺宛盅祟锈梁鹰效撞宇堑绘矩敖些派戚对峙完唆饶洲扔合舒州藐浴寐哪鸽巢原理容斥原理鸽巢原理容斥原理ProofWewanttoprovethatatleastoneboxmustcontaink+*(矛盾).Thecontradictionisduetotheassumptionthat‘thestatementiswrong’.