Chess Puzzle - 9

Carefully analyze the chess position below:

As you must have noticed, white is in a very strong position and has many good moves to choose from, including some free captures. Though there are many possible moves white can play that will leave him with a clear material advantage and an eventual victory, can you look past all the distraction and find a forced sequence leading to a quick mate?

This might take you a bit of time, but once you've spotted the sequence, you'll surely end up marvelling at its ingenuity. So, fire up those grey cells now .. and happy puzzle solving!

Chess Puzzle - 8

After a long hiatus, I'm finally posting a new chess puzzle on my blog.

 

Looking at the position above, can you find the sequence of moves that white needs to play in order to enforce a checkmate?

As usual, I will be waiting for your answers (hopefully in algebraic notation) to be posted in the comments section. Cheers!

Twin Primes and Prime Triples

A twin prime is a prime number that differs from another prime number by two, like for example, the twin prime pair (41, 43). Twin primes appear despite the general tendency of gaps between adjacent primes to become larger as the numbers themselves get larger due to the prime number theorem, which states that the "average gap" between primes less than $n$ is $log(n)$.

The twin prime conjecture, which postulates that there exist infinitely many twin primes, has been one of the great open questions in number theory for many years. In 1849 de Polignac made the more general conjecture that for every natural number $k$, there exist infinitely many prime pairs $p$ and $p′$ such that $p′ − p = 2k$. The special case $k = 1$ is known as the twin prime conjecture.

The Hardy–Littlewood conjecture (named after G. H. Hardy and John Littlewood) is a generalization of the twin prime conjecture. It is concerned with the distribution of prime constellations, including twin primes, in analogy to the prime number theorem.

The largest know twin prime pair found till date is $3756801695685 · 2^{666669} ± 1$. The numbers have $200700$ decimal digits each. There are known to be $808,675,888,577,436$ twin prime pairs below $10^{18}$. The first few twin prime pairs are as follows:

$(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), \dots$

When it comes to prime triples (three consecutive primes, each differing from the previous one by 2), however, it can easily be proved that $3,5,7$ is the only prime triple. The proof follows -

Let us assume, for the sake of argument, that there exists another prime triple apart from 3,5,7.

Also, let $p$, where $p>3$, denote the smallest prime which is a part of that triple.

Then, clearly, this prime triple consists of the three integers $p$, $p+2$ and $p+4$.

Now, by the Division Theorem, we know that any integer $p$ can be expressed in one of the forms $3k$, $3k+1$, or $3k+2$, where $k$ is an integer. Let us consider three distinct cases - 

Case 1: The integer $p$ can be expressed in the form $3k$, where $k$ is an integer.

In this case, the integer $p=3k$ is divisible by 3. 

Case 2: The integer $p$ can be expressed in the form $3k+1$, where $k$ is an integer.

In this case, the integer $p+2=3k+3=3(k+1)$ is divisible by 3. 

Case 3: The integer $p$ can be expressed in the form $3k+2$, where $k$ is an integer.

In this case, the integer $p+4=3k+6=3(k+2)$ is divisible by 3. 

So, we have proved that at least one of the integers $p$, $p+2$, $p+4$ is divisible by 3. But this is obviously a contradiction, since each of the integers $p$, $p+2$, and $p+4$ are supposed to be primes strictly greater than 3. Thus, our assumption must have been incorrect.

Hence, we have proved that the only prime triple is 3,5,7.

A Simple Bijection between Even and Odd Subsets

Let $E(n)$ denote the set of even subsets (subsets of even size) and $O(n)$ the set of odd subsets (subsets of odd size) of a set $S$ containing $n$ elements.  Assuming $n \geq 1$, we can describe a simple bijection between these two sets as follows-

Let $y$ be any arbitrary element of the set $S$. Then, we simply map each $A \subseteq S$ to the set $A \triangle \{y\}$, the symmetric difference of the subset $A$ and the singleton set $\{y\}$. In other words, if the set $A$ does not contain the element $y$, then we map it to the set $A \cup \{y\}$; otherwise, if $A$ already includes the element $y$, then we map it to the set $A \setminus \{y\}$.

Under this mapping, since each subset gets mapped to a subset whose cardinality is either 1 more or 1 less than its own cardinality, its easy to see that odd subsets get mapped to even subsets while even subsets get mapped to odd subsets. Moreover, since $|E(n)| = |O(n)|$ and the mapping is one-to-one, it has to be a bijection.  

An Irrational Raised to the Power of an Irrational - Can it be Rational?

If you like playing around with numbers, here is a question for you to ponder over: is it possible to obtain a rational number by raising an irrational number to the power of another irrational number?

The answer, rather surprisingly, is YES. 

And here is a classic proof to establish the fact beyond all doubt -

Let us consider the irrational numbers $\sqrt{2}$ and $\sqrt{3}$.

Now, let us look at the number $\sqrt{3}^{\sqrt{2}}$, which is obtained by raising an irrational number to the power of another irrational number.

If the number $\sqrt{3}^{\sqrt{2}}$ is rational, then we are already successful in proving our claim.

