Chapter 8: Advanced Counting Techniques

Construct a variation of the algorithm described in Example 12 along with justifications of the steps used by the algorithm to find the smallest distance between two points if the distance between two points is defined to be\(d\left( {\left( {{x_i},{y_i}} \right),\left( {{x_j},{y_j}} \right)} \right) = \max \left( {\left| {{x_i} - {x_j}} \right|,\left| {{y_i} - {y_j}} \right|} \right)\).

Suppose someone picks a number\(x\)from a set of\(n\)numbers. A second person tries to guess the number by successively selecting subsets of the\(n\)numbers andasking the first person whether\(x\)is in each set. The first person answers either "yes" or "no." When the first person answers each query truthfully, we can find\(x\)using\(\log n\)queries by successively splitting the sets used in each query in half. Ulam's problem, proposed by Stanislaw Ulam in 1976 , asks for the number of queries required to find\(x\), supposing that the first person is allowed to lie exactly once.

a) Show that by asking each question twice, given a number\(x\)and a set with\(n\)elements, and asking one more question when we find the lie, Ulam's problem can be solved using \(2\log n + 1\) queries.

b) Show that by dividing the initial set of\(n\)elements into four parts, each with\(n/4\)elements,\(1/4\)of the elements can be eliminated using two queries. [Hint: Use two queries, where each of the queries asks whether the element is in the union of two of the subsets with\(n/4\) elements and where one of the subsets of\(n/4\)elements is used in both queries.]

c) Show from part (b) that if\(f(n)\)equals the number of queries used to solve Ulam's problem using the method from part (b) and\(n\)is divisible by\(4\), then \(f(n) = f(3n/4) + 2\)

d) Solve the recurrence relation in part (c) for\(f(n)\).

e) Is the naive way to solve Ulam's problem by asking each question twice or the divide-and-conquer method based on part (b) more efficient? The most efficient way to solve Ulam's problem has been determined by A. Pelc [Pe87].

In Exercises\(29 - 33\), assume that\(f\)is an increasing function satisfying the recurrence relation\(f(n) = af(n/b) + c{n^d}\), where \(a \ge 1,b\) is an integer greater than\(1\), and \(c\)and\(d\)are positive real numbers. These exercises supply a proof of Theorem\(2\).

Use generating functions (and a computer algebra package, if available) to find the number of ways to make change for 1 using pennies, nickels, dimes, and quarters with

a) no more than 10 pennies.

b) no more than 10 pennies and no more than 10 nickels.

c) no more than 10 coins

Suppose someone picks a number\(x\)from a set of\(n\)numbers. A second person tries to guess the number by successively selecting subsets of the\(n\)numbers and asking the first person whether\(x\)is in each set. The first person answers either "yes" or "no." When the first person answers each query truthfully, we can find\(x\)using\(\log n\)queries by successively splitting the sets used in each query in half. Ulam's problem, proposed by Stanislaw Ulam in 1976, asks for the number of queries required to find\(x\), supposing that the first person is allowed to lie exactly once.

a) Show that by asking each question twice, given a number\(x\)and a set with\(n\)elements, and asking one more question when we find the lie, Ulam's problem can be solved using \(2\log n + 1\) queries.

b) Show that by dividing the initial set of\(n\)elements into four parts; each with\(n/4\)elements, \(1/4\)of the elements can be eliminated using two queries. (Hint: Use two queries, where each of the queries asks whether the element is in the union of two of the subsets with\(n/4\) elements and where one of the subsets of\(n/4\)elements is used in both queries.)

c) Show from part (b) that if\(f(n)\)equals the number of queries used to solve Ulam's problem using the method from part (b) and\(n\)is divisible by\(4\), then \(f(n) = f(3n/4) + 2\)

d) Solve the recurrence relation in part (c) for\(f(n)\).

e) Is the naive way to solve Ulam's problem by asking each question twice or the divide-and-conquer method based on part (b) more efficient? The most efficient way to solve Ulam's problem has been determined by A. Pelc (Pe87).

In Exercises\(29 - 33\), assume that\(f\)is an increasing function satisfying the recurrence relation\(f(n) = af(n/b) + c{n^d}\), where \(a \ge 1,b\) is an integer greater than\(1\), and \(c\)and\(d\)are positive real numbers. These exercises supply proof of the Theorem\(2\).

Use generating functions to find the number of ways to make change for \(100 using

a) \)10, \(20, and \)50 bills.

b) \(5, \)10, \(20, and \)50 bills.

c) \(5, \)10, \(20, and \)50 bills if at least one bill of each denomination is used.

d) \(5, \)10, and $20 bills if at least one and no more than four of each denomination is used.

Find the generating function for the finite sequence 1,4,16,64,256 .

In Exercises 3-8, by a closed-form, we mean an algebraic expression not involving a summation over a range of values or the use of ellipses.

Use Exercise 29 to show that if \(a = {b^d}\), then \(f(n)\) is \(O\left( {{n^d}\log n} \right)\).

If $\mathit{G}\mathbf{\left(}\mathit{x}\mathbf{\right)}$is the generating function for the sequence$\left\{a_k\right\}$, what is the generating function for each of these sequences?

a)$\mathbf{2}{\mathit{a}}_{\mathbf{0}}\mathbf{,}\mathbf{2}{\mathit{a}}_{\mathbf{1}}\mathbf{,}\mathbf{2}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{2}{\mathit{a}}_{\mathbf{3}}\mathbf{,}\mathbf{\dots }$

b) $\mathbf{0}\mathbf{,}{\mathit{a}}_{\mathbf{0}}\mathbf{,}{\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}{\mathit{a}}_{\mathbf{3}}\mathbf{,}\mathbf{\dots }$(Assuming that terms follow the pattern of all but the first term)

c) $\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}{\mathit{a}}_{\mathbf{3}}\mathbf{,}\mathbf{\dots }$(Assuming that terms follow the pattern of all but the first four terms)

d)${\mathit{a}}_{\mathbf{2}}\mathbf{,}{\mathit{a}}_{\mathbf{3}}\mathbf{,}{\mathit{a}}_{\mathbf{4}}\mathbf{,}\mathbf{\dots }$

e) ${\mathit{a}}_{\mathbf{1}}\mathbf{,}\mathbf{2}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{3}{\mathit{a}}_{\mathbf{3}}\mathbf{,}\mathbf{4}{\mathit{a}}_{\mathbf{4}}\mathbf{,}\mathbf{\dots }$[Hint: Calculus required here.]

f)${\mathit{a}}_{\mathbf{0}}^{\mathbf{2}}\mathbf{,}\mathbf{2}{\mathit{a}}_{\mathbf{0}}{\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{1}}^{\mathbf{2}}\mathbf{+}\mathbf{2}{\mathit{a}}_{\mathbf{0}}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{2}{\mathit{a}}_{\mathbf{0}}{\mathit{a}}_{\mathbf{3}}\mathbf{+}\mathbf{2}{\mathit{a}}_{\mathbf{1}}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{2}{\mathit{a}}_{\mathbf{0}}{\mathit{a}}_{\mathbf{4}}\mathbf{+}\mathbf{2}{\mathit{a}}_{\mathbf{1}}{\mathit{a}}_{\mathbf{3}}\mathbf{+}{\mathit{a}}_{\mathbf{2}}^{\mathbf{2}}\mathbf{,}\mathbf{\dots }$

Use Exercise 29 to show that if $\mathit{a}\mathbf{=}{\mathit{b}}^{\mathbf{d}}$, then $\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}$is $\mathit{O}\mathbf{(}{\mathit{n}}^{\mathbf{d}}\mathbf{}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{)}$.