Solution to integer part of fourth root reciprocals

This is a solution to the puzzle posted earlier.

The problem:

What is the integer part of
$$1 + \frac{1}{\sqrt[4]{2}} + \frac{1}{\sqrt[4]{3}} + \dots + \frac{1}{\sqrt[4]{10000}} $$
i.e. the integer part of
$$ \sum_{k=1}^{10000} \frac{1}{\sqrt[4]{k}} $$

Solution

---

The typical way to approach this problem is to approximate the sum by an integral and find appropriate upper and lower bounds.

We will essentially do the same, but presented differently.

Consider the function $\displaystyle f(x) = \frac{4x^{3/4}}{3}$. The derivative of $f$ is $\displaystyle f'(x) = \frac{1}{\sqrt[4]{x}}$

Now using the mean value theorem, and the fact that $\frac{1}{\sqrt[4]{x}}$ is decreasing, we have the following:
$$\frac{1}{\sqrt[4]{k+1}} \lt f(k+1) - f(k) \lt \frac{1}{\sqrt[4]{k}} \quad \quad (1)$$
Using the left side of the inequality, and adding from $k=1$ to $9999$ we get
$$ \sum_{k=2}^{10000} \frac{1}{\sqrt[4]{k}} \lt f(10000) - f(1) = \frac{4}{3}(10^3 - 1) = 1332$$
Thus adding $1$ to both sides,
$$ \sum_{k=1}^{10000} \frac{1}{\sqrt[4]{k}} \lt 1333$$
Using the right side of $(1)$, and adding from $k=1$ to $9999$ we get

$$ \sum_{k=1}^{9999} \frac{1}{\sqrt[4]{k}} \gt f(10000) - f(1) = 1332$$
Thus adding $\frac{1}{\sqrt[4]{10000}} = \frac{1}{10}$ to both sides,
$$ \sum_{k=1}^{10000} \frac{1}{\sqrt[4]{k}} \gt 1332 + \frac{1}{10}$$
Thus the integer part is $1332$.

Find the missed line (bridge hand)

This is a hand from the book "Beaten by the Masters", by David Bird.

It seems like the author missed a line which ensures the contract. Can you find it?

[It is possible that the missing of the line was intentional, based on the character that plays it.]

IMPS N/S	Dummy ♠ Q74 ♥ A4 ♦ AK7 ♣ AQ932
	You ♠ AKT962 ♥ J98 ♦ - ♣ K865

W	N	E	S
			1S
4D	4NT	5D	6S
P	7S	all	pass

West leads the DQ.

[Please feel free to comment with your line.]


Solution [added Dec 3rd 2014]

---

The spade spots are such that you can always get 6 tricks. Add to that one heart and two diamonds: requiring you to get 4 club tricks.

It is tempting to throw the heart losers on the diamonds, but you will have a problem if clubs are 4-0, and will need a squeeze of some kind. [That is the line taken by the character in the book.]

Note that you need only four club tricks, not five. To cater to the 4-0 break, you win the DA and make the key play: throw a club from hand!

Now you draw trump by playing spade to A, and finessing an opponent for Jack if the other shows out. (Coming back to hand with a diamond ruff if needed).

Now play AKQ of clubs and ruff a club, making the fifth club good, irrespective of the club split. This fifth club is your fourth club trick. This club and the DK will take care of the two heart losers.

Find the three missing numbers. Algorithm puzzle.

I will get straight to the puzzle.

You have an array of $2n+3$ positive integers, such that each element appears exactly twice in the array, except for three of them (say $a,b,c$) which appear exactly once.

Can you give an $O(n)$ time and $O(1)$ space (assuming RAM model) algorithm to find out what the three unique integers $a,b,c$ are?


An easier version: Exactly two appear once in array of $2n+2$.
Easier than that: Exactly one appears once in array of $2n+1$.


[Please feel free to comment with your solution to any version of the problem]

[Solution]

Integer part of fourth root reciprocal sums

A quick to state puzzle:

If

$$S = 1 + \frac{1}{\sqrt[4]{2}} + \frac{1}{\sqrt[4]{3}} + \dots + \frac{1}{\sqrt[4]{10000}} $$

what is the integer part of $S$?

i.e. what is the integer part of

$$\sum_{k=1}^{10000} \frac{1}{k^{1/4}} $$


(integer part of $x$ = largest integer $\le x$)

[Solution]

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]