Otherwise, if $\sqrt{3}^{\sqrt{2}}$ is irrational, then let us look at the number $(\sqrt{3}^{\sqrt{2}})^{\sqrt{2}}$, which is again obtained by raising an irrational number to the power of another irrational number.

However, $(\sqrt{3}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{3}^{(\sqrt{2}.\sqrt{2})} = (\sqrt{3})^{2} = 3$, which is a rational number. Thus, in this case also, our claim is proven. 

Hence, in either case, we have managed to establish that it is indeed possible to obtain a rational number by raising an irrational number to the power of another irrational number.


Notice that the above proof, attributed to Dov Jarden, is non-constructive in nature, which means that it does not provide us explicitly with a rational number obtained by raising an irrational to the power of another. However, in case you are someone who doesn't feel satisfied without seeing an explicit example, consider the number $(\sqrt{3})^{\log_{3}{4}}$.

We know that $\sqrt{3}$ is irrational. Let us convince ourselves that $\log_{3}{4}$ is also irrational.
Suppose it was rational. Then, we could have written it in the form $\frac{p}{q}$, where $p$ and $q$ are co-prime integers. In that case, we would have had:
$$\log_{3}{4} = \frac{p}{q} \Leftrightarrow 3^{\frac{p}{q}} = 4 \Leftrightarrow 3^{p} = 4^{q}$$
which is clearly a contradiction, since $3^p$ is odd while $4^q$ is even. Hence, the number $\log_{3}{4}$ must be irrational.
Now, $(\sqrt{3})^{\log_{3}{4}} = 3^{\frac{1}{2}\log_{3}{4}} = 3^{\log_{3}{2}} = 2$, which is rational. Thus, it is further proof that our assertion is indeed correct.

Product of k Consecutive Numbers is Divisible by k!

Suppose $P$ is the product of $k$ consecutive integers, where $k \geq 1$.
Then, $k!$ divides $P$ .


Proof 1 -

Let $P$ be the product of $k$ consecutive integers from $n+1$ up to $n+k$, so that we have:

$$P = (n+1)(n+2)...(n+k) = \frac{(n+k)!}{n!}$$

Now, we know that the power of any prime $p$ in $k!$ is given by the following finite sum:

$$\sum\limits_{m \geq 1}^{}{\left\lfloor \frac{k}{p^m} \right\rfloor}$$

Therefore, the power of any prime $p$ in the product $P$ is given by:

$$\sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n+k}{p^m} \right\rfloor} - \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n}{p^m} \right\rfloor}$$
Since $\forall p,q,r \in \mathbb{Z}^{+}: \left\lfloor \frac{p+q}{r} \right\rfloor \geq \left\lfloor \frac{p}{r} \right\rfloor + \left\lfloor \frac{q}{r} \right\rfloor$, we must have:

$$\sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n+k}{p^m} \right\rfloor} - \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n}{p^m} \right\rfloor} \geq \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{k}{p^m} \right\rfloor}$$

Thus, we see that, for every prime $p$, the power of $p$ in $k!$ never exceeds the power of $p$ in the product $P$. Hence, $k!$ always divides the product $P$.

Proof 2 -

Let $P$ be the product of $k$ consecutive integers from $n+1$ up to $n+k$. So, we have:
$\begin{aligned} \hspace{4cm} P & = (n+1)(n+2)...(n+k) \\ & = \frac{(n+k)!}{n!} \\ & = k!  \frac{(n+k)!}{n!k!} \\ & = k!  \binom{n+k}{k} \end{aligned}$

Now, the binomial co-efficient $\binom{n+k}{k}$, being the number of ways in which one can choose $k$ items out of a total of $n+k$ distinct items, is known to be integral. Hence, $k!$ must divide the product $P$.

Chess Puzzle - 7

The following position below is taken from a game between the legendary Russian grandmaster Garry Kasparov, considered by many to be the greatest ever chess player in the world, and his trainer Aleksander Nikitin in Moscow in 1981.

The position above (black to move) developed after 39 moves in the game that started off with the B44 Paulsen Variation of Sicilian Defense. Analyze the position carefully and try to figure out the next move by black which would leave his opponent in a pretty hopeless position. Lets see how many of you can spot it!

Finding GCD

Today, I am sharing a little problem from number theory, which is stated as:

Let $a = 7k + 2$ and $b = 9k - 5$. Then, prove that $gcd(a,b)$ is either 1 or 53.


The solution repeatedly makes use of the fact that, if $m > n$, $gcd(m , n) = gcd(m - n, n)$. It proceeds as follows:

$\begin{aligned} gcd (a,b) & = gcd(7k+2,9k-5) \\ & = gcd(7k+2,2k-7) \\ & = gcd(5k+9,2k-7) \\ & = gcd(3k+16,2k-7) \\ & = gcd(k+23,2k-7) \\ & = gcd(k+23,-53) \\ & = gcd(k+23,53) \end{aligned}$

Since 53 is a prime number, either it divides $k+23$, in which case we have $gcd(a,b) =$ 53, or it does not divide $k+23$, which makes $gcd(a,b) =$ 1. Hence proved.

