Lucky 3NT

This is a hand from the Lynwood/Everett regional a long time back, when they were playing handicapped knockouts.

This is a hand from the finals of the KO.

You hold Q32, T82, T852, 987. I don't remember the vulnerabilty (assume None).

Partner opens 1H, you decide to bid a forcing 1NT (hoping to drop partner in 2H), but partner surprises you by bidding 3NT. You decide to pass instead of bidding 4H.

LHO leads a low spade.

You see.

IMPS None	North ♠ AJ3 ♥ A9765 ♦ K3 ♣ AKQ
	South ♠ Q32 ♥ T82 ♦ T852 ♣ 987

W	N	E	S
	1H	P	1N
P	3NT	P	P
P

Partner could have opened 2NT. Anyway...

You run the spade to the Q and it wins.

With nothing better to do, you play a heart to the A (LHO following with the J) and a heart back, hoping opponents crash their honours. RHO plays low and LHO wins the second heart with the K.

[Technically, it might have been better to duck the first heart].

LHO now shifts to the DQ. You cover the K, RHO wins the A and leads a low diamond back. You hold your breath, and put in the 8: LHO wins the J. Your DT is now good! Unfortunately, hand entries are scarce.

LHO now plays a club.

Now the play is clear. You cash the top clubs, and play a heart. RHO wins the Q, but now is endplayed into playing a spade or a diamond! Cashing the clubs took away RHO's exit cards. 3NT made.

RHO could have defeated the contract by cashing the HQ before playing the second round of diamonds. That is why ducking the first round of hearts is technically better, as you take away that option.

At the other table opponents were in 4H which had no hope.

