Hello, I’ve been thinking about this problem for quite a while and i don’t see a clear path towards the solution. Can someone give me a hint?

Advertisements

Hello, I’ve been thinking about this problem for quite a while and i don’t see a clear path towards the solution. Can someone give me a hint?

Advertisements

%d bloggers like this:

Part (a) is a hint: a problem that looks quite hard is in bijection with a problem that is easy to solve.

The same bijection is useful for part (b), and several ways to proceed (none of which is immediate). Another hint: algebraic methods may be easier than combinatorial methods in this problem.

For part (a) (and I’m hoping for part (b) as well) it simplifies things greatly to think of

the subsets as binary selection vectors where if

and 0 otherwise. The geometric interpretation is elucidating.

For part (b) we’ve been trying to think of it as a switching problem. That is we have

ideal switches that can be on or off. Then starting with all of them off, how many ways

are there to turn them on and off times so that they’re all off at the end.

Whether or not this is a fruitful approach, I don’t know…