The identity $gcd(m , n) = gcd(m - n, n)$ doesn't just help us solve this particular problem. It is actually the core idea behind Euclid's recursive algorithm for computing the GCD of two integers. The earliest surviving description of the Euclidean algorithm can be found in Euclid's 'Elements' (c. 300 BC), making it one of the oldest numerical algorithms still in common use.

Bangla Kobita - 5

আজ সভ্যতা আমায় করেছে অন্ধ, 
তবু পাই আমি তাজা রক্তের গন্ধ- 
ভবিষ্যত্ হোক না মোর যতই ধোঁয়াশা, 
মেটে না প্রবল এই জীবনপিপাসা!

স্পর্শকাতর নয় এই মন-
বহু তীর ছুঁয়ে চলে যায়; 
ক্ষতবিক্ষত প্রতিটা ক্ষণ 
তবু বারবার মনকে কাঁদায়!  

Chess Puzzle - 6

Today's puzzle is quite a tricky one, but once you figure it out, I promise you that you will find yourself wonderstruck by the sheer beauty of the solution!

Looking at the position above (white to move), one can see quite clearly that its a won game for white. All white needs to do is to capture the last of black's pawns with Nxh7 and then queen his own pawn with the support of his remaining pieces - quite a straightforward victory!

However, there is a way for white to force a mate in just a few moves without even needing to queen his pawn. The challenge for you is: can you find it?

So friends, put on your thinking caps and put those grey cells to good use!

Oh, and once you've got it sorted out, please do not forget to post your answers (preferably in algebraic notation) in the comments section.

Bangla Kobita - 4

ভ্রষ্ট চেতনার ভীড়ে, 
নৃশংসতার নীড়ে,
বন্ধু হেঁটো সাবধানে- 
বিবেকের তত্বাবধানে। 

ঝলসে যাওয়া যত সুখ 
বেদনায় হয়েছে মূক; 
ভেঙ্গে যায় বুক 
তবু কেন বুজে মুখ?

শোকার্ত পাগলা হাওয়া 
বাদলকে করে চলে ধাওয়া; 
জীবন জুড়ে শুধু চাওয়া 
আর হতাশাদায়ক না-পাওয়া।

অপরিপূর্ণতা সাথী নিত্যদিন,
সংসারসুখ তবু রয় অমলিন;
বাইরের রূপটা তো সর্বদা সুশীল-
জ্বলছে সংগ্রামের আগুন অন্ত:শীল!  

Chess Puzzle - 5

The position given below has been taken from a game in 1894 involving the great Russian chess master Mikhail Ivanovich Chigorin (Russian: Михаи́л Ива́нович Чиго́рин).

The last great player of the Romantic chess style, his playing style featured a well honed tactical ability and an imaginative approach to the opening. Chigorin has several chess openings or variations of openings named after him, the two most important being the Chigorin Variation of the Ruy Lopez (1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.O-O Be7 6.Re1 b5 7.Bb3 d6 8.c3 O-O 9.h3 Na5 10.Bc2 c5 11.d4 Qc7) and the Chigorin Defence to the Queen's Gambit (1.d4 d5 2.c4 Nc6).

Born in Gatchina in 1850, Chigorin became serious about chess uncommonly late in life; his schoolteacher taught him the moves at the age of 16, but he did not take to the game until around 1874, having first finished his studies before commencing a career as a government officer. Once smitten with the game, he terminated his employment and started life as a chess professional. It was not long after that he came to be regarded widely as the best player in the whole of Russia.

Through his original talent, lively games and prolific teachings, many Russians hail Mikhail Chigorin as the founder of the Soviet School of Chess. Overshadowed in the 1920s by the exciting new theories of the hypermodern movement, Chigorin's influence nevertheless demands a prominent and permanent place in the Soviet chess hegemony of the 20th century.

Looking at the above position (white to move), can you find the forced mate lurking around the corner? Also, once you've found the mating sequence, you can amuse yourself by trying to find a way to ensure that the white pawn on g6 converts. Happy brainstorming!

Kings in a Tournament

In a tournament, each pair of teams plays one game, which one of the teams wins and the other loses. The number of teams in a tournament can be any integer greater than one. In a particular tournament, team X is said to be a 'king' if, for every other team Y, X beats Y or a team that beats Y. The aim of this article will be to establish that every tournament contains at least one king, yet no tournament can have exactly 2 kings. In order to prove these facts, I will introduce some definitions from graph theory first, which are as follows:

An orientation $\vec{G}$ of a graph $G$ is an assignment of an orientation (direction) to each edge.

We call the directed edges arcs. So if the edge $vu$ is oriented from $v$ to $u$, we refer to the resulting directed edge as the arc $(v, u)$. We denote the arcs of $\vec{G}$ by $A(\vec{G})$. Sometimes, we may refer to $v$ as the tail of the arc and $u$ as the head of the arc.

The indegree $d^{-}(v)$ of a vertex $v$ in an oriented graph $\vec{G}$ is the number of arcs that are oriented towards $v$, i.e. the number of arcs of the form $(u, v)$. Similarly, the outdegree $d^{+}(v)$ of a vertex $v$ in an oriented graph $\vec{G}$ is the number of arcs that are oriented from $v$, i.e., the number of arcs of the form $(v, u)$.

