More Bijections!

You can imagine that I’m really bored as I’m writing another blog post given I just wrote one yesterday. Anyhow, some more identities, with some more proofs. This post will be one of the most brusque posts I’ve ever written; so yes, you can blame me if you can’t understand parts of the post. (Yes, you may comment and I’ll respond, I promise.)

Behold!

\displaystyle \sum_{i=0}^{n} \dbinom{x}{i} \dbinom{y}{n-i} = \dbinom{x+y}{n}

Assume there is a class of x boys and y girls. (No, you may not assume x = y and that every girl/boy has a boy/girlfriend.) Now, you’re to pick n out of the class to go for a movie. The right hand side simply counts the number as a binomial coefficient without distinguishing between boys and girls. The left hand side, being a sexist, distinguishes between boys and girls, and picks i boys first, and then n-i girls for the picnic. Using the addition principle, the left hand side (sexist sod) counts the number of ways to take a total of n boys and girls for the movie.

Now that you’re bored watching the stupid movie, why not try another combinatorial identity? Yes, this one is a bit tricky. I always like the tricky ones.

\displaystyle \sum_{i=0}^{m} \dbinom{n+i}{i} = \dbinom{n+m+1}{m}

Consider the scenario where you have n +m+1 girls standing in a queue (or a stack or even a list). You are to pick, well, m girls out of the given n+m+1 for another movie this time. Again, the right hand side is the straightforward answer. The left hand side counts the same quantity, evaluated in a slightly complex way. We look at the largest continuous set of girls we’ve selecting starting from the first one. We can select at most m in this continuous string, or none at all. We select the first m-i (note 0 \le i \le m) girls, skip the (m-i+1)^{\mathrm{th}} girl (as we select the longest continuous string), and select the remaining i girls from the remaining n + m + 1 - (m - i) - 1 = n + i (removing the selected the first m-i, and rejected (m-i+1)^{\mathrm{th}} girl). Applying the addition principle on this evaluation simply yields the result.

Football! (And we need a captain this time.)

\displaystyle \sum_{i=0}^{n} i \dbinom{n}{i} = n2^{n-1}

This is one of my favourite identities among those which have a very simple bijective proof. Consider selecting a football team out of n boys with a captain. One way to count the number of possible teams is to select an arbitrarily sized team, and then select the captain out of the chosen ones. The left hand side simply counts this number. Another way to evaluate the same number would be to select the captain first, which can be done in n ways, and then select the remaining team, which can be done in 2^{n-1} ways (as you may either select a player, or reject him). And voila!

Boom! (Just wanted to end this post with a blast.)

PS The promised exercise for my devout readers is to prove the following identity.

\displaystyle \sum_{i=0}^{n} i^2 \dbinom{n}{i} =  n(n+1)2^{n-2}

PPS You might want a goalkeeper on your team to save a goal from the identity above.

Bijections!

Hello, imaginary reader! Long time, no see. It’s okay, I prefer rooks anyway. Now that I’ve started with a lame unoriginal joke you probably didn’t understand, I can continue with the core matter of this post which I’ve wanted to do for a long long (exponential) time. Proving combinatorial identities with bijections! This post is going to be somewhat terse, as that is the point of proving an identity bijectively.

I presume one knows what binomial coefficients mean bijectively, and some basic combinatorial principles like addition and multiplication principle. I’ll be a bit more explanative in the starting few examples, after which I’ll just, well, be lazy and write a few words which should be enough, given sufficient time, for one to understand.

So, here goes.

\displaystyle \sum_{i=0}^{n} \dbinom{n}{i} = 2^n

The left side counts the subsets of size i of a set of size n where i ranges from 0 to n. In particular, the left counts all the subsets of the set in reference by addition principle; whereas the right side counts all the subsets of the set in reference by multiplication principle, as each element of the set has 2 choices, either to be included in a subset, or not.

Moving on.

\displaystyle \sum_{i=0}^{n} (-1)^n \dbinom{n}{i} = 0

Okay, I’ll cheat a bit here. I won’t directly equate the left and right sides of the above identity, but make the “clever” and obvious observation that it is equivalent to proving that the number of odd sized subsets of a set, and the number of even sized subsets of a set are equal. The proof is surprisingly simple. Fix any arbitrary element a from the set, and any arbitrary subset A of the given set. If A contains a, remove a from A to get a new set A' of the opposite parity. If A does not contain a, then add a to A to get a new set A' of the opposite parity. I’ll leave it to you to verify that this gives a bijection between subsets of a set with even parity and subsets of a set with odd parity.

