What is normal?

This is a hand from a recent local BAM (board-a-match) tournament in the Seattle area.

White vs Red, you are dealer and you hold: ♠83 ♥A54 ♦A975 ♣K854

You decide to open 1D and the bidding proceeds: pass by LHO, 1H by partner, 2S preemptive by RHO, 2NT ogust by LHO, 3H by RHO showing a good spade suit but a bad hand, 3S by LHO passed out. (Your side passing after the 1H bid).

What do you lead? [Please pick one before reading on]

There were the four hands:

BAM E/W	North ♠ 6 ♥ Q9632 ♦ 843 ♣ AQT6
West ♠ KT42 ♥ KJ ♦ KQJ62 ♣ 72		East ♠ AQJ975 ♥ T87 ♦ T ♣ J93
	South ♠ 83 ♥ A54 ♦ A975 ♣ K854

W	N	E	S
			1D
P	1H	2S	P
2N	P	3H	P
3S	P	P	P

At the table, I led a low heart from Axx, and hit the jackpot, when dummy showed up with KJ, and declarer chose to play low.

We were able to cash the first 5 tricks for down 1 and +100 to us. Our teammates came back with a +140, and this board was a win for us (remember BAM scoring).

If you lead anything else, declarer will be able to make it, as he will have enough information to play the hearts correctly.

Given the bidding, I would say that underleading the heart Ace is the normal lead. Would you?

Missing Numbers II [Solution]

A solution to Missing Numbers II.

Stream of $n$ numbers: $1,2, \dots, n$, in some random order, and with two missing and two others repeated.

Need to given an $O(\log n)$ space and $O(n)$ time algorithm to find out the four numbers (repeated and missing).

Solution

---

As expected this uses Math.

Assume the numbers are $a,b,x,y$ the missing being $a,b$ and repeated being $x,y$.

Now in one pass we can compute the sum of $k^{th}$ powers of the numbers seen, and subtract from $1^k + 2^k + \dots + n^k$ to get

$$S_k =  a^k + b^k - x^k - y^k$$

We do this for $k=1,2,\dots 7$ (thus $O(\log n)$ space, and $O(n)$ time).

Now assume $a,b,x,y$ are roots of $P(z) = z^4 + pz^3 + qz^2 + rz + s$

This gives us the set of equations:

$$S_4 + pS_3 + q S_2 + rS_1 = 0$$
$$S_5 + pS_4 + q S_3 + rS_2  + sS_1 = 0$$
$$S_6 + pS_5 + q S_4 + rS_3 + sS_2= 0$$
$$S_7 + pS_6 + q S_5 + rS_4 + sS_3 = 0$$

Now the above set of equations is basically

$$P(a) + P(b) - P(x) - P(y) = 0$$
$$aP(a) + bP(b) - xP(x) - yP(y) = 0$$
$$a^2P(a) + b^2P(b) - x^2P(x) - y^2P(y) = 0$$
$$a^3P(a) + b^3P(b) - x^3P(x) - y^3P(y) = 0$$


Since the matrix

$$\begin{bmatrix}1&1&-1&-1\\a&b&-x&-y\\a^2&b^2&-x^2&-y^2\\a^3&b^3&-x^3&-y^3 \end{bmatrix}$$
 
is invertible (similar to a Vandermonde matrix) for distinct $a,b,x,y$, we have that $P(a) = P(b) = P(x) = P(y) = 0$.

Thus we solve for $p,q,r,s$ and find the roots of $P(z)$, either by verifying which of $1,2, \dots, n$ are roots, or by other means.

Four numbers game [Solution]

This is a solution to the four numbers game puzzle.

Brief description:

Start with four integers $(a,b,c,d)$ and repeatedly apply the transformation $(a,b,c,d) \to (|a-b|, |b-c|, |c-d|, |d-a|)$ stopping only when all become zero.

Are there initial $(a,b,c,d)$ for which you will never stop?

Harder: Characterize all the $n$ such that repeated such transformations to $(a_1, a_2, \dots, a_n)$ will always stop irrespective of initial numbers.

Solution

---

