What is the danger?

This puzzle is for the newer players (not completely new, though).

Playing Rubber Bridge, you are South and end up in 5S. West leads the club 2 and you see:

Rubber N/S	North ♠ QJT92 ♥ A2 ♦ QJ ♣ QJ43
	South ♠ K8754 ♥ K3 ♦ A3 ♣ AK65

You play low from dummy and East follows with the club 7.

What is the danger, and how will you deal with it? How will you play?

Solution (updated March 24th 2015)

---

Looks like West has led a singleton club.

The danger is when East has the singleton Ace of trumps.

In that case, if you play trumps immediately (after winning the first trick), East will win, give partner a ruff, and West will safely play back a heart. Leaving you to rely on the diamond finesse.


You cannot prevent the club ruff if it is there, but you can remove the safe heart exit from West, by playing two rounds of hearts before touching trumps. Now if West ruffs, he will be forced to return a diamond giving you the free finesse, or a heart for a ruff-n-sluff!

Generate a random binary tree

You want to generate a random binary tree on n nodes, such that each structurally different tree has the same chance of being generated as any other.

Suppose you have access to a random number generator oracle which generates an integer in $\{1,2,\dots, K\}$ (with probability $\dfrac{1}{K}$), given $K$ as an input ($K$ could be as large as you want).

Can you give an algorithm which generates an n node binary tree using $O(n)$ calls to the random number generator?

Can you do it using $O(1)$ calls?

[Solution]

A perfect square problem

Find all positive integers $n$ (with proof), for which $$n^4 + n^3 + n^2 + n + 1$$ is a perfect square.

[Solution]

Balanced Bit String [Solution]

The puzzle is here.

Problem: Given an array of n bits, can you tell if it is balanced (number of occurrences of 01 = number of occurrences of 10) in sub-linear time?

Solution

---

The algorithm depends on the following property:

A bit array is balanced if and only if the first and last bits are equal!

Can be proved using induction. Constant time algorithm!

One divides another [Solution]

The puzzle is here.

Gist: Are there two 7 digits numbers, each comprising of the digits 1,2,3,4,5,6,7 such that one divides the other?

Solution

---

Each number must leave a remainder 1 when divided by 9, as the sum of digits is 1 + 2 + ... + 7 = 1 modulo 9.

Now the larger number cannot be more than seven times the smaller number (largest possible digit is 7 and both are seven digit numbers).

Thus if the smaller leave a remainder 1, then the larger cannot.

Thus there aren't such two numbers.

A hand from Howard Schenken's book

This a hand from Howard Schenken's autobiography, "The Education of a Bridge Player" and is a good example of making the right assumptions.

You partner, North is dealer. After two passes to you, you open 1H and end up in 4H (opponents silent).

LHO leads a trump, you see

Rubber None	North ♠ 9 ♥ JT52 ♦ J97432 ♣ AQ
	South ♠ AJ8 ♥ KQ963 ♦ K5 ♣ T86

W	N	E	S
	Pass	Pass	1H
Pass	4H	Pass	Pass
Pass

RHO wins the HA and continues a trump (to which LHO will follow).

How will you play?

Solution (posted 12 March 2015)

---

RHO has shown up with the HA, and likely has a spade honor (because LHO didn't lead one). RHO also passed initially. So if RHO has the DA, then the club finesse is working.

So you make the assumption: Assume RHO has the CK.

In this case, you need to set up your diamonds (which are likely 3-2, based on the play to first two tricks: no one shifted to a singleton).

The book recommend line is winning trick 2 in dummy and playing the DJ! If RHO covers, you duck. Now RHO cannot attack clubs.

The key play is to lose the second diamond to LHO, not the first, which allows you to setup the diamonds before the clubs are attacked and CK is cashed.

Another line of play which works, and which reminds us of the Belladonna coup: win trick 2 in hand and lead a low diamond away from the K!

Balanced bit string

Another quickie.

A string of bits is called balanced if the number of times "01" appears is same as the number of times "10" appears in the string.

For example, in "0010010", 01 appears twice ("0010010") and 10 appears twice ("0010010"), so it is balanced.

So, the question is, given a bit string of n bits (as an array of bits), can you give a sub-linear time algorithm to determine if the bit string is balanced?

[Solution]

One divides other

Have been sick these past few days. So a quick one for now.

Are there two seven digit numbers, each with the digits 1,2,3,4,5,6,7 used exactly once such that one divides the other?

For example with two digits 1,2, the possibilities are 12 (twelve) and 21 (twenty one).

Try solving this mentally without using any pen/paper etc.

[Solution]

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]