Simple enough.

\displaystyle \dbinom{n-1}{i} + \dbinom{n-1}{i-1} = \dbinom{n}{i}

Let’s play football now! The right hand side simply counts the ways of choosing i players from a total of n for the starting squad. Now, for the left hand side, fix an arbitrary player p. If you pick p, then you’re left with n-1 players and have to pick i-1 out of them. On the other hand, if you don’t pick p, you’re left with n-1 players, and have to pick i out of them. The sum of these two, is the left hand side, and by the addition principle, equal to the number of ways of choosing i players from n, the right hand side, as desired.

And we’re done.

As you know the number of lazy bones I have is 207, I’ll stop right here.

Anyhow, I plan to convert this post into a series of posts on bijective identities, with three identities with bijective proofs, and one identity to be left to be proven by the lovely imaginary readers of my blog. Happy solving!

\displaystyle 2 \dbinom{2n-1}{n} = \dbinom{2n}{n}

Object Copier

Rijul Saini recently handed me a hypothetical scenario equivalent to the following:

Consider two boxes, A and B, each with a door, such that when both the doors of A and B are closed, the contents of A are destroyed, and are replaced by an exact copy of that of B.

Rijul was obviously stuck with considering the applications these boxes could have in real life, unlike me, who always desires to create a paradox, or in the worst case, a strange loop. The motive of this post is to argue against the exist of such boxes even in a (logical) hypothetical world. # All logical worlds are hypothetical.

Firstly, since the contents of B are reproduced in A, A has to be as large as B.

Now assuming that B can fit inside A, we fit B (with a chocolate inside it perhaps) inside A. We close B’s door, and A’s door. Now, the contents of A are (specifically, box B is) destroyed and replaced by the contents of B. But is it really a contradiction? What are the contents of the destroyed box B? One might argue that we’ll just find A empty in the end for box B is destroyed, and there are no contents of box B but void. But the problem with that is that box A calls box B to copy B’s contents to itself. Since box B no longer exists, it’s error 404. Since box B no longer exists, A loses it’s property of being able to copy whatever is present in B for B no longer exists.

To sum it up, if one can fit B inside A, it is possible to reach a paradox. One might argue that the paradox is not intrinsic but rather artificial; but I’d like to point out that most of the paradoxes are created, and emerge solely because the appropriate situation which results in them is thought of, or possibly constructed.

The other case, when one can’t fit B inside A, is far more tedious. Apparently, it’s so tedious that I haven’t been able to come up with a paradox, yet, which would eventually destroy the system and give me immense sadistic pleasure. Nevertheless, I trust that this scenario is much harder to deal with for it’s not immediate that we can call the system on itself like in the previous case by fitting in box B in box A. For now, I’m quite rather unsure whether the system of such boxes will be possible or not, but a paradox eludes my imagination for now.

PS This is a purely recreational blog post supposed to make no sense whatsoever. In the rare event that you find this article sensible, I suggest you book an appointment with your psychiatrist, for the subtle fact that you find this sensible, implies the existence of one.

On a Puzzling Chocolate Bar…

I know I haven’t posted in a while and you all have been mad at me for that. But I know you all are very kind and patient and have been waiting for my next post. And to reward you for your sincerity and probity, I’ll discuss about something we all totally love, chocolate bars.

So, let’s begin with a chocolate bar… and make more out of them. # Yes, I’m gonna share it with you.

You have a regular chocolate bar marked into m x n squares, and you wish to break up the bar into its constituent squares. At each step, you may pick up one piece and break it along any of it’s marked vertical or horizontal lines. Prove that every method finishes in the same number of steps.

I handed this puzzle to several of my friends. After a few minutes, most of them were convinced that (strong) induction was the way to go. But the problem automatically with “obvious” induction was that if one chose to induct on the length, an initial horizontal breaks ruins the dominoes falling down; and inducting of the breadth resulted in the same fall of “fall of dominoes”.

# If you’re not aware of induction, I’ve mentioned a much simpler solution in the last line.

Not many people think beyond the “obvious” variables to induct on. It’s the way we’re taught induction in school. Mostly we’re just given one variable, and a property P, and inducting on the variable to show that the property P is invariant is child’s play. But induction is much “stronger”.

