Happy new year! We are no longer in a prime year, but here’s a picture to cheer you up.

Enough said.

Skip to content
# Math Sanctuary

Random
# Happy 2018!

Analysis · Mathematics
# Banach Fix Point Theorem

Random
# New Favourite Place

Mathematics · Topology
# Dense and Nowhere Dense Sets

Uncategorized
# Introduction Day in ETH Zurich

Nom nom noms · Random
# Food in Zurich

Game Theory · Information Theory
# The Devil’s Chessboard (Problem)

### The Game Setting

Mathematics, food, fun, and insanity!

Happy new year! We are no longer in a prime year, but here’s a picture to cheer you up.

Enough said.

Advertisements

Banach fix point theorem is a very powerful tool in mathematics, in particular, in functional analysis and in operator theory. I was studying for functional analysis earlier this weekend and came across it once again, even though I did not see it coming. We will first look at a few definitions, and then the theorem itself.

Let be a metric space. A map is called a

contractionif ; it is called astrict contractionthe inequality is strict, or equivalently, if there exists such that .

As the name suggest, Banach fixed point theorem is a tool to find fix points for contraction mappings in complete metric space, and hence Banach spaces. The statement of the theorem is as follows:

Suppose is a complete metric space. If is a strict contraction, then there exists a unique such that . Furthermore, for any $x_0 \in X$, if we set for all , then .

The proof on Wikipedia is pretty concise, so we will not talk about it here. It is often used in differential equations to find fixed points of the equation itself. There is yet another clever application that I encounter earlier this weekend, it is used in a theorem by Stampacchia in functional analysis. Maybe we will talk about it next time.

Found a neat properties for dense and nowhere dense sets in functional analysis assignments recently. Suppose is a topological space, and is an arbitrary subset. We say that is dense if the closure is the whole space itself, i.e. ; we say that is nowhere dense if the interior of its closure is empty, i.e. .

Now, we can also think about closures and interiors in terms of their complement. We shall denote by to be the complement of instead of the usual ; the reason is obvious once we get to the main part, I promise.

Usually in topology, the interior and closure of a set , are defined to be the union of all open sets contained in , and the intersection of all closed sets containing respectively; in other words, they are the largest open set contained in , and the smallest closed set that contains respectively. In terms of complement, we have the interior and , this is not hard to prove.

If is dense, then the complement has empty interior. We have

This is not surprising and is pretty standard. On the other hand, we claim that is nowhere dense if and only if its complement contains an open dense subset of . This is slightly more work, we have

And since the interior itself is an open set, hence is the open dense subset we desired.

This is pretty useful result when trying to prove Baire Category’s Theorem, or for an application of the Baire’s Category Theorem. All the best doing your assignments!

Long story short, masters students get to skip bunch of ridiculous games and events and get straight to the point – Yes, we had free beers since lunch until 5 pm. Enough said.

Everything in Zurich is expensive. This is a general statement from a lot of people that had been to Zurich when you first ask them about Zurich. As a student, that is a total nightmare, as one has to spend approximately 1750 CHF/month (current conversion rate as of writing: 1 CHF = 1.0584 USD) to live in Zurich.

Luckily, for the first week I arrive in Zurich, I manage to spend only 7 CHF per meal on average ~~some meals are cheap because student pricing provided by ETH Zurich and University of Zurich, but that is not the point~~. Perhaps adjusting my diet and eating local food helps. Generally, following locals’ food habit is a good way to save money.

One other complaint that I hear from ~~Asian~~ people is that the bread are really hard compared to the ones in Asia. I’d like to point out that there are literally **hundreds** of breads to choose from. There will be the types of bread that you are looking for if you look hard enough. Alternatively, you can try each and every bread to decide which bread has the best taste and texture; ~~by the time you try all of them, you will already get used to eating bread~~ usually by the forth or fifth bread, you have a general idea of how hard each bread is just judging by its skin and the colour.

