Separating circle geometry puzzle

[This puzzle was given to me by Arvind Hariharan a long time back]

The puzzle is easy to state:

Given $2n+3$ points in the general position (no three collinear, no four concyclic) in the 2D plane, show that there are three points among those, such that the circle through those points has exactly $n$ of the remaining $2n$ points inside the circle (and exactly $n$ outside).

[Solution]

Playing Safe at Matchpoints

[This hand appeared in a local club game a while back. Most of the bidding is lost, but the relevant parts are probably there]

You are South, and end up in a contract of 4S, after RHO had shown 6 clubs.

LHO leads the club Ten and you see the following:

MPS None	North ♠ T9 ♥ 7542 ♦ 98742 ♣ A3
	South ♠ AK86432 ♥ AK ♦ 5 ♣ K72

How will you play?

[Please think about it before reading on]

Since this is MPs, you probably should be thinking of overtricks.

If trumps are 2-2, you can draw trumps, and come to 11 tricks, losing a club and a diamond.

If spades divide 3-1, drawing trumps will only give you ten tricks: you will lose a spade, a diamond and a club.

There is one way to cater to 3-1 spades: play one round of trumps, and then try to ruff a club. If LHO ruffs from 3, he will be ruffing your club loser with a natural trump trick, and you will still come to 11 tricks. This line will also give you 11 tricks if trumps are 2-2.

So win the CA, SA, and try to ruff a club, right?

No! There is still a problem.

Imagine LHO has QJx of spades. Now if you play one round of trump before going for the club ruff, LHO can ruff the third club with the J, play a diamond to RHO, and another club from RHO now promotes the spade Q, holding you to 10 tricks.

The solution to this is the scissors coup: cut opponent's communication. You don't want LHO to be able to put RHO in after the third round of clubs is played.

So after winning the CA on trick one, play a diamond from dummy immediately! RHO can win and return a club/heart.

You now draw one round of trumps, and go for the club ruff, making 11 tricks even when trumps break 3-1.

Not always do you need to make multiple "safety plays" [safety play being used loosely] at Matchpoints.

Stairs, Fibonacci numbers and O(log n) algorithms.

Introduction

---

You probably have heard of Fibonacci numbers.

They are the numbers in the sequence $1,1,2,3,5,8,13,\dots$ where each number is the sum of previous two numbers. So the next number after $13$ is $8+13=21$, and then $13+21=34$ and so on.

A combinatorial way of looking at them is the following:

Suppose you wanted to go up stairs having n steps, going up 1 or 2 at time. How many ways can you do this?

For instance, if there were 3 steps, you could go up as follows

$1,1,1$
$1,2$
$2,1$

where $1,2$ means go up one step, then go up two steps.

That the total number is a Fibonacci number is easy to see. If the number for $n$ steps was $F_n$, then the first number of steps is either one or two, and thus $F_n = F_{n-1} + F_{n-2}$.

We get $F_0 = 1, F_1 = 1, F_2 = 2, F_3 = 3, F_4 = 5, \dots$.

This combinatorial approach is a useful way [among many other approaches, like the matrix based approach] of looking at Fibonacci numbers. For instance, try proving the following identity combinatorially:

$$\binom{n}{0}F_0 + \binom{n}{1}F_1 + \dots + \binom{n}{n}F_n = F_{2n}$$

($\binom{n}{k}$ is the binomial coefficient: $n$ choose $k$)

We will use this combinatorial approach to demonstrate an $O(\log n)$ arithmetic operations algorithm to compute the $n^{th}$ Fibonacci number. [The matrix approach also gives an $O(\log n)$ algorithm]

Note, we are talking about $O(\log n)$ arithmetic operations, rather than $O(\log n)$ time. This is because the size of the Fibonacci numbers becomes substantial. Since $F_n \sim \varphi^n$, $\varphi$ being the golden ratio, $F_n$ will be $\Theta(n)$ bits in size.

Adding $F_n$ and $F_n$ will take $\Theta(n)$ time, and multiplying $F_n$ and $F_n$ would typically be slower than that, its run-time depending on the multiplication algorithm used.

[Please stop reading if you want to try coming up with an algorithm yourself]