The in-neighbourhood $S_I(v)$ of a vertex $v$ in an oriented graph $\vec{G}$ is the set of all vertices $u$ such that $(u,v)$ is an arc in $\vec{G}$. Similarly, the out-neighbourhood $S_O(v)$ of a vertex $v$ in an oriented graph $\vec{G}$ is the set of all vertices $w$ such that $(v,w)$ is an arc in $\vec{G}$.

In an oriented graph $\vec{G}$, a directed path is a path in which all the edges have the same orientation.

Any orientation of a complete graph is referred to as a tournament.
So, thinking of this to be a representation of an actual tournament where the arc $(v, u)$ indicates that $v$ beat $u$ in the competition, a vertex $v$ should be called a king if, for every other vertex $u$ in the graph, there is a directed path of length 1 or 2 from $v$ to $u$, since this implies that either $v$ beat $u$ or $v$ beat someone who beat $u$. Having thus restated our original problem in terms of graph theory, we are now ready to proceed with the proofs.

Tournament Graph with 5 Vertices having 4 Kings

Claim 1. Every tournament $T$ contains at least one king.

Proof. Suppose that $v$ is a vertex having maximum outdegree in the tournament graph $T$. Then, we claim that $v$ is a king in $T$. In order to verify this claim, it is enough to show that there is a directed path of length 2 from $v$ to each vertex in its in-neighborhood, denoted by $S_I(v)$.

So, let $u$ be any vertex belonging to $S_I(v)$. If there is a vertex $w$ in the out-neighbourhood of $v$, denoted by $S_O(v)$, such that $(w, u)$ is an arc of $T$, then the arcs $(v, w)$ and $(w, u)$ form a directed path of length 2 from $v$ to $u$.

On the other hand, if there is no such vertex in $S_O(v)$, then it must be the case that, for all vertices $y \in S_O(v)$, $(u, y)$ is an arc of $T$, which implies that $\forall y \in S_O(v)$, we have $y \in S_O(u)$. Now, since all the vertices in $S_O(v)$ also belong to $S_O(u)$, and additionally $v \in S_O(u)$, hence the outdegree of $u$ is greater than that of $v$. But this contradicts the choice of $v$ itself. Thus, there has to exist a vertex $w \in S_O(v)$ such that $(w, u)$ is an arc of $T$, and hence the claim is verified.


Claim 2. Let $q$ be a team that loses at least once in a tournament $T$. Then, the teams that beat $q$ include at least one king.

Proof. First, let us consider the case where $q$ is beaten by only one team $p$. In that case, $p$ is clearly a king in $T$ since it has a direct arc $(p, q)$ to $q$ and a directed path of length 2 to each of the remaining vertices of $T$, which all belong to the out-neighbourhood of $q$.

Now, if $q$ is beaten by more than one team, we simply consider the smaller tournament consisting only of the teams that beat $q$ and the games they play with each other. In other words, we will be looking at the tournament graph $T'$ induced on only the vertices belonging to the in-neighbourhood of $q$. From the previous claim, we know that the tournament $T'$ contains at least one king. Now, if $p$ is a king in the tournament $T'$, then $p$ must also be a king in $T$. This is true because, $p$ has a direct arc $(p, q)$ to $q$ and a directed path of length 2 to all the vertices in the out-neighbourhood of $q$, and being a king in $T'$, it is also guaranteed to have a directed path of length either 1 or 2 to each of the vertices (except itself) in the in-neighbourhood of $q$. Hence proved.


Claim 3. No tournament can have exactly 2 kings.

Proof. Let us assume, for the sake of argument, that a tournament has exactly 2 kings, say $q$ and $r$. As the two kings play each other, without loss of generality we can assume that $q$ beats $r$. However, since $r$ is a king in the tournament, $r$ must have beaten someone who beat $q$. In order for this to be possible, there must be at least one team who beat $q$ in the tournament. Now, from the previous claim, we know that there must be at least one king, say $p$, amongst the teams who beat $q$, and obviously, $p$ is different from both $q$ and $r$. Thus, our initial assumption is shown to be incorrect. Hence proved.

Chess Puzzle - 4

In the chess position given below, with white to move, can you spot a mating sequence for white?

Lets see how many of you can solve this one correctly.Those of you who think that they have figured it out, please post your answer (preferably in algebraic chess notation) as a comment. Enjoy!

Acyclic Orientations of k-Colourable Graphs

An orientation $\vec{G}$ of a graph $G$ is an assignment of an orientation (direction) to each edge. We call the directed edges arcs. So if the edge $vu$ is oriented from $v$ to $u$, we refer to the resulting directed edge as the arc $(v, u)$.

A colouring (or more specifically vertex colouring) of a graph $G$ is a labelling of the graph’s vertices with colours, drawn from the set of positive integers $\mathbb{Z}^+$, such that no two vertices sharing the same edge have the same colour. The minimum number of colours needed to colour a graph $G$ is called its chromatic number, and is often denoted by $\chi(G)$.

A vertex colouring of the Petersen graph with 3 colours, the minimum number possible.