We won the event, but only because of a handicap. Me and my partner threw away the next few boards :(

I think they stopped having handicapped tournaments after that. I believe the opponents complained that the handicapping was unfair, and I agree with them. Apart from me, the other three players on my team had won/placed well in national tournaments in India.

The handicaps were based on ACBL masterpoints, and apart from me, none of them were ACBL members (one was just visiting), and I believe we had no clue about seeding points etc.

Quicksort in log space [Solution]

The problem was to implement in-place quicksort (partitioning by pivoting on first element) in worst case $O(\log n)$ space.

Solution

---

This is a classic, probably due to Robert Sedgewick.

The absolutely trivial implementation of quicksort looks like

def qsort(arr, L, R):
  if L >= R:
    return
  mid = partition(arr)
  qsort(arr, L, mid)
  qsort(arr, mid+1, R)

Now the two recursive calls are interchangeable and the last one can be made tail recursive.

If we always pick the smaller partition to recurse on, and tail recurse on the larger partition, we will end up only using $O(\log n)$ space!

An implementation might look like (handwaving here)

def qsort(arr, L, R):
  while R > L:
  mid = partition(arr)
  if mid -L < R - mid:
    qsort(arr, L, mid)
    L,R = mid, R
   else:
    qsort(mid, R)
    L,R = L, mid

Note this idea can be used to make recursive binary tree traversals use $O(\log n)$ space, irrespective  of the tree structure, as long we maintain a count of the descendants of each node: recurse on the smaller tree, but tail recurse on the larger one.

Inequality from UW challenge of the week [Solution]

The problem was here.

In brief

$x_i$ are $n$ real numbers such that

$$ \sum _{k=1}^{n} x_i = 0$$

$$ \sum_{k=1}^{n} x_i^2 = 1$$

Show that for some $i,j$,

$$ x_i x_j \le -\frac{1}{n}$$

Solution

---

The official solution is quite neat.

wlog, assume $x_1 \le x_2 \le \dots \le x_n$.

Now

$$ 0 \le \sum_{k=1}^n (x_k - x_1)(x_n - x_k) = -nx_1x_n - 1$$

(The equality is just gotten from expanding out and using the given identities).

The inequality now follows immediately.

Misfit 3NT

This is a hand from the recent Bothell Sectional Swiss teams sectional event, near Seattle (where we probably set a record for the worst session ever!).

Red vs White, you hold AKJT8, K, Q65, Q765.

Partner is dealer and opens 1H. RHO bids 2H (Michaels), which you double (willing to penalize RHO), LHO bids 3D, pass, pass to you, and the vulnerability sways you to bid 3NT.

LHO leads the club ten. You see

IMPS N/S	North ♠ 92 ♥ AQJ93 ♦ 432 ♣ A32
	South ♠ AKJT8 ♥ K ♦ Q65 ♣ Q765

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

How will you play?

[Please think about it before reading on]






The lead of CT makes it look like LHO has a spade void and long diamonds and hearts, with RHO having the black suits.

There is great danger in ducking. RHO will win the CK and shoot a diamond through. You will be down immediately.

Assuming LHO has hearts and diamonds, looks like LHO can be caught in some form of an endplay.

Suppose you win and take four rounds of spades (taking the finesse: a good RHO would not cover the 9), and then cash the A (overtaking the K) and Q of hearts.

What 6 cards does LHO come down to? LHO needs to hold onto 2+ hearts. If LHO has come down to AK tight of diamonds, you can exit a diamond. Otherwise you can cash the HJ and exit a heart.

Turns out that LHO indeed had a spade void (as inferred from the lead) and would give a pretty accurate count of the hand for the end position. LHO also had the AKJ of diamonds.

This was all unncessary, though, as RHO had the singleton HT! LHO also had discarded two hearts, so we ended up making 10 tricks in 3NT.
 
We should have won IMPS on this board for bidding and making an overtrick 3NT, instead of doubling them non-vul in 3D (which is down 2/3), right? (or at least broken even?).

Unfortunately we lost IMPS. Teammates got to 4DX and went down 4. Ouch.

Quicksort in log space

This is a classic.

Can you implement simple quicksort: with the first element as the pivot, to in-place sort an array of size $n$, so that the implementation uses $O(\log n)$ space in the worst case?  If you use recursion, the stack depth is also counted.

[Assume WORD RAM model].

[Solution]

Inequality from UW challenge of the week

The UW math department (students) used to have a challenge of the week where they would post high school/undergraduate level math problems.  The winner would be selected randomly from the list of correct solvers, and given a gift certificate to Baskin Robbins!

Here is one problem:

Suppose $x_1, x_2, \dots, x_n$ are real numbers such that

$$ x_1 + x_2 + \dots + x_n = 0$$

and

$$ x_1^2 + x_2^2 + \dots + x_n^2 = 1$$

Show that there are some $i,j$ such that $$x_i x_j \le -\frac{1}{n}$$


[Solution]

A hand from the Chennai Bermuda Bowl

No, I didn't play in the Bermuda Bowl. This came up while using BBO's Vugraph table feature, which allows you to select hands from previously played tournaments.

You hold QJx, Qx, AKQxxxx, x. RHO opens 1S, you overcall 2D, 4S by LHO, 4NT (blackwood) by partner and you end up in 6D.

LHO leads a spade and you see

IMPS N/S	North ♠ - ♥ K98xx ♦ JTx ♣ AJxxx
	South ♠ QJx ♥ Qx ♦ AKQxxxx ♣ x

W	N	E	S
		1S	2D
4S	4NT	P	5S
P	6D	P	P
P

The contract is a good one and you are lucky that partner took a rosy view.

How will you play?


This hand has elements of a Morton's fork. 

Suppose you ruff the first spade and immediately play a low heart towards the Queen. RHO, who likely has the Heart Ace, now has to decide whether to go up with the A and play a trump (to avoid a spade ruff), or to let your Q win.

If he lets your Q win, then you can ruff a spade, CA, C ruff in hand, spade ruff, club ruff and draw trumps. This only loses if RHO has 5+ clubs, and even then you can choose to ruff the third club high in hand and survive if trumps are 2-1.


If he goes up with the HA and plays a trump, you can win in hand, cash the HQ, play a trump to dummy, ruff a heart back to hand, draw any remaining trumps (if any), and then CA to dummy to cash the HK and low heart to take care of your spade losers. This just requires a 4-2 heart break.

All starting points [Solution]

The problem was:

A circular road, with $n$ petrol stations, which just enough petrol to complete one full circle along the road. You have a car with an empty tank (but infinite capacity), and can start at any petrol station an drive along the road, filling petrol along the way.

You need to find all the stations that will allow you to complete a full circle without running out of petrol.

The algorithm needs to run in $O(n)$ time.

Solution

---

Note that we allow the car to travel either clockwise or anti-clockwise. We will provide a solution for the clockwise case, the other is similar. Also note that if the car chooses to go in one direction first, it has to continue along that direction.

We were given the input as $p_1, p_2, \dots, p_n$ and $d_1, d_2, \dots, d_n$

where $p_i$ was the amount of petrol in station $i$, and $d_i$ was distance between station $i$ and $i+1$ (written in clockwise consecutive order).

Let $e_i = p_i - d_i$, the amount of petrol left in the car, if an empty car starts at station $i$ and goes to station $i+1$. Note that $e_i$ could be negative.

Suppose we start at station $k$. Then the amounts of petrol that will be in the car at each station will be
$$e_{k}, e_k + e_{k+1}, \dots, e_k + \dots + e_n, e_k + \dots + e_n + e_1, \dots, e_k + \dots + e_n + e_1 + \dots + e_{k-1}$$

We need each of those to be non-negative.

Let $S_k = e_1 + e_2 + \dots + e_k$. We are given that $S_n = 0$ and the above intermediate amounts are

$$S_{k+1} - S_k, S_{k+2} - S_k, \dots, S_n - S_k, S_n - S_k + S_1, \dots S_n - S_k + S_{k-1}$$

Thus we need that for every $j$, since $S_n = 0$ that

$$ S_j \ge S_k$$

Thus we need to pick all the $k$ such that $S_k$ is the smallest.

Repeat in the other direction and we are done.
 

The $S_n \gt 0$ case is more interesting, and can still be solved in $O(n)$ time.

Now the conditions become

1) $ S_j \ge S_k$, for $j \gt k$