So, following the discussion above, we note that we should be able to induct on a variable which incorporates both the length and the breadth, and decreases after each break. The “obvious” choice now is the sum of the length and breadth.

Now, let me fill in the gaps. We let f(l, b) (= lb – 1) denote the number of breaks required for an l x b chocolate bar. Now, assume that this result holds true for all chocolate bars with the sum of their length and breath being less than m + n. This is our inductive hypothesis. I’ll leave the base case as an exercise.

Now, if our original bar is broken vertically with one length being p and the other m – p, we have the number of steps equal to f(p, n) + f(m – p, n) + 1. Or, if the bar is broken horizontally, with one breadth being q, the other n – q, we have the total number of steps required being f(m, q) + f(m, n – q) + 1. (Note the 1 is added to both because of the initial break.)

Now, it all falls into place with our initial guess of f(l, b) (= lb – 1). Now the question arises where did it pop into place from? I’ll leave that to you too, or maybe you can just see that it is the obvious guess to the recursive relation we’ll obtain assuming the problem is correct.

Another solution, which is simpler in nature, is obtained by considering the number of pieces at each stage. After we break the chocolate once, the number of pieces just goes up by one. And voila, we’re done. # And so am I.

And Yet It Leaks!

AIEEE 2011 was leaked. Skeptics like me do believe that a more deeper conspiracy was involved and the exam being delayed was just a cover. Whatever the case may be, getting a good rank in an exam like AIEEE is an essential step to one’s career, and if one looks at it game theoretically, having the paper in advance will very well increase your payoff provided it’s certain that you can get away with it. To me, it thus makes sense that an exam like AIEEE or even IIT-JEE is leaked for it might be a supposedly important step in one’s career. It’s basic animal (and human) behavior to take advantage of one’s situation and get what is believed to be the best out of it; even though it might be ethically wrong. (Trying really hard not to digress from the main idea of the post to philosophy here.)

In short, it makes complete sense for an exam like AIEEE or IIT-JEE to be leaked, publicly, or otherwise.

There is another not so popular exam, the Regional Mathematical Olympiad, shortened to RMO for convenience.

(If you don’t know about RMO, or any other related Olympiads, click here.)

RMO is what is the first stage towards the prestigious International Mathematical Olympiad, the IMO, what is equivalent to a mathematical Olympics.

RMO is conducted on a much smaller scale with barely ten gross people per region. In my humble opinion, the chances of RMO to be leaked are far less than that of AIEEE or IIT-JEE for first, the exam is not so popular among students; and second, it doesn’t directly provide a free pass to any acceptable university. However, clearing the next round, i.e., Indian National Mathematical Olympiad, INMO, and attending the International Mathematical Olympiad Training Camp, IMOTC, does provide a pass for admission to Indian Statistical Institute, and Chennai Mathematical Institute; both being very prestigious universities of India. Having said that, and keeping in mind the naive Indian culture and tradition, it is not surprising that no one in the my IMOTC batch joined any of the two institutes. The point here is that getting a free pass to CMI or ISI is not the major reason why people even bother appearing for Olympiads; as getting through their respective individual standard admission processes is easier compared to clearing INMO.

Moreover, even if one manages to be selected for the Indian IMO team by bribery, leaks, etc., i.e., where the Indian management, and hence most of the corruption problems, end. It’s highly unlikely that one can manage to get a hold of a single IMO problem before the actual exam, implying that one who hasn’t been selected on pure basis of merit is sure to have an appalling and egregious performance at the IMO.

Moreover, clearing RMO, INMO, and attending IMOTC, in my opinion, will not be considered even half good as just getting a pity rank in AIEEE, whereas a medal at IMO is recognized internationally and a matter of respect and eminence.

So, it seems utterly stupid if someone does indeed make the effort leak the RMO paper, and cause all the useless nuisance for the sincere participants.

And yet it leaks!

The RMO exam was leaked in 2009, 2010, and again in 2011. In 2009, the six problems of RMO, were posted on Yahoo! Answers, and in the subsequent years, on Art of Problem Solving.

The problem? Firstly, it’s bullshit. I mean, it makes no sense at all why the paper is leaking. Secondly, it is a major problem for the sincere participants. The solutions put forward by the authorities, that is a Re-RMO for students getting at least a certain number of marks, is completely ridiculous. What if more than half of the students appearing in the Re-RMO saw the leak, and a considerable number of students deserving didn’t even get the chance to appear in a fair RMO. Moreover, not just being unfair to the students, it destroys the prominence of the Olympiads throughout the nation. It also acts as a barrier to encouraging students to take more interest in Mathematical Olympiads, and thus diminishing our stakes at IMO.