Now suppose that $\vec{G}$ is an acyclic orientation of the graph $G$. We will show that, if $k$ denotes the number of vertices in a longest directed path in $\vec{G}$, then $G$ is $k$-colourable.

To prove the above claim, we will simply devise a colouring of $\vec{G}$ where each vertex $v$ is coloured with a number $l$ which is equal to the number of vertices in any longest directed path that begins at $v$. Since the number of vertices in any longest directed path in $\vec{G}$ itself is $k$, it is quite obvious that this colouring uses exactly $k$ colours. So, all we need to do is to establish that it is indeed a valid $k$-colouring.

Let $v$ and $u$ be adjacent vertices of $G$, and suppose that the edge $vu$ is oriented as the arc $(v,u)$. Then, if the number of vertices in a longest path that originates at $u$ is $l$, the number
of vertices in a longest path that originates at $v$ has to be at least $l+1$. Thus, any 2 adjacent vertices $v$ and $u$ must have different colours in the described $k$-colouring, implying that it is valid.


We will also show that, if $G$ is a graph having chromatic number $k$, then there exists an acyclic orientation $\vec{G}$ of $G$ in which the longest directed path contains exactly $k$ vertices.

To prove the above claim, we will consider a colouring of $G$ with the colours $\{1, 2, …, k\}$, and devise an orientation $\vec{G}$ based upon these colours where we simply orient each edge from the vertex with lower label to the vertex with higher label. Since the magnitudes of the vertex colours strictly increase as we traverse any directed path in $\vec{G}$, we immediately conclude that there cannot be any directed cycles in $\vec{G}$. Moreover, since the total number of colours used is only $k$, we also conclude that any directed path in $\vec{G}$ can contain at most $k$ vertices. However, using the previous result, we already know that there has to be at least one directed path in $\vec{G}$ having at least $k$ vertices, because otherwise, the chromatic number of the graph $G$ would have been less than $k$. This completes the proof.

Chess Puzzle - 3

Here is another chess puzzle for you guys. Looking at the position (black to move) below, can you come up with the next move that black should play so that it becomes impossible for white to avoid being checkmated? [Note: White might be able to prolong the game for a few moves with some spite checks, but it will merely be delaying the inevitable.]

As usual, I will request you to post your answer (preferably in algebraic notation) as a comment. Have fun while solving this!

The Lone Sentinel

The house stands like a lone sentinel;

Alone it stands in the middle of the field-

Separated from the outside world

As if by an invisible shield.

The faint light that seeps out of its windows,

Having somehow slipped past the heavy curtains,

Is gobbled up by the swirling mist that encircles it

And blurred into near insignificance.

Through a tatter in the clouds above,

The moon glumly looks down;

And sees the barren landscape

Reluctantly shed its dark gown.

Breaking the unearthly stillness,

A melancholy draught whispers by;

It makes the gnarled trees dotting the desolation

Shiver and sigh.

Yet, the house stands unmoved.

The Suicides of Dot-Town

Today, I am going to present before you a very general version of classical problems involving knowledge about knowledge. Fondly dubbed as "The Suicides of Dot-Town", the problem is stated in the following manner:

Each resident of Dot-Town carries a red or blue dot on his forehead, but if he ever figures out what colour it is, he kills himself. Each day, all the residents gather in the town hall and count the number of red and blue dots they see. However, they do not communicate their counts to one another. One day, a stranger comes and tells them something non-trivial about the number of blue dots. Prove that the aftermath of this event is that, eventually, every resident kills himself.

[Note: Here, “non-trivial” means that there is some number of blue dots for which the statement would not have been true. Thus, through his statement, the stranger is effectively letting the residents of Dot-Town deduce a set $K$ such that the number of blue dots cannot belong to $K$.]


An elegant proof devised by Peter Winkler, which uses backward induction on the number of disallowed numbers of blue dots, follows:

Suppose that the population of Dot-Town is $n$.
Now, let us assume that the stranger announces that the number of blue dots does not belong to the set $K$, where $K$ is some non-empty subset of the numbers from $0$ to $n$.

When $|K| = n−1$, the base case of the induction applies.
Though each resident is oblivious to the colour of his own dot, if he sees $y$ number of blue dots in the gathering, he will know that the actual number of blue dots has to be either $y$ (if he is red-dotted) or $y+1$ (if he is blue-dotted). However, if $|K| = n−1$, then each resident can immediately eliminate one of these possibilities and deduce the colour of his own dot, which leads him to commit suicide. Thus, the entire population of the town gets wiped out immediately.

Otherwise, let us consider what happens when $|K| < n−1$.
Suppose the actual number of blue dots is $j$. So then, when all the residents gather in the town hall, the red-dotted residents see $j$ blue dots while the blue-dotted residents see only $j−1$.

Now, if $j−1 \in K$, then the blue-dotted residents will be able to deduce the colour of the dot on their foreheads, and hence, they will all kill themselves on the first night after the stranger's announcement. On noting the absence of their blue-dotted counterparts the following morning, the remaining residents (if any) will deduce that their spots are red, and dispense with themselves the same night.

