在彩票游戏中,每张彩票由从以下集合中选择的 4 个不同数字组成1、2 、… 、151,2,…,15{1, 2, \ldots, 15}主持人随机选择一张秘密票,中奖票必须至少有 2 个数字与主持人的秘密票相同。玩家可以选择购买任何特定的票。例如,如果主持人的秘密票是1 , 5 , 6 , 131,5,6,十三{1, 5, 6, 13}:
- 6 ,10 ,12 ,136,10,12,十三{6, 10, 12, 13}是一张中奖彩票,因为它有 2 个共同的数字(6 和 13)。
- 1 , 3 , 4 , 91,3,4,9{1, 3, 4, 9}由于只有一个号码,所以不是中奖彩票。
- 表明购买 75 张彩票就足以保证中奖。
- 能保证分别最多有 49、24、7 张票吗?
我不知道如何开始。有人能给我一些提示吗?
\endgroup
2
最佳答案
2
这是一个覆盖问题。元素都是444-数字的组合1、2 、… 、151,2,…,151, 2,\dots, 15即主持人可以选择的所有票证。票证涵盖所有具有交集的元素,交集大小至少为222和它一起。
为了使其更加正式,让我们介绍一下需要覆盖的空间
X=\{ \space \{x_1,x_2,x_3,x_4\} \space | \space x_1,x_2,x_3,x_4 \text{ distinct numbers of } [15]\}
和票t = {吨1,吨2,吨3,吨4}吨={吨1,吨2,吨3,吨4}t = \{t_1, t_2, t_3, t_4\}涵盖所有x∈X十∈十x\in X使得| t∩x | ≥2|吨∩十|≥2|t\cap x| \geq 2。
换句话说,我们必须确保所有(152) =105(152)=105\binom{15}{2}=105我们的一张彩票中有一对数字
练习 1. 的答案是,我们可以在每张票里放两对,所以我们只需要⌈1052⌉ =53⌈1052⌉=53\left\lceil \frac{105}{2} \right\rceil = 53门票就可以做到这一点。
对于练习2.41 票就足够了。拿走票{ 1 , 2 , 3 , 4 } , { 5 , 6 , 7 , 8 } , { 9 , 10 , 11 , 12 }{1,2,3,4},{5,6,7,8},{9,10,11,12}\{1,2,3,4\}, \{5,6,7,8\}, \{9,10,11,12\}和{ 1 , 13 , 14 , 15 }{1,十三,14,15}\{1,13,14,15\}。通过这种强力的圣人计算:
X = Subsets(range(1,16),4)
ts = [set((1,2,3,4)), set((5,6,7,8)), set((9,10,11,12)), set((1,13,14,15))]
rest = [x for x in X if all(len(set(x).intersection(t))<2 for t in ts)]
#print (len(rest))
#print (rest)
restPairs = set()
for x in rest:
for p in Subsets(x,2):
restPairs.add(p)
print (len(restPairs))
#print (restPairs)
有737373在此之后,我们只需要⌈732⌉ =37⌈732⌉=三十七\left\lceil \frac{73}{2} \right\rceil = 37票。所以4 + 37 = 414+三十七=414+37=41总计。
对于下限,某种近似是必要的。或者在拿到上面提到的四张票之后(很明显,最好是拿这些票(或者拿任何元素而不是111最后)只有144144144剩下的票数可以覆盖,我们可以把它变成一个线性整数规划问题。
\endgroup
0
|
B 部分提示757575可能是一个不必要的大数字,因此解决 B 部分将自动解决 A 部分
将票分成444团体,
1 − 4 ,5−8 ,9−12 ,13 − 151−4,5−8,9−12,十三−151-4,\quad 5-8, \quad 9-12,\quad 13-15命名,说,甲、乙、丙,德一个,乙,碳,德A,B,C,D
并从每个组中选择一个 #
如果你幸运的话,你可能会偶然得到444中奖号码,但我们想在整个过程中评估最坏的情况。
这些组中奖券的配置可以
4000 ,3100 ,2200 ,2110 ,11114000,3100,2200,2110,11114000, \quad 3100, \quad 2200,\quad 2110,\quad 1111
和111仅当获胜彩票配置为111111111111
然后采取所有444A 组的门票,并尝试333D组门票已用完3 × 4 = 123×4=123\times4 = 12门票,(最坏的情况再次失败)
对 B 组 + D 组以及 C 组 + D 组重复此过程
因此,最坏情况下需要购买的最大票数是
4 + 3 (4 + 4 + 4 )= 404+3(4+4+4)=404 + 3(4+4+4) = 40
\endgroup
4
-
\begingroup
我知道你的前四张票是{ 1 , 2 , 3 , 4 }{1,2,3,4}\{1,2,3,4\},{ 5 , 6 , 7 , 8 }{5,6,7,8}\{5,6,7,8\},{ 9 , 10 , 11 , 12 }{9,10,11,12}\{9,10,11,12\}, 和{ 13 , 14 , 15 , x }{十三,14,15,十}\{13,14,15,x\}(十十x是任意的)。但我不知道你说的“从 4 # 组的所有票,然后从 3 # 的小组中逐一尝试”是什么意思,所以我无法从你的回答中确定剩下的三十六三十六36票是什么。您能否添加更多解释,或者至少明确列出五张票作为示例?
\endgroup
– -
\begingroup
@MikeEarnest:我已经编辑过了,我相信现在应该很清楚了。
\endgroup
– -
\begingroup
呵呵,你现在数多了!对于 A 组 + D 组的情况,只有444需要门票;门票是{ 1 , 13 , 14 , 15 } , { 2 , 13 , 14 , 15 } , { 3 , 13 , 14 , 15 }{1,十三,14,15},{2,十三,14,15},{3,十三,14,15}\{1,13,14,15\},\{2,13,14,15\},\{3,13,14,15\}, 和{ 4 , 13 , 14 , 15 }{4,十三,14,15}\{4,13,14,15\}同理,B组+D组和C组+D组都是各4张票,所以这个只有16张票。
\endgroup
–
-
\begingroup
此外,你只需要四张初始票,以及 A 组 + D 组票,就可以实现这一点。所以你实际上已经找到了 8 张票的解决方案!
\endgroup
–
|
首先要影响 MathSE 审阅者对你发布的问题做出积极反应。值得一提的是,几乎我见过的每个 MathSE 发布的问题,只要遵循了都会被点赞而不是被点踩。我并不一定提倡这个协议。相反,我只是陈述一个事实:如果你严格遵循链接的文章,不跳过/省略任何内容,你几乎可以保证得到积极的回应。
\endgroup
–
你知道秘密彩票的号码吗?如果知道,那么前两个数字与中奖彩票相同。所以你有13 × 12 × (42) ×2十三×12×(42)×213 \times 12 \times {4 \choose 2} \times 2中奖彩票号码。答案似乎是13 × 12 × (42) ×2十三×12×(42)×213 \times 12 \times {4 \choose 2} \times 2中奖彩票的可能性。
\endgroup
–
|