Quarter Wit, Quarter Wisdom: Linear Arrangement Constraints - Part II

Quarter Wit, Quarter WisdomToday, I want to discuss the symmetry principle of linear arrangements with you. If you do not understand the symmetry principle, then it is possible that the following has happened with you:

You see a hard question and start working on it. You know that there are going to be three-four different cases. You find the number of arrangements in each case. Then, very carefully, you add them all up and get your answer. You check the answer key and behold, your answer is correct. Just for the fun of it, you turn your page to the solutions section and see that there are just two lines there which go something like this: “You can arrange 6 people in 6! ways. In half of these 6! ways, A will be ahead of B so answer is 6!/2.” and you end up feeling pretty unhappy even though you got the correct answer!

To ensure that this doesn’t happen again, let’s try and understand the symmetry principle.

Let’s work on a simple example first:

Question: There are 3 contestants, A, B and C. In how many different ways can they complete a race if the race doesn’t end in a dead heat?

Solution: Since the race doesn’t end in a dead heat, there is no tie. The following arrangements are possible:

A B C
A C B
B A C
B C A
C A B
C B A

A total of 3! = 6 arrangements. The first position is occupied by the contestant whose name is written first i.e. A B C implies A stands first, B stands second and C stands third in the race.

In how many of these arrangements is A ahead of B? We count and get 3 (A B C, A C B and C A B)
In how many of these arrangements is B ahead of A? We count and get 3 again (B A C, B C A, C B A)

The question is that out of 6 arrangements, why is it that in half A is ahead and in the other half, B is ahead? This is so because the arrangements are symmetrical. Each element has the same status. Since we are taking into account all arrangements, if half of them are partial toward A, other half have to be partial toward B. There is no difference between A and B. They are considered equal elements. Now if I ask you the number of arrangements in which B is ahead of C, you should jump up and say 3 immediately.

Let’s now look at the question I left you with in the last post.

Question 6: 6 people go to a movie and sit next to each other in 6 adjacent seats in the front row of the theatre. If A cannot sit to the right of F, how many different arrangements are possible?

Solution: ‘to the right of F’ means anywhere on the right of F, not necessarily on the adjacent seat. Here we see symmetry because there are only 2 ways in which A can sit. In every arrangement, A is either to the left of F (any seat on the left) or to the right of F (any seat on the right). There is nothing else possible. The number of cases in which A will sit to the left of F will be the same as the number of cases in which he will sit to the right of F. That is why the answer here will be 6!/2 = 360.

I hope you understand this  principle now.

Let’s quickly look at a couple of variants now.

Question 7: 7 people (A, B, C, D, E, F and G) go to a movie and sit next to each other in 7 adjacent seats in the front row of the theatre. A will not sit to the left of F and B will not sit to the left of E. How many different arrangements are possible?

Solution: Number of ways of arranging 7 people in 7 seats is 7! (using Basic Counting Principle)

Of these 7! arrangements, we want those arrangements in which A is sitting to the right of F and B is sitting to the right of E. A will sit to the right of F in half of the 7! arrangements. Of these 7!/2 arrangements, half will have B to the right of E and other half will have B to the left of E. So the number of arrangements in which A is to the right of F and B is to the right of E is (7!/2)/2 = 7!/4

Question 8: 7 people (A, B, C, D, E, F and G) go to a movie and sit next to each other in 8 adjacent seats in the front row of the theatre. A will not sit to the left of F in how many different arrangements?

Solution: We have a vacant spot here. Recall the way we deal with vacant spots (discussed in the last post) — we use Mr V.

8 people (including our imaginary Mr V) can be arranged in 8 seats in 8! ways.

We want only those arrangements in which A is sitting to the right of F. In half of the 8! arrangements, A must be to the right of F (same as before) so required number of arrangements = 8!/2

There are many more variations possible but I will stop here. Try some on your own and get back if you have a doubt. I will discuss some other little concept of Combinatorics with you next week.

Karishma, a Computer Engineer with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches the GMAT for Veritas Prep and regularly participates in content development projects such as this blog!

7 Responses

  1. G says:

    Thanks Great Concept

    • Shashank says:

      Question 7: 7 people (A, B, C, D, E, F and G) go to a movie and sit next to each other in 7 adjacent seats in the front row of the theatre. A will not sit to the left of F and F will not sit to the left of E. How many different arrangements are possible.

      Hi,

      In this question would not the answer be 7!/6??
      because out of
      EFA
      EAF
      FAE
      FEA
      AEF
      AFE
      only EFA is possible so 1 out of 6 is possible.
      hence by symmetry it should be IMO 7!/6.

      • Karishma says:

        Good catch Shashank! I was actually thinking of relations between unbiased elements while writing this example. I will update it right away. As for why only 1 combination works out of 6 here, there is a neat little concept involved. I will tackle it in an upcoming post soon.

  2. hari says:

    Wow. great example. Liked the 6 ppl arrangement. Different dimension of looking at the combination problem.

    Thanks a lot.

  3. SonyGmat says:

    Karishma is the symmetry rule applied to all linear arrangements? I believe that when some items are identical we can’t use it..

  4. Karishma says:

    This topic, combinatorics, is extremely interesting because you just cannot generalize here. Teeny tiny differences change the question and the answer completely. Look at a case where 2 items are identical – aabc
    You can arrange these in 4!/2! = 12 ways
    These 12 ways are: aabc, aacb, abac, abca, acab, acba, baac, baca, bcaa, caab, caba, cbaa

    In how many of these is b to the left of c? 6 (Exactly half. Symmetry works here. Both b and c are independent of the identical items.)
    In how many of these is b to the left of both a? 4 (Symmetry doesn’t work because a is involved)
    You can ask different questions and you will get different answers. It’s very hard to set ‘rules’. The answer is always situation specific.

Leave a Reply

Spam protection by WP Captcha-Free