Jumping x's and o'x problem

Printable View

May 28th 2008, 08:32 AM
misskatemarie

Jumping x's and o'x problem

Okay I'm taking an online math course and my professor gives us these problems weekly I've been doing well with them until now. HELP!

With a grid of x's and o's how many jumps (minimum) does it take to get all the x's to the opposite side of the board and all the o's to the opposite side of the board.

•If you are an X, you can only move one or two spaces to the right to an open square. If you are an O, you can only move one or two spaces to the left to an open square. You may jump over one letter when moving, but it has to be a letter different from the letter moving. What is the minimum number of moves it takes to move the O’s to the other left and the X’s to the other right?

board looks like this:

XXX OOO

There are no spaces between letters but one space seperating x's and o's

the problem should end up looking like this:

OOO XXX
May 28th 2008, 09:40 AM
misskatemarie

more help

Okay so I think I have figured out a solution but now my prof wants an equation for the solution. I'm so lost now.

Heres what I found....

I found that if you have

3 blocks 1 of each letter you will have 3 total moves
5 blocks 2 of each letter you will have 8 total moves
7 blocks 3 of each letter you will have 15 total moves
9 blocks 4 of each letter you will have 24 total moves
11 blocks 5 of each letter you will have 34 total moves

the equation must be in y=mx+b form... I'm confused
May 28th 2008, 10:42 AM
Soroban

Hello, misskatemarie!

This is a classic brain teaser . . .

Quote:

We have a line of red and blue markers. .
The board looks like this:. . $X\:X\;X\:\square\;O\:O\:O$

We want to swtich the positions of the markers:
the X's at the right end and the O's at the left end.

An X can move one space to the right into an empty square,
or it can jump an O and land in an empty square.

An O can move one space to the left into an empty square,
or it can jump an X and land in an empty square.

What is the minimum number of moves required
to move the X’s to the right and the O’s to the left?

The solution looks like this: . $O\:O\:O\:\square\:X\:X\:X$

It can take many hours to find the solution.
Most attempts end up at a situation with no moves available.

Many years ago, I not only solved this puzzle,
. . but I found a pattern in the solution.

Number the positions from 1 to 7.
With each indicated move, there is only one legal move available.

We have: . $\begin{array}{ccccccc}X & X & X & \square & O & O & O \\ _1 & _2 & _3 & _4 & _5 & _6 & _7 \end{array}$

Move $\overrightarrow{3}\!:\;\;\begin{array}{ccccccc}X & X & \square & X & O & O & O \\ _1 & _2 & _3 & _4 & _5&_6&_7\end{array}$

Move $\overleftarrow{5}\!:\;\;\begin{array}{ccccccc}X & X & O & X & \square & O & O \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overleftarrow{6}\!:\;\;\begin{array}{ccccccc}X & X & O & X & O & \square & O \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overrightarrow{4}\!:\;\;\begin{array}{ccccccc}X & X & O & \square & O & X & O \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overrightarrow{2}\!:\;\;\begin{array}{ccccccc}X & \square & O & X & O & X & O \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overrightarrow{1}\!:\;\;\begin{array}{ccccccc}\sq uare & X & O & X & O & X & O \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overleftarrow{3}\!:\;\;\begin{array}{ccccccc}O & X & \square & X & O & X & O \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overleftarrow{5}\!:\;\;\begin{array}{ccccccc}O & X & O & X & \square & X & O \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overleftarrow{7}\!:\;\;\begin{array}{ccccccc}O & X & O & X & O & X & \square \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overrightarrow{6}\!:\;\;\begin{array}{ccccccc}O & X & O & X & O & \square & X \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overrightarrow{4}\!:\;\;\begin{array}{ccccccc}O & X & O & \square & O & X & X \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overrightarrow{2}\!:\;\;\begin{array}{ccccccc}O & \square & O & X & O & X & X \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overleftarrow{3}\!:\;\;\begin{array}{ccccccc}O & O & \square & X & O & X & X \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overleftarrow{5}\!:\;\;\begin{array}{ccccccc}O & O & O & X & \square & X & X \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

