• Support PF! Buy your school textbooks, materials and every day products Here!

Math Logic problem

  • Thread starter j9mom
  • Start date
  • #1
31
0

Homework Statement



I am supposed to prove that if you have a puzzle 8 in this configuration

A B C
D E F
H G

I have to prove that no matter how many moves you make (as you
would a normal puzzle moving one of the adjacent letters into the
blank space) you cannot make the configuration

A B C
D E F
G H

I know you can't. I have moved these letters around all over the place... but how do I start to prove it... I don't know where to start



Homework Equations





The Attempt at a Solution



I just want a starting point...

Homework Statement





Homework Equations





The Attempt at a Solution


Homework Statement





Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
33,173
4,858
This is an interesting problem.

Isn't the idea that you can slide a letter left or right, or up or down into an empty spot? The physical puzzles I've seen like this won't let you slide a letter diagonally.

I don't know for sure, but I think that what you need to do here is to look at all the ways the blank can move around, starting from the "home" position, and getting back to it.

For starters, the blank could move all around the 2x2 square at the lower right. At each of the four positions what is state of the puzzle.
It could move around the two rightmost columns. At each of the six positions, what is the state of the puzzle?
It could move all around the two lower rows. At each of the six positions, what is the state of the puzzle?
It could move all around the perimeter of the puzzle. At each of the eight positions, what is the state of the puzzle?
I can't think of any other possibilities, although there might be some I haven't counted.

Once you exhaust the possible moves, and the one you're looking for doesn't appear, that would convince me that it's not possible. You have to make sure that you haven't omitted any possible puzzle states, though.
 
  • #3
Dick
Science Advisor
Homework Helper
26,258
618
The proof of impossibility for games like this involves assigning a even or odd number to each game position and then showing that a move in the game can only change that number by two. So if the starting position is even and the final position is odd, you can't get from one to the other. This is a simple version of the '15 puzzle' - you can look that up for details.
 
  • #4
31
0
how do I look it up? Sorry new at this
 
  • #5
112
0
use google
 

Related Threads for: Math Logic problem

Replies
9
Views
8K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
2
Views
871
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
0
Views
1K
Top