# Math Problem - 7



## Harris Chan (Aug 13, 2008)

This isn't too hard if you knew the concept before  The actual question is really short but I like to set up the scenario.

It's 2009 and we're now starting the final round of the 3x3 speedsolve final in the WC09, with only 12 competitors left from the 543. As the scramblers finished up scrambling the last cube, an unfortunate event occurred. A judge tripped on one of the legs of the table where all the cubes were placed and actually snaped the leg, causing the table to fall down, sending the cubes tumbling down. The scorecard that were assigned to each competitor with his/her cube are all mixed up now. None of the scramblers/judges know which cube belongs to who.

Running slightly behind schedule, that decided not to go and ask each competitor to reclaim their cubes, because that would take a while and they don't want to show the scrambled cube to the competitor. So they decided to take a chance: they randomly assigned a cube to each competitor. How many possibilities are there that *NONE* of the competitors was assigned with their own rightful cube?


----------



## not_kevin (Aug 13, 2008)

Huh. I saw something like this before...



Spoiler



Is the answer 176214841/479001600 = 36.8%?


----------



## Lucas Garron (Aug 13, 2008)

Same as the probability that none of the edges of a 3x3x3 are in their original position (ignoring orientation) after a random scramble. 
Essentially 1/e.

http://cube.garron.us/BLD/probabilities.htm


----------



## brunson (Aug 13, 2008)

I'm going to go with my gut and say: 


Spoiler



1/12 probability


----------



## StachuK1992 (Aug 13, 2008)

*spoiler below*

(11/12)*(10/11)*(9/10)*(8/9)*(7/8)*(6/7)*(5/6)*(4/5)*(3/4)*(2/3)*(1/2)
=
1/12


----------



## rjohnson_8ball (Aug 13, 2008)

spoiler:
The probability of a contestant not getting his/her own cube is (11/12). Each contestant has the same probability, so the odds of ALL of them not receiving their own cube is (11/12)^12 = 35.2%. (So, in other words, 2 to 1 odds that somebody will get their own cube.)


----------



## MistArts (Aug 13, 2008)

Spoiler



11/12*10/11*9/10*8/9*7/8*6/7*5/6*4/5*3/4*2/3*1/2=0.0833333333333333333333333333333333 and on....


----------



## not_kevin (Aug 13, 2008)

To those who say that the answer is:


Spoiler



11/12*10/11*9/10*8/9*7/8*6/7*5/6*4/5*3/4*2/3*1/2 = 1/12


It's not right.


Spoiler



You can't pick the same wrong cube twice!


----------



## not_kevin (Aug 13, 2008)

You pick them without replacement, don't you?


----------



## MistArts (Aug 13, 2008)

not_kevin said:


> To those who say that the answer is:
> 
> 
> Spoiler
> ...





Spoiler



You way of saying it was confusing. But I got it. So it's (11/12)^12 ?


----------



## not_kevin (Aug 13, 2008)

MistArts said:


> Spoiler
> 
> 
> 
> You way of saying it was confusing. But I got it. So it's (11/12)^12 ?



Sorry about the ambiguity. Here's the greatest thing:


Spoiler



No, it's not! Doing that would be making the same error, if I'm not mistaken. Take a really simple case as an example: 3. By brute force, we can see there are 6 possible ways to have the cubes distributed, and only 2 that have all three incorrect. However, (2/3)^3 = 8/27, which clearly en't 1/3.

It's a pretty messy question, isn't it?


----------



## Stefan (Aug 13, 2008)

Spoiler



I claim Lucas is right, though I cannot prove it, I just have faith.


----------



## guusrs (Aug 13, 2008)

Spoiler Below​I'd claim Stefan is right!


----------



## MistArts (Aug 13, 2008)

not_kevin said:


> MistArts said:
> 
> 
> > Spoiler
> ...





Spoiler



1/12 is right then if using your explanation....I checked with 2 and 4 cubes.


----------



## not_kevin (Aug 13, 2008)

MistArts said:


> Spoiler
> 
> 
> 
> 1/12 is right then if using your explanation....I checked with 2 and 4 cubes.





Spoiler



Really? It works for 4? I thought it broke down starting there... Are you sure there's only 6 possibilities? I thought there were 24 - 1 - 1*6 - 2*4 = 9...


----------



## MistArts (Aug 13, 2008)

not_kevin said:


> MistArts said:
> 
> 
> > Spoiler
> ...






Spoiler



Never mind. I forgot cross-cycles.





Spoiler



(n-1)*(n-1)*(n-2) works for 4 and 5 for figuring out the possibilities of n! but not 3....


----------



## Harris Chan (Aug 13, 2008)

If the question was confusing; let say numbers 0-9 are in order 0123456789, how many ways can you arrange it such that none of the numbers are in their original spot?

So 1234567809 is not one of the possibility because 9 is in its original spot. But 1234567890 is one of the possibility.



Spoiler



Michael and Lucas is right =) Which means...Stefan is right too? lol


----------



## fanwuq (Aug 14, 2008)

Ok, I see that it's definitely not 1/12. I forgot how to find the answer immediately.
So I have to believe guusrs's statement.

So far using my simple logic, it should be:

(11/12)(1/12 + 11/12 * 10/11)(1/6 + 5/6 * 9/10)... 

Wait, that would mean that I got (11/12)^12 = 35.2%
Same as rjohnson 8ball


----------



## brunson (Aug 14, 2008)

Wait a sec... Is Lucas saying 1/e where e=12? I thought he was saying 1/e where e is Euler's number, i.e. d(e^t)/dt = e^t and I was about to dispute that.


----------



## badmephisto (Aug 14, 2008)

fanwuq i was thinking of exactly that same approach. Its basically what people said in the beginning, but with the added subtlety that not_kevin mentioned.
and I'm pretty sure Lucas meant the 2.7 e ?


----------



## Lucas Garron (Aug 14, 2008)

It's 1/e, where e=2.718281828459045235360...

http://en.wikipedia.org/wiki/Derangement#Counting_derangements

Why it's not 1/12: All you people not considering the probability that when we get to competitor n, her/his cube has already been misplaced, and (s)he gets it with probability 0.


```
(11/12)*(                0/11)*(               9/10)*...
should be:
(11/12)*(1/12*1 + 11/12*10/11)*(2/12*1 + 10/12*9/10)*...
=(11/12)*(11/12)*(11/12)*...
```
Except there is some dependency (each competitor's cube is more likely to be mismatched already when we get to him/her, since we are eliminating the random case that any competitor gets her/his own cube, and thus increasing the chances that they get someone else's), so the bottom is not quite that.

Anyhow, ((n-1)/n)^n goes to 1/e, and it's close-ish for 12 already.


----------



## ch_ts (Aug 14, 2008)

Ha, you're all wrong. The question is "how many possibilities" not "what is the probability".


----------



## fanwuq (Aug 14, 2008)

ch_ts said:


> Ha, you're all wrong. The question is "how many possibilities" not "what is the probability".



LOL
Harris fooled everyone else, including me.


----------

