tag:blogger.com,1999:blog-63282431161420015052023-11-16T19:28:06.533+05:30Psychotic RamblingsPritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.comBlogger42125tag:blogger.com,1999:blog-6328243116142001505.post-38208173932917557602016-08-28T14:45:00.000+05:302016-08-28T14:51:22.698+05:30The Whole Purpose of Education<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
For most of us, the first image that is conjured up in our minds upon hearing the phrase ‘educated’ is probably that of a studious, bespectacled guy who holds at least a post-graduate degree in his chosen field. Many of us might go on further to speculate that this figment of our imagination probably epitomized being a model student during his school and college days - always turning in his assignments on time, being the first to answer questions in class, and topping every god-damned examination! He has diligently hoarded up knowledge over the years, which he applies rather well In his professional sphere, and most likely gets paid handsomely for it too. However, the question we need to ask ourselves is: while our imaginary friend is no doubt a highly respectable citizen and deserves every bit of the success he has worked hard to achieve, does all that automatically entitle him to be called ‘educated’? In case you are tempted to answer ‘yes’ to that, then I would definitely beg to differ with you.<br />
<br />
Firstly, having a degree and being successful professionally is not, and should never be the criteria for judging how well educated a person is. After all, whom would you consider more educated - a street urchin who picks up a plastic wrapper off the street and deposits it into the nearest trash can, or the high-profile corporate magnate who just chucked it out of the window of his swanky sports car? The latter is almost sure to be more knowledgeable in most respects - after all, he probably had access to better schooling and holds a professional degree - but he is just too engrossed in pursuing his materialistic dreams in order to be a responsible citizen; in my opinion, this makes him quite ill-educated, despite paradoxically having a greater amount of knowledge at his fingertips! On the other hand, the street urchin, despite his rather limited exposure to any formal schooling, has successfully assimilated the lesson imparted to him regarding his responsibilities as a citizen, and crucially, he decides to act upon it and performs his civic duties when the opportunity presents itself. That, I believe, is one of the hallmarks of being a truly educated person - when you learn to think beyond your own narrow circle of existence, and apply whatever knowledge you have acquired for the greater good of the society that you are a part of. This has been expressed brilliantly by Sydney J. Harris through the following metaphor: "Most people are mirrors, reflecting the moods and emotions of the times, but few are windows, bringing light to bear on the dark corners where troubles fester. The whole purpose of education is to turn mirrors into windows.”<br />
<div style="text-align: left;">
<span style="font-family: "georgia" , "times new roman" , serif;"><b style="font-weight: normal;"><br /></b>
</span></div>
Another intrinsic quality that marks out the truly educated is their insatiable curiosity and thirst for knowledge; they come to realize how vast the boundless ocean of knowledge really is, and how little of it they have actually explored. No one could have put it more aptly than the legendary Socrates when he said: “I am the wisest man alive, for I know one thing, and that is that I know nothing.” This constant inner drive to keep learning and growing is an essential character trait for a person to qualify as ‘educated’.<br />
<br />
A proper education not only makes a man strive to constantly update himself, but it also teaches him to accept every new bit of knowledge only after rigorous verification and cross validation. This is especially relevant in the light of today’s educational system which tends to encourage rote learning by not providing enough incentives for students to question deeply what is being taught. This is quite disturbing, since a society which pushes men to merely hoard existing knowledge, without making any attempts to refine or add to it, is bound to stagnate sooner rather than later. The constant progress of human civilization down the ages has always depended on our ability to push the boundaries of existing knowledge, which ultimately leads to the creation of new technologies that benefit society as a whole. But the main impetus towards this expansion of knowledge has to come from the students belonging to the new generation, who must be taught to cultivate the habit of questioning ferociously before accepting any new piece of knowledge. For the sake of mankind’s progress, they simply cannot afford to be docile and accept calmly every new fact or solution that is thrown at them by their teachers; instead, we must strive to create an environment that promotes healthy debate in the classroom and encourages students to offer alternative solutions. For that is what education is truly about: it was never meant to be a one-way communication channel for passing down knowledge from a teacher to a student; rather, it was designed to be a two-way interaction that enriches and refines the knowledge of both the teacher and the student!</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com1tag:blogger.com,1999:blog-6328243116142001505.post-59363660613504276832016-03-04T20:07:00.001+05:302016-03-04T20:08:02.084+05:30An interesting application of the pigeonhole principle<div dir="ltr" style="text-align: left;" trbidi="on">
<b><i>Question:</i></b><br />
Suppose 2016 points of the circumference of a circle are coloured red and the remaining points are coloured blue. Given any natural number $n \geq 3$, prove that there is a regular n-sided polygon all of whose vertices are blue. <i><span style="color: red;">(<b>Source: INMO 2016</b>)</span></i><br />
<i><br /></i>
<b><i>Solution:</i></b><br />
<div>
<div>
Consider a regular $(2017 \times n)$-gon on the circle, say with vertices $A_1, A_2, A_3,\dots, A_{2017 \times n}$. For each $j$, such that $1 \leq j \leq 2017$, consider the set of points $\{A_k : k \equiv j \mod 2017\}$. Note that these are the vertices of a regular $n$-gon, say $S_j$. Thus, we get 2017 regular $n$-gons: $S_1, S_2,\dots, S_{2017}$. Since there are only 2016 red points on the circumference, by pigeonhole principle there must be at least one $n$-gon among these 2017 which does not contain any red vertex. But then, all the vertices of this regular $n$-gon must be blue. Hence proved.</div>
</div>
<div>
<br /></div>
</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com5tag:blogger.com,1999:blog-6328243116142001505.post-91264251947154693122016-03-03T14:03:00.002+05:302016-03-03T18:29:24.941+05:30Which one is greater - $e^{\pi}$ or $\pi^{e}$?<div dir="ltr" style="text-align: left;" trbidi="on">
Recall that: $ e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots $<br />
<br />
Therefore, $ \forall x > 0 $, $ e^x > 1 + x $. <br />
<br />
Substituting $x = \frac{\pi}{e} - 1$ in the above inequality, we get:<br />
<br />
$ e^{\frac{\pi}{e} - 1} > \frac{\pi}{e}<br />
\implies e^{\frac{\pi}{e}} > \pi<br />
\implies e^{\pi} > \pi^{e} $</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com1tag:blogger.com,1999:blog-6328243116142001505.post-3811331080680680122016-03-01T17:11:00.000+05:302016-03-01T17:38:02.378+05:30Addiction<div dir="ltr" style="text-align: left;" trbidi="on">
His mind was being invaded, and he was powerless to resist!<br />
Where once resided only dry logic, rationality and offensive practicality,<br />
A single innocent face started making its presence felt -<br />
Never deserting his thoughts for even a single moment in the day.<br />
<br />
Like a cancerous growth, the image kept spreading throughout his consciousness;<br />
Day by day it expanded, taking up more and more space in his mind,<br />
And pushing out every other thought till they were left tottering on the brink -<br />
Dangling at the edge of the precipice by one last tenuous thread of reason.<br />
Ultimately, it evolved into a burning passion that threatened to consume him -<br />
Consume him and the entire universe of his existence in one raging inferno!<br />
<br />
He was at a total loss to figure out what was happening to him;<br />
The gears and cogs of his desperate mind whirred uselessly, and then fell silent;<br />
But he was no closer to finding an explanation, and felt himself drowning in utter confusion!<br />
<br />
Initially, he fought hard against this invasion -<br />
Chided himself for this inexplicable madness,<br />
Rebuked himself for this illogical obsession,<br />
Scoffed at himself for chasing daydreams and fantasies!<br />
<br />
Yet, little by little, he found himself unable to resist;<br />
Till finally he was forced to abandon his ineffectual struggles and give in.<br />
And then, he was surprised to find himself relishing this strange alien sensation,<br />
Though he knew not what it was, nor could he find a name for it!<br />
<br />
However, as She slowly poisoned the cold, terse rationalist to death,<br />
And freed the poet long imprisoned in a deep, dark corner of his mind,<br />
Realization dawned at last inside his half-paralyzed brain;<br />
Realization of what he had become:<br />
A hopeless addict, full of delusions!<br />
And She? His intoxication!<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com1tag:blogger.com,1999:blog-6328243116142001505.post-4817967589195255302016-02-05T23:15:00.000+05:302016-02-05T23:15:46.689+05:30Vitriol<div dir="ltr" style="text-align: left;" trbidi="on">
Let the darkness engulf me,<br />
Please don't light the lamp.<br />
No need to give me shelter;<br />
I'm better off being a tramp.<br />
<br />
I've learnt to endure my thirst;<br />
To quench it, please don't bother.<br />
Just learn to save yourself first-<br />
There's no point sinking together!<br />
<br />
Inflict more pain on me,<br />
Put aside all bonhomie;<br />
Pour vitriol in my heart-<br />
Just tear my world apart!<br />
<br />
<br />
<br /></div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com3tag:blogger.com,1999:blog-6328243116142001505.post-80215291001533207902016-02-01T00:49:00.000+05:302016-02-01T00:49:15.919+05:30Nevermore?<div dir="ltr" style="text-align: left;" trbidi="on">
Shall we never again sit together on the rocks by the sea -<br />
Waves punctuating the silence, while your eyes speak to me?<br />
Shall we never again take a stroll together in the rain -<br />
With your hand in my hand, and happiness numbing my brain?<br />
Shall we never again sit and talk the entire night away -<br />
Losing all track of time till we see the dawn of a new day?<br />
Won’t you ever come ? Won’t you join me again?<br />
Won’t you come to end my solitude and my pain?<br />
<br />
Will I never more experience the warmth of your embrace -<br />
Or get to inhale the sweet scent of your hair on my face?<br />
Will you never more help me find peace in times of strife -<br />
With your magic smile will you never more light up my life?<br />
Won’t you ever come and end this long, torturous wait?<br />
Won’t you come to restore my belief in fairness of fate?</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com1tag:blogger.com,1999:blog-6328243116142001505.post-26589603451641712532016-01-05T12:56:00.003+05:302016-01-05T12:56:54.216+05:30When the Lights Go Out<div dir="ltr" style="text-align: left;" trbidi="on">
As the floodgates snap open,<br />
And the memories rush by,<br />
I fight to hold back the tears -<br />
Try not to cry!<br />
<br />
Toss and turn,<br />
Rage and burn,<br />
Till you're too numb to feel the pain!<br />
Toss and turn,<br />
Rage and burn,<br />
Until weariness takes you again!<br />
<br />
As the veil of courage flutters,<br />
And old fears come crawling out,<br />
I fight to master my senses -<br />
Try not to shout!<br />
<br />
Toss and turn,<br />
Rage and burn,<br />
Till you're too numb to feel the pain!<br />
Toss and turn,<br />
Rage and burn,<br />
Until weariness takes you again!<br />
<br />
As steely resolve wavers,<br />
And the doubts start to whisper,<br />
I fight to regain control -<br />
Try not to surrender!<br />
<br />
Toss and turn,<br />
Rage and burn,<br />
Till you're too numb to feel the pain!<br />
Toss and turn,<br />
Rage and burn,<br />
Until weariness takes you again!</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-22529517818321456272015-12-17T03:09:00.002+05:302015-12-17T03:10:17.559+05:30Someday ...<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
I'll meet you someday<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>Somewhere on this earth;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>Then my life it will be<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>Full of joy and mirth!<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>When that day will come<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>I cannot just yet see-<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>But I know that, one day,<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>You will come to me.<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>I'll meet you someday<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>Somewhere along the way;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>I will see you smile,<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>And that will make my day!<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>When that day will come<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>I cannot just yet see-<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>But I know that, one day,<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>You will come to me.<br />
<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>I'll meet you someday<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>While I'm still in pain;<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>You'll make me believe<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>In the magic of love again!<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>When that day will come<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>I cannot just yet see-<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>But I know that, one day,<br />
<span class="Apple-tab-span" style="white-space: pre;"> </span>You will come to me.</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-6753150873672270792015-12-09T14:33:00.001+05:302015-12-09T14:33:15.955+05:30Farewell<div dir="ltr" style="text-align: left;" trbidi="on">
The stars hid themselves in the cloudy dusk sky,<br />
As I finished saying all that I had to say.<br />
<br />
Perhaps you didn't pay any heed -<br />
Maybe that's why you could bid farewell so easily!<br />
<br />
I recalled the last time I had tried reading your eyes<br />
And you steadfastly looked down to avoid my gaze -<br />
The darkness of dusk had effectively veiled my mute pain then!<br />
<br />
But now the clouds broke forth,<br />
And the air resonated with the sound of the incessant downpour.<br />
<br />
Shall we ever recreate this evening again?<br />
Alas, not in this lifetime I believe!</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-56245261890059138062014-04-21T00:56:00.002+05:302014-04-21T03:11:47.237+05:30Chess Puzzle - 10<div dir="ltr" style="text-align: left;" trbidi="on">
Hi friends! I'm finally adding a new chess puzzle to my blog after a pretty long hiatus. So, it is time to put on your thinking caps once again. Look carefully at the position (black to move) below:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhb_jh-tRDM9nYrD_zUUrlDjU3B6HeIhx-GXrVB9k0EY0QJWX1l4iCMRJuL1L4rRQwKRpdaJBXKhQpn8N8O4ZhE1DE0gW1qr5h8KQKXb5RXVmGnUXdHP3x-0Rw7jj_hDWQlnZoNaL26ueo/s1600/Screenshot.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhb_jh-tRDM9nYrD_zUUrlDjU3B6HeIhx-GXrVB9k0EY0QJWX1l4iCMRJuL1L4rRQwKRpdaJBXKhQpn8N8O4ZhE1DE0gW1qr5h8KQKXb5RXVmGnUXdHP3x-0Rw7jj_hDWQlnZoNaL26ueo/s1600/Screenshot.png" height="400" width="397" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
It took me a really really long time to figure out how black can try to force a mate in 3 moves from here. (Note that the mate itself may not be unstoppable, but white will have to end up sacrificing a significant amount of material in order to counter the immediate threat.) Can you do better and spot the sequence quickly?</div>
<br />
If you think you've got it, please do post your answer as a comment below...</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-62400795399751644922013-12-20T00:10:00.002+05:302013-12-20T00:11:18.725+05:30Chess Puzzle - 9<div dir="ltr" style="text-align: left;" trbidi="on">
Carefully analyze the chess position below:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhCPI6RzYLz7aRgp1amoHqlJy0Y6KccJOkRk0tX0noJxu2_klrKBdhG8TiZAvPoPPJIZt8h5BRE1Xu8An2q0b8nD-ecUgvnNgkUspqFud4jYEnUbpRTAJg1FJu3cuxdDOYn98r5Bz9xb8k/s1600/Screenshot.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="398" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhCPI6RzYLz7aRgp1amoHqlJy0Y6KccJOkRk0tX0noJxu2_klrKBdhG8TiZAvPoPPJIZt8h5BRE1Xu8An2q0b8nD-ecUgvnNgkUspqFud4jYEnUbpRTAJg1FJu3cuxdDOYn98r5Bz9xb8k/s400/Screenshot.png" width="400" /></a></div>
<br />
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?<br />
<br />
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! </div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com4tag:blogger.com,1999:blog-6328243116142001505.post-75515694261553089882013-12-18T04:24:00.002+05:302013-12-18T04:25:42.676+05:30Chess Puzzle - 8<div dir="ltr" style="text-align: left;" trbidi="on">
After a long hiatus, I'm finally posting a new chess puzzle on my blog.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiC1W0Io6cdaFLVJiR9FaTFeFuiKnAXofEvJoJ4cKw2Rw5xJ69H5J-13KUHcgUoYPA3jkCDHFzE3h9uXsg7cQ0NZCt1IsgM1VQz95_oMylayHUn2VQIHu6IKfL_ykTOcgjJTu0E-nE0oMc/s1600/Screenshot.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiC1W0Io6cdaFLVJiR9FaTFeFuiKnAXofEvJoJ4cKw2Rw5xJ69H5J-13KUHcgUoYPA3jkCDHFzE3h9uXsg7cQ0NZCt1IsgM1VQz95_oMylayHUn2VQIHu6IKfL_ykTOcgjJTu0E-nE0oMc/s400/Screenshot.png" width="398" /> </a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
Looking at the position above, can you find the sequence of moves that white needs to play in order to enforce a checkmate?<br />
<br />
As usual, I will be waiting for your answers (hopefully in algebraic notation) to be posted in the comments section. Cheers!</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com5tag:blogger.com,1999:blog-6328243116142001505.post-25792523429120888402013-11-04T03:30:00.000+05:302013-11-04T03:30:35.502+05:30Twin Primes and Prime Triples<div dir="ltr" style="text-align: left;" trbidi="on">
A twin prime is a <a href="http://en.wikipedia.org/wiki/Prime_number">prime number</a> 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 <a href="http://en.wikipedia.org/wiki/Prime_number_theorem">prime number theorem</a>, which states that the "average gap" between primes less than $n$ is $log(n)$.<br />
<div>
<br /></div>
The twin prime conjecture, which postulates that there exist infinitely many twin primes, has been one of the great open questions in <a href="http://en.wikipedia.org/wiki/Number_theory">number theory</a> for many years. In 1849 <a href="http://en.wikipedia.org/wiki/Alphonse_de_Polignac">de Polignac</a> made the more <a href="http://en.wikipedia.org/wiki/De_Polignac%27s_conjecture">general conjecture</a> 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.<br />
<div>
<br /></div>
<div>
The Hardy–Littlewood conjecture (named after <a href="http://en.wikipedia.org/wiki/G._H._Hardy">G. H. Hardy</a> and <a href="http://en.wikipedia.org/wiki/John_Edensor_Littlewood">John Littlewood</a>) is a generalization of the twin prime conjecture. It is concerned with the distribution of <a href="http://en.wikipedia.org/wiki/Prime_constellation">prime constellations</a>, including twin primes, in analogy to the <a href="http://en.wikipedia.org/wiki/Prime_number_theorem">prime number theorem</a>.<br />
<div>
<br /></div>
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:<br />
<div>
$(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), \dots $</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
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 -</div>
<div>
<br /></div>
<div>
<div>
Let us assume, for the sake of argument, that there exists another prime triple apart from 3,5,7.</div>
<div>
Also, let $p$, where $p>3$, denote the smallest prime which is a part of that triple.</div>
<div>
Then, clearly, this prime triple consists of the three integers $p$, $p+2$ and $p+4$.</div>
<div>
<br /></div>
<div>
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 - </div>
<div>
<br /></div>
<div>
Case 1: The integer $p$ can be expressed in the form $3k$, where $k$ is an integer.</div>
<div>
In this case, the integer $p=3k$ is divisible by 3. </div>
<div>
<br /></div>
<div>
Case 2: The integer $p$ can be expressed in the form $3k+1$, where $k$ is an integer.</div>
<div>
In this case, the integer $p+2=3k+3=3(k+1)$ is divisible by 3. </div>
<div>
<br /></div>
<div>
Case 3: The integer $p$ can be expressed in the form $3k+2$, where $k$ is an integer.</div>
<div>
In this case, the integer $p+4=3k+6=3(k+2)$ is divisible by 3. </div>
<div>
<br /></div>
<div>
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.</div>
<div>
<br /></div>
<div>
Hence, we have proved that the only prime triple is 3,5,7.</div>
</div>
<div>
<br /></div>
</div>
</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-39063756642524673472013-10-08T04:55:00.001+05:302013-10-08T04:55:39.858+05:30A Simple Bijection between Even and Odd Subsets<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
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-<br />
<br />
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\}$.<br />
<br />
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. </div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-4766650422814750712013-10-08T04:11:00.000+05:302013-10-10T03:19:22.794+05:30An Irrational Raised to the Power of an Irrational - Can it be Rational?<div dir="ltr" style="text-align: left;" trbidi="on">
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?<br />
<div>
<br /></div>
<div>
The answer, rather surprisingly, is YES. </div>
<div>
<br />
And here is a classic proof to establish the fact beyond all doubt -</div>
<div>
<br /></div>
<div>
Let us consider the irrational numbers $\sqrt{2}$ and $\sqrt{3}$.</div>
<div>
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.</div>
<div>
If the number $\sqrt{3}^{\sqrt{2}}$ is rational, then we are already successful in proving our claim.</div>
<div>
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.</div>
<div>
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. </div>
<div>
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.<br />
<br />
<br />
Notice that the above proof, attributed to Dov Jarden, is <i>non-constructive</i> 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}}$.<br />
<br />
We know that $\sqrt{3}$ is irrational. Let us convince ourselves that $\log_{3}{4}$ is also irrational.<br />
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:<br />
$$ \log_{3}{4} = \frac{p}{q} \Leftrightarrow 3^{\frac{p}{q}} = 4 \Leftrightarrow 3^{p} = 4^{q} $$<br />
which is clearly a contradiction, since $3^p$ is odd while $4^q$ is even. Hence, the number $\log_{3}{4}$ must be irrational.<br />
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.<br />
<br />
<br />
<br /></div>
</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com1tag:blogger.com,1999:blog-6328243116142001505.post-31103505176549085462013-10-08T03:22:00.000+05:302013-10-08T03:22:41.338+05:30Product of k Consecutive Numbers is Divisible by k!<div dir="ltr" style="text-align: left;" trbidi="on">
<span class="Apple-style-span" style="color: #444444; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif;"><span class="Apple-style-span" style="font-size: 14px; line-height: 21px;"></span></span><br />
Suppose $P$ is the product of $k$ consecutive integers, where $k \geq 1$. <br />
Then, $k!$ divides $P$ .<br />
<br />
<br />
<i><u>Proof 1 -</u></i><br />
<div>
<i><u><br /></u></i>Let $P$ be the product of $k$ consecutive integers from $n+1$ up to $n+k$, so that we have:<br />
<div>
$$ P = (n+1)(n+2)...(n+k) = \frac{(n+k)!}{n!} $$</div>
<div>
Now, we know that the power of any prime $p$ in $k!$ is given by the following finite sum:</div>
<div>
$$ \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{k}{p^m} \right\rfloor} $$</div>
<div>
Therefore, the power of any prime $p$ in the product $P$ is given by:</div>
$$ \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n+k}{p^m} \right\rfloor}<br />
- \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n}{p^m} \right\rfloor} $$<br />
Since $ \forall p,q,r \in \mathbb{Z}^{+}: \left\lfloor \frac{p+q}{r} \right\rfloor \geq <br />
\left\lfloor \frac{p}{r} \right\rfloor + \left\lfloor \frac{q}{r} \right\rfloor $, we must have:</div>
$$ \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n+k}{p^m} \right\rfloor}<br />
- \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n}{p^m} \right\rfloor} <br />
\geq \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{k}{p^m} \right\rfloor} $$<br />
<div>
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$.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<i><u>Proof 2 -</u></i><br />
<div>
<i><u><br /></u></i>Let $P$ be the product of $k$ consecutive integers from $n+1$ up to $n+k$. So, we have:<br />
$ \begin{aligned}<br />
\hspace{4cm} P & = (n+1)(n+2)...(n+k) \\<br />
& = \frac{(n+k)!}{n!} \\<br />
& = k! \frac{(n+k)!}{n!k!} \\<br />
& = k! \binom{n+k}{k}<br />
\end{aligned} $</div>
</div>
<div>
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$.</div>
</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-60881739593725210352013-10-08T03:11:00.000+05:302013-10-08T03:11:20.098+05:30Chess Puzzle - 7<div dir="ltr" style="text-align: left;" trbidi="on">
The following position below is taken from a game between the legendary Russian grandmaster <a href="http://en.wikipedia.org/wiki/Garry_Kasparov">Garry Kasparov</a>, considered by many to be the greatest ever chess player in the world, and his trainer Aleksander Nikitin in Moscow in 1981.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh4p8KoTwsSx_Lpnk47j-CnA5hyphenhyphenl6il7V4Z0ISupux2ZfEO3lES8eVMy7BnlVy691thNKHP7hQ8vsvytATptobv0KlCeG_uhrDxLOn7Iav_8x8eAdpoIpeDg0xj0Cee7vxfEZ6CpALk3zE/s1600/chess.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh4p8KoTwsSx_Lpnk47j-CnA5hyphenhyphenl6il7V4Z0ISupux2ZfEO3lES8eVMy7BnlVy691thNKHP7hQ8vsvytATptobv0KlCeG_uhrDxLOn7Iav_8x8eAdpoIpeDg0xj0Cee7vxfEZ6CpALk3zE/s400/chess.png" width="395" /></a></div>
<span class="Apple-style-span" style="font-family: sans-serif; font-size: 13px; line-height: 19px;"><br /></span>
The position above (black to move) developed after 39 moves in the game that started off with the <a href="http://www.chessgames.com/perl/chessopening?eco=B44">B44</a> 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!<br />
<span class="Apple-style-span" style="font-family: sans-serif; font-size: 13px; line-height: 19px;"><br /></span>
</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com3tag:blogger.com,1999:blog-6328243116142001505.post-91867716322096432422013-10-08T02:02:00.001+05:302013-10-08T02:02:59.894+05:30Finding GCD<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
Today, I am sharing a little problem from number theory, which is stated as: <br />
<br />
Let $a = 7k + 2$ and $b = 9k - 5$. Then, prove that $gcd(a,b)$ is either 1 or 53.<br />
<br />
<br />
The solution repeatedly makes use of the fact that, if $m > n$, $ gcd(m , n) = gcd(m - n, n) $. It proceeds as follows:<br />
<br />
<span class="Apple-style-span" style="font-size: 14px;"><table><tbody>
<tr><td>$ \begin{aligned} <br />gcd (a,b) & = gcd(7k+2,9k-5) \\<br />& = gcd(7k+2,2k-7) \\ <br />& = gcd(5k+9,2k-7) \\ <br />& = gcd(3k+16,2k-7) \\<br />& = gcd(k+23,2k-7) \\<br />& = gcd(k+23,-53) \\<br />& = gcd(k+23,53)<br />\end{aligned} $</td></tr>
</tbody></table>
</span><br />
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.<br />
<div>
<br /></div>
<div>
<br /></div>
<div>
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 <a href="http://en.wikipedia.org/wiki/Euclidean_algorithm">Euclidean algorithm</a> can be found in Euclid's '<i>Elements'</i> (c. 300 BC), making it one of the oldest numerical algorithms still in common use.</div>
</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-58952376541525743942013-09-28T16:45:00.000+05:302013-09-28T16:45:24.853+05:30Bangla Kobita - 5<div dir="ltr" style="text-align: left;" trbidi="on">
<span class="Apple-style-span" style="font-size: large;">আজ সভ্যতা আমায় করেছে অন্ধ, </span><br />
<span class="Apple-style-span" style="font-size: large;">তবু পাই আমি তাজা রক্তের গন্ধ- </span><br />
<span class="Apple-style-span" style="font-size: large;">ভবিষ্যত্ হোক না মোর যতই ধোঁয়াশা, </span><br />
<span class="Apple-style-span" style="font-size: large;">মেটে না প্রবল এই জীবনপিপাসা</span><span class="Apple-style-span" style="font-size: large;">!</span><br />
<span class="Apple-style-span" style="font-size: large;"><br /></span>
<span class="Apple-style-span" style="font-size: large;">স্পর্শকাতর নয় এই মন-</span><br />
<span class="Apple-style-span" style="font-size: large;">বহু তীর ছুঁয়ে চলে যায়; </span><br />
<span class="Apple-style-span" style="font-size: large;">ক্ষতবিক্ষত প্রতিটা ক্ষণ </span><br />
<span class="Apple-style-span" style="font-size: large;">তবু বারবার মনকে কাঁদায়! </span></div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-34504956078187640872013-09-22T13:50:00.004+05:302013-09-22T13:50:44.187+05:30Chess Puzzle - 6<div dir="ltr" style="text-align: left;" trbidi="on">
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!<br />
<div style="text-align: left;">
</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivtgYJ_tvG8rZMif-qgJ6VBe424aKgDYn3iLCyVNzzG53x7UsbiW3PA8LqBdfsYYdrVadA3bGxVAbeCxxA6XIBdlCPP3ILst0IchjpTqgF6fG7NJDL6fZdMgIBYCQJ5ljELyi50XVLlco/s1600/chess.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivtgYJ_tvG8rZMif-qgJ6VBe424aKgDYn3iLCyVNzzG53x7UsbiW3PA8LqBdfsYYdrVadA3bGxVAbeCxxA6XIBdlCPP3ILst0IchjpTqgF6fG7NJDL6fZdMgIBYCQJ5ljELyi50XVLlco/s400/chess.png" width="396" /></a></div>
<br />
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!<br />
<br />
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?<br />
<br />
So friends, put on your thinking caps and put those grey cells to good use!<br />
<br />
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.</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com4tag:blogger.com,1999:blog-6328243116142001505.post-61858647863171654452013-09-22T13:50:00.002+05:302013-09-22T13:50:55.360+05:30Bangla Kobita - 4<div dir="ltr" style="text-align: left;" trbidi="on">
<span class="Apple-style-span" style="font-size: large;">ভ্রষ্ট চেতনার ভীড়ে, </span><br />
<span class="Apple-style-span" style="font-size: large;">নৃশংসতার নীড়ে,</span><br />
<span class="Apple-style-span" style="font-size: large;">বন্ধু হেঁটো সাবধানে- </span><br />
<span class="Apple-style-span" style="font-size: large;">বিবেকের তত্বাবধানে। </span><br />
<span class="Apple-style-span" style="font-size: large;"><br /></span>
<span class="Apple-style-span" style="font-size: large;">ঝলসে যাওয়া যত সুখ </span><br />
<span class="Apple-style-span" style="font-size: large;">বেদনায় হয়েছে মূক; </span><br />
<span class="Apple-style-span" style="font-size: large;">ভেঙ্গে যায় বুক </span><br />
<span class="Apple-style-span" style="font-size: large;">তবু কেন বুজে মুখ?</span><br />
<span class="Apple-style-span" style="font-size: large;"><br /></span>
<span class="Apple-style-span" style="font-size: large;">শোকার্ত পাগলা হাওয়া </span><br />
<span class="Apple-style-span" style="font-size: large;">বাদলকে করে চলে ধাওয়া; </span><br />
<span class="Apple-style-span" style="font-size: large;">জীবন জুড়ে শুধু চাওয়া </span><br />
<span class="Apple-style-span" style="font-size: large;">আর হতাশাদায়ক না-পাওয়া।</span><br />
<span class="Apple-style-span" style="font-size: large;"><br /></span>
<span class="Apple-style-span" style="font-size: large;">অপরিপূর্ণতা সাথী নিত্যদিন,</span><br />
<span class="Apple-style-span" style="font-size: large;">সংসারসুখ তবু রয় অমলিন;</span><br />
<span class="Apple-style-span" style="font-size: large;">বাইরের রূপটা তো সর্বদা সুশীল-</span><br />
<span class="Apple-style-span" style="font-size: large;">জ্বলছে সংগ্রামের আগুন অন্ত:শীল! </span></div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-1273856666533527002013-09-19T02:01:00.000+05:302013-09-19T02:01:34.257+05:30Chess Puzzle - 5<div dir="ltr" style="text-align: left;" trbidi="on">
The position given below has been taken from a game in 1894 involving the great Russian chess master <a href="http://en.wikipedia.org/wiki/Mikhail_Chigorin">Mikhail Ivanovich Chigorin</a> (Russian: Михаи́л Ива́нович Чиго́рин).<br />
<br />
The last great player of the <a href="http://en.wikipedia.org/wiki/Romantic_chess">Romantic chess</a> 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 <a href="http://en.wikipedia.org/wiki/Ruy_Lopez">Ruy Lopez</a> (<i>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</i>) and the <a href="http://en.wikipedia.org/wiki/Chigorin_Defence">Chigorin Defence</a> to the <a href="http://en.wikipedia.org/wiki/Queen%27s_Gambit">Queen's Gambit</a> (<i>1.d4 d5 2.c4 Nc6</i>).<br />
<br />
Born in <a href="http://en.wikipedia.org/wiki/Gatchina">Gatchina</a> 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.<br />
<br />
<span class="Apple-style-span" style="font-family: sans-serif; font-size: x-small;"><span class="Apple-style-span" style="line-height: 19px;">T</span></span>hrough his original talent, lively games and prolific teachings, many Russians hail Mikhail Chigorin as the founder of the <a href="http://en.wikipedia.org/wiki/Soviet_Chess_School">Soviet School of Chess</a>. Overshadowed in the 1920s by the exciting new theories of the <a href="http://en.wikipedia.org/wiki/Hypermodernism_(chess)">hypermodern movement</a>, Chigorin's influence nevertheless demands a prominent and permanent place in the Soviet chess hegemony of the 20th century.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwJtV0MqA8Roy53PS7j_dashqZy0NlxbW8lZOr5EQvsKmfoHUGR6re_w1dqnJLak2oBzl6SjQMh-ctHIUPaWoZNlIMu-ka5x0avHzNK1BKDR-FYEbbw8VHzmIrPo22vBM54VcbYmtyqWM/s1600/chess1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwJtV0MqA8Roy53PS7j_dashqZy0NlxbW8lZOr5EQvsKmfoHUGR6re_w1dqnJLak2oBzl6SjQMh-ctHIUPaWoZNlIMu-ka5x0avHzNK1BKDR-FYEbbw8VHzmIrPo22vBM54VcbYmtyqWM/s400/chess1.png" width="395" /></a></div>
<br />
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!<br />
<br /></div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com1tag:blogger.com,1999:blog-6328243116142001505.post-74384569095629671992013-09-18T09:04:00.002+05:302013-09-19T00:47:57.539+05:30Kings in a Tournament<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
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:<br />
<br />
An <i>orientation</i> $\vec{G}$ of a graph $G$ is an assignment of an orientation (direction) to each edge.<br />
<br />
We call the directed edges <i>arcs</i>. 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 <i>tail</i> of the arc and $u$ as the <i>head</i> of the arc.<br />
<br />
The <i>indegree </i>$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 <i>outdegree</i> $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)$.<br />
<br />
The <i>in-neighbourhood </i>$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 <i>out-neighbourhood </i>$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}$.<br />
<br />
In an oriented graph $\vec{G}$, a <i>directed path</i> is a path in which all the edges have the same orientation.<br />
<br />
Any orientation of a complete graph is referred to as a <i>tournament</i>.<br />
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 <i>king</i> 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. <br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjq2uI9-rU0gihwGcMB2mw8gT0VMp4pR5DrgH3wiFtB8FJUE-ve-BH4b2hyphenhyphenuBXrHp3OID8asPn0tsVx4bFxo4kHss-rgmnbylq5ij-PAPu5wNIXlmj0jtm0seXSwaHvH80cnOeH2EjUC8k/s1600/tournament.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="370" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjq2uI9-rU0gihwGcMB2mw8gT0VMp4pR5DrgH3wiFtB8FJUE-ve-BH4b2hyphenhyphenuBXrHp3OID8asPn0tsVx4bFxo4kHss-rgmnbylq5ij-PAPu5wNIXlmj0jtm0seXSwaHvH80cnOeH2EjUC8k/s400/tournament.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Tournament Graph with 5 Vertices having 4 Kings</td></tr>
</tbody></table>
<b><br /></b>
<b>Claim 1. </b>Every tournament $T$ contains at least one king.<br />
<br />
<b>Proof.</b> 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)$.<br />
<br />
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$.<br />
<br />
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.<br />
<br />
<br />
<b>Claim 2. </b>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.<br />
<br />
<b>Proof. </b>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$.<br />
<br />
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.<br />
<br />
<br />
<b>Claim 3. </b>No tournament can have exactly 2 kings.<br />
<br />
<b>Proof. </b>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.<br />
<br /></div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0tag:blogger.com,1999:blog-6328243116142001505.post-36601283750752976582013-09-18T05:34:00.000+05:302013-09-18T09:07:07.794+05:30Chess Puzzle - 4<div dir="ltr" style="text-align: left;" trbidi="on">
In the chess position given below, with white to move, can you spot a mating sequence for white?<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhiTfBOQr9poKHLEM7KupKaIVZOR_t5R_gjUwo4LlGf3wgGdIxYKSi6pqE0Fuzl54wUYjvSP3UIe_O3j4ycg3ej2DKT03Us9QTMlA-U5lbWOij4OJ_v8GFgKWiwYbjd_5q5oWvNLUqqvAM/s1600/Screenshot.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhiTfBOQr9poKHLEM7KupKaIVZOR_t5R_gjUwo4LlGf3wgGdIxYKSi6pqE0Fuzl54wUYjvSP3UIe_O3j4ycg3ej2DKT03Us9QTMlA-U5lbWOij4OJ_v8GFgKWiwYbjd_5q5oWvNLUqqvAM/s400/Screenshot.png" width="398" /></a></div>
<br />
<br />
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!</div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com9tag:blogger.com,1999:blog-6328243116142001505.post-47639678092114678962013-09-18T05:30:00.000+05:302013-09-18T19:25:52.603+05:30Acyclic Orientations of k-Colourable Graphs<div dir="ltr" style="text-align: left;" trbidi="on">
An <i>orientation</i> $\vec{G}$ of a graph $G$ is an assignment of an orientation (direction) to each edge. We call the directed edges <i>arcs</i>. So if the edge $vu$ is oriented from $v$ to $u$, we refer to the resulting directed edge as the arc $(v, u)$.<br />
<br />
A <i>colouring</i> (or more specifically <i>vertex colouring</i>) 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 <i>chromatic number</i>, and is often denoted by $\chi(G)$.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhF69G5FJk5XEt8PZ70maj7FjEV3Bv8Kp9ause44Iwd3CCDNOHL9Nej622xLC76prlG9u-EkgxZIsKjunbtOGxuEG2jOVzutf-WrDZJ6UrTzBxozmZtdBkbnFVBIx6Jh2k3xRLTT2OABNM/s1600/500px-Petersen_graph_3-coloring.svg.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="306" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhF69G5FJk5XEt8PZ70maj7FjEV3Bv8Kp9ause44Iwd3CCDNOHL9Nej622xLC76prlG9u-EkgxZIsKjunbtOGxuEG2jOVzutf-WrDZJ6UrTzBxozmZtdBkbnFVBIx6Jh2k3xRLTT2OABNM/s320/500px-Petersen_graph_3-coloring.svg.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span class="Apple-style-span" style="font-family: sans-serif; font-size: 11px; line-height: 15px;">A vertex colouring of the <a href="http://en.wikipedia.org/wiki/Petersen_graph" style="background-attachment: initial; background-clip: initial; background-color: initial; background-image: none; background-origin: initial; background-position: initial initial; background-repeat: initial initial; color: #0645ad; text-decoration: none;" title="Petersen graph">Petersen graph</a> with 3 colours, the minimum number possible.</span></td></tr>
</tbody></table>
<br />
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.<br />
<br />
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.<br />
<br />
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<br />
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.<br />
<br />
<br />
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.<br />
<br />
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.<br />
<br /></div>
Pritam Bhattacharyahttp://www.blogger.com/profile/04483442729163055796noreply@blogger.com0