Maximizing your profit [Solution]

Problem was here: http://ruffnsluff.blogspot.com/2016/08/maximizing-your-profit.html


To repeat:
Suppose you had $K$ dollars and knew the price of gold over the next $n$ days. You want to invest all the $K$ dollars in buying gold once, and then sell all the gold at a later day (both among those $n$ days).

You want to maximize your profit.

Assume you get the prices as an array of length $n$.

Can you find an $O(n)$ time algorithm for this?

Solution

---

If you invest $K$ dollar at price $p_i$, you get $\dfrac{K}{p_i}$ units of gold. If you now sell at $p_j$, the profit you make of $\dfrac{K \times p_j}{p_i}- K$.

Thus you just need to maximize $\dfrac{p_j}{p_i}$.

This you can do by keeping track of the min $p_i$ seen so far, and the max possible $\dfrac{p_j}{p_i}$ as you increase $i$ (go from earlier days to later days). You can also avoid floating point compares if needed.

Application of AM >= GM solution

The problem was to show that

$$\left(1 + \frac{1}{n+1}\right)^{n+1} \gt \left(1 + \frac{1}{n}\right)^{n}$$

using the AM >= GM inequality.

Let $x_1 = x_2 = \dots = x_{n} = 1 + \frac{1}{n}$ and $x_{n+1} = 1$

Applying the AM >= GM to the $x_i$ we get that

$$\frac{x_1 + x_2 + \dots + x_{n+1}}{n+1} \ge \sqrt[n+1]{x_1x_2\dots x_{n+1}}$$

i.e

$$ \frac{n\left(1+\frac{1}{n}\right) + 1}{n+1} \ge \sqrt[n+1]{\left(1 + \frac{1}{n}\right)^{n}}$$

i.e

$$ \left(1+\frac{1}{n+1}\right)  \ge \left(1 + \frac{1}{n}\right)^{\frac{n}{n+1}}$$

Raising both sides to the $(n+1)^{th}$ power gives us the result.

Maximizing your profit

Suppose you had $K$ dollars and knew the price of gold over the next $n$ days. You want to invest all the $K$ dollars in buying gold once, and then sell all the gold at a later day (both among those $n$ days).

You want to maximize your profit.

Assume you get the prices as an array of length $n$.

Can you find an $O(n)$ time algorithm for this?

[Solution]

Appilcation of AM >= GM

Arithmetic mean greater than or equal to geometric means is a well known ineqaility.

Use that to show that

$$\left(1 + \frac{1}{n+1}\right)^{n+1} \gt \left(1 + \frac{1}{n}\right)^{n}$$


[Solution]

Generate a random red-black tree [Solution]

The problem was to generate a random structurally unique red-black tree on $n$ nodes.

Solution

---

Now if we knew exactly how many red-black trees of $n$ nodes have $L$ nodes in the left subtree, then we can generate them as follows.

Count the total number of trees with $n$ nodes. For each $L$ in $\{0,1,\dots,n\}$,  count the fraction $\alpha_L$ of them with $L$ left nodes in the left subtree.

Now generate a random number $L$ in $\{0,1,2,\dots, n\}$ with probability $\alpha_L$. This will be the number of children in the left subtree. The number of children in the right subtree is $n-1-L$. Recursively generate the subtrees now.

This works because the subtrees of a red-black tree are red-black trees themselves. On how to count, see this previous post on this blog on counting red-black trees (some modifications might be needed).

exp(x) inequality [Solution]

The problem was to show that

$$e^x \ge 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$$

for all $x \ge 0$ and integer $n \ge 0$.

Solution

---

Let $f_{n}(x) = 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$ with $f_{0}(x) = 1$

Now $e^x \ge f_{0}(x)$ for all $x \ge 0$

Now suppose $e^x \ge f_{n}(x)$ for all $x \ge 0$.

Let $h(x) = e^x - f_{n+1}(x)$

Now $h(0) = 0$.

We also have that the derivative of $h$, $h'(x) = e^x - f_n(x)$

By induction assumption $h'(x) \ge 0$ for all $x \ge 0$.

Thus $h$ is increasing and so $h(x) \ge h(0) = 0$ for all $x \ge 0$.

