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.

Trump power

This is a hand from an internal swiss teams tournament at Google.

You are South and end up in 2S after West opens a 15-17 NT.

IMPS None	North ♠ 87 ♥ T42 ♦ AQT73 ♣ 874
	South ♠ KQJT6 ♥ A7653 ♦ K ♣ Q6

W	N	E	S
1NT1	P	2C2	2S
P	P	P

2C need not guarantee a 4 card major (in case of an invitational hand). They were playing a form of crawling stayman which could be bid with a 4 card major and 5 card minor.

LHO leads the HK which you duck. LHO follows with the HQ (RHO follows too) and you win the A.

How will you play? [Please think about it before reading on]




Given that RHO has <5 points, they likely have a 4 card spade and were trying to get out low in a suit contract.

Now you can practically guarantee the contract thanks to the trump spots in the dummy!

After winning the heart Ace, play the DK overtaken by the A and DQ throwing a club. If RHO ruffs the second diamond (unlikely, as LHO would have opened 1NT with 6 diamonds) you discard a club, and can hope to enjoy hearts. So assume RHO follows to the second diamond.
 
Now play a heart! The idea being trying to ruff a heart for the 8th trick (4 spades, 1 heart, 2 diamonds and need one more).

The opponents might win the third heart and force you in clubs. You ruff and play the fourth heart and try to ruff it in dummy.  If opponents ruff the fourth heart and try to force you in clubs, you can try to ruff the fifth heart. If opponents ruff the fourth heart and try to draw trumps, you can enjoy the long heart trick.

If opponents overruff both the 8 and 7 (with the 9 and A), you make 5 spades in hand, a heart and 2 diamonds.

There are other lines that work too, given that RHO likely has 4 spades and 5 clubs, but the ruffing line is pretty nice and I believe it is percentage play even if RHO didn't bid 2C.