Solution to only the twain shall meet geometry puzzle

This is a solution to the geometry puzzle about lines posted earlier.

A brief description of the problem:

Given a set $S$ of finite number lines in the 2D plane, no two parallel, and not all concurrent, show that there is a point through which only two lines of $S$ pass (hence the title).

Solution

---

Since no two lines are parallel, and not all are concurrent, there is at least one triple of lines which forms a non-degenerate triangle.

Of all such triplets, consider the lines which form a triangle of the least area. The claim is that one of the vertices of this triangle satisfies the requirement!

[Sorry, no figures yet, so it might help to draw it out]

Suppose not, then if the triangle was $\triangle ABC$, then there are lines passing through $A,B,C$ such that they form a bigger triangle, $\triangle DEF$, with each of $A,B,C$ lying on different sides of $\triangle DEF$ and $\triangle ABC$, say $A$ is on side $DE$ (between $D$ and $E$), B is on side $DF$ (between $D$ and $F$) and $C$ is on side $EF$ (between $E$ and $F$).

We consider two cases:

1) $A$ is closer to $D$ than $E$ (possibly equidistant from both points). $B$ is closer to $D$ than $F$. Then we must have that the area of $\triangle ABC$ lies between areas of $\triangle ABE$ and $\triangle ABF$, say area of $\triangle ABE$ is smaller. This we can see, by drawing lines parallel to $AB$ through $E$ and through $F$, and considering the altitude lengths.

Since $A$ is closer to $D$ than $E$, we must have that area of $\triangle DAB \lt$ area of $\triangle ABE$, and thus contradicting the fact that $\triangle ABC$ has the least area.

2) $A$ is closer to $D$ than $E$ (possibly equidistant) and $B$ is closer to $F$ than $D$, and $C$ is closer to $E$ than $F$.

In this case, we can move $C$ to the midpoint of $EF$ and $B$ to the midpoint of $DF$ and decrease the area of $\triangle ABC$. This we can see by drawing lines parallel to $AB$ through $C$ and the midpoint $M$ of $EF$, and lines parallel to $MA$ through $B$ and $M'$, the midpoint of $DF$ (and considering the altitude lengths).

The resulting area is exactly one-fourth the area of $\triangle{DEF}$, and hence area of $\triangle ABC$ is more than the average of the sum of triangles $ABC, DAB, EBC, FAB$ and thus there must be a triangle of lesser area.

The above two cases cover all the possibilities, so we are done.

Futher reading

---

The classic problem I was referring to is the Sylvester-Gallai problem, which is the dual of this problem, by considering the polar/pole version.

A different proof of the claim that $\triangle ABC$ is not the least can also be found here (Theorem 3.1.2 on pages 20-22).

More information about the Sylvester-Gallai theorem, including some nice history can be found here and here.

Solution to the C programming puzzles

There were the two puzzles (posted earlier).

The first one:

Write a method in C, which will print ";", but does not use any semi-colons anywhere. Assume you have printf available.


We can do a print of a semi-colon, using the ascii value, but it does not end there... C programs use semi-colons as statement separators. If statements don't however, and so the code will look like this:

void print() {
  if (printf("%c", 59)) {}
}

The second one:

Write a C program to print "hello world!" 2014 times. The catch is, it must fit inside an 80x25 page and must not use the characters f,o,w,?,&,| (last three are question mark, ampersand and pipe). Assume you have printf available (and don't need to #include the header).

This one is more difficult. The printing is the easy part (and so we assumed we could use printf etc). The size limits do not allow us to write the print 2014 times (and that is a silly solution, anyway). #define etc macro tricks to do that are clever, but still silly :-)

The difficult part is that not using those characters does not allow us to use if statements (or conditionals), for and while loops. There might still be ways to loop and have conditionals, but that is probably weird C territory [that will still be a valid solution to the puzzle].

One way to do things multiple times without using loops is using recursion. But, since we cannot use if, we need a different way to stop the recursion.

Even though we cannot use if, we are allowed (=), so we can at least tell when we have recursed 2014 times, count == 2014 will be 1 or 0, depending on count.

In order to use that, we use function pointers! If count == 2014 is 0, we recurse, otherwise we return. We do this by calling the appropriate function, using the function pointers stored in an array a. a[0] will be a pointer to the recursive function, a[1] will be a pointer to the function which stops the recursion (basically returns).

The code will look something like this:

int stop(int n){}

int print(int n){
  int (*a[2])(int) = { print, stop };
  printf("hell%c %c%crld!",111,119 ,111);
  n++;
  a[n==2014](n);
}

int main(){
  print(0);
}

The code above can be made better by counting down and checking against 0 (instead of 2014), that way we don't have to hardcode 2014.

One could also use integer division, instead of ==. count/2014 is 0 or 1 depending on whether 0 <= count < 2014 etc.

That will get rid of the use of any conditional, including the equality check.

A 100% 7NT hand by Fred Gitelman.

This was a hand posted by Fred Gitelman on the bridgebase forums a couple of years ago.

[Apparently, the source is Micheal Rosenberg's book, Bridge, Zia and me]

You are South, in 7NT, and get a club lead.

IMPS None	North ♠ KQT9 ♥ AJT9 ♦ KQT9 ♣ 2
	South ♠ A876 ♥ K2 ♦ A32 ♣ AKQJ

Can you guarantee the contract?

Please feel free to add your solution in the comments.

Solution (added November 22nd 2014).

---

This is a strange hand, for which only counting is enough. You do need to time it correctly to obtain the count.

The basic idea is to count the heart+diamond+clubs to get information on how to play the spades (you can finesse either opponent for the Jack, or play for the drop).

So one line is to win the club, spade to K, cash Heart A in dummy, three rounds of diamonds ending in hand.

If diamonds are not 3-3 (otherwise you have 13 tricks), you know who has the diamond length.

Now you cash clubs throwing the hearts. You now get a count of the clubs and diamonds.

If the DJ hasn't appeared yet, you cash the HK and throw the diamond from dummy.

At this point, the card played by the opponent with the DJ will tell you exactly how to play the spades! Try it out.

Only the twain shall meet, geometry puzzle.

This is a classic problem, in disguise. That problem was open for 20+ years, so if you solve this problem without using the classic result, pat yourself on the back!

You are given a finite set of lines, $S$ in the 2D plane, no two lines of which are parallel and not all are concurrent.

Show that there are two lines (call them $p$ and $q$) such that no other line in $S$ passes through the intersection point of $p$ and $q$.

i.e. among all the points of intersections formed by the lines in $S$, there is a point through which only two lines of $S$ meet.

[Solution]

A couple of C programming puzzles

Two puzzles in one post.

The first one is a quickie.

Write a method in C, which will print ";", but does not use any semi-colons anywhere. Assume you have printf available.


The second one is strange.

Write a C program to print "hello world!" 2014 times. The catch is, it must fit inside an 80x25 page and must not use the characters f,o,w,?,&,| (last three are question mark, ampersand and pipe). Assume you have printf available (and don't need to #include the header).


[Please feel free to comment with your solutions]

[One solution]

Solution to sort each column, algorithm puzzle

[This is a solution to the sort each column, algorithm puzzle posted earlier]

A brief description of the problem:

Given a matrix of integers, by permuting each row separately (with possibly different permutations), can each column of the matrix be sorted (in ascending order, with smallest in row one)? Give a polynomial time algorithm for it.

Solution

---

Consider the case of a $2\times n$ matrix, which has two rows and $n$ columns.

Suppose it was possible to sort the columns by permuting the rows.

The claim is that, the columns remain sorted, even after we sort the rows!

For example, this is a matrix in which the columns are sorted:

$\begin{bmatrix}4&7&8&6\\5&100&200&10\end{bmatrix}$

Now, if we sort each row individually we get

$\begin{bmatrix}4&6&7&8\\5&10&100&200\end{bmatrix}$

The columns are still sorted!

The proof is actually not difficult:

Suppose $a \le b$ and $c \le d$, then we have that:

$\min\{a,c\} \le \min\{b,d\}$ and $\max\{a,c\} \le \max\{b,d\}$.

Thus
$\begin{bmatrix}\dots&a&\dots&c&\dots\\\dots&b&\dots&d&\dots\end{bmatrix}$

can be replaced by

 $\begin{bmatrix}\dots&\min\{a,c\}&\dots&\max\{a,c\}&\dots\\\dots&\min\{b,d\}&\dots&\max\{b,d\}&\dots\end{bmatrix}$

and still have the columns sorted.

Thus if the columns are sortable, they are sortable by sorting the individual rows (and vice-versa).

So the algorithm is simple: sort each row, and then check if the columns are sorted.

Solution to separating circle puzzle

[This is a solution to the Separating Circle, geometry puzzle posted earlier]

The problem:

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

---

We use the following property of circles:

If $AB$ is a chord of a circle, and $P$ and $Q$ are any two points on the major (or minor) arc of a circle, then $\angle{APB} = \angle{AQB}$, i.e. the arc of the circle is the locus of points $X$ such that the angle subtended by $AB$ at $X$ is constant.

We won't use this other fact, but just mentioning it for clarity: if $R$ is a point on the opposite arc as $P$ and $Q$ then $\angle{ARB} = 180^{\circ} - \angle{APB}$.

We won't prove these facts here, as they are easily available in textbooks/online.

Now, we can show that, if $S$ is a point inside the circle, on the same side of $A,B$ as $P$ and $Q$, then $\angle{ASB} \gt \angle{APB}$.

Proof: Line through $A$ and $S$ cuts the circle at S'. If $S$ is inside, then $\angle{ASB} = \angle{AS'B} + \angle{SBS'} = \angle{APB} + \angle{SBS'}$

Similarly, if $S$ is outside, on the same side of $AB$ as $P$ and $Q$, then $\angle{ASB} \lt \angle{APB}$.

So, if we have a circle through $A,B,C$ which separates the points, and say all the points lie to the same side of $A,B$, then the angles of the other points will be such that exactly $n$ are smaller than $\angle{ACB}$ and exactly $n$ are bigger.

This gives us a constructive proof:

Take the convex hull of all the points. Since they are not all collinear, the convex hull will have at least three sides. Pick one side, say $AB$. Now all the other points lie on the same side as $AB$.

Now, for each of the remaining $2n+1$ points, $P_i$, compute the angle $\angle{AP_{i}B}$. Since no four are concyclic, all these angles will be distinct, and we can sort them in ascending order, say: $\angle{AP_1B} \lt \angle{AP_2B} \lt \dots \lt \angle{AP_nB} \lt \angle{AP_{n+1}B} \lt \dots \lt \angle{AP_{2n+1}B}$.

Pick $C = P_{n+1}$.

The circle through $A,B,C$ will have $P_1, P_2, \dots, P_n$ outside, and $P_{n+2}, \dots, P_{2n+1}$ inside.

This generalizes to any combination of $n\pm k$ and $ n \mp k$ inside/outside.

Masterpieces of Declarer Play #67

This is hand #67 from the book, Masterpieces of Declarer Play, by Julian Pottage. This book has some very nice hands.

You are South, and end up in 4H. West leads the club 9 (opponents lead low from xxx).

IMPS None	Dummy ♠ AT ♥ Kx ♦ AKxxxx ♣ Qxx
	You ♠ J ♥ AQJTxx ♦ Jx ♣ xxxx

W	N	E	S
		P	2H
P	4H	all	pass

RHO overtakes the C9 lead with the T, and returns a spade, J, K from LHO and won in the dummy with the A.

How will you play?

[Please feel free to comment with your solution]



Solution (posted on 12th November 2014)

---

The intended solution is as follows:

LHO seems to have led from 9(x) of clubs. So RHO has the AKJT(x). RHO also seems to hold the spade Q (weak inference). Since RHO passed initially, it is likely that LHO has the DQ.

Now if we play a club (key play #1) after winning the spade Ace, threatening to ruff the fourth with the HK, RHO will have to play back a heart. So you play a club, and on the expected trump return, draw trumps.

Now for key play #2: advance the DJ.

LHO has to cover this, which you duck!

LHO does not have any more clubs, and if diamonds are 3-2, you can now make 10 tricks.

[See the comments for another nice line by Martin]

Sort each column, algorithm puzzle.

[This algorithm puzzle was inspired by some Russian math contest problem I saw a long time back]

You have an $n \times n$ matrix of integers which you want to sort by columns: each column must be individually sorted in ascending order, the first row containing the smallest elements of each column.

There is a problem though, the only operation you are allowed to perform on the matrix, is to permute the elements of an individual row. That is you can pick one row, then permute the elements within that row. Then pick another row, permute the elements within that row etc. Each row could be permuted differently.

For example:

Say you are given the matrix:

$\begin{bmatrix}4&5&6\\1&3&2\\9&7&8\end{bmatrix}$

No matter how you permute the elements of the rows, the columns cannot be sorted.

If the matrix was

$\begin{bmatrix}3&1&7\\8&6&5\\9&7&8\end{bmatrix}$

Then you could shuffle just the first row (swap $3$ and $7$) so that it now looks like

$\begin{bmatrix}7&1&3\\8&6&5\\9&7&8\end{bmatrix}$

The columns are sorted: $[7,8,9], [1,6,7], [3,5,8]$

The puzzle is to come up with a polynomial time algorithm, which given the $n\times n$ matrix, tells if you could shuffle some rows (individually) so that the columns end up being sorted. The algorithm just has to give a Yes/No answer and not the actual permutations of the rows.

[Solution]

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.