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!