Similarly, if $j+1 \in K$, then the red-dotted residents will be able to deduce the colour of the dot on their foreheads, and hence, they will all kill themselves on the first night after the stranger's announcement. On noting the absence of their red-dotted counterparts the following morning, the remaining residents (if any) will deduce that their spots are blue, and dispense with themselves at night.

If no one kills himself on the first night, then the following morning, everyone can deduce that neither $j−1$ nor $j+1$ is in $K$, which means the actual number of blue dots is not within one of any number in $K$. This effectively increases the number of forbidden numbers of blue dots, and so the induction hypothesis can now be applied by expanding the set $K$ to include numbers that are exactly one away from those already in $K$.

Note that the proof also shows that $n$ nights suffice; further, that the full $n$ nights are needed only when either $K = \{0\}$ and all the dots are blue, or $K = \{n\}$ and all the dots are red, or $n \leq 2$.

Bangla Kobita - 3

সমাজের জাঁতাকলে
পিষ্ট যে হয়ে চলে 
হাজার হাজার তরুণ প্রাণ।

অচেনার ভীড় ঠেলে 
অজানার দেখা মেলে;
তবু হৃদয়ের অলিগলি শুনশান।

ভস্ম হয়ে যাওয়া শুকনো পাতার মত 
ভেঙ্গে যাওয়া স্বপ্নের টুকরো ওড়ে যত;
আজ আঁধার ঘনিয়ে আসে চোখের সামনে। 

যন্ত্রণা হয়ে ওঠে আততায়ী-
সুখের দুনিয়া কবে হবে স্থায়ী?
চলতে হবে না আর কোনো বাঁধা মেনে?

জানি অধিকাংশই বড় শান্তিকামী,
তবু বিদ্রোহ ঘোষণা করে যাই আজ আমি!

Chess Puzzle - 2

Chess Grandmaster Nikolai Spiridonovich Rossolimo, who was born in Ukraine when it was part of the Russian Empire, played for France in the Chess Olympiads of 1950 and 1972, and for the United States in 1958, 1960, and 1966. He was awarded the International Master title in 1950 and the International Grandmaster title in 1953. Rossolimo won many brilliancy prizes for his beautiful chess games, and has been called an "artist of chess".  The strongest players he defeated were Efim Bogoljubov, David Bronstein, and former World Champion Max Euwe, against whom he had two wins and a lifetime plus score. He also scored draws against four world champions: José Capablanca, Max Euwe, Bobby Fischer, and Vassily Smyslov. He authored two chess books, and ran the legendary Rossolimo Chess Studio in Greenwich Village in Manhattan. The Rossolimo Variation of the Sicilian Defence bears his name. Sadly, Rossolimo died of head injuries following a fall down a flight of stairs, just after finishing third in his final event, the 1975 World Open.


The position below is taken from a game played between Nicolas Rossolimo and Gabriel Wood in 1949. The game, which started off with the E90 King's Indian opening, ended in victory for Rossolimo, who was playing white.

Taking a look at the position above (white to move), which developed after the 86th move, can you come up with a forced sequence that leads to a checkmate for white?

You can post your answer (preferably in algebraic chess notation) as a comment below.

Lets see how many of you can solve this correctly. All the best!

Love in Kleptopia

Today, I am going to present a very nice logical puzzle that I chanced upon recently. The puzzle, popularly known as "Love in Kleptopia", is stated as follows:

Alice and Bob have fallen in love (via long, romantic chats on facebook) and Bob wishes to mail Alice an engagement ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Alice and Bob each have plenty of padlocks, but none to which the other has a key. Under these circumstances, how can Bob get the ring safely into Alice’s hands?


The solution, which is quite ingenious, follows:

Bob sends Alice a box with the ring in it and one of his padlocks on it. Upon receipt, Alice affixes her own padlock to the box and mails it back with both padlocks on it. When Bob receives it, he removes his own padlock and sends the box back to Alice. So now, Alice receives the box with the ring in it and a padlock on it to which she has the key. Voila!


The solution stated above is not only elegant, but also provides an idea that is fundamental in Diffie-Hellman key exchange, which was quite a historic breakthrough in cryptography!

The Mirror of Reality

I looked into the mirror and saw
A jolly face grinning back-
A face that radiated vigour and youth,
As if it had not a single care in the world!

I was beginning to turn away,
But then, something caught my eye;
I looked more closely, and with a critical eye,
And the face didn't look so jolly after all-
Even the grin now seemed somewhat strained,
Almost as if it hid a grimace of pain.

I looked even more closely, and was taken aback.
The youthful exuberance slid away
To reveal a haggard and careworn face;
'Twas a face scarred by many battles,
A face with lines etched deep into it-
The unmasked face of a Survivor!

The Spectre of Carnage

In the rotting decadence I stealthily prowl,

Ignoring reason, and its warning growl!

A piercing hunger gnaws steadily at my gut

As I stumble along with my eyes clenched shut.

In the deepest of shadows I silently lurk,

While centuries of evolution leave their mark-

Seeking a place which I could call home,

Like a restless soul I ceaselessly roam.

All around me the world lies ravaged-

The brutal savagery of man, uncaged!

The Immortal Game

