After all the practice of the past week, my average time has come down to about three and a half to five minutes. My personal best time is two minutes and 53 seconds. Interestingly, my daughter has also improved considerably, and in fact, her personal best time is two minutes and 33 seconds! Her average is no better than mine, but she got lucky once, and has a better personal best time than I have. I am wearing the cube and my fingers out trying to beat the record and take the title back from her!

I was actually wrong last week about the world record being 29 seconds. It turns out that the world record for solving the 3x3 cube is 5.66 seconds! That is less than the time it takes me to put together even a couple of cubes on the top side of my scrambled cube!! Oh well, the world record is quite safe from me as of now.

Anyways, I had posted a puzzle last week that illustrates isolation. As promised, here is the solution to that puzzle. The way to think about this is as follows: any cell in the table which is flipped an odd number of times changes from a 0 to a 1 or vice versa. Any cell which is flipped an even number of times remains what it was (a 0 remains a 0 and a 1 remains a 1). So, the idea is to flip every cell in the table zero or an even number of times, and flip just the cell (3,3) an odd number of times.

After some thought, you will realize that one way to accomplish this is to flip every cell in the row and column in which (3,3) is located exactly once. That way, cell (3,3) is flipped 7 times (an odd number of times), every other cell in row 3 and column 3 of the table is flipped 4 times (an even number of times), and all other cells in the table are flipped 2 times (an even number of times).

The sequence of flips is shown below. The original table is as below:

1 | 0 | 1 | 1 |

0 | 0 | 1 | 0 |

0 | 0 | 1 | 1 |

1 | 1 | 0 | 1 |

We start by flipping each element in column 3 first. After cell (1,3) is flipped, the table is as below (remember that every cell in the row and column in which the flipped element is present is also flipped):

0 | 1 | 0 | 0 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 1 |

1 | 1 | 1 | 1 |

Now we flip cell (2,3) to get the table below:

0 | 1 | 1 | 0 |

1 | 1 | 1 | 1 |

0 | 0 | 1 | 1 |

1 | 1 | 0 | 1 |

Now it is the turn of cell (3,3) to get flipped:

0 | 1 | 0 | 0 |

1 | 1 | 0 | 1 |

1 | 1 | 0 | 0 |

1 | 1 | 1 | 1 |

We move on to cell (4,3):

0 | 1 | 1 | 0 |

1 | 1 | 1 | 1 |

1 | 1 | 1 | 0 |

0 | 0 | 0 | 0 |

Now, we flip each element in the third row of the table. This is the state after flipping cell (3,1):

1 | 1 | 1 | 0 |

0 | 1 | 1 | 1 |

0 | 0 | 0 | 1 |

1 | 0 | 0 | 0 |

Now, we flip cell (3,2):

1 | 0 | 1 | 0 |

0 | 0 | 1 | 1 |

1 | 1 | 1 | 0 |

1 | 1 | 0 | 0 |

And finally, we move on to cell (3,4). Remember not to flip (3,3) twice. We flip each element in the third row and third column of the table exactly once:

1 | 0 | 1 | 1 |

0 | 0 | 1 | 0 |

0 | 0 | 0 | 1 |

1 | 1 | 0 | 1 |

Now, compare this last table to the first table. You will see that all the cells are exactly the same except for cell (3,3) which has been flipped from a 1 to a 0. Which was precisely the objective of the puzzle!

Can you find a shorter sequence of steps to accomplish the above transformation? I would love to hear it if you manage this in fewer steps. In a 4x4 table, this transformation took 7 steps. In a 2n x 2n table, this transformation takes 4n - 1 steps, which gets tedious for larger tables.

The more interesting challenge is to try to accomplish this in a square table with an odd number of elements per side (for example, in a 3x3 or 5x5 table). I have not been able to find any sequence of steps that will flip just one cell in such a table (obviously, it is trivial in a 1x1 table, but I am talking about tables that are true tables rather than a single element). If you come up with a set of steps to flip a single element in such a table, I would be very interested in hearing about it. Post your solution, if you find one, in the comments below.

In fact, the procedure above works for non-square tables also. The only condition is that each side of the table should have an even number of elements. So, the method would work perfectly fine on 4x10 tables, 14x40 tables, and so on. But if one or both sides have an odd number of elements, the procedure fails. So, it is no good on 5x3 tables, 15x30 tables and so on. It would be really good if a solution existed for odd-sided square tables, and the procedure could be extended to non-square tables without much additional thought. Good luck!

Obviously, there are similarities between this puzzle and what happens in a Rubik's Cube (when you try to change the position of one small cube, a whole layer of cubes moves), but also differences (it is not as simple as changing a 0 to a 1 or vice versa). The trick is to figure out isolation sequences for the cube which accomplish the changes you want while avoiding changes you don't want. The mathematics of it are interesting, but also quite challenging. I am just starting to read up on it. I will keep you posted as to how it goes.

## 1 comment:

Hello, thank you for sharing this powers of 2 knowledge for all, it can help me think out of more, so if you want to learn more on it easy step check for more what powers of 2 learning here.

Post a Comment