An $O(\log n)$ algorithm

---

So, we want to compute $F_n$, the number of ways to climb a stair of $n$ steps, going up one or two at a time. Assume for the moment, that you don't know that $F_n$ is a Fibonacci number.

To get an $O(\log n)$ algorithm, an effective technique is to reduce the problem in half (e.g: binary search).

So, if we could compute $F_n$ in terms of $F_{n/2}$ (or similar) we would have an $O(\log n)$ algorithm.

So let us try to compute $F_{2n}$ in terms of $F_n$.

Of all the ways to go up $2n$ steps, each possibility will have us end up at step $n-1$ or $n$ at some intermediate stage.

So we count the total number by splitting into two: possibilities that go through step $n-1$ but not step $n$, and possibilities that go through step $n$.

We get the following identity:

$$F_{2n} = F_{n-1}^2 + F_{n}^2$$

And similarly:

$$F_{2n+1} = F_{n}F_{n-1} + F_{n+1}F_{n}$$

Thus we can compute $F_{2n}$ if we knew $F_{n-1}$ and $F_{n}$, and we could compute $F_{2n+1}$ if we knew $F_{n-1}, F_{n}$ and $F_{n+1}$.

A naive recursive implementation of these identities would give an algorithm which requires $\Omega(n)$ arithmetic operations.

A common way to speed up such recursive algorithms is to use memoization: cache the previously computed values and use those instead of recomputing them.

As is frequently the case, using memoization gives us an exponential speedup, leading to an $O(\log n)$ arithmetic operations algorithm!

To prove that, consider what values we need, to compute the four Fibonacci numbers $F_{2n+1}, F_{2n+2}, F_{2n+3}, F_{2n+4}$:

$$F_{2n+1}, F_{2n+2}, F_{2n+3}, F_{2n+4} \to F_{n-1}, F_{n}, F_{n+1}, F_{n+2}\quad (1)$$

And to compute $F_{2n}, F_{2n+1}, F_{2n+2}, F_{2n+3}$:

$$F_{2n}, F_{2n+1}, F_{2n+2}, F_{2n+3} \to F_{n-1}, F_{n}, F_{n+1}, F_{n+2}\quad(2)$$

Thus starting with $F_{2n}$ (or $F_{2n+1}$) we can see that ultimately, we need to only compute a total of $O(\log n)$ such $F_i$.

For example, starting with $F_{8n+4}$:

$$F_{8n+4} \to F_{4n+1}, F_{4n+2} \to F_{2n-1}, F_{2n}, F_{2n+1} \to F_{n-2}, F_{n-1}, F_{n}, F_{n+1}$$

To compute $F_{8n+4}$, we need to compute two Fibonacci numbers of half the size ($F_{4n+1}, F_{4n+2}$). To compute those two, we need to compute three more of half their size ($F_{2n-1}, F_{2n}, F_{2n+1}$), and then four more. Based on $(1)$ and $(2)$ above, the amount of new numbers added to compute then stays at four, and never increases. At each step we halve the size, and so the total number of numbers is $O(\log n)$.

The number of arithmetic operations associated with computing $F_i$ is $O(1)$, if we use a memoization table, and so the whole algorithm will be using $O(\log n)$ arithmetic operations.

We can get rid of the memoization table by trying to compute the tuple of 4 elements instead: $T_n = (F_{n}, F_{n+1}, F_{n+2}, F_{n+3})$ and noticing that $T_n$ can directly be computed using $T_{\lfloor n/2 \rfloor -1}$.

[If you look at the matrix approach, you can view it as computing a tuple of three elements]

By massaging the identities a bit more, and using $F_{n+2} = F_{n+1} + F_{n}$, we can in fact, reduce the size of the tuple to two.

Further optimizations can be done, to reduce the number of multiplications (as they are slower than additions for large sized integers). See the GNU gmp Fibonacci implementation which actually does that by using similar identities to what we had earlier.

Conclusion

---

We looked at a combinatorial way of looking at Fibonacci numbers, and used that to give an $O(\log n)$ arithmetic operations algorithm.