What is being done about the problem? As far as I know, they’re just trying to cure the symptoms and not kill the disease itself, which makes it highly likely that the leak would be repeated for as long as the person doesn’t get bored, for what I believe we’re dealing is with a psychopath who just wants to cause trouble, or maybe someone with a negative IQ. Conducting the RMO again consumes time and effort, and we all tend to be lazy.

What do I think about it? Well, it might seem personal, but I believe CBSE might have a hand in the leaks. Why? CBSE constitutes a different region, and gives out the same paper by the name of Group Mathematical Olympiad, and is held at the same date and time. Why CBSE? For it is the largest of the bodies in involved directly with the first stage of the Mathematical Olympiads in our country.

Do we have a solution to the problem? Yes, find the root of the problem; eradicate it.

Will it be done? No. (We can’t apply fuzzy logic here, I’m sorry.)

For a detailed report on the leak and the superficial action following, click here.

Oh My God!

Er, yes. Philosophy, religion, and spirituality up on my blog, finally!

Before I begin my naive effort, I may point out that the views (after the usual intro) are mine inspired by various sources and some people and mean no offence to whomsoever whatsoever. Moreover, it is further stated that everyone is entitled to consider this post as a joke or complete junk and move on. (Translation: I’ll post some interesting ‘logical’ stuff sooner or later, as always.)

God is mostly perceived as a single omnipotent being who created, manages, and/or destroys the world.

So, what arose this concept of God? Why do we even need a single creator for everything, or multiple creators in some faiths?

Atheists (some, at least) argue that if the God(s) created the universe, who created the God(s). Theists respond by blabbering something about the divinity of God. Atheists, who consider themselves highly logical people ask for proof. And hence begins the never ending fight over the existence of something we can’t even define properly. Many argue that God is just an idea to explain what we don’t understand. The supernatural.

How many people have died in the name of God? Directly or indirectly, organised religion has done far more harm than good. Living in a country like India,  where people are born with a special talent just to do stuff without thought and conscience, its not hard to destroy peace just in the name of God. Rituals! Prayers! And that too with strong public display. For “God’s” sake, what is it that everyone trying to prove? (I’m not against public display of religion or any philosophy if done properly to share knowledge and views, but just the way the popular public displays of rituals, prayers and everything else is done.)

Agnosticism tries to handle the situation with elegance, and states the existence of God is unknown and/or unknowable. Fair enough. At least if everyone were agnostic, we would have avoided many wars, and we would have lived in a over-overpopulated planet. (I’m still in favour of agnosticism over theism or atheism, but it still involves a leap of faith and again fails to clearly give an idea of what actually God is, if there is one, or many.)

Apatheists simply don’t care about God, and argue that even if his existence is proved, it’s irrelevant in this life as God doesn’t intervene in it according to them. The whole question of whether God exists or doesn’t is completely irrelevant.

These are as of yet the most popular beliefs of people I’ve encountered with monotheism and polytheism being highly popular followed atheism, agnosticism and apatheism, in that very order.

Rarely I’ve encountered someone who is spiritual and has a spiritual approach to understanding God or it’s existence. Popular spiritualism believes in monotheism, but the God may or may not be anthropomorphic, that is human like. An additional belief in spiritualism is regarding the spirits of the dead living in a spirit world with the ability to communicate with us in certain ways. It also has a belief in reincarnation, soul, and the purpose of this life to be growing spiritually. Even though this requires a leap of faith for most of the people, this approach is far better as it considers growing spiritually to be one’s religion. Altruism, kindness and peace. That’s what this world needs at the moment.

Another rarely accepted philosophy is that of pantheism. Pantheism is the point of view where the line between universe (everything) and God is blurred. It avoids a personal, anthropomorphic God which created everything. God is everything, the universe.

My take on God is presently a blend of spiritualism and pantheism. I believe that God and energy are isomorphic. And since everything in this universe is just a form of energy, the universe and God are actually just one and the same. I don’t know how one defines praying, but as per my view, praying is just a way, either by thought, chanting, or physical means to manipulate the energy, that is, God. Every thought carries energy with it, and learning how to manipulate this energy for the good is what I believe religion is all about, along with growing spiritually. I’m rather uncertain about reincarnation and spirits, but I’m more of a guy who’ll believe in it, or wants to believe in it.