Visit Migros (Some market that is like Walmart, but better quality. Perhaps like Valumart in Ontario, Canada) for cheap food, they alternate the deals every now and then so that poor students like me can get a change of flavour once in a while. There are also tricks in getting quality food in these markets, as long as you know how to ask, and where to look at. Some of the generic/off brand food actually taste as good as named brands, but costs half as much. For these brands you kinda have to try it and try your luck. Most of them taste pretty good though.

Finally, if you are a student, perhaps going to events is a good idea. These events will not feed you until you’re full, but at least you will not feel hungry in the middle of the day and have to spend a fortune for a sandwich. Or you can just take extra from the event and call it your dinner.^{Just kidding. Actually, don’t do it.}.

DISCLAIMER: NO GOD, DEVIL, OR ANY SUPERNATURAL BEING OF ANY KIND IS HARMED IN THE PROCESS OF PRODUCING THIS ARTICLE. VIEWER DISCRETION ADVISED.DISCLAIMER: NO GOD, DEVIL, OR ANY SUPERNATURAL BEING OF ANY KIND IS HARMED IN THE PROCESS OF PRODUCING THIS ARTICLE. VIEWER DISCRETION ADVISED.

The Devil’s Chessboard is an information theory problem in game theoretic setting. As one may or may not have heard before, the Devil’s Chessboard is a rather intimidating problem, or at least when one first learns about the problem. If one attempts to play the game (with the Devil) without any kind of strategy or by using pure luck, it is rather impossible to win the game as the probability of choosing the correct move is (or about 1.56\%).

Furthermore, the problem can be extended to larger grids, which decreases the chance of choosing the correct move exponentially, if we choose to play the game by using only luck. In fact, some of these game theoretic problems does not even have a winning strategy (Note: Simply put, a winning strategy is a strategy in which the player(s) is(are) guaranteed to win.); in case a winning strategy exists, what is it; if the winning strategy does not exists, what is the best strategy to tackle the problem. In this article, we are going to examine the Devil’s Chessboard, and come up with the best strategy to play the game.

Imagine this. You and a friend both studies mathematics in your undergraduate studies. Envying your ability to reason, God decided to send both of you to the Devil. Contrary to the legend, the Devil did not send both of you to burn for eternity immediately. Instead, he would like to play a game with you. If both of you win the game, then you will be released and proceed with life. Otherwise, you will suffer for the rest of the eternity.

The game is as follows: there is an isolated room in which no communication to the outside realm is possible. In the center, there is a table, and on top of the table there is a chessboard. You and your friend are to follow the Devil one at a time into the room, where further actions will be taken. For simplicity, we will refer to and as first and second person that enters the room respectively.

Once and the Devil are in the room, the Devil will perform the following steps:

- Seal the door (presumably with magic) so that no communication to the outside world is possible.
- Make 64 coins identical in colour, weight, etc magically appear on top each square of the chessboard; since it is done by magic, you cannot interfere with this process.
- The Devil then points at a square at random, and mark the position of the square on the chessboard as a proof; of course, the mark is invisible to human naked eye until the game is over.
- is allowed to flip one coin on the chessboard, should s/he chooses to.
- will be lead out of the room to avoid any form of collusion with $B$.

During this whole process, is to remain silent, otherwise both of the players will be sent to Hell for eternity immediately.

Now will enter the room with the Devil. After the Devil seals the room (again, with magic), will get a chance to examine the board and then to pick a square on the board. If s/he choose the exact same square the Devil did, then both players are released immediately. Otherwise, both of you go to Hell. Finally, the Devil agrees that he will not cheat by manipulating the marked square; hoping that you succeed and to annoy God, the Devil allows you and your friend to have a discussion to come up with a strategy before the game starts.

Is there a winning strategy in which you and your friend will be guaranteed freedom? If there is, can you find out what the strategy is? If not, what would be the best strategy to maximize the probability of escaping Hell? The solutions will be posted next time.