买彩票 (ZT from 灵机一动) - 珍珠湾ART

难度：+++

每张彩票可以从１到２０中任选６个数，如果其中有三个（或三个以上）与抽出来的６个数重合（顺序不论），则可以得奖。最少买几张彩票就可以保证得奖？

不对，太少了。

不管计算过程，我觉得这个数量级应该算正常。要保证中奖，就要考虑最坏情况，也就是买了所有不中的号码。这个数字当然应该很大，不然开彩票的就做不下去了。

直观地看，排除重复的情况，20选6的所有可能应该有C(20,6)=38760种，30030占总数78%，也就是说78%的彩票不会中，应该可以理解。30030之外每种选择都必然中奖。

C(14,6)+C(6,1)*C(14,5)+C(6,2)*C(14,4)+1中，第一项是1个数字都不中的情况，第二项是中1个，第三项是中2个。

也可以用另一种麻烦一点的方法来验证，就是算所有中奖的可能，然后用总数减去。特等奖6个数字全中为C(6,6)共1种，一等奖中5个数字有C(6,5)*C(14,1)共84种，二等奖中4个数字有C(6,4)*C(14,2)共1365种，三等奖中3个数字有C(6,3)*C(14,3)共7280种，共计有8730种得奖组合。用总数38760减去8730，也等于30030。

本贴由[勇敢的辛]最后编辑于：2006-4-15 3:49:17

我以为是随机选号，低估了这题目的难度。在这里解释组合的基本概念，实在多余。

要保证中3个，也就是只要中3个就可以，20个数字有3个可以不考虑。剩下17个数字取3个有680种。买680张一定可以买中。

问题是，680一定还不是最优化的结果。每注有6个数字，本身就可以有20种3数字组合。买680张的话一定有重复，举例来说，最起码1-6这1注就已经含了（1，2，3）和（4，5，6）这样完全不交叉的3数字组合，可以至少少买1注。

我试图找出优化的办法，没有头绪。搜索了一下想找点理论指导，结果找到了这个。

在乐透型彩票中，用旋转矩阵来组号中取了一等奖早已不算什么新闻，由于国内足彩的时间尚短，玩足彩的彩民朋友中使用旋转矩阵的还在少数，因此还未听说使用旋转矩阵中了一等奖的。随着旋转矩阵的优势逐渐被彩民认识，预计不远的将来将也会发生使用旋转矩阵捧得大奖归的彩民朋友。用复式中大奖的彩民也有一些。这样，许多彩民朋友可能会有这样的疑问：究竟用旋转矩阵和复式投注那个更好？

要回答这个问题，我们首先要知道什么是旋转矩阵，什么是复式投注。
所谓旋转矩阵就是根据数学的集合覆盖原理进行优化组合的一种方法，主要特点是使排列出的组合尽可能的分散以覆盖更多的组合，以尽可能少的注数提供低一级的中奖保证。而复式投注是以滴水不漏、无遗漏的全覆盖设计对所有可能的排列都进行组合。旋转矩阵是经过优化了的组合，复式投注是全部的组合。

一、从寇克曼女生问题讲起
旋转矩阵涉及到的是一种组合设计：覆盖设计。而覆盖设计，填装设计，斯坦纳系，t-设计都是离散数学中组合优化问题。它们解决的是如何组合集合中的元素以达到某种特定的要求。
为了使读者更容易明白这些问题，下面先从一道相当古老的数学名题讲起。

（一）寇克曼女生问题某教员打算这样安排她班上的十五名女生散步：散步时三名女生为一组，共五组。问能否在一周内每日安排一次散步，使得每两名女生在这周内一道散步恰好一次？看起来题目似乎很简单，然而它的彻底解决并不容易。事实上，寇克曼于1847年提出了该问题，过了100多年后，对于一般形式的寇克曼问题的存在性才彻底解决。用1-15这15个数字分别代表这15个女生，下面给出一组符合要求的分组方法：
星期日：（1，2，3），（4，8，12），（5，10，15），（6，11，13），（7，9，14）
星期一：（1，4，5），（2，8，10），（3，13，14），（6，9，15），（7，11，12）
星期二：（1，6，7），（2，9，11），（3，12，15），（4，10，14），（5，8，13）
星期三：（1，8，9），（2，12，14），（3，5，6），（4，11，15），（7，10，13）
星期四：（1，10，11），（2，13，15），（3，4，7），（5，9，12），（6，8，14）
星期五：（1，12，13），（2，4，6），（3，9，10），（5，11，14），（7，8，15）
星期六：（1，14，15），（2，5，7），（3，8，11），（4，9，13），（6，10，12）