and

2) $ S_j + S_n \ge S_k$, for $j \le k$.


The candidates satisfying condition 1) can be computed by traversing the $S$ array from right to left, keeping track of the minimum seen so far.

The candidates satisfying condition 2) can be computed by traversing the array from left to right and keeping track of the smallest possible value of $Sj + S_n$.

Four Number Game II [Solution]

This was the puzzle:

You start with $n$ integers $a_1, a_2, \dots, a_n$ and in one step you perform the following transformation

$$(a_1, a_2, \dots , a_n) \to (|a_1-a_2|, |a_2 - a_3|, \dots, |a_{n-1} - a_n|, |a_n - a_1|)$$

($|x| = $ absolute value of $x$)

You keep performing this operation till all the numbers become zero.

Find all $n \gt 1$ (with proof), such that no matter which integers you start with, the numbers eventually become zero.

Solution

---

 The answer is the game terminates for every starting tuple of integers if and only if $n$ is a power of $2$.

The proof is based on the following observations (note, you might have to fill in a few details):

Lemma 1)

It is enough to consider the game modulo $2$, i.e, we play the game as

$$(a_1, a_2, \dots , a_n)  \to $$
$$ (|a_1-a_2| \mod 2, |a_2 - a_3| \mod 2, \dots, |a_{n-1} - a_n| \mod 2, |a_n - a_1| \mod 2)$$

which is equivalent to the game, working in the field $\mathbb{F}_2$ (where each $a_i$ is $0$ or $1$ and $1+1 = 0$) as

