Joao Ferreira

I was going through my to-do list, and I've noticed that I had an item named "explore vox.com account". I've then logged in and, after joining some interesting groups, I decided to write my first post. I don't really know if I'm going to post here regularly (I already have a blog that is not usually updated -- shame on me!), but at least I can try to write something that allows me to test minimally Vox.

Now, as first post I'm just going to share with you a simple problem that admits a very nice and elegant solution. You can find it in the first chapter of A.J.M. van Gasteren's PhD thesis "On the shape of mathematical arguments" (you should be able to find a link to the book from my book list located at the right column).

So, citing A.J.M. van Gasteren, the problem is:

We are requested to provide an argument for the termination of the following game: a finite bit string (i.e. a string of zeroes and ones) is repeatedly transformed by replacing

• a pattern 00 by 01  , or
• a pattern 11 by 10

whenever in the string and as long as such transformations are possible.

Rephrasing the problem: if you start with a finite bit string and if you apply the rules above continuously and for as long as possible, will you ever stop? For instance, if we start with the bit string "1110", we could apply the following transformations:

• "1110" -> "1010"  , or
  
• "1110" -> "1100" -> "1000" -> "1010"