该问题就是最典型的组合设计问题。其本质就是如何将一个集合中的元素组合成一定的子集系以满足一定的要求。表面上看起来，寇克曼女生问题是纯粹的数学游戏，然而它的解却在医药试验设计上有很广泛的运用。寇克曼女生问题是t-设计中很特殊的一类——可分解斯坦纳设计。下面我会详细解释这几个名词的含义。

（二）几种组合设计的含义
所谓t-设计是“策略组态，Tactical Configuration”的简称。
不妨用数学语言来定义t-设计：
S={S1，S2，……SV}是一个包含有v个元素的集合；
B1，B2，……，Bb是S的b个子集，而它们包含的元素个数和都是k个；
B={B1，B2，……Bb}是由这b个子集组成的集合（子集系），
对于固定整数t，和S的任意一个t元子集（t≥1），如果包含该子集的B中子集的个数都是同一个常数λt，则称B={B1,B2,……，Bb}是集合S上的一个t-(v,k,λt)设计，简称t-设计。
如果t-(v,k,λt)设计中，t=2,λ=1,则称为斯坦纳系（Steiner)。在该领域，我国已故的数学家陆家羲作出的巨大的贡献，如今每一本讲组合设计的书讲到这个问题，就不能不提到他的大名和以他的名字命名的定理。至今为止，斯坦纳系仍然存在着许多未解决的问题，至今还没有人证明S（17，5，4=476）和S（18，6，5=1428）的存在或不存在。虽然它的参数显得很小。而旋转矩阵涉及的则是另一种更加复杂、参数更多的组合设计——覆盖设计。
覆盖设计是一种经过精心设计的b个区组组成的子集系，其中每个区组都有k个元素组成。它可以确保如果选出k个元素，有m个在其中，至少有λ个区组中的元素有t个元素符合。区组中元素的顺序与区组的排列顺序不影响覆盖设计本身。
（c:v,k,t,m,λ=b)
可以用数学语言来定义比较简单的覆盖设计：
S={S1，S2，……SV）是一个包含有v个元素的集合；
B1，B2，……，Bb是S的b个子集，而它们包含的元素个数都是k个；
B={B1，B2，……Bb}是由这b个子集组成的集合（子集系）。
对于固定整数t，和S的任意一个t元子集（t≥1），如果该子集至少包含在B的λ个区组中，则称B={B1,B2，……，Bb}是集合S上的一个c-(v,k,λt）设计，简称覆盖设计。填装设计是与覆盖设计相反的设计：
S={S1，S2，……SV）是一个包含有v个元素的集合；
B1，B2，……，Bb是S的b个子集，而它们包含的元素个数都是k个；
B={B1，B2，……Bb}是由这b个子集组成的集合（子集系）。
对于固定整数t，和S的任意一个t元子集（t≥1），如果该子集至多包含在B的λ个区组中，则称B={B1,B2，……，Bb}是集合S上的一个p-(v,k,λt）设计，简称填装设计。 t-设计又叫恰好覆盖与恰好填装。t-设计不一定存在，而覆盖设计一定存在。t-设计中，λ=1，而覆盖设计一般λ>1。此外，t-设计中m=t，所以t-设计只是覆盖设计中比较特殊的一种。只要b足够大，显然覆盖设计一定存在。而有意义的是找到b的最小值，并找出在上最小值下的覆盖设计，此时的覆盖设计叫做最小覆盖。寻找最小覆盖的问题是组合优化问题的一类，被称为集合覆盖问题（SCP，Set covering problem)，与著名的推销员旅行问题或成本最小化、利润最大化问题，都是优化问题的一种。但是集合覆盖问题往往经这些问题更加困难。因为其它问题往往已经有比较成熟的、固定的方法。而覆盖设计并没有通用的公式，所以大部分的设计即使用如克雷般超级电脑也很难求出，全盘搜索的算法耗用时间将会是一个天文数字。这方面，算法就显得相当重要。Oester Grad教授创造出一种全新的模拟算法，它大大提高了求解覆盖设计的速度，但它不能保证找到的覆盖设计一定是最小覆盖设计。它具有很强的通用性。而之前的其他算法往往只能解决固定某些参数的特定问题，解决的往往只是一类问题。对覆盖设计的研究始于19世纪，1835年J·Plue Cker和W.S.B.Wool House(1844)开始研究此类问题。
到了1969年，人们发现它对军队中布阵与战略设计以及计算机芯片设计都大有用途，因此得到了迅速发展。在统计上，医药设计，农业试验，核研究，质量控制甚至在彩票中都大有用途。组合设计问题往往来自于智力游戏，对它们的研究也是纯数学的。但是当研究逐渐深入时，人们逐渐地在生产与其他学科中发现了它的用武之地。这样对它的研究就有了更强大的动力，吸引了更多人的注意，成果也就更加丰富。在选7的彩票涉及的旋转矩阵中，所有的（6，六）型和（5，五）型旋转矩阵都是t-设计。而一般的旋转矩阵都是覆盖设计。由于数学上对t-研究的比较多，所以有时候我们可以利用t-设计生成一些覆盖设计。如以下的设计即为一个t-(10,3,3)设计，它在有限射影几何中有很广泛的运用。
B：（2，3，4）  （1，5，10）  （1，6，9）
（1，7，8）  （2，9，10）  （3，8，10）
（4，8，9）  （4，6，7）  （3，5，7）  （2，5，6）即1-10每个数字都出现了3次，而且每两个数字恰好一起出现1次。从它可以生成10注10个号（7，六）型矩阵（它相当对称，平衡但不是最优的），具体生成方法很简单，取每一组的剩余的7个数就可以生成对应的一组。

（三）组合设计的研究内容
1.存在性问题
若给出要求，研究符合要求的组合设计是否存在，以及存在的条件问题。比如，彩票中的覆盖设计问题，它的存在性就不是问题，因为只要注数足够多，总是可以覆盖的（它的上限为复式投注即完全组合，有意义的是它的下限）。而t-设计又叫恰好覆盖，它的存在性就是一个很值得研究的问题，也就是说，参数要符合什么条件，才会存在恰好覆盖一次的设计。
对存在性的研究更多的是从理论上。然而，对于一般情形的t-设计是否存在的问题，还远远没有解决。
2.构造问题
如果已知某种组合设计存在时，如何把它们构造出来？这是与实际应用联系最紧的问题。实际上，最终无论在彩票中，还是新药设计中，人们关心的是构造出的组合设计。经过数学家上百年的努力，现在已经有一些构造方法。如利用有限的射影几何，关联矩阵，数论中的差集等构造出大量的设计。用组合论自身也能解决一些构造问题。然而，对于一般情形的组合设计的构造性问题离解决还相当遥远。比如彩票中覆盖设计问题（即旋转矩阵）当参数变大时，设计的难度是几何级数上升。对于一般的最小覆盖问题，仍然没有通用的构造方法。也就是说，目前市场上出现的许许多号码比较多的旋转矩阵，都很难保证是最小覆盖设计，也就是无法保证它是最优的。很多旋转矩阵不断地有人刷新它的下限纪录，也就是越来越接近最小覆盖设计。然而，要证明一个旋转矩阵是否已经是最小覆盖设计，是极其困难的，如果号码很少，还可以通过计算机编程用穷举的方式来解决，而号码稍微多一点，用穷举法超级电脑运算所耗用的时间也将是天文数字。

3.组合设计之间的关系
例如：一个组合设计是否与另外一个组合设计本质上一样的（同构）。比如把组合中某两个数字互换，这两个设计应该算同一种设计。每一种设计的同构设计是非常多的。有些同构是很难直接看出的，所以就需要研究同构的设计有什么特点，如何准确快速的判断和产生同构设计。组合设计还研究如何由一个组合设计构造出另外一个。
比如旋转矩阵中存在着这样的问题，比如10个号码01-10，开始我先选定3注：
01，02，03，04，05，06，07，
01，03，05，07，08，09，10，
02，04，06，07，08，09，10
问如何添上尽可能少的注数，使它成为（7，六）型平衡式矩阵。
又如一个旋转矩阵与另外一个旋转矩阵是否同构。即使两个旋转矩阵所有参数都相同，也不一定同构。然而，在实际运用中，人们并不关心同构问题。因为只要能用就行了。
又如10个号码（7，六）型的有8注，比如是01-10这10个号码，问能否在这基础上添上尽可能少的注数，使得它成为11个号码的（7，六）型的旋转矩阵（01-11）。

4.计数问题
如果已知某类组合设计存在，自然希望知道这类设计的个数。也就是说互不同构的设计的个数。然而，这个问题是一个极其艰难的问题，现在还很少人去研究它。

看了上边这些，我突然觉得，我这辈子，能研究出一点什么前人没研究出来的新东西，死都欣慰了......我又突然觉得，中国人的创造力（注一），真的是不行。但是中国人（或者说东亚人）的学习能力，模仿能力和改造力（注二）还是不错的。

创造力：即“发明”，前人没有的问题，提出来，前人没有的理论，创造出来，前人没有的新东西，造出来。

改造力：世界上已经有了理论的，已经发明出来的新东西，中国人拿来改进，改装，更新。