Pigeonhole Quandries

Question

Struggling with these problems, which I believe are both cases of pigeonhole principle but I am struggling to get the right answer.

1) An IT survey asks desktop computer users the following questions: -- which OS type they are using (Windows, macOS, Linux, other) -- if Windows: Windows 10, 8.1, 7 or other -- if macOS: 10.12, 10.11, lower -- if Linux: Mint, Debian, Ubuntu, other -- screen resolution used (lower, equal or higher than 1920x1080) -- whether they play games on their desktop (yes/no) How many people have to be asked to guarantee that you will find 10 with identical answers?

2) How many subsets are there of a set of 100 elements that contain at least 4 elements? You must simplify your answer until it contains only unresolved large exponential expressions of the form with a and b integers.

Thank you.

Answer 1

For (2)

There are $2^{100}$ subsets of a set of $100$ elements (each element is either in or our of the subset). How many of them have fewer than 4 elements? ${{100}\choose{3}}+{{100}\choose{2}}+{{100}\choose{1}}+{{100}\choose{0}}=166751$. So the number of subsets containing at least $4$ elements is $2^{100}-166751$.

Answer 2

Hint for Number 1: How many different surveys are possible? i.e. what is the maximum possible number of surveys, so that any two will differ in at least one answer.

Number 2 isn't really a PHP problem.

Answer 3

1) If there $N$ different possible ways to answer the survey, and $9$ people answer it each of the $N$ ways, then there will not be $10$ people answer the same. If you add one more than that $9N +1$ person must answer the survey the same as $9$ other people.

Answer 4

You always start with four choices. then depending on the OS you have additional choices within that branch of the OS choice. Then you multiply by the screen res and games. Add the results.

(4*4*2*2) + (4*3*2*2) + (4*4*2*2) + (4*2*2)