Average free subset

A problem which someone posted in Google's internal GooglePlus page (yeah...).


Show that there is a subset $S$ of $\{1, 2, \dots, 3^k - 1\}$ such that, $S$ has at least $2^k$ elements and any three distinct elements $x, y, z$ of $S$ do not satisfy $x+y = 2z$

(i.e. no number is the average of some other two numbers).

Don't cross the streams!

There are $N$ red and $N$ blue points in the 2D plane, no three of which are collinear.

Show that we can pair off each red with a blue so that none of the $N$ line segments intersect.

[Solution]

Careful!

It has been a while since I posted a bridge hand.


This is a hand from the Seattle Round Robin (2016).

You end up in 6S and LHO leads a trump. Don't remember the bidding (but both sides were bidding). Scoring is IMPS, KO.

	North ♠ J2 ♥ A43 ♦ Q543 ♣ KJT9
	South ♠ AKQT9854 ♥ 2 ♦ A2 ♣ 32

How will you play on a spade lead?





Did you draw trumps first? Then you will go down!

We basically need the club finesse, but the first club could get ducked! If you draw trumps and then take the club finesse which gets ducked, how will you get back to hand? If you ruff a heart you lose your only dummy entry to cash the club for a diamond discard. If you play a diamond, they can cash the DK.

It is easy to go wrong at the table. In fact a very good player indeed drew trumps first and went down when my teammate (John Krah) made the excellent play of ducking the first club (CQ was onside). At our table we were in 4S and this turned out to be a huge swing board in a semi-final match which was decided by a single IMP!

Length of the creeper

There is a tree with a trunk that is a perfect cylinder. The circumference of the base being 6ft. The height of the cylinder is 8ft. A creeper wraps around the trunk, rising uniformly from the ground to the top, and in doing so, makes exactly one turn (so the end point is on the same vertical line as the starting point).

What is the length of the creeper?

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.