Sum of unit fractions puzzle

A unit fraction is a number of the form $\dfrac{1}{n}$, where $n$ is a positive integer $ \gt 0$.

Show that any positive rational number can be written as a sum of a finite number of distinct unit fractions.

For example 1 can be written as 1/2 + 1/3 + 1/6.


[Solution]

Textbook hand in real life?

This hand had appeared playing on BBO (if I recollect correctly).

Normally, in textbooks you see plays which one might think will be required only rarely at the table: most bread and butter hands require counting and drawing the right inferences, and not some counter-intuitive subtle technique...

Anyway, you are South, and end up in 6C after your RHO preempts 3H. I don't remember the bidding, so you can ignore it.

IMPS None	Dummy ♠ J93 ♥ T9876 ♦ KQJ ♣ 42
	You ♠ AKT ♥ 2 ♦ 2 ♣ AKQJT976

W	N	E	S
		3H	6C
all	pass

LHO leads a small spade. How will you play?


Solution (posted on Jan 3rd 2015)

---

Looks like LHO has a heart void. So LHO will have the SQ, and DA.

Seems like we got a free finesse at trick one, but if you win the T in hand, you will not make it! You will lose a diamond and a heart for sure: draw trumps and play a diamond. LHO will win the first round and exit a spade.

You need to throw your heart on the diamonds, and the only way to do that is to make sure LHO helps you by putting you in the dummy.

So win the SA at trick one (playing low from dummy), draw trumps and play diamonds.

LHO who is now left with only spades and diamonds, will have to win either the first or second round (you throw a heart on the second round if LHO ducks the first), and either lead a spade (you put up the J in dummy) or a diamond, allowing you to dispose off your losers.

Solution to finding the semi-balanced string, algorithm puzzle

This is a solution to finding the semi-balanced string algorithm puzzle.

A brief description:

Given a string S consisting of exactly (n+1) X's and n O's, show that there is exactly one cyclic shift of S which is semi-balanced, and give an O(n) time algorithm to find it.

A string is semi-balanced iff every non-empty prefix contains more X's than O's.

This property can actually be used to show that Catalan numbers are $\dfrac{\binom{2n}{n}}{n+1}$.

Solution

---

It will be a constructive proof, giving the algorithm with the proof.

Given string S consisting of X's and O's, replace X with a $1$ and O with a $-1$.

