Thread: Problem 2.10
View Single Post
  #2  
Old 09-29-2016, 11:01 AM
magdon's Avatar
magdon magdon is offline
RPI
 
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 595
Default Re: Problem 2.10

Hint: Any dichotomy 2N points can be viewed as a dichotomy on the first N points plus a dichotomy on the second N points.
Quote:
Originally Posted by wolszhang View Post
I understand that for the case m(N) = 2^N, we can show that this is true. But how do we prove it when m(N) < 2^N? It seems like every single theorem is giving me an upper bound. Any hints would be super appreciated.
__________________
Have faith in probability
Reply With Quote