Suppose you are given a list of \(n\) integers, each of size at most \(100n\text{.}\) How many operations would it take you to do the following tasks (in answering these questions, we are interested primarily in whether it will take \(\log n\text{,}\)\(\sqrt{n}\text{,}\)\(n\text{,}\)\(n^2\text{,}\)\(n^3\text{,}\)\(2^n\text{,}\) … steps. In other words, ignore multiplicative constants.):
Determine if there are two numbers in the list whose product is \(2n+7\) (This one is more subtle than it might appear! It may be to your advantage to sort the integers in the list).
Determine the longest arithmetic progression in the list (a sequence \((a_1, a_2,\dots,a_t)\) is an arithmetic progression when there is a constant \(d\neq 0\) so that \(a_{i+1}=a_i+d\text{,}\) for each \(i=1,2, \dots, t-1\)).
Determine the number of distinct sums that can be formed from members of the list (arbitrarily many integers from the list are allowed to be terms in the sum).
Determine the number of distinct products that can be formed from members of the list (arbitrarily many integers from the list are allowed to be factors in the product).
If you have to put \(n+1\) pigeons into \(n\) holes, you have to put two pigeons into the same hole. What happens if you have to put \(mn+1\) pigeons into \(n\) holes?
Consider the set \(X=\{1,2,3,4,5\}\) and suppose you have two holes. Also suppose that you have \(10\) pigeons: the \(2\)-element subsets of \(X\text{.}\) Can you put these \(10\) pigeons into the two holes in a way that there is no \(3\)-element subset \(S=\{a,b,c\}\subset X\) for which all pigeons from \(S\) go in the same hole? Then answer the same question if \(X=\{1,2,3,4,5,6\}\) with \(15 = C(6,2)\) pigeons.
Let \(n=10,000\text{.}\) Suppose a friend tells you that he has a secret family of subsets of \(\{1,2,\dots,n\}\text{,}\) and if you guess it correctly, he will give you one million dollars. You think you know the family of subsets he has in mind and it contains exactly half the subsets, i.e., the family has \(2^{n-1}\) subsets. Discuss how you can share your hunch with your friend in an effort to win the prize.
Let \(N\) denote the set of positive integers. When \(f:N\rightarrow N\) is a function, let \(E(f)\) be the function defined by \(E(f)(n) = 2^{f(n)}\text{.}\) What is \(E^5(n^2)\text{?}\)