For a prefix of length $i$, take the sum $S_i$ of the $1$'s and $-1$'s that form that prefix (basically compute #X's - #O's).

For a semi-balanced string, we must have that $S_i \gt 0$ for all $i, 1 \le i \le 2n+1$.

Note that $S_{2n+1} = 1$ for any string S consisting of $n+1$ X's and $n$ O's.

Now suppose a cyclic shift left by $k$ of S gave a semi-balanced string.

Then we must have that (look at the prefix of the shift from $k+1$ to $j$)

$S_j - S_k \gt 0 \quad \forall j, k \lt j \le 2n+1$

and (look at the prefix from $k+1$ to $2n+1$ and then $1$ to $j$).

$ S_{2n+1} - S_k + S_j \gt 0 \quad \forall j, 1 \le j \le k$

i.e

$S_j \gt S_k \quad \forall j \gt k$

and (note that $S_{2n+1} = 1$)

$S_j + 1 \gt S_k \quad \forall j \le k$

Thus if $ m = \min \{S_1, S_2, \dots, S_{2n+1}\}$ then there is a unique $k$: the largest $k$ such that $S_k = m$.

This easily gives an $O(n)$ time algorithm too.

Solution to area exactly half, geomety puzzle

This is a solution to area always half puzzle.

The problem description:

Show that a triangle whose vertices are integers points (both x and y co-ordinates) and which does not have any integer point inside or on the sides (except the vertices) has area exactly half.

These triangles are sometime called primitive triangles.

Solution

---

As promised, this is the proof from the book, "Proofs from the book".

This requires some Linear Algebra background.

[Perhaps a simpler proof is to just complete the rectangle (draw horizontal and vertical lines through $p_0$ and $p_2$ in the below figure) and count the number of integer points in the triangles, but the point is to show the book proof.]

The proof in the book goes as follows:

If the points are $p_0, p_1, p_2$, then the parallelogram formed by $p_i$ and $p_1 + p_2 - p_0$ does not contain any integer point, because both $\mathbb{Z}^2$ and the parallelogram are symmetric with respect to the reflection $x \to p_1 + p_2 -x$.

Now we can tile the plane by translating this parallelogram (by integer distances) and thus, $p_1 - p_0$ and $p_2 - p_0$ form a basis for $\mathbb{Z}^2$, which implies that the parallelogram has area $1$, and the triangle has area $\dfrac{1}{2}$.

A basis of $\mathbb{Z}^2$ is linearly independent vectors $e_1, e_2$ such that $\mathbb{Z}^2 = \{ae_1 + be_2 | a, b \in \mathbb{Z}\}$.

Area of the parallelogram spanned by $e_1 = (p,q), e_2 = (r,s)$ is given by the absolute value of the determinant of $A(e_1, e_2) = \begin{bmatrix} p & r \\ q & s \end{bmatrix}$

Given any other basis $f_1, f_2$, there is an invertible matrix $Q$ with integer entries such that $A(e_1, e_2) = A(f_1, f_2)\times Q$.

Since $Q$ is invertible and contains integer entries, we must have $|det(Q)| = 1$, and hence $|det (A(f_1, f_2))| = |det(A(e_1, e_2))|$.

Choosing $f_1, f_2 = (1,0), (0,1)$ gives us the result.

There are other elegant proofs, for instance using Minkowski's theorem. See here.

Another way to prove is to prove that the integer coordinates of primitive triangle (with a $(0,0)$ vertex) form consecutive numbers in the Farey sequence.

The stronger theorem I was referring to in the problem blog post is Pick's theorem.

Finding the semi-balanced string, algorithm puzzle

A string S consisting of exactly n+1 X's and n O's is called semi-balanced, iff every non-empty prefix of S has more X's than O's.

For example:

XXO is semi-balanced while OXX is not.
XXOXO is semi-balanced but XOXOX is not.

This puzzle is in two parts.

a) Show that for any string S consisting of exactly n+1 X's and n O's, there is exactly one cyclic shift of $S$ which is semi-balanced.

For example if S = OXX, its cyclic shifts are OXX, XOX and XXO, the last one being semi-balanced.

b) Given S consisting of exactly n+1 X's and n O's, can you given an algorithm to determine, in O(n) time, which cyclic shift of S is semi-balanced?

[Solution]

Area always half, geometry puzzle.

A cute fact about triangles with integer co-ordinates:

Lemma: Suppose $A, B, C$ are points in the 2D plane each with integer co-ordinates, such that no point with integer co-ordinates lies inside, or on the sides (except $A, B, C$) of triangle $ABC$. Then, the area of triangle $ABC$ is exactly $\dfrac{1}{2}$ 

[A point with integer co-ordinates is a point whose x and y co-ordinates are both integers].

For example, $A = (0,0)$, $B = (1,1)$, $C = (2,1)$. The "base" $BC$ and height $AD$ (where $D = (0,1)$) are both of length $1$ and so the area of $\triangle{ABC}$ is exactly $\dfrac{1}{2}$

Can you prove the Lemma?

[Note, using a stronger theorem about lattice points and areas would be circular (unless you prove the stronger theorem without using this Lemma).]

[A neat proof of this appears in Proofs from the Book: Solution]

Rabbit Leads a Heart

[I had posted this article on bridgewinners.com. It is based on the characters in "Bridge in the Menagerie" by Victor Mollo, just like an earlier article: Rabbit plays a spade.]


With great reluctance and pressure from the regional bridge authorities, the members of the Griffin club agreed to hold a pre-played Matchpoint tournament. The hands would be ones which were already played at more than a 100 tables previously, and the scores would be compared against the results of those tables, rather than the tables present at the club. The results slip which contained the contracts and the opening leads at those 100+ tables, would be available as soon as the board was played.

