Problem Solving

An insect has one shoe and one sock for each of its twelve legs. In how many different orders can the insect put on its socks and shoes, assuming that, on each leg, the sock must be put on before the shoe?

a) 2^12 * 12!
b) 24!/(12!^2)
c) 24!/(2^12)
d) 24!
e) 24!*12^2

OA C

Here's what I did : For each of the legs, there are 12 possible socks => 12!. Once the socks are chosen, there are 12 possible shoes => 12!

Therefore, using Fund. Principle of counting, the total permutations should be (12!*12!) = (12!)^2 ?


Lost...

Please help.....

Just curious, where did you find this problem? Whoever wrote it, besides obviously knowing nothing about insects, clearly ripped it off from this problem that appeared on the 2001 AMC 12.

Before looking at those solutions, though, notice that this problem is closely related to another counting problem that has already been discussed ad nauseum on this forum: the six mobsters problem. Take a look at the solution that Brent first introduces in the fourth post and see if you can use it to make sense of the correct answer to the problem you posted.

Pete,
It's nice to see you after such a long time! This is a problem from GMATClub 700 series document by Bunuel (GC forum moderator).

I see why 24!/2^12 works. Essentially, there are 24 pairs of shoe/socks. For each of the legs, there will be 1/2 ways when socks will be put before shoes. Hence, 24!/2^12 for legs.

However, I am still not clear. If I have a pizza for 4 different spices and 3 different breads, the total number of combinations = 4! * 3! (using Fundamental principle of counting). Similarly, if we imagine 3 one-legged aliens, who have 3 shoes and 3 socks, the total number of ways aliens can wear socks = 3!. Once the socks are put, shoes can be tied in another 3! ways. Hence, 6*6=36. However, 6!/(2^3) = 720/8=90. I am not sure what's missing.

This problem has confused me now.

Thoughts?

voodoo_child wrote:Pete,
It's nice to see you after such a long time! This is a problem from GMATClub 700 series document by Bunuel (GC forum moderator).

I see why 24!/2^12 works. Essentially, there are 24 pairs of shoe/socks. For each of the legs, there will be 1/2 ways when socks will be put before shoes. Hence, 24!/2^12 for legs.

However, I am still not clear. If I have a pizza for 4 different spices and 3 different breads, the total number of combinations = 4! * 3! (using Fundamental principle of counting). Similarly, if we imagine 3 one-legged aliens, who have 3 shoes and 3 socks, the total number of ways aliens can wear socks = 3!. Once the socks are put, shoes can be tied in another 3! ways. Hence, 6*6=36. However, 6!/(2^3) = 720/8=90. I am not sure what's missing.

This problem has confused me now.

Thoughts?

Thanks! Good to be back.

I'm a little unclear on what you mean by "I have a pizza for four different spices and 3 different breads." What exactly are you trying to count? If it's the number of different pizzas you can make by choosing one bread and some combination of spices, it should be 3*2^4=48.

As far as the alien scenario goes, it's important to pay attention to exactly what the question is asking. If it's "how many ways can you distribute three different socks and three different shoes to three one-legged aliens?" then 3!3! makes sense. If the aliens already each have one shoe and one sock and the question is "in how many different sequences can the aliens put on their socks and shoes?", then 6!/2^3 makes sense.

(12!)^2 is wrong for a couple of reasons.

1. The question states that the "insect" has a shoe and sock for each of its 12 legs. That is, he has a shoe and sock already assigned to each leg. This problem is not about how we can distribute 12 socks to each of his 12 legs and then 12 shoes to each of his 12 legs. It's about how many different orders he can put on his 12 socks and 12 shoes that he has already picked out for his 12 legs. Thus, there is no danger of him putting two shoes on the same foot because each shoe (and sock) is already assigned to a specific leg. To illustrate, let's look at a simpler case of something with three legs and a sock and shoe for each leg. Let A,B, and C represent the socks for legs 1, 2 and 3, respectively. Let 1,2,3 represent the shoes for legs 1, 2, and 3 respectively. So, one possibility is the sequence ABC123 which would represent him putting all of his socks on first in order and then all of his shoes on in order. This sequence can be arranged 6! ways. But in half of these, he puts his shoe on over his sock on his first foot. In another half he puts his shoe on over his sock on his second foot, and so on. So we have to divide by 2^3 to divide out these sequences that violate the restrictions


