Find the unique root

It can be shown that the below equation has a unique root in the interval $(0,2)$.

Can you find it?

$$ \sqrt{2 + \sqrt{2 - \sqrt{2 + x}}} = x $$

[Solution]

Matchpoint greed?

This is a hand from yesterday's Matchpoint game at Mercercrest bridge club, in Mercer Island near Seattle.

You are South and end up in 4S, after showing 6 hearts and 5 spades, and North showing a diamond suit.

[In the actual hand, East was declarer, made South here for convenience]

West leads a trump. You see:

MPS Both	North ♠ KT9 ♥ - ♦ KT97642 ♣ KT5
	South ♠ QJ543 ♥ A87543 ♦ A5 ♣ -

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

[Bidding given is as it happened at the table]

East wins the SA (low from dummy), and returns a trump (win in dummy with the T), West following.

Now what?

At the table, South played a diamond to the A (both opponents following with low cards), and a diamond toward the K, with West playing the DJ.

If this was IMPS, you have a clear play to duck this trick!

You are short of entries to dummy. If diamonds break 3-1 (singleton with East), and you play the K, East might be able to ruff and dummy's diamonds will be dead. There will be no way to establish (the Q is still out) and cash the diamonds.

If you duck, the diamonds are already setup, with the SK as an entry.

Coming back to matchpoints.

If you duck, you guarantee 11 tricks.

If you go up with the K and diamonds are 2-2, you make 12, risking going down if diamonds are 3-1.

At the table, South got greedy and went up with the K. Unfortunately for her, this got ruffed, and she ended up down 2, when she threw a heart on the club return.

Looking at the traveller, she would have made a near top if she made 11 tricks. Getting greedy, she got a near bottom.

I think she got greedy, but perhaps you disagree. How would you have played?

Sorting with reversals II [Solution]

The problem was:

You have an size $n$ array of zeroes, ones and twos. The only write operation is to reverse a sub-array (paying cost equal to the length of the the sub-array). Can we sort the array in $O(n \log n)$ cost?

Solution

---

One solution is to use divide and conquer.

Suppose you divided the array into two approximately equal halves, and sorted each sub-array separately.

Then you will see an array like


$$0 \dots 0 1 \dots 12 \dots 2\vert 0 \dots 0 1 \dots 1 2 \dots 2$$

Now, we can sort a chunk of 2s and 0s by doing a cyclic shift of the chunk $2 \dots 2 0 \dots 0$, so that it looks like $ 0 \dots 0 2 \dots 2$.

We can do a cyclic shift of an array using only three reversals. Say you want to cyclic shift $a_1, \dots a_m$ to look like $a_k, a_{k+1}, \dots, a_m, a_1, a_2, \dots a_{k-1}$. This we can achieve by first reversing $a_1, \dots a_{k-1}$ and $a_k \dots a_m$, so the array now looks like $a_{k-1}, \dots a_1, a_m, \dots a_{k+1}, a_k$ and then reversing the whole array.

Each reverse costs $O(n)$, and with a constant number of these, give the two sorted halves, we can sort the whole array.

Thus the cost satisfies the recurrence

$$ C(n) = 2 C(n/2) + O(n)$$

which gives us $C(n) = O(n \log n)$.

Consecutive product sum [Solution]

The task was to find (without pen and paper)

$$\sum_{k=r}^{n} k(k-1)\dots(k-r)$$

Solution

---

Let $S_k = k(k-1) \dots (k-r)$.

One way to solve this is to notice that

$$(k+1)k(k-1)\dots(k-r) - k(k-1)(k-2)\dots(k-r)(k-r+1)$$

$$= (k+1-(k-r+1))k(k-1)\dots(k-r) = r k(k-1)\dots(k-r)$$

i.e

$$P_k - P_{k-1} = rS_k$$

where $P_k = (k+1)k(k-1) \dots (k-r)$

Thus we get a sum where most of the terms cancel each other out (called a telescopic sum) and the answer is simply $P_n - P_{r-1}$ which is

$$\frac{(n+1)n(n-1)\dots(n-r)}{r}$$

There are other solutions, like writing in terms of binomial coefficients etc, not sure we can do those without pen and paper though.

Sorting with reversals II

In a previous post, we were asked to sort an array (of size $n$) consisting only of the elements 0,1 and 2. The catch being: the only write operation on the array that was allowed was to reverse a sub-array $A[i, i+1, \dots, j]$.

The task was to use $O(n)$ reversals.

This problem is similar. We still have an array of zeroes, ones and twos, and we can only write by doing reversals.

The difference is that the reversal has a cost associated with it.

Reversing the sub-array $A[i, i+1, \dots, j]$ has cost $j-i+1$ associated with it (similar to what you would normally pay when doing an actual reverse).

Can you now sort the array with $O(n \log n)$ cost?

[Solution]

Consecutive product sum

Can you solve this without pen and paper?

Suppose $r \gt 0$ is a fixed positive integer.

Can you give a formula (in terms of $n$ and $r$) for


$$ \sum_{k=r}^{n} \left( \prod_{j=0}^{r} (k-j) \right)$$

i.e.

