Question

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

$6, 10, 12, 13$ {6, 10, 12, 13}是一张中奖彩票，因为它有 2 个共同的数字（6 和 13）。
$1, 3, 4, 9$ {1, 3, 4, 9}由于只有一个号码，所以不是中奖彩票。

表明购买 75 张彩票就足以保证中奖。
能保证分别最多有 49、24、7 张票吗？

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

首先要影响 MathSE 审阅者对你发布的问题做出积极反应。值得一提的是，几乎我见过的每个 MathSE 发布的问题，只要遵循了都会被点赞而不是被点踩。我并不一定提倡这个协议。相反，我只是陈述一个事实：如果你严格遵循链接的文章，不跳过/省略任何内容，你几乎可以保证得到积极的回应。 — 
你知道秘密彩票的号码吗？如果知道，那么前两个数字与中奖彩票相同。所以你有 $13 \times 12 \times (\binom{4}{2}) \times 2$ 13 \times 12 \times {4 \choose 2} \times 2中奖彩票号码。答案似乎是 $13 \times 12 \times (\binom{4}{2}) \times 2$ 13 \times 12 \times {4 \choose 2} \times 2中奖彩票的可能性。 —

Answer 1

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

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

十 = {{十 1 ， 十 2 ， 十 3 ， 十 4} | 十 1 ， 十 2 ， 十 3 ， 十 4 不同数字 [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 = {t_{1}, t_{2}, t_{3}, t_{4}}$ t = \{t_1, t_2, t_3, t_4\}涵盖所有 $x \in X$ x\in X使得 $| t \cap x | \geq 2$ |t\cap x| \geq 2。

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

练习 1. 的答案是，我们可以在每张票里放两对，所以我们只需要 $⌈ \frac{105}{2} ⌉ = 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, 13, 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)

有 $73$ 73在此之后，我们只需要 $⌈ \frac{73}{2} ⌉ = 37$ \left\lceil \frac{73}{2} \right\rceil = 37票。所以 $4 + 37 = 41$ 4+37=41总计。

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

Answer 2

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

将票分成 $4$ 4团体，
$1 - 4, 5 - 8, 9 - 12, 13 - 15$ 1-4,\quad 5-8, \quad 9-12,\quad 13-15命名，说， $A, B, C, D$ A,B,C,D

并从每个组中选择一个 #

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

这些组中奖券的配置可以

$4000, 3100, 2200, 2110, 1111$ 4000, \quad 3100, \quad 2200,\quad 2110,\quad 1111

和 $1$ 1仅当获胜彩票配置为 $1111$ 1111

然后采取所有 $4$ 4A 组的门票，并尝试 $3$ 3D组门票已用完 $3 \times 4 = 12$ 3\times4 = 12门票，（最坏的情况再次失败）

对 B 组 + D 组以及 C 组 + D 组重复此过程

因此，最坏情况下需要购买的最大票数是

$4 + 3 (4 + 4 + 4) = 40$ 4 + 3(4+4+4) = 40

我知道你的前四张票是 ${1, 2, 3, 4}$ \{1,2,3,4\}， ${5, 6, 7, 8}$ \{5,6,7,8\}， ${9, 10, 11, 12}$ \{9,10,11,12\}，和 ${13, 14, 15, x}$ \{13,14,15,x\}（ $x$ x是任意的）。但我不知道你说的“从 4 # 组的所有票，然后从 3 # 的小组中逐一尝试”是什么意思，所以我无法从你的回答中确定剩下的 $36$ 36票是什么。您能否添加更多解释，或者至少明确列出五张票作为示例？ — 
@MikeEarnest：我已经编辑过了，我相信现在应该很清楚了。 — 
呵呵，你现在数多了！对于 A 组 + D 组的情况，只有 $4$ 4需要门票；门票是 ${1, 13, 14, 15}, {2, 13, 14, 15}, {3, 13, 14, 15}$ \{1,13,14,15\},\{2,13,14,15\},\{3,13,14,15\}，和 ${4, 13, 14, 15}$ \{4,13,14,15\}同理，B组+D组和C组+D组都是各4张票，所以这个只有16张票。 — 
此外，你只需要四张初始票，以及 A 组 + D 组票，就可以实现这一点。所以你实际上已经找到了 8 张票的解决方案！ —

组合学 – 找到购买最多彩票来赢得彩票游戏的方法 – 数学

最佳答案
2

组合学 – 找到购买最多彩票来赢得彩票游戏的方法 – 数学

最佳答案 2

最佳答案
2