When the Minister of Culture and Sport wrote in this tweet in 2010
He probably spoke his mind more freely than he does now.
Like the minister, I can’t stand football. Franco used it to stun the public, but only on Sundays. Now, in a democracy, the torture is daily.
What bothers me most is that, in relation to football, the media only talk about mathematics when the league is coming to an end. Mathematically Lleida has been relegated, or mathematically Barcelona has won the league.
And I think, what idea do they have of mathematics? What a theorem! All you have to do is do four calculations and you have the proof.
But, a few days ago, I came across the following news:
The problem of determining the elimination of a team in European football tournaments is NP-hard.
How, I said to myself, NP-hard? That means that whoever solves the overall problem will get a million dollars from the Clay Institute!! (ver Claymath/p-vs-np-problem).
I then searched for the article where such a prodigy is explained:
Thorsten Bernholt, Alexander Gülich, Thomas Hofmeister, Niels Schmitt, Football Elimination is Hard to Decide Under the 3-Point-Rule.
The authors are from the University of Dortmund in Germany. Disbelieving, I started reading and something didn’t add up. The 3-Point-Rule is that if they draw, each team gets 1 point, but if one of them wins, then that team gets 3 points. I thought it was 2 points. I asked a colleague and he replied that they changed the rule some time ago. I have played football only once, as a kid, and I scored a goal, but in my own goal. Since then I have tried not to listen to anything related to football. But the media pressure is such that I haven’t managed to do so, and I can name almost the entire Barcelona line-up. And I even know who Piqué is and why he is relevant.
So they changed the way they allocate points. And very wisely because, as I read in the article, with the 2-Point-Rule the problem is not in NP but in the P class of silly problems. Just like with baseball tournaments in the USA. It seems that the people who changed the rule, had the intuition that \(P\ne NP\), and that the league would be much more interesting with this new rule.
What is the problem? We have a set of teams, each with a number of points scored in the games already played, we have a set of pairs of teams, corresponding to the remaining games to be played; we now select a team A, and the problem is to decide whether it is possible for team A to win the tournament and become the champion.
The problem is in class NP because someone who wants to prove that A can be the champion only has to show a set of results of the matches to be played and show that with those results A would be the champion. This does not mean that finding the results is easy.
That this problem is NP-hard means that, given any other example \(H\) problem that is of type NP, i.e., whose positive solution has a quick way of being proved, I can imagine an example of an unfinished tournament and a team A, so that A is champion in this particular game is equivalent to \(H\) having a positive solution.
That is, whoever knows how to solve this kind of football problem, will know how to solve any other NP-problem. For example, he will know how to break all the keys that banks use nowadays, which is also an NP problem.
One last interesting thing I read in the article. In case each team has only two or less games left to play, the problem becomes silly again. And I get the impression that when people start saying: Mathematically Barcelona are champions, it’s when there are only two rounds left to play. As easy as that.
Leave a Reply