[superprismatic]

An automatic card shuffler always

rearranges the cards the same way if the

setting is the same. A set of twelve

cards bearing the letters

     GOLDENBINARY

[/code]


is put through the machine, and the

cards, in the order in which they

emerge, are put through again.  They

come out

[code]

     ANINOYGREDBL

What message did the cards convey after

the first operation, assuming the

setting is left unchanged?

"setting" means the permutation to be applied to the cards.

If Perm is the permutation which the shuffler applies to the cards, then ANINOYGREDBL=Perm(Perm(GOLDENBINARY)) and you are asked to find Perm(GOLDENBINARY) which is a simple English sentence with spaces removed.

[Guest]

I don't know if there is any way to solve it logically, but here's the answer derived via brute force

LEARNBYDOING

[bushindo]

I don't know if there is any way to solve it logically, but here's the answer derived via brute force

LEARNBYDOING

Here's the logical way

Let x be our input vector ( G O L D E N B I N A R Y ), and let y be the output vector ( A N I N O Y G R E D B L ). The scrambling operation operation can be described by a binary matrix A, which has 0's everywhere, and a single 1 on every single row and every single column. The question is equivalent to the following

A*(A*x) = y. Find A*x.

Given x and y, we can construct the scrambling matrix B = A*A that takes x directly to y, which is equal to

B = 

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]

 [1,]    0    0    0    0    0    0    0    0    0     1     0     0

 [2,]    0    0    0    0    0    0    0    0    1     0     0     0

 [3,]    0    0    0    0    0    0    0    1    0     0     0     0

 [4,]    0    0    0    0    0    1    0    0    0     0     0     0

 [5,]    0    1    0    0    0    0    0    0    0     0     0     0

 [6,]    0    0    0    0    0    0    0    0    0     0     0     1

 [7,]    1    0    0    0    0    0    0    0    0     0     0     0

 [8,]    0    0    0    0    0    0    0    0    0     0     1     0

 [9,]    0    0    0    0    1    0    0    0    0     0     0     0

[10,]    0    0    0    1    0    0    0    0    0     0     0     0

[11,]    0    0    0    0    0    0    1    0    0     0     0     0

[12,]    0    0    1    0    0    0    0    0    0     0     0     0

So our job is now to solve B = A*A, where B is known and A is a special matrix of zeroes, and a single 1 on every row and column. So there are 12 number 1's inside A. Let (a, b, c, d, e, f, g, h, i, j, k, l) represent the column index of the 1's, so that

A[ 1, a] = 1

A[ 2, b] = 1

..

A[ 12, l] = 1

A little examination of A and matrix multiplications will show that the following has to be true

A[ 1, a] = A[ a, 10]

A[ 2, b] = A[ b, 9]

A[ 3, c] = A[ c, 8]

A[ 4, d] = A[ d, 6]

A[ 5, e] = A[ e, 2]

A[ 6, f] = A[ f, 12]

A[ 7, g] = A[ g, 1]

A[ 8, h] = A[ h, 11]

A[ 9, i] = A[ i, 5]

A[ 10, j] = A[ j, 4]

A[ 11, k] = A[ k, 7]

A[ 12, l] = A[ l, 3]

If we start with a guess of the variable 'a', we can quickly derive the other 11 variables. For instance, if we pick a= 3, then

A[ 1, 3] = A[ 3, 10] = A[ 3, c]

Since there is only one number 1 on every row and column. This forces c to be equal to 10. If we keep going, we can sweep out all the other variables. To find the solution, we need to start with a guess for 'a' between 1 and 12, and compute all the other variables. The solution is the set of (a, b, c, d, e, f, g, h, i, j, k, l) where no two variable has the same value (again, this is because of the row and column contraint on A). Assuming that there is a solution, we are guaranteed to find it by exhaustively searching all values of 'a' between 1 and 12.

Edited August 15, 2009 by bushindo

[bushindo]

Here's the logical way

Let x be our input vector ( G O L D E N B I N A R Y ), and let y be the output vector ( A N I N O Y G R E D B L ). The scrambling operation operation can be described by a binary matrix A, which has 0's everywhere, and a single 1 on every single row and every single column. The question is equivalent to the following

