#1
|
|||
|
|||
A-SHUFFLE PROBABILITY HELP!! MATHEMATICIANS PLEASE!!
i think its called an "a-shuffle" but i'm a little hazy so here it goes...
i was shuffling 6 blue $1 mirage chips and 6 white $1 st. tropez chips and i noticed that after 6 PERFECT A SHUFFLES i turned and counted each time many many times over, the stacks invariably returned to 6blue 6white...i then tried it with 2, 3, 4, 5, 7, 8 (had to do it one chip at a time), same with 9 and 10 but i did it anyway to see 'cause i was curious and i recorded all results: N (#total chips) #A-Shuffles to return to original 4- 2 6- 3 8- 3 10- 5 12- 6 14- 4 16- 4 18- 9!!!! (checked this one about a million times) 20- 6 This got me thinking about how to write an equation (or what is the equation if a relationship exists) for the relationship between # of total chips and # of perfect shuffles needed to return them to original 2 stacks of uniform colors... SOOO thats my question. math and probability professors and statisticians, please let me have it! -Barron |
#2
|
|||
|
|||
Re: A-SHUFFLE PROBABILITY HELP!! MATHEMATICIANS PLEASE!!
FURTHER:
i would like to know a few other odd aspects of this problem. 1) if one chip is misplaced by one position aaaaaa, bbbbbb----> ababababBAab ... will it ever return to original aaaaaa, bbbbbb? i never shuffled enough to find out 2) if we start with random sorts, abaababbabab or the like, what is P(aaaaaa,bbbbbb|random sort, but perfectshuffles from then on in) 3) what is general notation for this stuff? thanks -Barron |
#3
|
|||
|
|||
A-shuffle? Only know about the INs and OUTs!
What's an A-shuffle?
The most common terms for a "perfect shuffle" are in-shuffle and out-shuffle, so let me illustrate each based on a deck of 8 cards: An in-shuffle on a deck of 1 2 3 4 5 6 7 8 results in 5 1 6 2 7 3 8 4 whereas an out-shuffle on a deck of 1 2 3 4 5 6 7 8 results in 1 5 2 6 3 7 4 8. Suppose the deck has 2n elements where n is an integer. The results of in-shuffles and out-shuffles have been examined before. In the case of in-shuffles, the first element is considered the 1st place and in-shuffling is just the same as multiplication by 2 modulo (2n+1) whereas for outshuffles, the first element is considered the 0th place and out-shuffling is multiplication by 2 modulo (2n-1). By that, I mean that the kth place goes to the (2k)th place after one shuffle. Note: modular arithmetic is just "remainder" arithmetic or "clock" arithmetic where the only allowed results are 0, ... (m-1) where m is the modulus. Thus, the lowest exponent k for which 2^k is congruent to 1 mod 2n+/-1 gives the least number of shuffles returning the deck to its original state. Also, it will take at the very most 2n in-shuffles or 2n-2 out-shuffles to return to the original state (this comes from a theorem by Euler, a generalization of Fermat's Little Theorem that if a and m are coprime, a^phi(m) is congruent to 1 mod m). Actually, the biggest it could be is phi(m) shuffles where m is the modulus in question and phi is the Euler totient function (phi(m) is the same as the number of integers between 0 and m-1 inclusive that are coprime with m). In any case, the actual least number of shuffles to return to the original state must divide exactly into phi(m). Since the number 53 is prime, and 2 is a primitive root modulo 53 (or 2 is a generator of the multiplicative group of nonzero congruence classes modulo 53) it takes 52 in-shuffles for a deck of cards to go back to its original state and similarly 8 out-shuffles (since 2^8 is congruent to 1 mod 51 and no smaller exponent of 2 is congruent to 1). At first, I thought you were talking about out-shuffles, but your data doesn't coincide with what would be the data for out-shuffles. |
#4
|
|||
|
|||
Re: A-shuffle? Only know about the INs and OUTs!
well i got to the first paragraph and will ask you one question before i slog through the rest because it will take me some effort (that i'm willing to put in) but not if the premise is faulty.
for the in shuffle you demonstrate (and out for that matter) it seems as if neither is what i would call a "perfect shuffle" nor the one that occurs w/ my little baby chips. taking 12345678 and LOL. ok, i'll stop here. funny [censored]. clearly we're lookin at an inshuffle of 51627384. i thought were were taking 12345678 and 12345678. clearly thats wrong and i will now go back to slogging. ty VERY much for your time and effort for this post! -Barron |
#5
|
|||
|
|||
Re: A-shuffle? Only know about the INs and OUTs!
ok, heres my problem.i love math and stat. i'm an economist for the dept. of laber (not many 23 year olds that have that job...)
but i do not know to what you refer with many of the words you are using. it is like looking up words in the definition of the word you just looked up. plus, being a statistics guy, i see phi(m) and take a while guess what i think of...thats right our favorite buddy the normal distribution for m. so i really am lost here. if you would be so kind (and i really would appreciate this) would you please either private message me or post the same exact proof in language i can at least slog through lol. further, what would REALLY be great, although i'm sure its in that post somewhere, is how to derive the formula for how many shuffles does it take to return a set of n elements of x (x=2 in this example) variety to original order m. that would be fantastic! thanks again! -Barron |
#6
|
|||
|
|||
Re: A-shuffle? Only know about the INs and OUTs!
You can lookup explanations of all these terms at www.mathworld.wolfram.com.
|
#7
|
|||
|
|||
Okay, I know what you mean now!
Actually, you don't need the same chip to go back to the
original place, right? You simply require that the same "pattern" of alternating chips as the start is reinstated. As per my previous post then, if you have 2n elements (chips or that are alternating in exactly 2 or g different colors where g divides into 2n), then the least positive number of shuffles to get back to the original pattern must divide into phi(2n+1). Here, phi(k) is a number-theoretic function: Again, it is simply the number of elements of {0,1,...,m-1} that are relatively prime to m. [Two numbers n1 and n2 are relatively prime if there is no common divisor other than 1 that divides both n1 and n2.]. Also, m and n are coprime means the same as m and n are relatively prime. For example, if p is a prime, phi(p)= p-1. For nth powers of primes, phi(p^n)= (p-1)p^(n-1). Also, phi is multiplicative, i.e., if m and n are coprime, phi(mn)=phi(m)phi(n). Since we know every positive integer greater than 1 has a unique factorization as a product of primes, phi(m) can be easily determined from the above. Now, as to the question about EXACTLY how many times you need to shuffle k chips, that seems a bit more difficult, but I'll see what I can do! This brings a completely new meaning to "pattern mapping" that I didn't intend! LOL! [img]/images/graemlins/smile.gif[/img] |
#8
|
|||
|
|||
Re: A-SHUFFLE PROBABILITY HELP!! MATHEMATICIANS PLEASE!!
Also, your data isn't quite right: for example, you consider
the pattern abab equivalent to baba which is not quite so. You have been taking the number of shuffles to get to the "inverse" as well! Your data should be: 2n: min # of shuffles to original , min # to inverse 4: 4, 2 6: 3 8: 6, 3 10: 10, 5 12: 12, 6 14: 4 16: 8, 4 18: 18, 9 20: 6 |
#9
|
|||
|
|||
MY EDUCATED GUESS
My apologies for not having worked sufficiently more on this
problem! Since the shuffle you are dealing with is an inshuffle and it is known that the state of the deck will return in r shuffles where r is the lowest positive exponent of 2 which is congruent to 1 modulo (2n+1) (where 2n = number of objects that are shuffled), the actual least number of shuffles to return to the original pattern must divide r. Call this least number of shuffles s (clearly, s >=2 and s divides r). I suppose someone could check this out if they had adequate computing resources and the inclination: to see if the pattern only returns after r shuffles for the first few thousand values of 2n (I am basically quite lazy at times especially when it comes to coding and try to solve these kinds of problems analytically). Suppose the set of objects starts off as: 1 2 3 ... 2n And suppose that after s shuffles, the same pattern occurs, i.e., the odd placed spots are filled with odd numbers and the even placed spots have even numbers. My argument to suggest that r is the answer is this: since the positions of the objects for each shuffle is equivalent to multiplying by 2 modulo (2n+1), for the same pattern to develop after s shuffles, all the even numbers above must go the even-numbered positions and therefore after s-1 shuffles, the objects would be ordered like this: {even objects in first half} {odd objects in last half} {2, 4, .., 2n in some order} {1, 3, .. ,2n-1 in some order} for then after another shuffle, the even objects get thrown into the even-numbered positions. What does this actually mean? Well, the even objects are really numbers of the form 2m where 1 <= m <= n, so this just means that 2m.2^(s-1) is congruent to a number m0 where 1 <= m0 <= n because these even numbers are in the first half of the deck after (s-1) shuffles. This is true for all m, so (using =/= as the congruence symbol), 2m.2^(s-1) = m.2^s =/= m0 where 1 <= m0 <= n or m goes to m0 after s shuffles where both m and m0 are between 1 and n inclusive. but m.2^s being in the first half just means the first half of the deck goes to the first half of the deck after s shuffles. Thus, the last half of the deck also goes to the last half after s shuffles. So this highly suggests that this will only happen when 2^s =/= 1 (also, even numbers go to even placed spots and odd numbers...). So my "guess" is that s would have to be r. Any comments from the peanut gallery? |
#10
|
|||
|
|||
ANSWER
As highly suggested from my "guess", the answer must be the
order of 2 in the multiplicative group generated by 2 mod (2n+1) where there are 2n objects; i.e., the answer is r where r is the least positive integer such that 2^r is congruent to 1 modulo (2n+1). Does anyone see why? It's actually not hard to deduce from the text in the post "MY EDUCATED GUESS". In other words, the pattern only repeats after the chips return to their original positions; this is not a very obvious result! |
|
|