$$\sum_{k=r}^{n} k(k-1)(k-2)\dots(k-r)$$


[Solution]

All is not lost

This hand came up while playing a local game at Mercercrest bridge club in Mercer Island, near Seattle (one heart spot modified for the narrative). The club participates in the common game, night version.

You are West holding AQ5, QJ, KT654, J83. E/W vul with E dealer.

After two passes, you open 1D (likely 4+), double by LHO, 1H by partner, 2S by RHO which gets passed out.

You lead the HQ and you see:

MPS E/W	North ♠ K832 ♥ A843 ♦ 73 ♣ Q62
West ♠ AQ5 ♥ QJ ♦ KT654 ♣ J83

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

Not everyone will double with that hand.

Declarer goes up with the HA (partner encouraging) and plays a club to the A, partner showing an odd number.

Now declarer plays the S9. You choose to duck, as dummy and partner both follow with a low card.

Now declarer plays another spade, on which you go up with the SA, partner following.

To beat 2S, you need to be able to get 2 heart tricks, 2 diamonds and 2 spades. Thus you assume partner is 2-4-4-3 with the DA and DK and a fourth round of hearts can promote your SQ.

You play the HJ, it wins and you now quickly play a low diamond, and partner wins the DA. Partner now plays the HK, declarer following with the T.

At this point you realize your mistake. Instead of a low diamond, you should have played the DK first. Then a diamond to the DA, HK, followed by another heart by partner, and you get your SQ.
[A defensive version of the cross-ruff principle for declarer: cash you side suit tricks before you start your crossruff, otherwise the opponents(s) will throw the cards in the side suits and you won' get your winners there.]

As you played it, declarer (with a 4-3-2-4 hand) can throw his losing diamond on the fourth heart.

But all is not lost!

Partner seems to have started with HK9xx in which case you have a chance!

You are left with two clubs (declarer had played one round earlier). You throw one of them on the HK. Now when partner plays the H9 (the top heart at that moment), if declarer throws his last diamond, you can throw your last club! Partner can now give you a club ruff, for down one.

Even if you make a mistake, it might not be the end. There still might be opportunities lurking. The same is true not just for a single hand, but for the whole match. Don't let one mistake mess up the other hands for you, which will happen if you dwell upon your mistakes. You should definitely look at your mistakes (how else will you improve?), but only after the match. It is easier said than done, though.

[Beating 2S gives you just an average+ (while playing and making 3D is a near top), so, I guess the real moral of the story is to bid 3 over 2 in matchpoints, even with only an eight card fit...]

Sorting with reversals [Solution]

The problem was to sort an array consisting of only 0,1,2 only using $O(n)$ reversals of subarrays.

When I posted this problem, I had one solution in mind (which I will not reveal just now, but try to reuse for the next problem), without realizing that swapping $A[i]$ and $A[j]$ can be done using two reversals: reverse $A[i, \dots, j]$ and then reverse $A[i+1, \dots, j-1]$!

So any sorting algorithm which uses $O(n)$ swaps should do.

For example, using the Dutch National Flag (DNF) algorithm, we can achieve sorting in $O(n)$ reversals.

Collins made a nice observation that if we use the DNF algorithm, we don't even need to do the second reverse when trying to swap $A[i], A[j]$. See the comments on the question.

How many non-decreasing functions [Solutions]

The problem was to find the number of ordered pairs $x = (x_1, x_2, \dots, x_n)$ such that $x_i \le x_{i+1}$ and $1 \le x_i \le m$ for all $i$, $x_i$ being a natural number.

Solution

---

We will present two solutions.

Solution 1)

The first solution uses what is called the Stars and Bars approach.

For each $k \in \{1, 2, \dots, m\}$ you look at exactly how many $x_i = k$. Call this number $y_k$ (note, it could be $0$).

We must have that $y_1 + y_2 + \dots + y_m = n$, with $0 \le y_i \le n$.

Now given a $y = (y_1, y_2, \dots, y_m)$ we can easily map this back to the $x = (x_1, x_2, \dots, x_n)$ from which it was created.

Thus it is enough to count the number of solutions to $y_1 + y_2 + \dots + y_m = n$, with $0 \le y_i \le n$.

The way to look at this is to consider $n$ stars, and $m-1$ vertical bars. Finding a solution to the above equation is equivalent to placing the $m-1$ bars among the $n$ stars. The number of stars to the left of the leftmost bar is $y_1$, the one next to it is $y_2$ and so on.

The number of ways to do this is to select the position of the stars among a total $n + m - 1$ spots: $$ \binom{n+m-1}{n}$$

Solution 2)

The second solution I find particularly elegant.

Suppose instead of $x_i \le x_{i+1}$, we had the condition $x_i < x_{i+1}$ (i.e. strictly increasing).

Then it is easy to count: just select $n$ among $m$ = $\binom{m}{n}$ (and sort to get the increasing order).

We can reduce our problem to the strictly increasing case.

Set $z_i = x_i + i - 1$.

Now we have that $z_i \lt z_{i+1}$ (strictly increasing) and that $ 1 \le z_i \le m + n - 1$.

Thus the answer is $$\binom{m+n-1}{n}$$

