>>14374270The two formulations aren't the same. The question asks for something stronger than the alternative formulation. In the alternative, you're only allowed to take intersections and unions. In the original question, you're allowed to use complements on top of that. I'll answer the question.
Easy upper bound on the minimum: 2n.
Put the elements in a square, use the n rows and n columns as a basis. To get an element, take the intersection of the row and column it's in.
Better bound: ~2log_2(n)
We're going full CS for this.
We may as well assume the elements are the numbers from 0 to n^2-1, via a bijection.
The 0th subset is the subset that contains all numbers with 1 in the 0th position in their binary representation.
The 1st subset is the subset that contains all numbers with 1 in the 1st position in their binary representation.
The 2nd subset is the subset that contains all numbers with 1 in the 2nd position in their binary representation.
And so on, and hopefully you see where this is going. There will be roughly ceiling(log_2(n^2)) subsets (because that's how many bits there are in n^2-1).
To get an element, read it out in binary. Make an intersection of subsets based on the bit in the pth position:
If the pth position contains a 1, take the pth subset.
If the pth position contains a 0, take the complement of the pth subset.
And you're done.
To do this with the second formulation, just add the complements of the subsets, so you have about 4log_2(n) subsets.
