Solution to Math Puzzle

A few days a go I posted a math termination puzzle. There was one reply with the draft of a solution, so now I am posting the solution from Communications of the ACM here. It is a little involved, so beware. Here it is:

Let x0, x1, x2, x3, x4 be the five numbers. summing to s > 0, with indices taken modulo 5. Define a doubly infinite sequence z by z0 = 0 and zi = zi-1 + xi. The sequence z is not periodic, but it is periodically ascending; z5 = zi + s. In the example, the x values are 2, 4, -3, 1, -3; s = 1; and the z sequence is:

... -2 0 4 1 2 -1 1 5 2 3 0 2 6 3 4 1 3 7 4 5 2 4 8 5 6 ...

where the leftmost 0 represents z0.

If xi is negative, zi < zi - 1 and flipping xi has the effect of switching zi with zi - 1, they are now in ascending order. Simultaneously, it does the same for all paris zj, zj - 1 whose indices are shifted from them by multiples of 5. Thus, flippling labels amounts to sorting z by adjacent transpositions.

Tracking the progress of the sorting process needs a potential function Phi to measure the degree to which z is out of order. Let i+ be the number of indices j > i for which zj < zi; note i+ is finite and depends only on i modulo 5. We let Phi be the sum 0+ + 1+ + 2+ + 3+ + 4+.

When xi+1 is flipped, i+ decreases by 1, and every other j+ is unchanged, so Phi decreases by 1. When Phi hits 0 the sequence is fully sorted so all labels are non-negative and the process must terminate.

We conclude that the process terminated in exactly the same number (the initial value of Phi) of steps regardless of choices, and the final configuration is independent of choices. The reason is there is only one sorted version of z. Moreover, the proof works with 5 replaces by any integer greater than 2.

So, there you have it. A very interesting solution, the key here is the function Phi, which decreases by 1 after every flipping, because of the way the sequence was constructed :-) Very nice. I must confess that I wasn't going this way about it. My Phi function was turning more complicated, but the real trick here is the sequence, which transform the problem into a sorting problem, simplifying the Phi function quite a bit.

A Piece of Art

I finally got around to playing Prince of Persia, which was actually released last December. All I can say is, wow, what a game. I loved it. The controls are tight, gameplay is fun and fluid, graphics are top, great art design... what more can you ask for in a game?

There has been a lot of discussion on the internet, especially from the so-called (and self-proclaimed) hardcore gamers, about how easy this game is, and how Ubisoft dumbed it down compared to previous entries in the series just to appeal to a casual audience. Well, I am what you could call hardcore gamer, but I prefer Krpata's taxonomy, under which I am a Skill Player (rather than a Tourist Player), with more Completist than Perfectionist tendencies, but fall into the Premium Player category when it comes to the time I can spend on video games, due to my lifestyle (you know, I have this thing called a job, and a family). With this I am trying to say, I play video games, and I play them a lot, to the extent I can. I know about video games. And in the case of Prince of Persia, I think all those gamers out there, complaining about the game, don't have a strong case.

If you ask me, the issue with Prince of Persia is more psychological than it is factual. The whole thing comes from, I think, the idea that you don't die in this game. Like somehow there's no consequence to playing, and that makes the whole experience worthless. Most gamers were flaming the game on these grounds even before it was out. Well, after playing and finishing the game, in my opinion, this game is as easy or as tough as Prince of Persia: The Sands of Time. And to even make my point, I played both, side by side, and I can tell you, at points, the new PoP felt more challenging. The only thing that could be said against the new PoP is that it is way shorter than PoP:TSoT, which might give the illusion that the old game is tougher because you spent more time on it.

Somehow, if you're not faced with a Continue or a Load Last Save screen, then there's no consequence to failure. In PoP, instead of this annoyance you're just returned to the last checkpoint, which is the last platform you were standing on. Between this, and having to look at a screen, select Yes and have to wait for the game to load the same area I was in just 30 seconds ago, I'd rather have what they implemented in PoP, and I applaud Ubisfot for that, and I hope this becomes a trend in the video game industry. If when I'm fighting an enemy, failure means I have to reload the last checkpoint, and wait for the area to load, which places in the same spot I was at the beginning of the fight, with the enemie's health replenished... or just have me stand up and continue, but simply replenish the enemie's health... I choose the latter. Does that make it easier? I don't think so.