$$(a_1, a_2, \dots , a_n) \to (a_1 + a_2, a_2 + a_3, \dots, a_{n-1} + a_n, a_n  + a_1)$$


Lemma 2)

Looking at the tuples as vectors over $\mathbb{F}_2$, if the game terminates for $u$ and $v$, then the game terminates for $u+v$.

Now the game is basically multiply a vector $v$ by a fixed matrix $A$, and the game terminates if $A^k v = 0$ for some $k$.

Lemma 3)

If the game terminates for $e = (1,0, \dots, 0)$, then the game terminates for all vectors in $\{0,1\}^n$. This is because we can cyclic shift $e$ to get that the game terminates for $(0, 1, \dots, 0)$ etc, and add as appropriate (by Lemma 2).

Lemma 4)

 If the game terminates for $e = (1, 0, \dots, 0)$, it does so in no more than $n$ steps!

This we can see by considering the starting state $v$, and the subsequent states $Av, A^2v, \dots, A^nv$.

Now suppose we have that $A^mv \ne 0$ for all $m \lt K$, and $A^K v = 0$.

The claim is that $v, Av, A^2v, \dots, A^{K-1}v$ are all linearly independent vectors.

If they were linearly dependent, then we have that

$$A^{s_1} v + A^{s_2}v + \dots = 0$$

with $s_1 \lt s_2 \dots \lt K$

Now just multiply the above with $A^{K-1-s_1}$ to get that $A^{K-1}v = 0$.

Since the $K$ vectors are linearly independent, we have that $K \le n$.

Main proposition)

The game played on $(1, 0, \dots, 0)$ gives us the rows of the Pascal's triangle on each step, and we are looking for all numbers to become even within $n$ steps.

We can now use Lucas' theorem to show that the only $n$ for which termination occurs is powers of $2$.

More reading: https://en.wikipedia.org/wiki/Ducci_sequence

Only hope

This is a hand from a casual game in Google Seattle (so assume IMPS and some vulnerability).

You hold Q765, AT, KJ43, 543.

RHO is the dealer and opens 1C, you pass, LHO passes, partner doubles, pass by RHO, you bid 2S and partner jumps to 4S.

LHO leads the club 8 (they play MUD, if it matters), and this is what you see:

IMPS None	North ♠ 432 ♥ Q43 ♦ AQ76 ♣ AKQ
	South ♠ Q765 ♥ AT ♦ KJ43 ♣ 543

W	N	E	S
		1C	P
P	X	P	2S
P	4S	P	P
P

You ought to have been in 3NT by partner, which is cold, and you will reach that if partner just bid normally. But, you are in 4S now.

You win in dummy and play a spade. RHO wins the K of spades, cashes the Ace of spades and leads back a club. You win, LHO following with a low card. When you play a spade from dummy, RHO throws a club.

How will you play?




You have three trump losers. The only hope of making this contract is that LHO holds the heart Jack, and you endplay LHO to lead a heart. You just need to guess LHO's minor suit distribution correctly. If LHO has 3 clubs and 2 diamonds, you need to cash 2 diamonds and a club, and then endplay LHO. If you guess incorrectly, LHO can ruff early and have a card to exit with.

Now RHO has AK of spades, K of hearts and J of clubs, with no more than 4 hearts and 5 clubs. So RHO has at least 2 diamonds.

If RHO was balanced with 11 points, RHO might not have opened. So give RHO some distribution, and hence 5 clubs (also consistent with the discards). RHO could have beaten the contract legitimately by giving LHO a club ruff while he still had exit cards, but that is a difficult defense to find.

Thus we play LHO to hold two clubs. So the plan is: win the SQ, cash three rounds of diamonds ensuring a hand entry, then cash a club and then the last diamond to hand, planning to throw LHO in with a spade. LHO can ruff in (or not) anytime time, but then has to lead a heart ensuring two tricks there.