No matter what is one’s take on God, altruism, empathy, and spiritual development (even without introducing the idea of spirits) should be part of every religion without any idiotic public displays at all.

I think I’ll stop now. That’s enough of clearing my clogged head out!

How Do You Think?

Most of us love a puzzle, tickle our brain a bit, and take a shot at it. But what is it that these puzzles really test? I’ll give an example of a few puzzles, and how (most of the) people tackle them.

Anne went to the market with four baskets to buy some eggs. She, in total, bought 27 eggs, and brought all of them home safely. Each of her basket contained an odd number of eggs. How is it possible?

As soon as one finishes reading the problem, our mind has already made assumptions which make solving the problem a lot harder. The basic fault is modern human brains is that they tend to think discretely and jump to conclusions.

Most of the people I gave this problem to, as I narrated the problem, imagined four identical baskets, and all the eggs present in the basket.

These are the two basic assumptions (almost) everyone I gave this problem to, presumed implicitly.

If one assumes that Anne didn’t bring all the eggs in the baskets, but just some of them, one can easily obtain a solution. Say each basket has 5 eggs, and the rest 7 eggs were in a bag or something.

Now, some versions of the problem specify that all the eggs are carried in the four baskets. In this case, eliminating the assumption that all the baskets are of the same size, one can obtain an elegant solution with three baskets being small containing 9 eggs each, and the three baskets are placed in a larger fourth bucket. Simple, and elegant.

Another related puzzle, which challenges our inability to jump to conclusions, is the following, which I’ll leave as an exercise to you, for it’s a lot easier.

A man and his son are in a car crash. The father is killed and the child is taken to hospital gravely injured. When he gets there, the surgeon says, ‘I can’t operate on this boy – for he is my son!!!’ How can this possibly be?

Well, now that we’re done with jumping to conclusions, another major fault with human intelligence is intuition, or lack of.

Consider a hypothetical cricket match, where we have two bowlers in opposing teams, bowler Alpha, and bowler Beta. In the first innings, Alpha has figures 2 for 43, whilst Beta has to live with 1 for 32. In the second innings, Alpha has figures 4 for 21, and Beta, has figures 6 for 37.

Who was the better bowler in the first innings?

Who was the better bowler in the second innings?

Who was the better bowler throughout the match?

Here, the performance of a bowler is judged upon his average, that is, the lower number of runs per wicket, the better the bowler?

The better bowler, in the first innings was clearly, Alpha. The better bowler, in the second innings too, was Alpha. Now, intuitively, one would assume that if Alpha was better than Beta in the first innings and in the second innings as well, Alpha was better than Beta, throughout the match. This is the point where one realizes that intuition, in the wrong sense, is not that useful as it can be. One can easily calculate that although Alpha has better bowling averages for both the first and second innings, Beta, has an upper hand if the statistics are considered throughout the match.

Another similar problem, which is famous enough that I can call it by Prisoner’s dilemma. The problem can be presented in various forms, but being lazy enough, I’ll copy it right away from Wikipedia, giving you another reason not to read my blog.

Two suspects are arrested by the police. The police have insufficient evidence for a conviction, and, having separated the prisoners, visit each of them to offer the same deal. If one testifies for the prosecution against the other (defects) and the other remains silent (cooperates), the defector goes free and the silent accomplice receives the full one-year sentence. If both remain silent, both prisoners are sentenced to only one month in jail for a minor charge. If each betrays the other, each receives a three-month sentence. Each prisoner must choose to betray the other or to remain silent. Each one is assured that the other would not know about the betrayal before the end of the investigation. How should the prisoners act?

The non-intuitive thing happening here, is the fact that individually, it’s better for each suspect to defect, no matter what the other prisoner does, but the best possible result for both the suspects is observed when both of them cooperate, implying that individual preferences may be the best choice for the individual, but it might not lead to the desired outcome. Problems like Prisoner’s dilemma are what they call game theorists study, and is a topic which I’m trying to scratch the surface of.

All in all, the purpose of the post was not to guide you through some puzzles or dilemmas, but rather how naive sometimes we all can be in our thoughts. How do we think, and not think? Why can’t we let our brain run at an efficient slow pace rather than just jumping at conclusions?

Before I get into more philosophical questions questioning our existence, I think I’ll cease fire here.