Alright, let's break this down clearly—you’re spot-on with the intuition that at least 2/3 of the numbers have to end up in the final union, and I’ll walk through the rigorous proof to back that up, plus cover the extreme case you mentioned.

Problem Recap #

First, let’s make sure we’re aligned on the setup:

• We have N distinct numbers (labeled 1 to N) and N nodes (labeled T₁ to T_N).
• Each node picks exactly 2/3 of the numbers (we’ll assume N is a multiple of 3 for simplicity—adjustments for non-multiples use floor/ceil functions and follow the same core logic) and shares its selection.
• The algorithm outputs the union of all numbers that are chosen by at least 2/3 of the nodes.
• We need to prove this union is at least 2/3 the size of the original number set, and note the edge case where every number makes it into the union.

Rigorous Proof of the Lower Bound #

We’ll use a proof by contradiction here—if we assume the opposite of what we want to show, we’ll end up with an impossible statement, which confirms our original intuition.

1. Define our sets:

   • Let U be the output union: all numbers selected by ≥2/3 of the nodes.
   • Let B be the "bad" set: numbers selected by <2/3 of the nodes. By definition, |U| + |B| = N (every number is in one set or the other).

2. Assume the opposite:
   Suppose for contradiction that |U| < 2N/3. That means |B| > N/3 (since |B| = N - |U|).

3. Double-count selected pairs:
   Let’s count the total number of times a number is picked by any node—we can do this two ways:

   • First way: Each node picks 2N/3 numbers, so total selected pairs (node + number) = N * (2N/3) = 2N²/3.
   • Second way: Sum up how many nodes picked each number. For numbers in U, this sum is at least |U|*(2N/3) (each is picked by at least 2/3 of nodes). For numbers in B, this sum is less than |B|*(2N/3) (each is picked by fewer than 2/3 of nodes).

   Combining these, we get:

   2N²/3 = (sum of picks for U) + (sum of picks for B)
   

   Rearranging to isolate the sum for B:

   sum of picks for B = 2N²/3 - sum of picks for U
   

4. Hit the contradiction:
   Since every number in U is picked by ≥2/3 of nodes, sum of picks for U ≥ |U|*(2N/3). Substitute that into the equation above:

   sum of picks for B ≤ 2N²/3 - |U|*(2N/3)
   

   But |U| = N - |B|, so substitute that in too:

   2N²/3 - (N - |B|)*(2N/3) = (2N/3)*(N - (N - |B|)) = |B|*(2N/3)
   

   So now we have sum of picks for B ≤ |B|*(2N/3). But wait—by definition of B, every number in B is picked by <2/3 of nodes, which means sum of picks for B < |B|*(2N/3).

   Let’s make this concrete with N=3k (a multiple of 3, so 2N/3=2k). If |B|>k (since |B|>N/3), then sum of picks for B < |B|*2k. But from the double-counting, we also have sum of picks for B ≤ |B|*2k. Taking this a step further:
   The sum of picks for B is also equal to total picks minus picks for U:

   sum of picks for B = 3k*2k - sum of picks for U = 6k² - sum of picks for U
   

   Since sum of picks for U ≥ |U|*2k and |U|=3k - |B|, substitute:

   sum of picks for B ≤6k² - (3k - |B|)*2k =6k² -6k² + |B|*2k= |B|*2k
   

   But we know sum of picks for B < |B|*2k (because every number in B is picked by fewer than 2k nodes). This gives us |B|*2k > sum of picks for B ≤ |B|*2k—which simplifies to |B|*2k > |B|*2k. That’s a contradiction!

5. Final Conclusion:
   Our initial assumption that |U| <2N/3 is impossible. Therefore, the size of the union U must be at least 2N/3.

Extreme Case: All Numbers Make the Union #

You’re right that there are scenarios where every number ends up in the output. For example, take N=3k and arrange the numbers in a circle. Each node T_i picks the next 2k numbers (wrapping around the circle if needed). In this setup, every number is picked by exactly 2k nodes (which is exactly 2/3 of the total nodes), so all N numbers meet the threshold and are included in the union.

内容的提问来源于stack exchange，提问作者ShaharA