Move $\overrightarrow{4}\!:\;\;\begin{array}{ccccccc}O & O & O & \square & X & X & X \\ _1&_2&_3&_4&_5&_6&_7 \end{array}$

The solution requires a minimum of 15 moves.

The moves seem to have no discerable pattern:
. . 3, 5, 6, 4, 2, 1, 3, 5, 7, 6, 4, 2, 3, 5, 4
until I arranged them like this . . .

$\begin{array}{ccccccccccccc} & & & & 3 & & \rightarrow & & 5 \\ & & & & & & & & & \searrow \\ & & 2 & & \leftarrow & & 4 & & \leftarrow & & 6 \\ & \swarrow \\ 1 & & \rightarrow & & 3 & & \rightarrow & & 5 & & \rightarrow & & 7 \\ & & & & & & & & & & & \swarrow \\ & & 2 & & \leftarrow & & 4 & & \leftarrow & & 6 \\ & & & \searrow \\ & & & & 3 & & \rightarrow & & 5 \end{array}$

. . . . . . . . . . . . . . . $\swarrow$
. . . . . . . . . . . . . . $4$
May 28th 2008, 11:33 AM
Soroban

Hello, misskatemarie

Quote:

Heres what I found....

$\begin{array}{ccc} \text{No. of blocks} & \text{Moves} \\ \hline \text{3 blocks, 1 of each} & 3 \\ \text{5 blocks, 2 of each} & 8 \\ \text{7 blocks, 3 of each} & 15 \\ \text{9 blocks, 4 of each} & 24 \\ \text{11 blocks, 5 of each} & 35 \end{array}\quad\hdots$ Good!

The equation must be in y = mx+b form . . . . No

It is not a linear function . . .

Consider the difference of consecutive terms of your sequence,
. . then the differences of the differences, and so on.

$\begin{array}{cccccccccc} \text{Sequence} & 3 && 8 && 15 && 24 && 35 \\ \text{1st diff.} & & 5 && 7 && 9 && 11 \\ \text{2nd diff.} & & & 2 && 2 && 2 \end{array}$

The second differences are constant.
. . The function is of the second degree: a quadratic.

The general quadratic function is: . $f(n) \:=\:an^2 + bn + c$

We can determine $a,b,c$ with the first three terms of the sequence.

$\begin{array}{ccccccccc}f(1) = 3: & a(1^2) + b(1) + c &=& 3 & \Longrightarrow & a + b + c &=& 3 & {\color{blue}[1]}\\ f(2) = 8: & a(2^2) + b(2) + c &=&8 & \Longrightarrow & 4a + 2b + c &=& 8 & {\color{blue}[2]} \\ f(3) = 15: & a(3^2) + b(3) + c &=& 15 & \Longrightarrow & 9a + 3b + c &=& 15 & {\color{blue}[3]}\end{array}$

Subtract [2] - [1]: . $3a + b \:=\:5\;\;{\color{blue}[4]}$
Subtract [3] - [2]: . $5a + b \:=\:7\;\;{\color{blue}[5]}$

Subtract [5] - [4]: . $2a \:=\:2\quad\Rightarrow\quad\boxed{ a \:=\:1}$

Substitute into [4]: . $3 + b \:=\:5\quad\Rightarrow\quad\boxed{ b \:=\:2}$

Substitute into [1]: . $1 + 2 + c \:=\:3\quad\Rightarrow\quad\boxed{ c \:=\:0}$

Therefore: . $f(n) \;=\;n^2 + 2n \;=\;\boxed{n(n+2)}$
May 28th 2008, 12:31 PM
misskatemarie

soroban,

I didn't think it was linear. My professor is asking us to put it in that form and It just not working out. I also came up with the same equation for a quadratic function as you did. Thanks so much for the help