The Immortal Game was a chess game played by Adolf Anderssen and Lionel Kieseritzky on 21 June 1851 at the Simpson's-in-the-Strand Divan in London. It was an informal game played between the two great players during a break in the London 1851 chess tournament, which was also the first international chess tournament. Incidentally, Adolf Anderssen went on to win the sixteen-player tournament, earning him the status of the best player in Europe.

The French chess magazine La Régence published the game in July 1851. It was nicknamed "The Immortal Game" in 1855 by the Austrian chess master Ernst Falkbeer. In this game, Anderssen, playing white, sacrificed a bishop (on move 11), both rooks (on moves 18 and 19), and the queen (on move 22) to produce checkmate against Kieseritzky who had only lost three pawns. In doing so, he successfully managed to illustrate that two active pieces can be worth a dozen inactive pieces.

This game is acclaimed as an excellent demonstration of the style of chess play in the 19th century, where rapid development and attack were considered the most effective way to win, and where many gambits and counter-gambits were offered. In fact, in that era, not accepting gambits was considered slightly ungentlemanly. These games, with their rapid attacks and counter-attacks, are often entertaining to review, even though some of the moves would no longer be considered the best by today's standards.

Animation of The Immortal Game

The game in algebraic chess notation -

White: Adolf Anderssen; Black: Lionel Kieseritzky; Opening: Bishop's Gambit

1.   e4         e5 

2.   f4         exf4

3.   Bc4      Qh4+

4.   Kf1       b5

5.   Bxb5     Nf6 

6.   Nf3       Qh6 

7.   d3         Nh5

8.   Nh4      Qg5

9.   Nf5       c6

10. g4         Nf6 

11. Rg1       cxb5

12. h4         Qg6 

13. h5         Qg5 

14. Qf3       Ng8

15. Bxf4     Qf6 

16. Nc3      Bc5

17. Nd5      Qxb2

18. Bd6       Bxg1

19. e5         Qxa1+

20. Ke2       Na6

21. Nxg7+   Kd8 

22. Qf6+     Nxf6 

23. Be7#

At the end, black is ahead in material by a considerable margin: a queen, two rooks, and a bishop. But the material does not help black. Through sheer strategic brilliance, white has been able to use his remaining pieces - two knights and a bishop - to force mate.


I have intentionally not annotated the game and left it as an exercise for the reader to figure out the motives behind some of the rather surprising moves and their possible alternatives. If you have too much trouble deciphering a particular move (or sequence of moves), please feel free to leave a comment and I'll be happy to explain. So, my fellow chess enthusiasts, go ahead and rack your brains, and have fun while doing it. Enjoy!
 
 

Confessions of an Eternal Optimist

I have been to hell and come back again;
I have lived through droughts and excess rain;
I have had my share of mirth and pain;
Sometimes I lose, sometimes I gain;
Yet, all the while, before your eyes,
I have dared to live life king-size!

Bangla Kobita - 2

আমি এক ছন্নছাড়া,
জীবনের বাঁধনহারা;
অনিয়মই নিয়ম আমার-
কথা নেই কোথাও থামার!

দুর্বল হয়েছে শরীর কদাচিত-
আক্রমণ করেছে মোরে জরা;
শুকিয়েছে ভাবনার জলাশয়,
মনেতে দেখা দিয়েছে খরা।

তবু প্রতিবারই সুপ্ত শক্তির জাগরণে 
পলাতক হয়েছে সে জরা;
আর সৃজনশীলতার বাঁধভাঙ্গা উচ্ছাস 
নিশ্চিহ্ন করেছে সে খরা।  

হয়েছে যখনই চিত্ত ম্রিয়মাণ,
নতুন সুরে গেয়ে উঠেছে প্রাণ!   

Chess Puzzle - 1

Today, I am going to share a brilliant chess puzzle I came across on the internet.

The position below is taken from a game in 1737 involving the English chess master Philipp Stamma (c.1705–55). He authored the book 'Essai sur le jeu des echecs' (English translation: 'The Noble Game of Chess') in 1737, which introduced algebraic chess notation in an almost fully developed form before the now obsolete descriptive chess notation evolved. His name is also attached to Stamma's mate, which is a rather rare checkmate.

Take a look at the position above (white to move) and note that black is just one move away from enforcing a checkmate. Now, here's the challenge: can you come up with a forced sequence of 8 moves that leads to a checkmate for white?
 
You can post your answer (preferably in algebraic chess notation) as a comment below.

Lets see how many of you can solve this correctly. All the best!

Dominating Set in a Graph

Here is a nice little problem in graph theory that was posed to me recently (by Swagato) -

A dominating set of an undirected graph is a set of vertices $U$ such that every vertex in $V - U$ has at least one neighbour in $U$. Now, in an undirected graph $G = (V,E)$ having minimum degree $d$, if $(V_1, V_2)$ be a cut of size less than $d$, then prove that every dominating set of $G$ has a non-null intersection with both $V_1$ and $V_2$. [Note: size of a cut = number of cross edges]


My proof follows -

Let $|V| = v$, $|V_1| = v_1$ and $|V_2| = v_2$.
Without loss of generality, we can assume that $v_1 \leq v_2$.