The Hog agreed to play with the Rabbit, and on the way to the club, the Hog said, "Raise me with 2 trumps, or a singleton honour. Feel free to double the opponent's contract, no transfers when you open NT". The rabbit replied, "Ok. Lets play 3rd/5th and udca". The Hog, with a generous wave of his hand, said, "Sure". He ignored the Rabbit's defensive signals, anyway.

Meanwhile, Karapet, who was paired with Papa was saying, "Never raise me with just 3. With me they split 5-0. Never double the opponent's contract, they will make it, and never use stayman or transfers which will result in a fatal lead directing double. Why, just last Tuesday..."

He was interrupted by the Hog and Rabbit arriving at their table. Papa and Hog quickly made a side bet about who would make the Rabbit squirm in his seat first, while the Rabbit and Karapet exchanged system information. A few moments later, the tournament began.

Papa was South and was dealt



 Papa opened 2C, Karapet responded 2D, showing 0-4 or 8+ in their system. Papa bid 2S, and Karapet jumped to 4S, denying interest in slam, and showing 0-4.

At this point, Papa, starting his usual monologue with his imaginary kibitzer, thought: "Listen closely. Many players will pass here. Not Papa. You see, Rabbit is on the lead. That is usually worth one, if not two tricks. I am playing the hand, and that is worth an extra trick. I am going to bid 6S. But wait! Not so fast. Where is your imagination? If you are going to bid 6S anyway, why not give opponents a chance to make a lead directing informative double to our advantage?".

Papa bid 4NT, and Karapet showed his 0 Aces with 5D. 6S from Papa closed the bidding. The Rabbit and the Hog had passed through out.

The Rabbit led the H8, and this is what Papa saw:



Papa continued, "See! You can count on the Rabbit! The lead marks the Hog with HKQxxx(x). After winning the HQ with the HA, even the Rabbit can force an entry to dummy by overtaking the HT with the HJ. Draw trumps, unblock clubs, force entry, throw D loser on CJ. 12 easy tricks and a well deserved top!".

Congratulating himself, Papa asked for the H3 from dummy, and was taken aback when the H2 appeared on his right. After getting over the initial shock, he thought, "Hog is a good player, but this is brilliant! With HKQxxx(x) and he can afford to make an entry denying duck. He deserves a good result, but unfortunately for him, I am declaring. I can still make the hand. Wait and see".

So Papa won with the HT, drew trumps, cashed the CAKQ and the HA.

The play so far(click Next):





Papa continued, "We are at the fork in the board, if you will. I can still make the hand if I can tell who has the DK. If the Hog has it, I can exit with a heart, endplaying him. If the Rabbit has it, then I can play DA and DQ. The Rabbit who is out of hearts, must give me the 12th trick. Now who has the DK you ask? Remember the bidding? Imagination? Karapet bid 5D, and Hog did not double! That inference is good enough to place the DK with the Rabbit. Of course, if it was a better player like me, who is capable of making a deceptive double... besides, I will have a chance to make the Rabbit squirm and win the bet".

So Papa played the DA and a D to the Q. It was won by the Rabbit with the DK who now started squirming in his seat.

Papa thought, "Aha! As we inferred. Let him squirm for sometime. I win the bet and a top! I will claim just before he is about the play a card".

After some agony, the Rabbit detached a card, and Papa was about to claim as it hit the table, when he was totally shocked to see that it was the HQ, which took the setting trick.



This was the whole hand:





Papa spluttered, "You.. you... led the H8 from KQ84?".

"Yes, we are playing 3rd/5th", said the Rabbit.

"What were you thinking about when you got in with the DK!?", cried the Hog, handing Papa an IOU for his side winnings.

"I was not sure whether we play the HK or the HQ in this situation. Maybe I should have played the HK. In any case, it did not cost a trick".

Meanwhile Karapet who had opened the pre-played results slip, spoke: "Most were in 4S making 6. Some were in 6S making and some were in 6NT making. One South was passed in 2C making 12 tricks. At all tables, the lead was HK."

"Maybe they weren't playing 3rd/5th", said the Rabbit, as they drew cards for the next board.

Solution to online cake splitting algorithm puzzle.

This is a solution to the cake splitting puzzle posted earlier.

