Problem of the Week #16: Monday April 24rd, 2023 As before, these problems are the results of me following my curiosity, and I make no promises regarding the topics, difficulty, solvability of these problems. Please register for an account if you would like to join the discussion below or share your own problems.
Consider a sliding puzzle in a grid like this:
The gray square is an empty slot, and the numbered squares are sliding pieces that can be moved into a neighbouring (above, below, left, right) empty slot. The above shows the puzzle when it’s solved.
a). Suppose the puzzle is scrambled like this:
How many moves does it take to solve this puzzle (restore it to the original arrangement by sliding pieces into the empty slot)?
b). What is the most number of moves a scrambled 3×3 sliding puzzle requires to be solved?
c). Suppose we can take the pieces out and rearrange them however we like. Find one arrangement of the pieces that is impossible to solve (cannot be restored to the original arrangement by sliding pieces into the empty slot).
d). Is this rearrangement of the pieces solvable?
e). How many rearrangements of the pieces in a 3×3 sliding puzzles are solvable?
f). Given a rearrangement of the pieces in a 3×3 sliding puzzle, can we tell if it’s solvable or not without trying?
g). What is the maximum number of moves an nxn sliding puzzle requires to be solved, where n is a natural number?
h). How many rearrangements of the pieces in an nxn sliding puzzle are solvable?
i). Share your own problem inspired by this one.
j). Give one of these questions to a friend/colleague/student/family member to start a mathematical discussion.