\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section4.6Exercises

1

Suppose you are given a list of \(n\) integers, each of size at most \(100n\). 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\), \(\sqrt{n}\), \(n\), \(n^2\), \(n^3\), \(2^n\), … steps. In other words, ignore multiplicative constants.):

  1. Determine if the number \(2n+7\) is in the list.

  2. Determine if there are two numbers in the list whose sum is \(2n+7\).

  3. 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).

  4. Determine if there is a number \(i\) for which all the numbers in the list are between \(i\) and \(i+2n+7\).

  5. Determine the longest sequence of consecutive integers belonging to the list.

  6. Determine the number of primes in the list.

  7. Determine whether there are three integers \(x\), \(y\) and \(z\) from the list so that \(x+y=z\).

  8. Determine whether there are three integers \(x\), \(y\) and \(z\) from the list so that \(x^2+y^2=z^2\).

  9. Determine whether there are three integers \(x\), \(y\) and \(z\) from the list so that \(xy=z\).

  10. Determine whether there are three integers \(x\), \(y\) and \(z\) from the list so that \(x^y=z\).

  11. Determine whether there are two integers \(x\) and \(y\) from the list so that \(x^y\) is a prime.

  12. 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\), for each \(i=1,2, \dots, t-1\)).

  13. 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).

  14. 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).

  15. Determine for which integers \(m\), the list contains at least \(10\%\) of the integers from \(\{1,2,\dots,m\}\).

2

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?

3

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\). 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.

4

Let \(n=10,000\). Suppose a friend tells you that he has a secret family of subsets of \(\{1,2,\dots,n\}\), 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.

5

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)}\). What is \(E^5(n^2)\)?