The numbers will be non-negative after one step.

Now we can show that, eventually, all the numbers will be become even (try it out!).

Since $(2a,2b,2c,2d)$ stops iff $(a,b,c,d)$ stops, we can divide by two.

Thus, the maximum of the four numbers will decrease in a finite number of steps.

Thus the transformation will have to stop.

The harder version: The only such $n$ for which this works is powers of two. (I will leave the proof of this open, for the next blog post, here: http://ruffnsluff.blogspot.com/2015/10/four-number-game-ii-solution.html).

Finesse at trick one?

You are South in a team game and end up in 6H. You get a low diamond lead.

This is what you see:

IMPS None	North ♠ 43 ♥ KQT94 ♦ A2 ♣ J432
	South ♠ AQ5 ♥ AJ8765 ♦ Q3 ♣ AK

How will you play?

[Please feel free to comment with your solution]

Solution (Updated Feb 24th 2015)

---

If you take the finesse at trick one, lose, and a spade comes back, then you are forced to take the spade finesse.

If you don't take the finesse at trick one, then you can give yourself an extra chance: Qx(x) of clubs.

Win the A of diamond, draw one round of trump, play AK club, trump to dummy and ruff a club. If the Q has not dropped yet, then you play a trump to dummy, and ruff the fourth club. Now exit with the DQ.

If LHO has the DK (as the finesse takers at trick one hope), then LHO will be endplayed to give you your 12th trick.

If RHO has the DK and returns a spade, you take the finesse.

Missing Numbers II

Another one of those missing numbers puzzles.

You are given a stream of $n$ numbers, consisting of the integers $1, 2, \dots, n$, except that two of those are missing, and some other two are repeated.

For example, the stream could be 6,1,4,2,1,4. The numbers 3 and 5 are missing, while 1 and 4 are repeated.

Can you give an algorithm to find out what the four numbers are (missing and repeated) which uses $O(\log n)$ space?

Remember, this is a stream of numbers, so you cannot revisit the numbers you have seen before, unless you store them and that counts towards your space usage.

The total time used must be $O(n)$.


[Solution]

Four numbers game

An easier puzzle (but still medium difficulty).

You start with 4 integers $(a,b,c,d)$ and play a game. At each step you replace $(a,b,c,d)$ with $(|a-b|, |b-c|, |c-d|, |d-a|)$, i.e. you replace the numbers with the absolute value of differences with the adjacent numbers (adjacent when placed on a circle).

You only stop when the numbers all become zero.

For example, say you start with $(1,2,3,4)$

After one step, it becomes $(1,1,1,3)$, then $(0,0,2,2)$ then $(0, 2, 0, 2)$, then $(2,2,2,2)$ and then $(0,0,0,0)$ after which you stop.

Are there games (i.e. some initial choice of the four integers) where you will never stop?

What about that case if you start with five integers?

Hard: Characterize the $n \gt 1$ such that if you play the game with $n$ integers, you will always stop, irrespective of the initial choice of the $n$ integers.

[Solution to part one]

[Solution to part two]

Solution to Is a binary tree red black?

This will be a quick (and incomplete) post. I might edit to add more details later.

The goal was to determine if a given binary tree is a red black tree.

A well known necessary condition of a red-black tree: For each node the max height is no more than twice the min height.

This is in fact used to prove that the height is $O(\log n)$.

In fact, this is also sufficient!

Using this property gives us an easy $O(n)$ time algorithm.

I will leave the details of the proof and the algorithm to you :-).

Solution to equal coins puzzle

This has solutions to the Equal coins puzzle posted earlier.

A brief description of the problem:

There are $2n+1$ reals numbers, $r_1, r_2, \dots, r_{2n+1}$. Given any $r_i$, you can split the remaining $2n$ into two groups of $n$ each, such that the sum of elements of one group is the same as the sum of elements of the other group.

Show that $r_i = r_j$ (i.e. all must be equal).

Solutions

---

All the solutions that I know use Linear Algebra (if you know/can think of one without using Linear Algebra, please share!).

Solution 1)

This is the solution I had come up with when I first saw this problem.

