HW 2 Q3b

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?



  1. 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.

  2. mattcadier

    For part (a) (and I’m hoping for part (b) as well) it simplifies things greatly to think of
    the subsets S_i as binary selection vectors {\bf w} where w_k = 1 if k\in S_i
    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
    n 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 k times so that they’re all off at the end.
    Whether or not this is a fruitful approach, I don’t know…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: