\begingroup

在彩票游戏中,每张彩票由从以下集合中选择的 4 个不同数字组成1、2 151215{1, 2, \ldots, 15}主持人随机选择一张秘密票,中奖票必须至少有 2 个数字与主持人的秘密票相同。玩家可以选择购买任何特定的票。例如,如果主持人的秘密票是1 , 5 , 6 , 13156十三{1, 5, 6, 13}

  • 6 10 12 1361012十三{6, 10, 12, 13}是一张中奖彩票,因为它有 2 个共同的数字(6 和 13)。
  • 1 , 3 , 4 , 91349{1, 3, 4, 9}由于只有一个号码,所以不是中奖彩票。
  1. 表明购买 75 张彩票就足以保证中奖。
  2. 能保证分别最多有 49、24、7 张票吗?

我不知道如何开始。有人能给我一些提示吗?

\endgroup

2

  • 1
    \begingroup
    首先要影响 MathSE 审阅者对你发布的问题做出积极反应。值得一提的是,几乎我见过的每个 MathSE 发布的问题,只要遵循了都会被点赞而不是被点踩。我并不一定提倡这个协议。相反,我只是陈述一个事实:如果你严格遵循链接的文章,不跳过/省略任何内容,你几乎可以保证得到积极的回应。
    \endgroup


    – 

  • \begingroup
    你知道秘密彩票的号码吗?如果知道,那么前两个数字与中奖彩票相同。所以你有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


    – 



最佳答案
2

\begingroup

这是一个覆盖问题。元素都是444-数字的组合1、2 1512151, 2,\dots, 15即主持人可以选择的所有票证。票证涵盖所有具有交集的元素,交集大小至少为222和它一起。

为了使其更加正式,让我们介绍一下需要覆盖的空间

= { { 1234} |  1234 不同数字 [ 15 ] }={ {1234} | 1234 不同数量的 [15]}

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 = {1234}={1234}t = \{t_1, t_2, t_3, t_4\}涵盖所有x∈Xx\in X使得| tx |2||2|t\cap x| \geq 2

换句话说,我们必须确保所有152 =105152=105\binom{15}{2}=105我们的一张彩票中有一对数字

练习 1. 的答案是,我们可以在每张票里放两对,所以我们只需要1052 =531052=53\left\lceil \frac{105}{2} \right\rceil = 53门票就可以做到这一点。

对于练习2.41 票就足够了。拿走票{ 1 , 2 , 3 , 4 } , { 5 , 6 , 7 , 8 } , { 9 , 10 , 11 , 12 }{1234}{5678}{9101112}\{1,2,3,4\}, \{5,6,7,8\}, \{9,10,11,12\}{ 1 , 13 , 14 , 15 }{1十三1415}\{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 =37732=三十七\left\lceil \frac{73}{2} \right\rceil = 37票。所以4 + 37 = 414+三十七=414+37=41总计。

对于下限,某种近似是必要的。或者在拿到上面提到的四张票之后(很明显,最好是拿这些票(或者拿任何元素而不是111最后)只有144144144剩下的票数可以覆盖,我们可以把它变成一个线性整数规划问题。

\endgroup

0

\begingroup

B 部分提示757575可能是一个不必要的大数字,因此解决 B 部分将自动解决 A 部分

将票分成444团体,
1 4 5−8 9−12 13 151458912十三151-4,\quad 5-8, \quad 9-12,\quad 13-15命名,说,,一个A,B,C,D

并从每个组中选择一个 #

如果你幸运的话,你可能会偶然得到444中奖号码,但我们想在整个过程中评估最坏的情况。

这些组中奖券的配置可以

4000 3100 2200 2110 1111400031002200211011114000, \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+34+4+4=404 + 3(4+4+4) = 40

\endgroup

4

  • \begingroup
    我知道你的前四张票是{ 1 , 2 , 3 , 4 }{1234}\{1,2,3,4\}{ 5 , 6 , 7 , 8 }{5678}\{5,6,7,8\}{ 9 , 10 , 11 , 12 }{9101112}\{9,10,11,12\}, 和{ 13 , 14 , 15 , x }{十三1415}\{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十三1415}{2十三1415}{3十三1415}\{1,13,14,15\},\{2,13,14,15\},\{3,13,14,15\}, 和{ 4 , 13 , 14 , 15 }{4十三1415}\{4,13,14,15\}同理,B组+D组和C组+D组都是各4张票,所以这个只有16张票。
    \endgroup


    – 


  • \begingroup
    此外,你只需要四张初始票,以及 A 组 + D 组票,就可以实现这一点。所以你实际上已经找到了 8 张票的解决方案!
    \endgroup


    –