A brief description of the puzzle:

Given a stream of numbers which sum to $1$ and each number being a negative power of $2$, can you give an algorithm to split the numbers in two groups, each of which sum to half when the stream is finished? When you see a number you have to immediately decide which group it goes to. Prove that your algorithm works.

[A more clear description is on the question post].

Solution

---

The algorithm is actually simple: Keep putting the new pieces in group $A$, unless adding that piece will make the sum go over half. In which case, add it to group $B$!

The interesting part is actually proving that it works.

One such proof (thanks to Eigenray of a forums I used to frequent) goes as follows:

Let $R_A$ and $R_B$ be the volumes remaining in each group.

The key property of the algorithm:

When you look at $R_A$ and $R_B$ in binary, if $R_A \ne R_B$ and $R_A \neq 0$, then the ones (or set bits) in $R_A$ all are to the right of the ones in $R_B$.

Let $b$ be the position of left most bit in $B$.

Now suppose the algorithm is adding a piece $2^{-c}$. Now we have that $2^{-c} \le R_A + R_B \lt 2^{-b} + 2^{-(b+1)} + \dots = 2^{-(b-1)}$.

Thus if we cannot add the piece to $A$, we can add it to $B$, and still maintain the property of the bits of $R_B$ being to the left of $R_A$. This property stops holding when $R_A = 0$.

Solution to monochromatic equilateral triangle puzzle

This is a solution to the math puzzle posted earlier.

We will post a solution to the variant (which also solves the main puzzle).

The problem:

Each point of 2D plane is coloured either black or white. Given three positive angles $\alpha + \beta + \gamma = 180^{\circ}$, show that there are there points $A,B,C$ of the same colour such that the triangle formed by those three has the angles $\alpha, \beta, \gamma$.

Solution

---

The solution is quite similar to the one posted in the comments by 226.

First we show that there are three collinear points $X,Y,Z$ which are coloured the same, and $Y$ is the midpoint of $X$ and $Z$.

Assume that is not true.

Consider two points which are coloured the same (say black, wlog). Say they are $(0,0)$ and $(2a, 0)$.

Now $(a,0)$, $(-2a, 0)$ and $(4a, 0)$ must be coloured white. These three points satisfy the requirement.

Say $X,Y,Z$ are coloured black.

Let $\gamma = \max \{\alpha, \beta, \gamma\}$

Let $P,Q$ be such that $\angle{YXP} = \angle{ZYQ} = \alpha$ and $\angle{XYP} = \angle{YZQ} = \beta$. Both $\triangle{XYP}$ and $\triangle{YZQ}$ have the angles $\alpha, \beta, \gamma$.

Ths $P$ and $Q$ must both be coloured white.

Now consider point $R$ such that $\angle{QPR} = \angle{ZXR} = \alpha$ and $\angle {PQR} = \angle{XZR} = \beta$

Triangle $PQR$ also has the given angles, and so $R$ must be black. But $\triangle{XZR}$ also has the given angles, and all vertices are black.

Basically, $XZR$ is an $\alpha, \beta, \gamma$ triangle, and $P,Q,Y$ are the midpoints of the sides of $\triangle{XZR}$.

Best play for making 3NT

I don't remember the source of this hand. I had posted this on bridgebase forums a few years back.

Playing Rubber Bridge, you reach 3NT as South. West leads the HQ and you see:

Rubber None	Dummy ♠ AJT9 ♥ AK ♦ K32 ♣ Q932
	You ♠ KQ8 ♥ 432 ♦ Q54 ♣ AJ74

How will you play?

[Please feel free to comment with your line.]

Solution [Added Dec 13th 2014]

---

You have 6 tricks in the majors and need three from the minors.

If clubs are 3-2 you can get 3 tricks from the clubs. But if they are 4-1 or 5-0, you can get 3 tricks if LHO holds the club length, by playing a club to the J (and later the CA and then club to 9).

The problem occurs when RHO holds the club length: you can only get two tricks from the clubs and would need a trick from diamonds.

You only have a single heart stopper left after the opening lead. If you go out once in clubs, a heart will come back and you cannot go out in diamonds now.