The psychological bias and predisposition goes so far, that I even read comments from people saying how easy the platforming was now, that you just had to "sit back and press buttons... no skill required". Comments like these is what made me play the two games side by side. I had play PoP:TSoT before, but it had been a while, and I wanted to make a fresh comparison. And my discovery was that the platforming gameplay is the same. Yeah, when a stunt sequence starts, it usually becomes a task of timing button presses, pretty much not using the directional stick, on both games. The skill set required to play PoP is the same one required to play PoP:TSoT.

In my book, Prince of Persia is a 9/10. A jewel of gaming. And I hope Ubisoft keeps it up with games like this.

A Termination Puzzle

Here is an interesting puzzle I saw in the print version Communications of the ACM. See if you can solve it and let me know of your solution in the comments:

Five integers with positive sum are assigned to the vertices of a pentagon. At any point you may select a negative entry (say, -x) and flip it to make it positive, or x, but then you must subtract x from each of the two neighboring values; thus, the sum of the five integers remains the same. For example, if the numbers are 2, 4, -3, 1, -3 [in that order on the pentagon's vertices], you can either flip the first -3 to get 2, 1, 3, -2, -3 or the second to get -1, 4, -3, -2, 3. Now prove that no matter what numbers you start with and strategy you follow, all the numbers will eventually become non-negative, and thus the procedure terminates after finitely many steps.

Now, be honest and don't go all over the internet looking for the solution. I have the solution in the magazine, but I haven't looked at it, and will be trying to solve it myself :-) But it's good to know that I have the solution somewhere and have a standard to compare against. Now show your mathematical might! :-)

The Elusive Particle

Looks like the Higgs particle becomes more and more elusive. Results from experiments at Fermilab have ruled out a mass between 160 and 170 GeV. This of course narrows the search for the upcoming experiments at the Large Hadron Collider, but as they keep finding these no-go windows, the idea of succeding in finding this particle seems more uncertain. Also, a consequence of all these is that the remaining ranges seem to be harder to search, because the implication is that the Higgs particle would not be as massive as expected (below 160 GeV), which makes it harder to spot.

I have a pop drink riding on this, so they better find it! :-)

Happy Birthday to me

My birthday is not today, it was actually two days ago, on March 14th. I didn't do anything special, some friends came to my place and we hung out all day, playing video games, eating pizza, and just having a good time. But I just found out the US congress gave me a great birthday present, as March 14th has been recognized as Pi day :-) (3.14, get it?). I guess I had never myself realized the relationship of my birthday to this irrational number, but it's very cool nonetheless :-)

I hope you had a great Pi day. I know I did :-)

Our Obstinate Obsession to do Things the Wrong Way

In a previous post I talked about voting machines and how I think the government has made a big mess about the whole thing. I mentioned that academia has already set forward useful guidelines, and resourceful information about this subject, but no one seems to listen. Then I ran into this article. The article basically explains how computer scientist from that Harvard School of Engineering and Applied Sciences and the Université Catholique de Louvain, deployed a Web-based voting system, which was tested for the presidential elections at UCL. The system is mathematically verifiable. It is open source. It is also free, as is free beer. When I say mathematically verifiable, I mean the system produces a mathematical proof, which cannot be spoofed, that the tallying was done correctly.

Furthermore, the tallying process is completely open, that is, any person from outside can come in and verify that there are no irregularities. This is possible because of the encryption scheme used that ensures that no sensitive information is released. All of this sounds wonderful, yet somehow I know it would never be picked up... why not? Because it doesn't cost money.

I think this society, in its capitalistic frenzy of spending like the world is going to end, has evolved into a mindset that associates anything worthwhile with money. If it doesn't cost, it must not be good. Why else, having some of the best academic institutes on earth, hasn't the government turned to the people who actually know, instead deciding to pay all this money to companies that are basically producing a bunch crap? I guess if you pay for it, it's good crap. Yet, it is crap nonetheless!

The only thing I don't like about the system above is the absence of a paper trail, and yet, in this particular system, because of the openness of the process, I thikn it would work without a paper trail... but in these things I always say better safe than sorry.

Turing Award - Barbara Liskov

The ACM announced the winner of the Turing Award, and it went to Barbara Liskov. Now, for those of you who don't know, the Turing Award is the equivalent of the Nobel Prize in Computer Science. Because of my work, I happen to be very familiar with Liskov's work, specially her work on Behavioral Sub-typing. Her book Abstraction and Specification in Program Development is a seminal work in the area of specification of object oriented programs, and specification refinement.

Congratulations to Dr. Barbara Liskiv for her well deserved recognition.

Watchmen

