跨组选择并集的下限
Lower bound on union of selection across group
设置如下：
- 有 N 个数字标记为 1....N
- 有 N 个节点标记为 T1,...TN
- 每个节点 selects（根据一些不共享的内部标准）正好是 N 个数字的 2/3 并广播其决定。
- 算法的结果是 select 由 至少 2/3 的节点 编辑的数字的并集
我正在尝试计算生成的并集大小的下限。
我的直觉是，至少有 2/3 的数字必须始终出现在联合中，但我在形式化证明时遇到了麻烦...
在"worst case"中，每个节点将select一组不同的2/3数字，导致所有数字成为工会.
你的直觉不正确。鉴于 N 可以被 3 整除（否则节点不能 select 恰好 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 为数字 selected 至少 2N/3 次的计数。由于总共有2N2/3 select个离子，最多可以select个数N次，我们有：
2N2/3 - (N-k)(2N/3 - 1) <= kN
求解 k，我们得到：
k >= 3N / (N+3)
这个比例好像没有下限。如果 N 很大，我们可以有 k=3.
我们可以有 k < 2N/3 只要 N>=6。让我们试试吧。我们有 6 个节点，每个 selects 4 个数字。对于 6 个数字中的每一个，这里是 select 它的节点：
number1: 123456
number2: 123456
number3: 123
number4: 456
number5: 123
number6: 456
只有 1/3 的数字被至少 2/3 的节点select编辑。
设置如下：
- 有 N 个数字标记为 1....N
- 有 N 个节点标记为 T1,...TN
- 每个节点 selects（根据一些不共享的内部标准）正好是 N 个数字的 2/3 并广播其决定。
- 算法的结果是 select 由 至少 2/3 的节点 编辑的数字的并集
我正在尝试计算生成的并集大小的下限。
我的直觉是，至少有 2/3 的数字必须始终出现在联合中，但我在形式化证明时遇到了麻烦...
在"worst case"中，每个节点将select一组不同的2/3数字，导致所有数字成为工会.
你的直觉不正确。鉴于 N 可以被 3 整除（否则节点不能 select 恰好 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 为数字 selected 至少 2N/3 次的计数。由于总共有2N2/3 select个离子，最多可以select个数N次，我们有：
2N2/3 - (N-k)(2N/3 - 1) <= kN
求解 k，我们得到：
k >= 3N / (N+3)
这个比例好像没有下限。如果 N 很大，我们可以有 k=3.
我们可以有 k < 2N/3 只要 N>=6。让我们试试吧。我们有 6 个节点，每个 selects 4 个数字。对于 6 个数字中的每一个，这里是 select 它的节点：
number1: 123456
number2: 123456
number3: 123
number4: 456
number5: 123
number6: 456
只有 1/3 的数字被至少 2/3 的节点select编辑。