Interesting questions

Here are two simple and interesting ideas.

1. A group of ‘n’ persons are in a classroom. Prove that there always exist two people having the same number of friends.

(Note that if ‘a’ is a friend of ‘b’, then ‘b’ is also a friend of ‘a’.)

This can be easily proved using a principle known as the Pigeon Hole Principle.

This basically states that if we have larger number of pigeons and a lesser number of holes, then there will be at least one hole with more than one pigeon. Quite simple.

Returning to the question, assume there is at least one person in that group who is a friend of everyone else. This implies that there does not exist any person having zero friends. (Since every person has at least one friend- the one who is the friend of everyone else.)

So, what are the possible values for the number of friends any person in the group can have?

1, 2, 3, …., n-1. (As we observed above, value zero is not possible here. )

Now, what are the total number of persons in the group?

n.

So, we have ‘n’ persons, to each of whom we need to assign a value (number of friends that person has). We can assign values from a set of only ‘n-1’ possible values.

Hence, there will be at least two persons having the same number of friends, for the case that there is at least one person who is a friend of everyone else.

Now, what if there is no person having ‘n-1’ friends?

In this case, the set of values indicating the possible number of friends a person can have, does not include value ‘n-1’.

(The set of values is: {0, 1, 2, …, n-2} )

The same argument as above applies here. Hence proved.  QED

Point to ponder:

It was stated earlier that: If ‘a’ is a friend of ‘b’, then ‘b’ is also a friend of ‘a’. Question: Where has that fact been used in the above proof?

2. A group of ‘n’ friends live in a hostel. Let us name the friends as 1, 2, 3, …, n. Each one has a room assigned to him/her. (Person 1 is assigned Room 1; Person 2 is assigned Room 2, and so on.) There are ‘n’ rooms in all- one for each person.

One day, on coming back to the hostel after a trip, they decide to randomly enter whichever room they wish to. For instance, Person 1 enters Room 5; Person 2 enters Room 3; and so on (keeping in mind that only one person can enter any given room.)

Question: What is the expected number of persons who entered their assigned rooms?

Randomly entering a room (keeping in mind that only one person enters any given room) corresponds to a random permutation of  1, 2, …, n.

In other words, randomly re-order the sequence 1, 2, …, n.

For example (n= 5 ), we get 3, 5, 1, 4, 2. Here , Person 3 enters Room 1; Person 5 enters Room 2; and so on.

Now, what is the probability that Person 1 enters Room 1?

Answer: 1/n. (Since he has ‘n’ rooms to choose from.)

Let us define a few random variables which will help us in computing the expected value.

Let X_i be a random variable that has value = 1 if Person ‘i’ enters Room ‘i’, and value = 0, if Person ‘i’ does not enter Room ‘i’.

We need to find the expected number of persons in their assigned rooms. This is the same as: \Sigma _{i=1} ^n E[X_i] .

Let us compute E[X_i] .

E[X_i]  =      Pr[Person ‘i’ enters Room ‘i’] x [Value of X_i for this event]  +  Pr[Person ‘i’ does not enter Room ‘i’]  x [Value of  X_i for this event]

= (1/n) x 1 + (n-1)/n x 0

= 1/n.

(Notation: E[X] denotes Expected value of random variable X; Pr[e] denotes probability that event ‘e’ occurs.)

Now, we will use a technique called “Linearity of Expectation. What this says is that if we have two random variables, X and Y, then E[X + Y] = E[X] + E[Y]. (This can be extended to any number of random variables, not just two.)

(Now, if X and Y are independent random variables (i.e. Y’s value does not depend on what the value of X is; and vice versa), then it is intuitively clear that the expectation of the sum should equal the sum of expectations. But the powerful idea behind the principle of Linearity of Expectation is that this holds even when the random variables are not independent.)

Coming back to the question:-

We can apply Linearity of Expectation to solve the problem.

E[X_1 + X_2 + ... + X_n] = E[X_1] + E[X_2] + ... + E[X_n] .

Therefore, E[X_1 + X_2 + ... + X_n] = 1/n + 1/n + … + 1/n = 1

In other words, the expected number of persons who will enter their assigned rooms is one.

——–

As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality. – Albert Einstein

——–

How wonderful that we have met with a paradox. Now we have some hope of making progress. -Niels Bohr


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: