每张彩票可以从１到２０中任选６个数，如果其中有三个（或三个以上）与抽出来的６个数重合（顺序不论），则可以得奖。最少买几张彩票就可以保证得奖？
解答：下列10张票保证得奖：
1 2 3 4 5 6
1 2 3 4 7 8
5 6 7 8 9 10
5 6 7 8 11 12
9 10 11 12 13 14
9 10 11 12 15 16
13 14 15 16 17 18
13 14 15 16 19 20
17 18 19 20 1 2
17 18 19 20 3 4
不知道9张行不行，感觉是不行。
Is there a formula to calculate this?1 2 3 4 5 6 1 2 3 4 7 8 5 6 7 8 9 10 5 6 7 8 11 12 9 10 11 12 13 14 9 10 11 12 15 16 13 14 15 16 17 18 13 14 15 16 19 20 17 18 19 20 1 2 17 18 19 20 3 40||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;"> 第1，2注，3，4注，...9，10注之间各有C(4,3)＝4种3数字组合的重复，共20个重复，正好等于C(6,3)，理论上还可能省出一张彩票。需要进一步证明。 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;"> 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">学习了一下组合设计的理论，有如下公式： 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">C(v1,k,t,m1,L,=b1) + C(v2,k,t,m2,L,=b2) = C(v1+v2,k,t,m1+m2-1,L,=b1+b2) 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">这里可以解释为从v个数字里每张彩票可以买k个数字，最少买b张彩票可以保证如果有m个数字在中奖范围内，至少有L张彩票中t个数字。 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;"> 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">C(19,6,3,6,1,=b1+b2) = C(7,6,3,3,1,=b1) + C(12,6,3,4,1,=b2) 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">显然，b1＝40||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;"> 1 2 3 4 5 6 1 2 3 4 7 8 5 6 7 8 9 10 5 6 7 8 11 12 9 10 11 12 1 2 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">9 10 11 12 3 4 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">第1，2注，3，4注，5,6注之间各有且仅有C(4,3)＝4种3数字组合的重复，共12个重复，小于C(6,3)，不可能再省出一张彩票。所以b2=6，0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">C(19,6,3,6,1,=b1+b2=10)。 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">显然，其它条件一样，20个数字里的最小解法不可能小于19个数字。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.TopChineseNews.com"; ; return false;">C(20,6,3,6,1,=10)。 |
学习了半天发现这是组合设计里的最小覆盖设计问题。 “覆盖设计并没有通用的公式，所以大部分的设计即使用如克雷般超级电脑也很难求出，全盘搜索的算法耗用时间将会是一个天文数字。”“对于一般的最小覆盖问题，仍然没有通用的构造方法。也就是说，目前市场上出现的许许多号码比较多的旋转矩阵，都很难保证是最小覆盖设计，也就是无法保证它是最优的。很多旋转矩阵不断地有人刷新它的下限纪录，也就是越来越接近最小覆盖设计。然而，要证明一个旋转矩阵是否已经是最小覆盖设计，是极其困难的，如果号码很少，还可以通过计算机编程用穷举的方式来解决，而号码稍微多一点，用穷举法超级电脑运算所耗用的时间也将是天文数字。” constant给出的是一种平衡旋转矩阵，通常平衡矩阵不是最优，这题目里是正确的。 |
这10张票是凑出来的，也没什么理论基础。后来发现这个方法可推广到10k个数（k>=3)：需要票数为5*(C(k,3)+C(k,2)*C(k,1))。对30，40，50个数，票数为50，140，300。 |
This is a typical set covering problem. We can formulate it as an integer programming problem and solve it. In general, it's NP hard with no polynominal time solution. |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |