An Unusual Endplay

Playing a team game, you are South (and dealer) holding AQ982, K7, AQ8, 542.

The bidding proceeds as follows:



West leads a trump, and you see



Now you have 9 top tricks, 5 spades, 3 clubs and the diamond A. The tenth trick can come from an endplay. You could draw trumps, eliminate clubs, and try playing a diamond towards the AQ8 from the dummy. If East plays the Jack or Ten, you can play the Ace (not the Q), go back to dummy and play a diamond towards the Q8. This will make whenever East does not have JT9 of diamonds, a pretty good chance.

But given the bidding, there is a practically guaranteed play.

If you assume West has the heart Ace (given the bidding), you can make the unusual play of a low heart from Kx, after eliminating trumps and clubs. If East wins and plays a diamond, you go up with the Ace, and exit with the Heart King. West has to win this, and give you your tenth trick.

The \(n^{th}\) root of \(n\)

For the sake of a quick, "pure" math post.

It is a well known fact that \(\lim_{n \to \infty} \sqrt[n]{n} = 1\)

There are multiple proofs of that. One such proof is to use the inequality of Arithmetic and Geometric means

$$ \frac{x_1 + x_2 + \dots + x_n}{n} \ge \sqrt[n]{x_1\cdot x_2\cdots x_n} \quad (x_i \ge 0)$$

Choose \(x_1 = x_2 = \dots = x_{n-2} = 1\) and \(x_{n-1} = x_n = \sqrt{n}\)

Then we get,

$$\frac{n-2 + 2\sqrt{n}}{n} \ge \sqrt[n]{n} \ge 1 $$

And so,

$$ 1 - \frac{2}{n} + \frac{2}{\sqrt{n}} \ge \sqrt[n]{n} \ge 1$$

By the sandwich theorem, the limit is one.

Rabbit Plays a Spade