If you haven't watched this movie, I really recommend it. I never read the graphic novel and I've heard the movie is very loyal to the source, so I guess the credit goes to the comic - so I guess the movie made me want to read the comic :-) The movie touches some interesting aspects relating to the human nature, just as The Dark Knight did, and well, I just love any piece of art that makes me think.

If you haven't seen the movie, and you're planning to see it, stop here because there are some MAJOR SPOILERS AHEAD.

The most interesting plot piece the movie has to offer, in my opinion, is the state of affairs of the movie's universe at the end of the film. Without going into much detail, one of the heroes, who is known as "the smartest man in the world" (rightfully so) is the one responsible for the planning of armageddon, sending the world to the brink of nuclear annihilation. When the other heroes find out, they try to stop him... but it's too late, he's always one step ahead of everyone. I like the line where he says "Do you think I'm so comic book supervillain? Do you think I would tell you my plans if you had the slightest chance of stopping me? I triggered everything 20 minutes ago... it already happened". He destroys several major cities in the world, not with bombs, but something more devastating that basically vaporizes everything. It all looks like the work of one of the good heroes, as this is the kind of power he wields.

And here's where the moral conundrum comes. The world thinks the other hero did it (a hero called Dr. Manhattan). And so the world, that was about to go into nuclear war, after this event, goes in peace to unite against this new enemy, and they vow to fight Dr. Manhattan. This was the plotter's plan all along... he knew this would happen, and this is how he saw he could achieve real lasting world peace. He now suggests to everyone that they should now support him and condone the lie, that Dr. Manhattan has to take the blame and go into exile for the good of humanity, that his plan, despite the deaths of millions of people, worked, and was the right thing to do. Dr. Manhattan agrees... but another hero, called Rorschach says people have to know the truth, that this is no way to achieve world peace... this was a massacre. The remaining heroes are on the line... Rorschach tries to leave, but Dr. Manhattan cuts him.

Now, Dr. Manhattan is this all powerful being that can do pretty much everything. Rorschach says "Never compromise... not even in the face of armageddon". He basically tells Dr. Manhattan that people need to know, and he's going to have to kill him, because otherwise he's going to tell everyone what happened, and Dr. Manhattan says he can't let him do that, as he thinks this will put the world back where it was, eventually ending in total destruction. So Rorschach tells him "So this is it?... one more body to lay on the foundations where you'll build your world peace?... Do it!", and... Dr. Manhattan vaporizes him... The movie ends with Dr. Manhattan going into exile to another galaxy, the other heroes keeping silent, and a journalist finding the Rorschach's journal.

So, as I did before in the post about Fable 2, I ask you now... what would you do? What do you think is the right choice here? I mean, after everything has been done, would you keep quiet for the benefit of this peace? Or do you think it is important to tell the truth about what happened, whatever consequences that may carry? Are you a Dr. Manhattan or a Rorschach? Please comment and elaborate on your reasons :-)

I will say where stand in a later comment and why.

Seriously? A DELETE button?

Recently I ran into this article concerning the findings of a three months investigation regarding problems with voting machines in California. Now, I've had discussions with some of my friends, in particular with Scott Harmon, about all the problems with voting machines, and why it's just something very hard to get right, but the people involved in the design of the machines discussed in this article seemed to be working very hard to get it wrong. According to the findings of the investigation, they put a button, which by the way was next to the one used to request a print, that basically deletes logs. That's right, it deletes the log from the memory, even if it hasn't been printed and there's no paper trail. What's better is that it doesn't even prompt you with a message asking you whether this is something you really want to do... nothing! It just deletes the log as if nothing happened.

Now, what were they thinking? Hasn't all the debate and discussions about the problems with voting machines reached the people that are actually making them? And why, oh why, didn't anyone notice this until now? Now, after it was used in an election and there was a loss of about 200 ballots (according to the article). I mean, really? So, you're meaning to tell me nobody thought this was not a good idea!

There has to be a problem of miscommunication here. The academia has put out many articles in the past couple of years, where experiments and extensive studies have been done, and things like this have been pointed out as big problems. Yet, you still have to see this in the news, as if the work of those people never happened. It looks as if the only people looking at that work (which is payed for with taxpayers money by the way) are us, the geeks, and the rest of the world seems to be oblivious to all this information... until something bad happens.

*sigh* Seriously, my hopes for humanity decrease by the day... Hopefully, now they will start listening to the computer scientists and designing these machines with all these problems in mind, from the get go... yeah right, what am I even saying? Sometimes I think they put that delete button on purpose. What's even hilarious is that it took a three months investigation to notice a delete button in the machine :-).