Also, its easy to see that we must have $v_1 > 1$, because otherwise, if we have $v_1 = 1$, then all the edges incident to the single vertex belonging to $V_1$ cross the cut $(V_1, V_2)$. The minimum degree of the graph $G$ being $d$, there has to be at least $d$ edges incident to this solitary vertex belonging to $V_1$, which in turn implies that there has to be at least $d$ edges crossing the cut. However, this directly contradicts the fact that the cut $(V_1, V_2)$ has size less than $d$.

Now, since the graph $G$ has minimum degree $d$, each vertex $u \in V_1$ must have at least $d$ edges incident to it, out of which a maximum of $v_1-1$ edges can have a vertex also belonging to $V_1$ as its other endpoint. Thus, each vertex $u \in V_1$ must contribute at least $d-(v_1-1)$ cross edges to the cut $(V_1, V_2)$, which means that the size of the cut has to be at least $v_1.(d-(v_1-1))$. However, we already know that the size of the cut is strictly less than $d$. Combining the above two facts, we get:
$\begin{align} v_1.(d-(v_1-1)) < d &\implies d.(v_1-1) < v_1.(v_1-1) \\\\                                     &\implies d < v_1 \hspace{44mm} \hbox{[ since $v_1 > 1$ ]} \end{align}$
This implies that the size of the cut has to be strictly less than $v_1$.

Let $U$ be any dominating set in the graph $G$.

If possible, let us assume that $U \cap V_1 = \emptyset$, which implies that $U \subseteq V_2$. Going by the definition of dominating set, each vertex $u \in V_1$ must be adjacent to at least one vertex belonging to $U$. Since $U \subseteq V_2$, this implies that each vertex $u \in V_1$ must be contributing at least one cross edge to the cut $(V_1, V_2)$. Thus, the size of the cut must be at least $v_1$, which leads to a contradiction.

Again, if possible, let us assume that $U \cap V_2 = \emptyset$, which implies that $U \subseteq V_1$. Going by the definition of dominating set, each vertex $u \in V_2$ must be adjacent to at least one vertex belonging to $U$. Since $U \subseteq V_1$, this implies that each vertex $u \in V_2$ must be contributing at least one cross edge to the cut $(V_1, V_2)$. Thus, the size of the cut must be at least $v_2$, and hence at least $v_1$, which leads to a contradiction.

Since both our assumptions $U \cap V_1 = \emptyset$ and $U \cap V_2 = \emptyset$ lead to contradictions, any dominating set in the graph $G$ must have a non-null intersection with both both $V_1$ and $V_2$. Hence proved.

Bangla Kobita - 1

গগনপটে রক্তাক্ত মেঘের আনাগোনা;
কালসিটে পড়া চোখে সূর্যটাও আনমনা।
জীবনের আতিশয্যে ধুঁকছে আজ প্রাণ;
সভ্যতার গরিমা আজ হয়ে আসে ম্লান।

আজ মানুষের ধমনীতে মিশে গেছে প্রবল এক বিষ;
স্বার্থের চীত্কারে ডুবে যায় বিবেকের ফিসফিস!
দেহের কারাগারে রুদ্ধ যত অশান্ত মানবাত্মা;
আত্মমগ্নতার এ যুগে সাহচর্য্যও বেপাত্তা!

Mind Warp

Harken back to those sleepless nights-
When reality fades and conscience bites;
When surreal thoughts begin to take hold
And distort our vision of the world manifold;
When we begin to realize the bitter truth,
In the grip of desires both foul and uncouth;
When the wind brings back the eternal pain;
When the universe threatens to lie still again!
In those moments, before we come around,
Germinate the seeds of ideas profound!

The Song of the Road

Standing still at a crossroad in my life,
I find myself unable to choose a way;
Balancing somehow on the edge of a knife,
I pray to survive just one more day;
Recklessly entering the dragon’s lair,
I try to think of a reason to stay.
Stumbling along, sans any verve or flair,
I still keep enjoying life while I may!

Yet another blogger strolls into cyberspace

Hello! So, here I am - yet another blogger starting off his journey on cyberspace. Finally decided it was time for me to jump on to the blogging bandwagon. This decision was probably inevitable given the number of friends I have who maintain such excellent blogs. It was just a matter of overcoming my characteristic laziness (ল্যাদ) and getting down to creating a blog of my own. Anyway, now that I've finally entered the fray as well, I guess they'll soon be facing some stiff competition.

Before starting off, it is my moral responsibility to convey a small word of caution to you all. As the name of the blog suggests, I will be pretty much writing about any random thing that catches my fancy. So, I guess you should be prepared for quite an eclectic mishmash - starting from amateurish attempts at poetry to geeky discussions regarding interesting problems in theoretical computer science; from passionate eulogies to tips on fitness and bodybuilding; from an occasional article or two analyzing a brilliant strategy employed by some grandmaster in chess to philosophical meanderings pondering over the meaning of life and the universe - you can never be sure of what you might come across here!

Anyway, now I have blabbered long enough for this to qualify as my first blog post. I sincerely hope that, in the days to come, you have as much fun reading this blog as I will surely be having while writing it. Ciao!