[This is an article I had posted on www.bridgewinners.com, and is based on the characters in Victor Mollo's, "Bridge in the Menagerie" series. The menagerie book is a must read for any bridge player]

It was business as usual at the Griffins club. It was the first board of the rubber, and Rueful Rabbit had the mixed fortune of cutting Hideous Hog for a partner, and the good fortune of playing against Karapet and the Secretary Bird.

On the very first hand, they were dealt



Karapet bid 1H and the Hog as usual bid 1NT preparing to play the hand, while simultaneously ordering a plate of biscuits. The Bird raised to 2H. The Rabbit quickly bid 2S, with Karapet overcalling 3D. Just then, the waiter arrived drawing Hog's attention for a moment, and forgetting he had not overcalled 1S, the Hog bid 4S. Delighted, the Bird doubled, and that was the final contract.

Karapet let the HK, and taking a quick glance at the Rabbit's cards, the Hog chuckled, "Even you should not go down more than three on this", as he fumbled to place the dummy down.

"Ace heart", said the Rabbit, as Bird signalled with the H7 and Rabbit played the 2.

The Rabbit now thought, "I have 3 clubs, 1 heart, 2 ruffs in hand. That is 5 tricks. I need the SK to be singleton to get 5 more tricks from spades".

"Ace spade" called the Rabbit. The Hog immediately played a low spade, while offering the others some biscuits. The Bird played the K. "No thank you", said the Rabbit and played low, while Karapet discarded a heart. The Bird led the DA next.




"Wait! I won the trick in dummy", said the Rabbit.

"No, you called for a small spade".

"I said Ace spade, not a spade", said the Rabbit with a quivering nose.

"The rules of our club are clear", said Bird. "Once the trick is over, and a card is led to the next trick, you cannot take back a played card".

"It is ok, partner, he can take it back", said Karapet.

"I agree", said Hog. "The rules are indeed clear."

By now, Rabbit's cheeks had become red with anger, and with a trembling voice he said, "Alright! Let's get on with it".

The DA was won by the Bird, and he played another diamond to Karapet's Q, who returned a third diamond.

The Rabbit still fuming and thinking, "A spade! Down three! I will show him how to waste tricks!". He didn't want to make it too obvious by discarding. "Ruff with the top spade, partner".

The Hog played the SA, and the Bird discarded, while Karapet slumped back in his chair. He thought, "This is nothing compared to that time anyway...".

The rabbit then called for a spade, and when the Bird played the S9, he played the ST, hoping to lose to the SJ. To his surprise, he won the trick, as Karapet discarded another heart.



Unable to lose tricks, he wondered if playing normally would help. He played the SQ and ruffed a diamond, but could not avoid taking the rest of the tricks.

"Down how many?".

"You made it".

"Well played, partner".

On the very next deal, the Hog was distracted again to put the Rabbit in 5H, with Karapet leading the S3.


Guess what happened?

Hamiltonian Paths in Graph Powers

[Based on a puzzle given to me by Anand Ganesh]

Determining whether a connected graph \(G\) has a Hamiltonian Path is NP-Complete.

A little known fact is that determining if the square of a connected graph \(G\) has a Hamiltonian Path is also NP-Complete. In the square of \(G\), two vertices are adjacent iff they are at a distance at most two in \(G\).

This post is about the cube (distance at most three) of a connected graph.

It can be shown that the cube of any connected graph always contains a Hamiltonian Path, and there is a simple proof of that, which demonstrates the power of using a stronger induction hypothesis.

It is enough to prove that the cube of a tree is Hamiltonian, as given a graph, we can just consider a spanning tree.

Given a tree, assume it is a rooted tree (pick an arbitrary vertex as the root), so we can talk about children and parents etc. Now we try to arrange the vertices of the tree as \(v_1, v_2, \dots, v_n\) such that the distance between \(v_k\) and \(v_{k+1}\) is at most three (i.e. \(v_1, v_2, \dots, v_n\) is a Hamiltonian Path in the cube of the graph).

We now use the following induction hypothesis:

Proposition: The \(n \ge 2\) vertices of a rooted tree \(T\) can be arranged as \(v_1, v_2, \dots, v_{n}\) such that \(v_k\) and \(v_{k+1}\) are at a distance at most three in \(T\), and (this where we make the hypothesis stronger) \(v_1\) is the root, and \(v_n\) is a child of the root.

Now if the root has \(s\) sub-trees, we get the arrangements for the sub-trees (using the induction hypothesis), concatenate them, put the root at the end and reverse the resulting arrangement.

The resulting arrangement has the root as the first vertex, and a child of the root as the last. It is also easy to verify the distance at most three requirement: the distance between any child and any grand-child (possibly a child of a different child) is at most three.

This inductive proof can also be converted to a linear time algorithm for finding a Hamiltonian path in the cube of a graph.

Note that while trying to prove the property about Hamiltonian paths, we basically ended up proving the property about Hamiltonian cycles.

Related reading: http://en.wikipedia.org/wiki/Graph_power

Typsetting math with Latex in your blogger/blogspot blog, using mathjax

Mathjax allows you to typeset math in your webpages, using the familar latex syntax. It uses javascript to render the math in the browser, and does quite a good job of it.

To add mathjax to your blogger/blogspot blog (like this one):

Go to the blog dashboard, click on Layout and add an HTML/Javascript gadget at the top, and paste in the following

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"> </script> 

To get this gadget to work in the mobile version of your blog, you might need to take some additional steps: http://ruffnsluff.blogspot.com/p/getting-your-gadget-to-work-on-mobile.html

To inline math, use

\(..\)

For display math (like an equation on its own line), use

\[...\] or $$...$$ 

Example of inline math: \( x^n + y^n \neq z^n \).

Display math:

$$\int_{0}^{1} \frac{1}{1+x^2} \text{d}x = \frac{\pi}{4}$$

It even works in the preview and comments.

More information about Mathjax is here: http://docs.mathjax.org/en/latest/start.html