algorithm - 跨组选择并集的下限

Question

设置如下:

1. 有 N 个数字标记为 1....N
2. 有N个节点标记为T1,...TN
3. 每个节点选择(通过一些不共享的内部标准)正好是 N 个数字的 2/3 并广播其决定。
4. 算法的结果是由至少 2/3 的节点选择的数字的并集。

我正在尝试计算生成的并集大小的下限。

我的直觉是，至少有 2/3 的数字必须始终出现在联合中，但我在形式化证明时遇到了麻烦......

在“最坏情况”下，每个节点将选择一组不同的 2/3 数字，导致所有数字成为并集的一部分。

Answer 1

你的直觉是不正确的。鉴于 N 可以被 3 整除(否则节点无法选择恰好 2/3 的数字)，计算实际下限的关键是:

The count of numbers selected at least 2N/3 times is minimized by maximizing the count of numbers selected exactly 2N/3 - 1 times.

令k 为至少选择2N/3 次的数字的计数。由于总共有2N²/3个选择，一个数最多可以被选择N次，我们有:

2N²/3 - (N-k)(2N/3 - 1) <= kN

求解k，我们得到:

k >= 3N/(N+3)

这个比例似乎没有下限。如果 N 很大，我们可以有 k=3。

只要 N>=6，我们就可以有 k < 2N/3。让我们试试吧。我们有 6 个节点，每个节点选择 4 个数字。对于 6 个数字中的每一个，这里是选择它的节点:

number1: 123456
number2: 123456
number3: 123
number4: 456
number5: 123
number6: 456

只有 1/3 的数字被至少 2/3 的节点选中。