The property basically means that there is a $(2n+1)\times(2n+1)$ matrix $A$ such that

Every row of $A$ has exactly $n$ ones and $n$ minus ones.

The main diagonal of $A$ is $0$

$Ax = 0$ has a non-trivial solution.

Since $x = [1,1, \dots, 1]$ is an obvious solution, in order to show that all the coins/real numbers must be equal, it is enough if we show that the rank of $A$ is $2n$.

Consider the characteristic polynomial of $A$, $P_{A}(t) = \det(A - tI)$.

It is enough to show that coefficient of $t$ in $P_{A}(t)$ is non-zero.

Consider the formula for the determinant of an $N \times N$ matrix $M$

$$ \det M = \sum_{\sigma} \text{sign}(\sigma)\prod_{i=1}^N M_{i\sigma(i)}$$

where $\sigma$ runs over the permutations of $\{1,2, \dots, N\}$ and $\text{sign}$ gives the sign (based on the parity of the permutation).

For the $P_{A}(t)$, the coefficient of $t$ is given by those permutations such that there is exactly one $i$ such that $\sigma(i) = i$.

Since each product $\prod A_{j \sigma(j)}$ is $\pm 1$, the coefficient of $t$ is a sum of ones and minus ones.

It is thus enough to show that there is an odd number of such permutations.

This number is basically $(2n+1)D_{2n}$, where $D_{2n}$ is the number of derangments of $1,2 \dots, 2n$!

This is easily shown to be odd (based on a recursive formulas) and is left as an exercise :-).

I was quite happy with this solution, when Professor David Zuckerman of UT Austin showed me this neat proof:

Solution 2)

Like 1), we start with matrix $A$, but consider it over $\mathbb{F}_2$, the field of ${0,1}$. One can show that $rank(A)$ over $\mathbb{R} \ge rank(A)$ over $\mathbb{F_2}$.

Now use the fact that $rank(A) + rank(B) \ge rank(A+B)$

In $\mathbb{F}_2$, A is just the all ones matrix, except the diagonal, which is all zeros.

To that, we add the all ones matrix $B$, giving the identity. The all ones matrix $B$ trivially has rank 1.

Thus we get $rank(A) + 1 \ge 2n+1$.

Since $rank(A) \ne 2n+1$ (it has a non-trivial solution), we are done.

And the third solution, which is quite neat too and generalizes to $kn+1$ numbers.

Solution 3)

First assume that the $r_i$ were integers. We can also assume they are all non-negative, as adding a fixed constant does not change the property.

Now consider the $r_i$ which has the smallest maximum.

If $ S = r_1 + r_2 + \dots + r_{2n+1}$, then the property gives us that $S = r_i \mod 2$ for every $i$.

Thus all are even or all are odd. If all are even, we can divide by $2$. If all are odd, we can subtract the smallest number.

Thus they must be equal. This easily extends to the case when the numbers are rational.

Now the Linear Algebra application: the reals are a vector space over the rationals! (See Hamel Basis). Writing the reals as a (finite) linear combination of the basis numbers, with coefficients in $\mathbb{Q}$, gives us that the coefficients of each basis vector/number should satisfy similar properties, and thus must be equal, implying the $r_i$s are equal!

One of my favourite bridge puzzles

I don't know the source of this one (if you do, please share) and not even sure how I came across it. I am guessing this is from before 1960.

You are South, playing rubber bridge and reach 6H.

West leads a diamond.

Rubber None	North ♠ AK54 ♥ 532 ♦ JT ♣ AKJT
	You ♠ 32 ♥ AKQJT4 ♦ - ♣ 98765

Can you guarantee 6H?

[Please feel free to comment with your solution]


Solution (Updated Feb 13th 2015)

---

The only problem is when trumps are 4-0 and clubs are 4-0.

The solution is to ruff the first trick, and draw four rounds of trumps, pitching a diamond from dummy. Pitching a diamond is the key play.

Now you play clubs from the top. If opponents win the third round and play a diamond, you can ruff in hand with your last trump, while pitching a club from dummy, unblocking them.