Competition Math

[Dark]

If you solve the problem, be a dear and post another one for people to tackle. Also, post relative difficulty if you feel like you can determine that. And don't pick problems which require the knowledge of really esoteric theorems - I hate those types of problems. Stick to algebraic manipulation, basic geometry, and combinatorics. Seriously.

Feel free to discuss solutions here and try to post solutions in spoilers. Don't Google the problem. Unless you're too stupid to take a shot at it yourself.

 

"A spider has one sock and one shoe for each of his eight legs (the socks are identical and the shoes are identical, but the legs are distinct). In how many different orders can the spider put on his socks and shoes, assuming that, for each leg, a sock must be put on before a shoe?" (Like, 3/10 for difficulty.)

 

[spoiler=Solution]

 

Denote putting a sock on foot "n" to be an: hence, you have a1 through a8.

Denote putting a shoe on foot "n" to be bn: hence, you have b1 through b8.

 

So, in total, you have a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8. These are sixteen items, and the amount of ways to order them is 16!

 

However, a1 must come before b1, a2 must come before b2, and so on. So, for each of eight pairs of items, a distinct one has to come before the other: so, half of the options for each pair are invalid.

So, you divide the total by 2 for each pair, so divide by 2^8.

 

Hence, the answer is: 16! / 2^8

 

...which is why, when I said "a lot more," I meant it. The answer is of the order 10^10.

[/spoiler]

[Tourmaline]

I am having trouble understanding what you mean exactly by order (I look far too into things and doubt myself), but is it sixty-four? I am imagining it as the eight shoes forced into a specific leg, but if the shoes can also be moved, is it 4096...?

 

I did see your previous post in the topic on activity, too. I thought you wrote it out pretty eloquently, too, but I would be glad to encourage your posting, given how entertaining you make yourself sound.

[Dark]

For example, with two legs, here are all the possible orders:

 

Sock on Left, Shoe on Left, Sock on Right, Shoe on Right

Sock on Right, Shoe on Right, Sock on Left, Shoe on Left

Sock on Left, Sock on Right, Shoe on Left, Shoe on Right

Sock on Left, Sock on Right, Shoe on Right, Shoe on Left

Sock on Right, Sock on Left, Shoe on Right, Shoe on Left

Sock on Right, Sock on Left, Shoe on Left, Shoe on Right

[Tourmaline]

Is it 1536?

[Dark]

It's actually much, much higher. But, with posting answers, also post how you got to it so I can tell you where you went wrong.

 

I mean, I guess you got 8*8*8*3 perhaps, but not sure why the 3 is there. In any case, the answer is much higher.

[Aix]

It's actually much, much higher. But, with posting answers, also post how you got to it so I can tell you where you went wrong.

 

I mean, I guess you got 8*8*8*3 perhaps, but not sure why the 3 is there. In any case, the answer is much higher.

Damn, been a while since I've done this kind of stuff and I never got very far into it.

 

564480? First of all, the order which the legs can put on stuff is 8! which is 40320.

 

And then I simply tried listing all the possibilities. 1=Sock, 2=Shoe.

11112222

11121222 11122122 11122212

11211222 11212122 11212212 11221122 11221212

12111222 12112122 12112212 12121122 12121212

[Tourmaline]

I  got it by calculating 64*24 (the asterisk represents multiplication). In terms of why I have those numbers, the sixty-four represents the number of combinations a single point can be in while the twenty-four is the number of points there are. I am also thinking every foot also may occupy one of eight spaces (eight), be paired with one of eight socks (8*eight) and each of those socks have eight more shoes to be paired with 8(8(8*eight), but that puts me back at 4096....

[Dark]

@Aix: Your string of 1s and 2s is only for four legs, not for eight legs. Also, "11112222" is more than just one possibility. 11112222 could mean:

 

1.) Sock on 1, Sock on 2, Sock on 3, Sock on 4, Shoe on 1, 2, 3, 4

 

or

 

2.) Sock on 2, Sock on 1, Sock on 3, Sock on 4, Shoe on 1, 2, 3, 4

 

And both of those are distinct "ways" to put on socks and shoes. The answer is much higher than your answer.

@Hina: You're thinking of ways to orient the socks, which is different. If I asked you how many different combinations you can make of feet/socks/shoes, the answer would just be 8*8*8. But I'm asking how many ways you can put on socks and shoes. Having sock A on foot 1 and sock B on foot 1 doesn't matter - it just matters when you put the sock on foot 1.

[.Rai]

I'm dubious of my answer, due to random assumptions around halfway through the problem. Taking it in step order, no matter what you do for the first eight steps, you have eight choices, then from then on, I think it becomes another 8! of possibilities, taking the permutation that you used the first 8 steps as putting a sock on each leg (and I assume the permutations are symmetrical here because they should be). I got:

[spoiler=pfft]8⁸ x 8!. Which is like several billion or something. Superscript 8 is virtually unreadable, by the way.[/spoiler]

[Tourmaline]

Oh....

 

I suppose I did not understand the question. I should try to understand the question before trying it, but it could also be good that I put some effort in something.

 

Would you present another question, please?

[~Shin~]

6799543296000... I think?

[spoiler=I did this]

items = orders

1 = 1

2 = 2

3 = 6

4 = 24

5 = 120

[spoiler=did that this way]12345, 12354, 12435, 12453, 12543, 12534, 13245, 13254, 13425, 13452, 13524, 13542, 14235, 14253, 14325, 14352, 14523, 14532, 15234, 15243, 15324, 15342, 15423, 15432... after that I placed 2, 3, 4 then 5 in 1's spot and did the same thing with the other four numbers.[/spoiler]

Then found out that to get a number of items possible orders I only need to multiply said number by the number of orders the number right below has. (ex: 6*4=24).

So I did that until I got out with the result of 16 items... ya I had the time to spare, I'm free like 24/7 anyways... I regret nothing.[/spoiler]

 

My engrish does not help here....

[Dark]

@Rai: "no matter what you do for the first eight steps, you have eight choices"

 

Socks and shoes on feet 1-4, and then you only have four choices for the next move. You can also do those socks and shoes in a large number of different orders, as I explained in a previous post.

@Hina: I'll think of another question - I kind of want to stay on combinatorics for a bit but I can't think of any at the moment.

@Muteki: You basically just computed 16!, but... that's the closest anyone has gotten so far. You're answer is a bit of an overestimate, though. There are sixteen items, sure, but not every possible ordering is valid - you can't put a shoe on foot 1 before a sock is on it.

[~Shin~]

"computed"? I know the word, but in that context... is it being used as a term?.... If it matters, I would like you to reword it, plz. Nevermind this, I got it now.

 

Ya, that did not come to mind, so I just take half the result... Na that probably wouldn't be right.

[spoiler=So]

From what you said I understand that the 8 socks have 13440 orders. And that each and every one of those orders holds another 13440 orders (of shoes being put on?) under it. So I do this:

13440*13440=180633600

?

I feel as if I'm missing something big, but this could be right, so I will just post it.[/spoiler]

[Tentacruel]

I'm sure there's a proper way to solve this without resorting to brute force arithmetic but I'm completely confounded.  Not going to look at the solution just yet though.  This is very intriguing. 

[Tentacruel]

I got 16!/16, which is 15!

 

I'm not really sure how I arrived at that, but that pattern seemed to work on the same equation with fewer legs.

 

Didn't want to necro but it's still on the first page.