A*(A*x) = y. Find A*x.

Given x and y, we can construct the scrambling matrix B = A*A that takes x directly to y, which is equal to

B = 

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]

 [1,]    0    0    0    0    0    0    0    0    0     1     0     0

 [2,]    0    0    0    0    0    0    0    0    1     0     0     0

 [3,]    0    0    0    0    0    0    0    1    0     0     0     0

 [4,]    0    0    0    0    0    1    0    0    0     0     0     0

 [5,]    0    1    0    0    0    0    0    0    0     0     0     0

 [6,]    0    0    0    0    0    0    0    0    0     0     0     1

 [7,]    1    0    0    0    0    0    0    0    0     0     0     0

 [8,]    0    0    0    0    0    0    0    0    0     0     1     0

 [9,]    0    0    0    0    1    0    0    0    0     0     0     0

[10,]    0    0    0    1    0    0    0    0    0     0     0     0

[11,]    0    0    0    0    0    0    1    0    0     0     0     0

[12,]    0    0    1    0    0    0    0    0    0     0     0     0

So our job is now to solve B = A*A, where B is known and A is a special matrix of zeroes, and a single 1 on every row and column. So there are 12 number 1's inside A. Let (a, b, c, d, e, f, g, h, i, j, k, l) represent the column index of the 1's, so that

A[ 1, a] = 1

A[ 2, b] = 1

..

A[ 12, l] = 1

A little examination of A and matrix multiplications will show that the following has to be true

A[ 1, a] = A[ a, 10]

A[ 2, b] = A[ b, 9]

A[ 3, c] = A[ c, 8]

A[ 4, d] = A[ d, 6]

A[ 5, e] = A[ e, 2]

A[ 6, f] = A[ f, 12]

A[ 7, g] = A[ g, 1]

A[ 8, h] = A[ h, 11]

A[ 9, i] = A[ i, 5]

A[ 10, j] = A[ j, 4]

A[ 11, k] = A[ k, 7]

A[ 12, l] = A[ l, 3]

If we start with a guess of the variable 'a', we can quickly derive the other 11 variables. For instance, if we pick a= 3, then

A[ 1, 3] = A[ 3, 10] = A[ 3, c]

Since there is only one number 1 on every row and column. This forces c to be equal to 10. If we keep going, we can sweep out all the other variables. To find the solution, we need to start with a guess for 'a' between 1 and 12, and compute all the other variables. The solution is the set of (a, b, c, d, e, f, g, h, i, j, k, l) where no two variable has the same value (again, this is because of the row and column contraint on A). Assuming that there is a solution, we are guaranteed to find it by exhaustively searching all values of 'a' between 1 and 12.

I omitted some details earlier. Here's the revised part, which should convey the point better.

Let B = A*A, where B is known and A is a binary scrambling matrix. A little examination of A and matrix multiplications will show that the following has to be true

A[ 1, a] = A[ a, 10] = 1

A[ 2, b] = A[ b, 9] = 1

A[ 3, c] = A[ c, 8] = 1

A[ 4, d] = A[ d, 6] = 1

A[ 5, e] = A[ e, 2] = 1

A[ 6, f] = A[ f, 12]= 1

A[ 7, g] = A[ g, 1] = 1

A[ 8, h] = A[ h, 11]= 1

A[ 9, i] = A[ i, 5] = 1

A[ 10, j] = A[ j, 4] = 1

A[ 11, k] = A[ k, 7] = 1

A[ 12, l] = A[ l, 3] = 1

If we start with a guess of the variable 'a', we can quickly derive the other 11 variables. For instance, if we pick a= 3, then

A[ 1, 3] = A[ 3, 10] = A[ 3, c] = 1

The rest of the details are the same as above

[Guest]

The permutation is 1to12, 2to9, 3to1, 4to8, 5to2, 6to11, 7to6, 8to10, 9to5, 10to3, 11to4, 12to7.

When applied to GOLDENBINARY once, it gives LEARNBYDOING.

