买彩票问题

同事出了一道有意思的题，不光有意思，还有一定难度，这题是这样说的：有一种博彩游戏，一张彩票上可以选择10个不重复的数字，范围从1-100，开奖时，也会摇出10个数字，如果没有一个摇出的数字与你彩票上所选的数字相同，你就赢了。问你至少需要买多少张彩票才能确保赢。

我想到了一种买法，总共需要22张彩票就可确保获胜，买法是这样的：首先，买10张，上面所选的数字分别是1-10、11-20、21-30、……、91-100，这10张彩票相当于将1-100这100个数划分为10个区，根据鸽巢原理，如果不中奖，那么每个区里必然有且仅有一个摇出的数字。。现在再买10张彩票，买法如下：第一张数字为1-4及95-100，第二张及其余八张分别为5-14、15-24、25-34、……、85-94。如果第一个区里摇出的数字小于5，那么已后每个区里摇出的数字都必须小于X5（x可为1、2、3、……、9，下同），否则第二次买的10张彩票里必有一张没有所摇出的10个数字，获胜。因此再买一张彩票，每个所选数字都是每个区中大于5的数字必可获胜。如果第一个区里摇出的数字大于等于5，那么每个区里摇出的数字也必须大于等X5，故而再买一张每个所选数字都是每个区中小于5的数必可获胜。买齐这22张选票，则无论摇出的号码是多少，总有一张彩票可以获胜。

结果后来同事给出了一种更数量更少的买法，只需要14张即可，与我的买法一样，还是先买10张，分别是1-10、11-20、21-30、……、91-100，即将100个数划成互不相临的区，根据鸽巢原理，摇出的10个数字必然在这10个区里，且每区有且只有一个数字。现在来考虑第一个摇出的数字，必然只有两种可能，要么是1-5、要么是6-10。同样，对于第二个摇出的数字，也必然只有两种可能，要么是21-25，要么是26-30。因此，同样买4张彩票，选号分别为（1-5，21-25）、（1-5、26-30）、(6-10、21-25）、（6-10、26-30），无论前两个摇出的数是多少，这4张彩票总有一张上的数字与所摇出的数字不同。比如，摇出的数字是在(1-5）及(26-30）之间，那么(6-10，21-25）这张彩票即可获胜了。

现在来证明上面的买法的确可以确保张数最少。根据鸽巢原理，所买的彩票数如果小于等于10必不能确保获胜。同样，要想所买的彩票数最少，各张彩票所选数字要尽可能不重复，故而，这10张彩票可以将100划分为10个相反不重复的区域，也即每个区域中有10个数。无论这10个数是什么样的数，总可以重新为这10个数按顺序编号为1-10、11-20、……、91-100。故而，最优解必然以上面解法的第一步开始。并且在此前提下，考虑了摇出数字所在区间的所有可能（比如，第一区中摇的数要么小于5，要么大于等于5，第二区中摇出的数也要么小于15，要么大于等于15），故而可得知上面的解法是一种最优解。证毕。