Thus by induction, we are done.

Generate a random red-black tree

Following up on two previous posts.

Given $n$, can you give an algorithm to generate a random red-black tree consisting of $n$ nodes? Each structurally unique tree should have an equal chance of being generated (we are not interested in the actual assignment of colors).

[Solution]

exp(x) inequality

Quick one.

Use induction to show that

$$e^x \ge 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$$

for all $x \ge 0$.

$n$ is a natural number $\ge 0$.

[Solution]

Number of AVL trees [Solution]

The problem was to compute the number of AVL tree of $n$ nodes.

Solution

---

The solution is very similar to that of the corresponding problem for red-black trees.

Using dynamic programming, try to compute $T[n, h]$ the number of AVL trees on $n$ nodes with height $h$.

Now write a recursive formula based on the AVL tree properties, and you have an algorithm.

I will leave the details to you.

Harmonic numbers are not integers [Solution]

The problem was to show that

$$ H_n = \sum_{k=1}^{n} \frac{1}{k} = 1 + \frac{1}{2} + \dots + \frac{1}{n}$$

is never an integer for $ n \gt 1$.

Solution

---

There are multiple solutions. One of them uses Bertrand's postulate, which says that there is a prime between $n$ and $2n$ for any $n \gt 1$.

Now consider the largest prime $p$ in $1, 2, \dots, n$.

The denominator of $H_n$ is divisible by $p$. The numerator has terms divisible by $p$, plus the term $1 \times 2 \times \dots \times (p-1) \times (p+1) \times \dots \times n$

By Bertrand's postulate, we have that $2p \gt n$ (otherwise $p$ won't be the largest prime).

Thus the numerator is not divisible by $p$. Thus $H_n$ is not an integer.

Number of AVL trees

AVL trees were one of the first balanced tree structures to provide $O(\log n)$ operations and do so based on height differences between left and right subtree. Look at the wiki link for an exact definition.

Can you give an algorithm to compute the number of AVL trees having exactly $n$ nodes?

[Solution]

Harmonic numbers are not integers

A classic:

Show that

$$H_n = \sum_{k=1}^{n} \frac{1}{k}$$

is never an integer, for $n \gt 1$.

i.e.

$$ 1 + \frac{1}{2} + \dots + \frac{1}{n}$$

is never an integer for $n \gt 1$.

Number of Red Black Trees [Possible Solution]

The puzzle was to count the number of possible red-black trees on $n$ nodes.

Possible Solution

---

Red black trees have the following property:

For every node, the (max) height of the subtree at that node is no more than twice the min height. This condition is both necessary and sufficient.

This gives the max height to be at most $2 \lceil \log_2 n\rceil$

Each subtree is also a red-black tree.

This gives us a dynamic programming algorithm.

Let the number of red black trees of min height $h$ and max height $H$, with $n$ nodes be $T(n, h, H)$.

Now we can give a recursive formula by considering the possible number of nodes and the min and max heights of the left and right subtrees (which are red-black trees themselves), then summing the up.

This should give a polynomial time algorithm.

Note: I haven't tried it, but if you choose to, you should be able to verify it by checking with OEIS which has the sequence I believe.

2n choose n [Solution]

The problem was to show that the binomial coefficient $\binom{2n}{n}$ is divisible by $n+1$.

Solution

---

Let $$C = \dfrac{\binom{2n}{n}}{n+1}  = \dfrac{2n!}{n! (n+1)!}$$

$C$ is actually a well known number, it is called a Catalan Number and has numerous combinatorial interpretations. Picking any one such would prove that $C$ is an integer.

But since this is an easy puzzle we will give a short proof.

Now

$$(n+1)C = \dfrac{2n!}{n! n!} = \binom{2n}{n}$$

and

$$nC = \dfrac{2n!}{(n-1)! (n+1)!} = \binom{2n}{n+1}$$

Thus $C = (n+1)C - nC$ is the difference of two binomial coefficients, and is thus an integer.

We can also phrase this as a consquence of:

If $r$ is a rational and $a,b$ are two relatively prime integers such that both $ar$ and $br$ are integers, then $r$ is also an integer.