The answer is LEARNBYDOING.

[Guest]

Oh, I think of permutations as cycle covers. It is a smaller representation; for combinatorialists it is simpler.

So if S was the unknown permutation, then the data suggests that S*S is one of the two

- because S*S could take 6 (resp 8) to either 2 or 4 (resp 4 or 2)

CASE 1: 1->7->11->8->3->12->6->2->5->9->4->10->1

CASE 2: 1->7->11->8->3->12->6->4->10->1 and 2->5->9->2

Now from first principles, S has cannot have fewer cycles than S*S.

So if it is CASE 1, and considering the data, the single cycle of S should be of the form

1->a->7->b->11->c->8->d->3->e->12->f->6 ... oooops I should have reached 1 by now, run out of numbers,

so CASE 1 is impossible.

So it must be CASE 2:

The cycle 2->5->9->2 of S*S could only result from the cycle 2->9->5->2 of S. (1)

The cycle 1->7->11->8->3->12->6->4->10->1 of S*S can reveal the corresponding cycle of S by reasoning:

In S we must have 1->a->7->b->11->c->8->d->3->1, since the cycle is of length 9.

Now 3->12 in S*S implies a=12 condering the structure of the cycle above,

12->6 in S*S implies b=6,

6->4 in S*S implies c=4, and

4->10 in s*S implies d=10.

Therefore, the other cycle of S is 1->12->7->6->11->4->8->10->3->1 (2)

Applying S as suggested by (1) and (2) to GOLDENBINARY we get LEARNBYDOING.

[bushindo]

Oh, I think of permutations as cycle covers. It is a smaller representation; for combinatorialists it is simpler.

So if S was the unknown permutation, then the data suggests that S*S is one of the two

- because S*S could take 6 (resp 8) to either 2 or 4 (resp 4 or 2)

CASE 1: 1->7->11->8->3->12->6->2->5->9->4->10->1

CASE 2: 1->7->11->8->3->12->6->4->10->1 and 2->5->9->2

Now from first principles, S has cannot have fewer cycles than S*S.

So if it is CASE 1, and considering the data, the single cycle of S should be of the form

1->a->7->b->11->c->8->d->3->e->12->f->6 ... oooops I should have reached 1 by now, run out of numbers,

so CASE 1 is impossible.

So it must be CASE 2:

The cycle 2->5->9->2 of S*S could only result from the cycle 2->9->5->2 of S. (1)

The cycle 1->7->11->8->3->12->6->4->10->1 of S*S can reveal the corresponding cycle of S by reasoning:

In S we must have 1->a->7->b->11->c->8->d->3->1, since the cycle is of length 9.

Now 3->12 in S*S implies a=12 condering the structure of the cycle above,

12->6 in S*S implies b=6,

6->4 in S*S implies c=4, and

4->10 in s*S implies d=10.

Therefore, the other cycle of S is 1->12->7->6->11->4->8->10->3->1 (2)

Applying S as suggested by (1) and (2) to GOLDENBINARY we get LEARNBYDOING.

That's a marvelous solution. Makes me regret that I didn't take group theory when I had the chance. Can you take a look at this Walter Penney also? I can solve it using the matrix method I described above, but cycles are a lot more elegant and I learned a lot from your solution here.

Edited August 15, 2009 by bushindo

[bonanova]

We know 1-> x-> 7, where x is in {1 , 12} excluding 1 and 7.

Similarly for the other 11 positions.

All x values lead to contradictions until we get to the last value [12].

It gives a cycle [we conclude 6-> y-> 4, not 2, which doesn't work]:

1-12-7-6-11-4-8-10-3-1, leaving the trivial 2-9-5-2 to finish it off.

The silver lining to x being the last possible value is, we gain the knowledge that the solution is unique.

[Guest]

That's a marvelous solution. Makes me regret that I didn't take group theory when I had the chance. Can you take a look at this Walter Penney also? I can solve it using the matrix method I described above, but cycles are a lot more elegant and I learned a lot from your solution here.

Thanks. Will try to take a look. School starts. Too much to catch up with...