X's and O's

Logic Level 2

Let's play a game! Given a string of X's and O's, you can

  1. Replace any "X" by "XO".
  2. Replace any "XXX" by "OX".
  3. Replace any "OO" by "XOO".

What is the fewest number of steps needed to change the string OOX into OXOOOX?

6 4 7 5

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Steps 1. and 3. increase the length of a string by one character and step 2. decreases the length of a string by one character. So to go from a string of length 3 3 to one of length 6 6 we must use steps 1. and 3. a total of n 3 n \ge 3 times and step 2. a total of n 3 n - 3 times for a total of 2 n 3 2n - 3 steps, which, being odd, rules out 4 4 and 6 6 as possible choices.

Now although 3 3 is not an answer option, we should first, in the interest of completeness, rule it out as the actual minimum. To increase the length of a string by 3 3 characters in 3 3 steps would mean that we can only use steps 1. and 3.. Given this restriction, the only way to increase the number of O O 's by two and the number of X X 's by one would be to employ step 1. twice and step 3. once. But none of the three possible such sequences of steps would result in a string beginning with " O X OX ", and so the desired transformation cannot be achieved in 3 3 steps.

To achieve the transformation in 5 5 steps, one possible sequence is to apply step 3. three times to get X X X O O X , XXXOOX, then apply step 1. to get X X X O O O X . XXXOOOX. From here we apply step 2. to end up with O X O O O X , OXOOOX, the desired string.

Your solutions are always fun to read, Brian.

Andrew Ellinor - 5 years, 9 months ago

Log in to reply

You questions are always fun to solve, Andrew.(Sir)

Nihar Mahajan - 5 years, 9 months ago

Thanks, Andrew! I always enjoy this type of question. The desired transformation didn't look possible at first, but then I worked "backwards" and eventually realized the required sequence of steps.

Brian Charlesworth - 5 years, 9 months ago

I suppose you forgot to mention an important condition --> Only one of the three steps can be applied at a time I kept on applying all three together and the sequence only got longer and longer

Sidrah Amin - 5 years, 8 months ago

1- replace (oo) with (xoo) three times (three steps ) you will have (xxxoox) 2- replace (xxx) with ox (one step) you will have (oxoox) 3- replace the first (x) with (xo) (one step ) final result is (oxooox ) sum of steps is five

Rizqi Okta
Sep 30, 2015

INITIAL: OOX, STEP 1: XOOX, STEP 2: XXOOX, STEP 3: XXXOOX, STEP 4: OXOOX, STEP 5: OXOOOX,

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...