2. So maybe you're thinking, "hey, this question is ambiguous. it's not clear that each sock and shoe are preassigned to specific legs." Even if I grant you that, 12!^2 still doesn't make any sense (and this is the bigger point) because it doesn't take into account the order in which he puts them on. It conspicuously ignores the fact that the insect doesn't have to put on ALL of his socks before putting on his shoes; he only has to make sure that he put a sock on any given leg first before he puts a shoe on that leg. There's no reason why he can't, say, put on his sock and shoe for his first leg before putting any other socks or shoes on. For example, let's say that you have a red sock and a blue sock, and two different shoes that can (remarkably) go on either of your feet. We can surely agree that there are 2*2=4 ways to assign a sock and a shoe to each foot. But once you've assigned the socks and shoes, there are still many different orders in which you could put them on your feet. Specifically, there are six possibilities:

1. Right sock, left sock, right shoe, left shoe
2. Right sock, left sock, left shoe, right shoe
3. Right sock, right shoe, left sock, left shoe
4. Left sock, right sock, right shoe, left shoe
5. Left sock, right sock, left shoe, right shoe
6. Left sock, left shoe, right sock, right shoe

So there would be 4 (or 2!2!) ways to assign the socks and shoes and then 6 (or 4!/2^2) orders in which you could put any given assignment of socks and shoes on. This question asks about the order, and never mentions having to first select a sock and shoe for each leg, so 24!/2^12 is the right answer.

