0

In the 15-puzzle, suppose the initial state (on the left) is transformed by legal moves to the state on the right in the diagram below. How many times must this transformation be repeated to return to the initial state?

enter image description here

I'm really uncertain how to approach this question. The only thing I can think is that because "3" and the "blank square" return to their original location, they have to have been moved up/down an equal number of times, and left/right an equal number of times. So the number of transpositions must be even even, so it is a product of an even number of transpositions.

I'm stumped as to what other avenues I can explore with this question. I'd really appreciate a small push in the right direction.

(NOTE: this is an assignment question, so please don't give too much away!)

Explanation of the 15 Puzzle: https://en.wikipedia.org/wiki/15_puzzle

mathstack
  • 899
  • 1
    I don't know much about this kind of thing, but my gut instinct was to look at 1 and follow where it would go after $n$ transformations, and figure out when it returns. Or if you could find a way to characterize what actually happened to the pieces that would be really nice, but I don't immediately see anything there. – Will Craig Apr 10 '17 at 03:22
  • 1
    I think that @WillCraig is onto something. The number 1 goes through a certain amount of cycles in the puzzle. You can consider what happens to this cycle. Then, if there are any remaining numbers, you could consider how many numbers are in the remaining cycles. My guess is that the class or assignment that you are studying has to do with some sort of combining cycles together. Hopefully these hints help! – Matt Groff Apr 10 '17 at 03:36

1 Answers1

1

Presenting this as a $15$ puzzle is a red herring. All you have is a permutation, so $1$ goes to $4$, which goes to $7$ and so on. You don't care what moves are needed to make that happen. Figure out the cycle structure of the permutation. Once you have that, the number of applications of the permutation that are needed to get the identity is ??????

Ross Millikan
  • 374,822