This algorithm naturally falls out by applying two basic algorithm techniques: divide and conquer (by halving the input size) and caching (using memoization on the recursive version) and does not require any 'major leaps' (like the matrix approach).

Solution to AOSREMPHE

[This is the intended solution to the puzzle-huntish puzzle AOSREMPHE posted earlier]

The puzzle was just this image:


Solution

---

If you looked at the hint, it stated "AOSREMPHE is an anagram".

One such anagram is SEMAPHORE.

SEMAPHORE is a reference to flag semaphore, commonly used in such puzzles.

Flag Semaphore is used by navies as a way to encode the alphabet to help two ships communicate visually.

For instance, A encodes as

If you look at the first triangle, the angle corresponds to the letter A!

A list of the flag encodings is in the image here:

If you decode the puzzle image, you see that you will get ALTERINGS, which is the same permutation of TRIANGLES, as AOSREMPHE is of SEMAPHORE (ALTERINGS is also an anagram hint a-la cryptic crosswords).

So the intended answer is TRIANGLES.

[The image does contain a bunch of triangles :-)]

Solution to Last 1000 digits puzzle

[This is a solution to the last 1000 digits puzzle earlier.]

A brief description of the problem:

What are the last 1000 digits of $$1 + 50 + 50^2 + \dots + 50^{999}$$ when written in base-10? A reasonably easy to compute (by a human) description is enough.

Solution

---

The solution relies on the following fact:

If $a$ is relatively prime to $49$, then $a^{42}- 1$ is divisible by $49$: by applying Euler's theorem, as $\varphi(49) = 42$.

Now, the last $1000$ digits of $$1 + 50 + 50^2 + \dots + 50^{999}$$ are the same as the last $1000$ digits of $$S  = 1 + 50 + 50^2 + \dots + 50^{1007} = \frac{50^{1008} -1}{49}  =$$ $$\frac{(5^{1008}-1)10^{1008} + (10^{1008}-1)}{49}$$


Since $1008$ is divisible by $42$, $5^{1008}-1$ is divisible by $49$.

Thus

$$S = K*10^{1008} + \frac{10^{1008}-1}{49}$$

Thus the last $1000$ digits of $S$ are same as the last $1000$ digits of $$\frac{10^{1008}-1}{49}$$ which are the same as the last $1000$ digits of $$\left\lfloor\frac{10^{1008}}{49}\right\rfloor$$ .

Since $\dfrac{1}{49}$ is a repeating decimal with period $42$ , the last $1000$ digits can easily be computed:  $204081632653061224489795918367346938775510$ repeated.

Timing for all the chances [bridge hand]

[This is a hand from the 2000 Indian Nationals held in Baroda, and was given to me by Rajendra Gokhale.]

You are South and with no opposing bidding, you reach a small slam in hearts.

West leads the DK.

You see:

IMPS None	North ♠ A73 ♥ T73 ♦ 7643 ♣ Q64
	South ♠ KJ2 ♥ AKQJ4 ♦ J ♣ AKJT

West wins the trick and continues with the DQ.

How will you play?

[Please think about it before reading on.]



You have 2 spades, 5 hearts and 4 clubs. Where is the 12th trick going to come from?

If the hearts are 4-1, you probably have to rely on the spade finesse (a diamond-spade squeeze seems unlikely from the initial two tricks).

One option with hearts 3-2, is to ruff another diamond in hand and try for a diamond-spade squeeze/guess for finesse in the end position.

When hearts are 3-2 one could also think of trying for a dummy reversal: ruff 3 diamonds in hand, giving 6 heart tricks.

Opponents have been kind enough to lead the second round of diamonds, but you are still an entry short to dummy. You need the heart T to draw the last trump, and cannot use that as entry to ruff the diamonds in hand.

So, besides the heart T, SA and CQ, you need another entry.

Is there some situation where you can get an extra entry to do the dummy reversal?

The heart 7 should give you an idea: what if one opponent holds the heart 98 doubleton? Now you can use the heart Ten as an entry and use the H7 to draw the last trump!

With all these options available, you need to time your play correctly:

Ruff the second diamond with heart A. Play the heart K and the heart 4 to the T. Now you know whether heart 98 is doubleton or not, or whether the hearts are 4-1.