The solution to this is to play the CA, then play a club to the J from dummy!

If clubs are 3-2 or LHO has the length, you make 3 club tricks.

If RHO has the length, he cannot go up with the K (otherwise you have 3 club tricks). Once you win the J, you shift to diamonds for your ninth trick.

A 100% play.

Online splitting a cake, algorithm puzzle

You want to evenly split a cake of volume one between two people, say $A$ and $B$, so that each gets the same volume of cake.

Problem is, there is another person, $C$, who has already split the cake into a finite number of pieces, each piece being of a volume which is a negative power of two: of the form $\dfrac{1}{2^k}$ for some integer $k \gt 0$. The pieces need not have the same volume and you could have multiple pieces with the same volume. For example, one such split could be $\{\frac{1}{8}, \frac{1}{8}, \frac{1}{4}, \frac{1}{2}\}$.

$C$ is also holding the cake hostage, and will only give you one piece at a time (in some random order), on the condition that you immediately make a decision who ($A$ or $B$) to give the piece to. You cannot revisit that piece later.

Can you think of an algorithm which will help split the cake equally between $A$ and $B$ in this scenario? Just an algorithm won't do, you need to prove that it works too.

[For the reason why it is called online, read this]

[Solution]

Monochromatic Equilateral Triangle, IMO problem

This problem appeared in the International Math Olympiad (IMO) in the 1970/80s.

Each point of the 2D plane, is coloured either black or white. Show that there are three points $A,B,C$ which are of the same colour, and form the vertices of an equilateral triangle.

In other words, there is a monochromatic equilateral triangle, no matter how you colour each point of the plane, with one of two colours.

A variant:

Given three positive angles $\alpha + \beta + \gamma = 180^{\circ}$, show that there is a monochromatic triangle with those angles.

[Solution]

Solution to find the three missing numbers

The puzzle (posted earlier):

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?

Solution

---

If we had just one number missing, this would be the classic puzzle whose solution is to XOR (bitwise exclusive or, denoted $\oplus$) all the numbers. The result will be the unique number.

A similar solution works in the two unique case (missing $a,b$), where you XOR all the number together, and use a set bit position in the result (which is $a \oplus b$) to differentiate between the two unique numbers by making another pass and bucketing based on that bit. [See Collins' comments on the question post for more details.]

When you try to apply that to the three unique case, we compute $S = a \oplus b \oplus c$, but this might well be $0$. Even if some bit of $S$ was set to $1$, the corresponding bits of $a,b,c$ could all be $1$ and we cannot be sure of using that position to distinguish one of them.

But, consider this: If $S$ differed from $a$ at some bit position, then that bit position could be used as a distinguishing bit for $a,b,c$. Because if $a,b,c$ were all the same at that position, then $S$ would be too, and cannot differ from $a$. $S$ will always differ from some bit of $a$ as otherwise we will $S = a$ and thus $b = c$.

But, we don't really know what $a,b,c$ are, to find out a differing bit.

That does not matter though, if we consider the smallest position where they might differ.

If $f(x,y)$ is the smallest bit position (rightmost bit position being $0$) where $x$ and $y$ differ, then we cannot have that $f(S,a) = f(S,b) = f(S,c)$, as otherwise $a,b,c$ would agree at that position and thus would not differ from $S$ at that position. [Note that $f(x,y)$ can be computed in $O(1)$ time and space by using the classic bithack: $x \& (x-1)$.]

Thus the algorithm becomes:

Compute $S = a \oplus b \oplus c$ by doing an XOR of all $a_i$.

Now make another pass through the array and compute the XOR $T$ of all $\displaystyle 2^{f(S, a_i)}$, where $a_i$ are the elements of the array.

Note that $\displaystyle 2^{f(S,a_i)}$ can be computed in $O(1)$ time, and would fit in the underlying register (so $O(1)$ space). We also ignore $a_i$ for which $S = a_i$.

Now, $T$ cannot be $0$ as it is the bitwise XOR of three powers of $2$. Thus, a set bit of $T$ can now be used to distinguish one of $a,b,c$, and we can then fall back to the two unique case to find the other two.