Sorting with reversals

You are given an array $A$ of $n$ elements, each element being either $0$ or $1$ or $2$.

You want to sort the array.

The catch is, the only write operation you can do on the array is pick two any two indices $i \le j$, and reverse the contiguous portion of the array from $A[i]$ to $A[j]$, i.e. after the operation, $A[i]$ and $A[j]$ are swapped, $A[i+1]$ and $A[j-1]$ are swapped, $\dots ,A[i+k]$ and $A[j-k]$ are swapped (where $k \approx (i+j)/2$).

Let's say we call this operation the splice-reverse.

Can you sort the array using $O(n)$ splice-reverses?

[Solution. Also see comments below]

How many non-decreasing functions?

How many non-decreasing functions exist which map $\{1, 2, \dots, n\} \to \{1, 2, \dots, m\}$?

i.e

How many ordered pairs $(x_1, x_2, \dots, x_n)$ exist such that

$x_i \le x_{i+1}$ and $ 1 \le x_i \le m$ for all $i$?

[Solution]

Bless partner, curse partner.

You are South and hold QJ9642, 2, 5, AQ872, with E/W vul.

Your LHO is the dealer and opens 1H. Partner doubles and RHO bids 4H. You bid 4S, wondering if you missed a slam.

LHO passes, and bless partner, who bids 6S.

LHO lead the DA and you see

IMPS E/W	The Dummy ♠ AKT73 ♥ AQ ♦ KJT ♣ J94
	You ♠ QJ9642 ♥ 2 ♦ 5 ♣ AQ872

W	N	E	S
1H	X	4H	4S
P	6S	P	P
P

Curse partner. Overbid again.

While you are cursing partner, LHO goes into a tank, and emerges with a low club! Now you have a chance. Bless partner?

You play the 9, covered by the T, which you win with the Q.

Now LHO likely has the HK, DQ and the CK for his opening bid. In that case you have him, but have to time the hand correctly.

You should play all the trumps, throwing a club from dummy, then play a heart to the Q, and cash the HA and DK coming down to the DJ and CJ in the dummy and CA8 in hand.

West is squeezed in the minors.

Sum involving golden ratio [Solution]

The problem was to find

$$S_n = \sum_{k=1}^{n} [k \varphi]$$

where $\varphi$ is the golden ratio and $[x]$ is the integer part of $x$.

The challenge was to do it using polynomial in $\log n$ time.

Solution

---

If you look at the numbers of the form $a_k = [k \varphi]$ and *not* of the form $[k \varphi]$, you will notice a pattern.

The pattern is as follows:

If $a_k = [k \varphi]$ and $b_k = a_k + k$, then we have that $$\{a_1, a_2, \dots\} \cup \{b_1, b_2, \dots\} = \mathbb{N}$$

i.e, the numbers not of the form $[k \varphi]$, are precisely of the form $[k \varphi] + k$.

This observation can be proved using Beatty's theorem (and is not that difficult to prove).

Now, if you consider the numbers $\{1, 2, \dots, a_n\}$ then these can be split into two disjoint sets $\{a_1, a_2, \dots, a_n\}$ and $\{b_1, b_2, \dots, b_m\}$ for some $m$.

Thus we have that

$$1 + 2 + \dots + a_n = S_n + \sum_{k=1}^{m} b_m = S_n + S_m + m(m+1)/2$$

Thus

$$S_n = n(n+1)/2 - m(m+1)/2 - S_m$$

which is a recursive formula for $S_n$. It can be shown that $m = \theta(n)$, and thus this recursive formula gives us a polynomial in $\log n$ time algorithm to compute $S_n$.

All we need to do is compute $m$. I will leave that to you.

Limit everywhere function [Solution]

The problem was to find a function $f$ whose limit $g$ exists everywhere (i.e. $\lim_{t\to x} f(t) = g(x)$) and $f(x) = 2g(x) - \sin x$.

The key is to realize that $g$ must continuous!

(In fact one can show that $f$ is continuous almost everywhere, but that does not help this problem immediately).

If $g$ is continuous then, the functional equation implies that $f$ is too, and the result that $f(x) = \sin x$ follows easily.

To prove $g$ is continuous at $c$ we need to show that given an $\epsilon \gt 0$, there is a $\delta \gt 0$, such that $$|g(x) - g(c)| \lt \epsilon \quad \forall x, 0 \lt |x - c| \lt \delta$$ 

Now we have that there is some $\delta$ such that

$$ |f(x) - g(c)| \lt \frac{\epsilon}{2}, \quad \forall x, 0 \lt |x - c| \lt \delta$$

Also for any $x_1$ such that $0 \lt |x_1 - c| \lt \delta$ we have a $\delta_1$ such that $$|f(x) - g(x_1)| \lt \frac{\epsilon}{2} \quad \forall x, 0 \lt |x - x_1| \lt \delta_1 $$

Thus we can find an $x$ such that for any $0 \lt |x_1 - c| \lt \delta$ we have the above two to be true, and hence adding them gives us that

$$|g(x_1) - g(c)| \lt \epsilon \quad \forall x_1, 0 \lt |x_1 - c| \lt \delta$$