If hearts are 4-1, you just draw trumps, play clubs and rely on the spade finesse/unlikely diamond-spade squeeze.

If hearts are 3-2 with 98 doubleton, you can do a dummy reversal.

If hearts are 3-2 without the 98 doubleton, you can ruff a diamond and go for the squeeze/finesse ending.

The exact play to the tricks 2,3,4 is crucial: HA, HK, HT in that order. Deviate from that order, and you might not be able to pick the right play.

On the actual hand, the only chance that let it make was the dummy reversal with the heart 98 doubleton! The finesse and the squeeze don't work.

Solution to Construct the BST algo puzzle.

[This is a solution to the construct the binary search tree algorithm puzzle posted earlier]

A brief description of the puzzle:

If you insert $a_1$, then $a_2$, then $a_3$ and so on till $a_n$ into a binary search tree, with no rebalancing etc, you get a unique tree with $a_1$ as the root, $a_2$ as a child of the root etc.

A naive algorithm to construct the unique tree is $\Omega(n^2)$ in the worst-case.
(e.g: $a_1 \lt a_2 \lt \dots \lt a_n$).

Give an $O(n\log n)$ time algorithm to construct the tree.

We will present three solutions.

Solution 1)

---

This solution is based on Shyam's idea.

Initially we start with $(-\infty, \infty)$.

When we insert $a_1$ this interval splits into two: $(-\infty, a_1), (a_1, \infty)$. The left interval corresponds to the left sub-tree of $a_1$ and the right interval corresponds to the right sub-tree of $a_1$.

Basically, the binary search tree can be looked at as a collection of disjoint intervals, whose union is $(-\infty, \infty)$ (ignoring the split points).

Each time you insert a new value into a tree, some interval is split into two, around that value.

Now we can maintain the intervals as a red-black tree whose keys are the left end points, and the values are the right endpoints, plus a pointer to a node in the target tree (target tree is the tree which we want to construct). This node in the target tree holds the value which resulted in the creation of that interval.

Given a new value which we need to insert into the target tree, say $a_j$, we look-up the predecessor of $a_j$ in the tree of intervals ($O(\log n)$ time), and can now add the new node at the appropriate place in the target tree, in $O(1)$ time (and update the book-keeping).

Solution 2)

---

This solution is based on Arvind's idea, and is perhaps essentially the same as Solution 1). It is the simplest, though.

The key observation used in this solution is the following:

When you insert $x$ into a binary search tree, it will either be the right child of it's predecessor among the elements already present in the tree, or will be the left child of it's successor among the elements already present in the tree.

So you maintain a red-black tree along with the target tree. The nodes in the red-black tree maintain pointers to the corresponding node in the target tree, and also the when it was inserted (i.e. for $a_j$ you store $j$).

Now when you are inserting $a_j$, lookup both the successor and predecessor of $a_j$ in the red-black tree.

Say we get $a_p$ and $a_s$ with $a_p \lt a_j \lt a_s$.

Now if $p \lt s$ (predecessor was inserted before), then $a_j$ will be the left left child of $a_s$ in the target tree. If $p \gt s$, then $a_j$ will be the right child of $a_p$ in the target tree.

Solution 3)

---

This uses a lesser known data-structure called Cartesian Trees.