Now, the problem COULD be modified so that 12!^2 makes sense. For example, if all of the socks and shoe are identical (or, if they're not identical but are pre-assigned to specific legs) and you add the restriction that the insect has to COMPLETELY FINISH putting his socks on before putting his shoes on, then when he chooses the order for his socks, he would have 12 choices for the first leg, 11 for the second, 10 for third, and so on or 12! orders for putting his socks on. And then when he was done, he'd put his 12 shoes on by the same process and have 12! choices for the order in which he did. But again, the key is that the problem, as originally stated, never says the insect has to put ALL of his socks on first, just that a sock has to go on any given leg before the shoe goes on that leg.

Anyway, C is the correct answer.

Brent@GMATPrepNow wrote: I'd have to say that the original wording leaves some room for ambiguity. I read the line "An insect has one shoe and one sock for each of its twelve legs" as meaning the ratio of socks to feet is 1:1, and the ratio of shoes to feet is 1:1. In other words, we don't have any extra shoes or socks to consider. To prevent any possible misinterpretation, we might add an example such as, "For example, sockA is preassigned to one specific foot only and cannot be placed on any other foot"

Yeah, I can see your point. I first saw this problem years ago when I used to help high school kids prepare for the AMC, and that's how the official solution interpreted the wording, so that's how I've thought about it ever since. But I agree that the ratio interpretation is reasonable. I think to some extent it depends on the context. Certainly if someone said something like "there were three women for each man at the party", he would almost surely mean the ratio was 3:1 and not that three specific women were with each man. If the question is from a trusted source you can use the answer choices to clarify the intent of the problem, but obviously it's better if the question can only be interpreted one way.

If order is the key here, then the answer is, indeed, 24!/(2^8). However, this answer is correct only if the shoes and socks are pre-assigned. If we don't allow for pre-assigned shoes and socks (that is, sockA can go on any foot), then 24!/(2^8) is not correct.

Agreed (I'm assuming you meant to say 24!/2^12 here). I think instead of specifying that they are pre-assigned we could also say that the socks are all identical and the shoes are all identical. Either way, we skip the step of assigning the footwear and focus on the order in which he puts them on.

Having said all of that, the solution (12!)^2 is correct for the question (as I read it):

An insect has 12 different shoes and 12 different socks. In how many different ways can the insect wear all of its socks and shoes, assuming that shoes are worn on the outside and socks are worn on the inside?

Agreed. This version of the problem is probably more within the scope of the GMAT, too.

GmatMathPro wrote:

voodoo_child wrote: However, I am still not clear. If I have a pizza for 4 different spices and 3 different breads, the total number of combinations = 4! * 3! (using Fundamental principle of counting).

Thanks! Good to be back.

I'm a little unclear on what you mean by "I have a pizza for four different spices and 3 different breads." What exactly are you trying to count? If it's the number of different pizzas you can make by choosing one bread and some combination of spices, it should be 3*2^4=48.

Pete,
Yes, I meant that how many different ways I can make a pizza. Why would it be '48'? If I use Fundamental principle of counting, there should be 3! options for the bread, assuming that the Pizza guy makes bread first -- something that is true in the real world. Now, he could add 4 different spices to each of the pizza. If we assume that he adds *any* combination of the spices, then, in my opinion, the answer should be (2^4)*3! (I guess you meant 2^4*3! and not {2^4}*3). If only one of the spices is to be added, then the answer should be 4!*3!. Am I correct?

Thoughts?

Pete,
I rethought about my post. I guess the question is about making a pizza vs. three pizzas. A pizza => your solution is correct. 3 pizzas with only one spices => 3!*4!; 3 pizzas with *any* combination of spices => 3!*(2^4)...I guess I didn't write the question properly....

Thoughts?

I can hardly see any place for confusion in this question. I find it clear enough: there are 12 socks and 12 shoes, each sock and shoe corresponds to only one leg. On each leg, the sock must be put on before the shoe. Nowhere does it state that ALL the socks must be put before you start putting shoes.

now if we consider that the shoes can be put before the socks, we have 24! different orders to put shoes and socks.
between these 24! we want to keep only the ones where socks were put before the shoes for each leg.
Let's think of it as a 12 digit binary number, we have 2^12 different numbers:
000000000000
000000000001
....
111111111111

when it's 0 it means the sock was put before the shoe, so we only want to keep 000000000000

The solution is [spoiler]24!/2^12[/spoiler]

GmatMathPro wrote:(12!)^2 is wrong for a couple of reasons.

1. The question states that the "insect" has a shoe and sock for each of its 12 legs. That is, he has a shoe and sock already assigned to each leg. This problem is not about how we can distribute 12 socks to each of his 12 legs and then 12 shoes to each of his 12 legs. It's about how many different orders he can put on his 12 socks and 12 shoes that he has already picked out for his 12 legs. Thus, there is no danger of him putting two shoes on the same foot because each shoe (and sock) is already assigned to a specific leg. To illustrate, let's look at a simpler case of something with three legs and a sock and shoe for each leg. Let A,B, and C represent the socks for legs p, q and r, respectively. Let 1,2,3 represent the shoes for legs p, q, and r respectively. So, one possibility is the sequence ABC123 which would represent him putting all of his socks on first in order and then all of his shoes on in order. This sequence can be arranged 6! ways. But in half of these, he puts his shoe on over his sock on his first foot. In another half he puts his shoe on over his sock on his second foot, and so on. So we have to divide by 2^3 to divide out these sequences that violate the restrictions

Hi Brent!

Even i calculated the answer to be 12!^2.But i have a doubt in the answer choice 24!/2^12 for the following reason:

Suppose there are 24! ways to arrange the 12 shoes and 12 socks, considering these(shoes and socks) to be 24 different articles. I cannot convince myself to divide 24! by 2^12 for the logic that there are total of only two possibilities for each leg, namely, shoe over sock and sock over shoe. Because if ABC123 logic mentioned above is taken into account and there are 6! ways of arranging this sequence, then for each leg there may be four possibilities on considering few of the possible permutaions as follows:

(The arrangement is p-q-r-p-q-r)

ABC123 (shoe over sock on leg p)
A12C3B (sock over sock on leg p)
123ABC (sock over shoe on leg p)
1AB23C (shoe over shoe on leg p)

If all the above sequences are to be correct. Then is it correct to divide 24! by 2 for each leg?

Thanks!

Also, in your post, in stage 15 it will be 10 ways.

Stage 14: Select a shoe for leg #2. There are 11 shoes remaining, so there are 11 ways to accomplish this stage.
Stage 15: Select a shoe for leg #3. There are 10 shoes remaining, so there are 11 ways to accomplish this stage.