Counting Possible Arrangements for a Group Photo
Date: 10/21/2003 at 19:11:16 From: kimberly Subject: story problem Eight women of eight different heights are to pose for a photo in two rows of four. Each woman in the second row must stand directly behind a shorter woman in the first row. In addition, all of the women in each row must be arranged in order of increasing height from left to right. Assuming that these restrictions are fully adhered to, in how many different ways can the women pose? I understand the question, but I cannot figure out where to begin in order to construct an equation. I have only figured out how to move the numbers around, and there must be a more efficient approach. 5678 1234 4678 1235 2678 1345 etc....
Date: 10/22/2003 at 08:09:29 From: Doctor Luis Subject: Re: story problem Hi Kimberly, Interesting question. I suppose you numbered the women 1 thru 8 in order of ascending height, where women 8 is tallest. We know that only one person is tallest since all the heights are different. It's important to know their heights are unique, otherwise we'd have to worry about permuting the women of equal height. We know there's 8 possible places for the women. Following your notation, we have these positions: Back row: EFGH Front row: ABCD The requirements for this arrangement are A<B<C<D, E<F<G<H, and A<E, B<F, C<G, D<H. Well, let's start by positioning tall woman number 8. She can't be in the front row or anyone behind her would be shorter. So positions A,B,C,D are out. Likewise, she can't be either E,F,G or someone to the right of her would be shorter. So the only choice for woman 8 is position H. The tallest woman only had one choice. What about the shortest woman? Similar reasoning can convince you that woman 1 can only be at position A. Because women 1 and 8 are fixed, we have a single configuration, which I'll call R1. Back row: EFG8 Front row: 1BCD Women 2 thru 7 have yet to be positioned. Inspired by our method so far, we start by positioning the shortest and tallest of the women that are left. We start with the taller one, woman 7. She can be placed either at D, right in front of 8, or she can be placed at G. Those are the only two choices for her, since the tallest person must be placed to the right of everyone else that's shorter. If she's in the back row, she must be at G, or there'd be no one taller to fill in between women 7 and 8. If she's in the front row, she must be at D, because she's the tallest person left after we've placed 8. A similar argument holds for woman 2. Her only two choices are B,E. Two choices for 2 and two choices for 7 leaves us with 4 possible configurations. S1 S2 S3 S4 Back row: 2FG8 2F78 EFG8 EF78 Front row: 1BC7 1BCD 12C7 12CD So, our single configuration R1 branched out into four configurations S1 thru S4. Every time we branch out, we must add the number of arrangements for each configuration. Remember that the four women that have yet to be positioned are women 3, 4, 5, and 6. We always seek to position the tallest and shortest women first, hence women 3 and 6 will be positioned. Once 3 and 6 are in place, each configuration could branch out into one or more possible configurations. And finally, now that only two women are left, 4 and 5, you can easily position them and count the number of configurations. This is a systematic method you can use to come up with all the possible arrangements. By picking two women at a time, the tallest and shortest, you'll end up with a tree that's four levels deep. How many nodes, each representing a different configuration, would we have in this tree? The first time we picked (1 and 8) there was no branching since the choice was unique. So there's one node at level one. For the second pick, we showed that there are four branches coming out because there are two choices for woman 2, and two choices for woman 7. There's a total of four nodes at level two, one for each configuration S1 thru S4. For the third pick, we'd expect less branching since we have less freedom because of the ordering conditions. One of the women is probably going to have no choice for where she stands (you can tell by analyzing S1 thru S4), so we'd expect a branching factor of two (i.e. the number of choices for only one woman). So, for level three, we expect about 8 nodes. For the fourth pick, we have two people left to position. If they had no choice whatsoever, we'd have a branch factor of one, or 8 nodes for level four. If they had full freedom, the branch factor would be two, and we'd have 16 nodes at level four. This means we'd expect somewhere between 8 and 16 nodes for level four of our tree. But by level four all the women are standing. This means that we expect the number of possible arrangements to be between 8 and 16. This is a small enough tree that we can draw it by hand. Here it is: EFG8 1BCD _________________________|__________________________ | | | | 2FG8 2F78 EFG8 EF78 1BC7 1BCD 12C7 12CD | ____|____ _____|____ _____|___ | | | | | | | 2F68 2678 2F78 EF68 3F68 EF78 E678 13C7 13CD 13C6 1237 12C7 1236 123D ____|__ | ___|___ | ___|__ | ___|__ | | | | | | | | | | | 2468 2568 2678 2478 2578 4568 3468 3568 4578 4678 5678 1357 1347 1345 1356 1346 1237 1257 1247 1236 1235 1234 That should represent the total number of arrangements. Look at each node, and convince yourself that the branches below a node represent all the possibilities for that node. I don't think I missed any, but let me know if you can find any other configurations. Let us know if you have any more questions. - Doctor Luis, The Math Forum http://mathforum.org/dr.math/
Date: 10/22/2003 at 21:51:02 From: kimberly Subject: Thank you (story problem) Dr. Luis, Thank you so very much for your help and wonderful explanation. I am currently studying for the GMAT and plan to take the exam sometime next year. I have purchased several guides and have constructed a strict study routine for the next several months. This problem really got me stuck :) You'll probably hear from me again! Kind regards, Kimberly
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.