Given points $$(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$$ with $x_1 \lt x_2 \lt \dots \lt x_n$, a cartesian tree of these points is basically a treap (a tree + heap), with the $x_i$ forming the binary search tree values, and $y_i$ from the heap values: i.e. each node of the tree with contain an $(x_i, y_i)$ pair, and when you just look at the $x_i$, the tree will be a binary search tree, and when you just look at the $y_i$, the tree will be a heap.

This tree can be constructed in $O(n)$ time (see the wiki page for details).

Suppose the sorted list of $a_1, \dots, a_n$ is $b_1, \dots, b_n$, with $b_1 \lt b_2 \lt \dots \lt b_n$. Also, suppose $b_k = a_{f(k)}$.

Then we are looking for the Cartesian Tree corresponding to the points $$(b_1, f(1)), (b_2, f(2)), \dots, (b_n, f(n))$$ with the $f(i)$ forming a min-heap.

We can sort $a_i$ in $O(n \log n)$ time, and create the cartesian tree in $O(n)$ time.

AOSREMPHE

When I was at Microsoft, I was a part of a team which participated in puzzle hunts held by other Microsofties. The hunt ran over the weekend with people staying up all night solving puzzles!

Only a few teams managed to solve the final meta-puzzle, but it was quite satisfying to solve whatever amount we could solve.

The puzzles were very creative, with the winners of last year usually holding the contest for the current year.

This puzzle is a puzzle in that spirit.

The answer is one word.

[Solution]

Last 1000 digits puzzle

What are the last $1000$ digits of

$$1 + 50 + 50^2 + \dots + 50^{999}$$

when written in base-$10$?

i.e.

What are the last $1000$ digits of

$$\sum_{k=0}^{999} 50^k$$

Of course, the idea is to find a way to find this manually/mathematically, and only use a calculator/computer if needed.

You don't have to list the $1000$ digits, just some simple, reasonably easy to compute (by a human) description would do too.

[Solution]

Solution to the two triangles puzzle.

[This is a solution to the two triangles geometry puzzle posted earlier]

The problem, repeated here:

In the figure below (not to scale, forgive the shoddy drawing skills).




$ABC$ is a triangle such that $\angle{BAC} = 60$ and $\angle{ABC} = 25$.

$DEF$ is an isosceles triangle, such that $\angle{EDF} = \angle{EFD}$, and $\angle{DEF} = 10$

(all angles are in degrees).

We also have that $|BC| = |DE|$ ($|XY|$ = length of the segment $XY$)

Show that $2|AC| + |DF| = |AB|$

Solution

---

Notice that $\angle{FDE} = 85$ and $\angle{ACB} = 95$, and so their sum is $180$.

Since $|BC| = |ED|$, we can position one copy of $\triangle{ABC}$ with $B$ coinciding with $E$ and $C$ coinciding with $D$ to get a bigger triangle.

Another copy of $\triangle{ABC}$, call it $\triangle{A'B'C'}$, can be positioned so that $B'$ coincides with $E$ and $C'$ coincides with $F$.

The result will be an even bigger triangle, $\triangle{EAA'}$ as below (more drawing incompetence):

Placing two copies of ABC along with DEF results in an equilateral triangle.

$\triangle{EAA'}$ is an equilateral triangle, and thus the base of the triangle which is $2|AC| + |DF|$ is same as the other side which is $|AB|$.

A Dream of Genie [bridge hand]

This hand has been stolen from the book Around the world in 80 hands by Zia Mahmood, which itself was stolen from Adventures in Card Play by Ottlik and Kelsey. This hand is so amazing, that I bought the 80 hand book because of this hand! (I already had the Adventures book at that time).

In the book, the chapter is titled "A Dream of Genie".

The story is about 3 bridge players who find a bottle with a genie who claims to be a master bridge player. With the genie making up the fourth, they had enough players to play a few hands of bridge.

This is the very first hand:

IMPS None	North ♠ 83 ♥ 963 ♦ AKQJ9 ♣ Q63
West ♠ KJ9652 ♥ - ♦ 87542 ♣ T8		Genie ♠ AQT4 ♥ A74 ♦ T63 ♣ KJ7
	South ♠ 7 ♥ KQJT852 ♦ - ♣ A9542

W	N	E	S
3S	P	4S	5H
all	pass

West leads the spade 2 against the contract of 5H by South, dummy plays the 3 and the genie sitting East, after some considerable thought, plays the 4!, South winning with the 7.

After this trick, the three players stuff the genie back into the bottle and throw him into the sea.

Later they show the hand to Micheal Rosenberg, expecting him to chuckle at the Genie's play, but Micheal Rosenberg calls them idiots and explains:

If East makes the normal plays of winning the spade and returning the suit (any other switch allows declarer access to diamonds), then South can ruff with the heart T, and lead the heart 8 to the dummy's 9. The Genie has to win this, but now any return he makes, declarer gets access to the dummy's winners. Even though East can ruff the 4th diamond, declarer can draw trump (if needed) and play the heart 2 to the heart 3!

If East ducks the first spade, as the Genie did, East avoids the throw-in, as he has a spade exit card when South plays the heart 8 to the heart 9.

Declarer must play the spade 8 at trick one to make it.
 

Constructing a Binary Search Tree [algorithm puzzle]

Suppose you are given a sequence of distinct numbers $a_1, a_2, \dots, a_n$.

You can create a unique binary search tree of those numbers by inserting $a_1$, then $a_2$ etc in the order they appear.

$a_1$ becomes the root, if $a_2 \gt a_1$, then it becomes the root of the right sub-tree and so on. Note that the sequence uniquely determines the tree.

For example, if the sequence was $4,5,1,2,3$ the corresponding binary search tree would look like

Tree formed by inserting 4, then 5,1,2,3 in order.

Now suppose you wanted to write a program to create the final binary search tree corresponding to a given insertion order.

A naive solution would be to run the binary search tree insertion algorithm for each element in the sequence to get the final tree. In the worst case, this creation algorithm would be quadratic in the number of elements in the sequence: if the sequence was sorted, for e.g.

This puzzle is about doing the binary search tree construction better.

Can you give an $O(n \log n)$ worst-case time algorithm which will construct the binary search tree of the given insertion sequence of distinct numbers $a_1, a_2, \dots, a_n$? Note that the resulting tree should be the same as the one gotten by the naive algorithm.

(Assume a pointer based tree, with left and right pointers, and if needed, parent pointers)

[Solutions]

Solution to Catch the Magical Monkey puzzle

[This is a solution to the catch the magical monkey puzzle posted earlier]

Brief description of the puzzle:

A monkey is moving at constant integer velocity among the integer points.

You can pick a point at any given time and check if the monkey is there. If he is there, you can catch him.

Can you eventually catch the monkey?

Solution

---

The solution relies on the following fact: $\mathbb{Z}^2$ is countable, and so there is a bijection mapping every ordered pair of integers $(a,b)$ to a natural number $f(a,b)$.

The strategy is to guess that the monkey's position at time $f(a,b)$ is $a + bf(a,b)$, corresponding to a guess of initial position $a$ and velocity $b$.

If the monkey's actual speed is $v$ and initial position was $u$, then we will catch him at time $f(u,v)$

A property of two triangles, geometry puzzle

[This is a geometry puzzle, solvable by elementary 8th grade geometry, i.e. no trigonometry etc]

In the figure below (not to scale, forgive the shoddy drawing skills).




$ABC$ is a triangle such that $\angle{BAC} = 60$ and $\angle{ABC} = 25$.

$DEF$ is an isosceles triangle, such that $\angle{EDF} = \angle{EFD}$, and $\angle{DEF} = 10$

(all angles are in degrees).

We also have that $|BC| = |DE|$ ($|XY|$ = length of the segment $XY$)

Show that $2|AC| + |DF| = |AB|$

[Solution]

Be careful at trick one (and two)

[Another hand I had posted to bridgebase forums]

You are South playing teams, and reach a contract of 5D.

West leads the spade 5.

You see:

IMPS None	North ♠ AQ3 ♥ Q752 ♦ 653 ♣ Q72
	South ♠ 642 ♥ AK ♦ AKQJ98 ♣ K3

You have 6 diamonds, 3 hearts, 1 spade and will definitely get a club after knocking out the CA. That is 11 tricks. So what is the problem?

The problem is that your only sure dummy entry is in spades and is in danger of getting knocked out before you can unblock your hearts.

You probably don't want to play the SA at trick one. If you play the Q, East might win the SK and continue spades. If East has both the SK and CA, you will not be able to get to dummy.

Consider what happens when you play low from dummy.

You have the S6 to cover West's card, so East has to win (otherwise you have 11 tricks without needing the HQ).

Now East cannot play spades without giving you a trick.

So play low and relax, right?

Not so fast.

Suppose East wins tricks 1, and returns a club. You have to go up with the K now.

If you play a low club from hand, West will win the CA, and play a spade, knocking out the SA while both hearts and clubs are blocked.

If you go up with the K, you will have the CQ as entry in case West wins. If the CK wins, you have the SA as entry.