Friday, May 31, 2013

Last Lectures in EPFL

MSE-461: Class got evicted from lecture theatre, finished the course in a pantry
MSE-470: Dude from WSU comes and introduces to the whole world the small boring town I was born in
BIOENG-442: Business as usual feeling
MICRO-565: Out-of-town lecture in Neuchâtel
MSE-466: Left early (still feeling a bit bad about it)
MATH-360: Won a prize
MATH-250: Everyone clapped when he finished reading from the slides. I don't know why, but I joined them

Monday, May 27, 2013


Question of Session 5: Dwellers of Flatplanet are hostile creatures. Their countries don't even share borders, but are well separated from each other. There are six countries in total, three of them are the Allies, and the other three are, not surprisingly, the Axis. For strategic reasons, each country is topologically connected. An embedded correspondent is informing us that the shortest distance from any of the Allies countries to any of the Axis countries is equal to 1 flatkilometer (a unit of length widely used on Flatplanet). Could she be right?

Assuming that our correspondent’s testimony is true, we model each Allied nation L1, L2, L3 as a topologically connected set of points in euclidean space. As has been provided, they do not share borders. We define sets of points L1+,L2+,L3+ as the points that are less than 1 fkm away and L1e, L2e, L3e as the points that are exactly 1 fkm away from the nearest point in L1, L2, and L3 respectively. We also define the sets X1, X2, X3, each representing a topologically connected piece of Axis territory.
Now we can remodel the map as a graph G containing the points l1, l2, l3, x1, x2, x3 with the following rule: If the set Xn shares at least one point with the set Lme (and does not share any point with Lm+), then there is an edge xnlm in G. Given the known information and the testimony of our correspondent, every edge xnlm (n,m∈{1,2,3}) is an edge existing in G. The resultant graph turns out to be identical to the complete bipartite graph K3,3.

K3,3 represents the countries of Flatplanet situated on a topological surface. Each edge in the graph K3,3 corresponds to a set of “border” points shared between a set Xn and a set Lme. No two Axis countries share the same points. It follows that for the correspondent’s testimony to be true, K3,3 must be a planar graph with no intersecting edges.

Proof that K3,3 is not a planar graph
We aim to prove by contradiction that K3,3 is not a planar graph. Assume that K3,3 is a planar graph, then Euler’s polyhedral formula holds: |V|-|E|+|F|=2. As the number of vertices |V|=6 and the number of edges |E|=9 in this case, we obtain |F|=2-6+9=5.

As there are no loops and two edges connecting the same pair of points, there cannot be a face with only one or two edges. As no two points on the same side are connected, there are also no closed paths that can be achieved by just three edges, as points that are two edges away from each other are always at the same side of the bipartite graph. However, a closed path l1→x2→l2→x1→l1 of 4 edges can be found in the graph. Hence, a face in the graph can only be inscribed by 4 or more edges.

We have determined that |F|=5. Then the sum of the edges of each face can only be equal to or greater than 5×4=20. As each edge can be shared by a maximum of two faces, the number of edges |E|≤20/2=10, with |E|=10 being the case in which all edges are shared.

However, we have already established that |E|=9. We have arrived at the contradiction by assuming that K3,3 is planar graph. Hence, K3,3 is not planar. By our earlier model, it implies that it is not possible for every Allied country on Flatplanet to be exactly 1fkm away from every Axis country, and that our correspondent’s testimony is false.

Another proof that K3,3 is not a planar graph
This should be much less painful to follow. You can ignore the previous section now

(24 Mar 2013, Dorigny in the Switz)

Saturday, May 25, 2013

Baron Münchhausen

Question from Session 3: Baron Münchhausen is very proud: "I chose a huge set of positive integers smaller than 2013, and yet among any four elements there are two such that one is divisible by the other." He went on boasting to his stupefied audience: "I bet no one could ever find such a set with more elements." However, the infamous storyteller was exaggerating again. The set he had found was rather small. Help him find a set that could save his honor.

Definition of the problem
We are tasked to construct the largest set of numbers such that
1. It is a subset of the set of natural numbers larger than or equal to 1 and less than or equal to 2013.
2. For any four numbers selected from from the set, there is at least one selected number which is divisible by another selected number.
If Baron Münchhausen makes a bet that no one can find a set larger than this set that we will constuct, it will not be possible for him to lose.

Solving the problem with paths
Let us rethink the set of all natural numbers from 1 to 2013 as a directional graph. Each number n is represented by a vertex vn. A vertex vn connects to another vertex vm only if m is divisible by n. For example, one such possible directional path in this graph would be:

The path terminates at the vertex where it is not possible to multiply the number with any other number (picked from 2 to 2013) without producing a number larger than 2013. In the case above, 2772 * 2 = 5544 (> 2013).

For any two numbers picked from the path, the larger one is divisible by the smaller one. This is because we constructed the graph in a way that a vertex on a path is divisible by all its predecessors.
In order to satisfy the condition that for any four numbers chosen in the subset, one of it is divisible by another, we should construct a subset such that all the numbers can fit into three paths. In order to find the largest subset, we should construct the three unique paths that are as long as possible.

Finding the three longest possible unique paths
To find the longest path i.e. the path containing the most number of numbers below 2013, we have to let each successive number on the path be the smallest multiple of its predecessor. This would yield m=2n for every connection vn→vm. We use the smallest number of the set, 1, as the starting vertex for this path:

As 1024 * 2 = 2048 > 2013, the graph terminates. 1024 being 210, this path has 10 + 1 = 11 vertices.

The second longest path uses 3 as the starting vertex, as the numbers 1 and 2 are already included in the first path. As in the last path, we make each successive number in the path to be two times its predecessor:

As 1536 is 3 * 29, this path has 9 + 1 = 10 vertices.

The third path uses 5 as the starting vertex, as the multiples of 4 are already included in the previous two paths. Again we make each successive number in the path to be two times its predecessor:

As 1280 is 5 * 28, this path has 8 + 1 = 9 vertices.

We thus obtain the set of 9 + 10 + 11 = 30 numbers from the above three paths
{1, 2, 3, 4, 5, 6, 10, 12, 16, 20, 24, 32, 40, 48, 64, 80, 96, 128, 160, 192, 256, 320, 384, 512, 640, 768, 1024, 1280, 1536}
For every 4 numbers that are chosen from this set, two will land on the same path.
If two numbers land on the same path, then one number out of the two is divisible by the other. This is just how we have constructed the paths in the first place. So for every four numbers chosen, at least one number is divisible by another in the set.

Also by our construction, this is the maximal set. If the baron had chosen this set instead of whatever he had chosen before, his challenger can never find any larger set of numbers to fulfill the same mentioned criterion.

(13 Mar 2013, Dorigny in the Switz)

Friday, May 24, 2013

Card Trick

The start of a series of bonus questions and solutions done in the Graph Theory course at EPFL (MATH-360)

XDA Wallpapers

Question from Session 2: Two people perform a card trick. The first performer takes 5 cards from a 52-card deck (previously shuffled by a member of the audience), looks at them, keeps one of the cards and arranges the remaining four in a row from left to right, face up. The second performer guesses correctly the hidden card. Prove that the performers can agree on a system which always makes this possible, and devise one such system.

Let us assume that the 52-card deck consists of 4 suits of 13 cards. Let us label the decks C for clubs, S for spades, H for hearts and D for diamonds. A suit X has elements x1, x2, x3, …, 13 that denote the 13 cards in each deck, the subscript being the number value of the card.
Between cards of the same deck, a card with a higher number value has a higher “deck value” (so c2 is more valuable than c1). Between cards of different decks, spades are the most valuable, followed by hearts, diamonds, and clubs.

Guessing the suit of the hidden card
When player 1 (P1) draws a set of five cards from the pile, it is impossible to have every card of a different suit, as there are only 4 suits. Given a suit X with at least 2 cards in the drawn pile which are xn and xm, it is possible for P1 to choose xn as hidden card, and then to place xb as the r-th card in the row (r is predefined and can vary so as to make the trick harder for a spectator to figure out) as a signal to the P2 that the hidden card is of the suit X.
For example, if r=1, X=C, then P1 can choose to make the arrangement

Guessing the number on the hidden card
Next, the number on the revealed card xm and the identities of the other three cards a,b and c are used to communicate the number n of the hidden card. For this, the performers can make use of a graph consisting of a cycle C of 13 vertices v1, v2, v3,…, v13, one for each number value of the card as follows:

The cards a,b and c are defined by P1 and P2 as their deck value, so that a < b < c. Based on how a,b and c are arranged in the row (ignoring xm), P2 starts from the point on the graph with the number value m and then moves along the cycle according to the key:

This is because in C, it is possible to reach any vertex from a start point by a maximum of 6 steps (i.e. after covering 6 edges), as demonstrated below:

P1 should pick xn as the card to hide if it is possible to travel clockwise on C from vm to vn within 6 steps.
With these rules, the suit, as well as the number value of xn, can be unambiguously determined by P2 from the 4 cards displayed by P1.

Overview of performance (Example)
P1 draws 5 cards from the shuffled pile. He draws a set of cards {h1, c13, s1, s3, h8 }. 2 hearts and 2 clubs are present in the 5 cards on his hand. P1 chooses Hearts as the suit of his hidden card.
As it is possible to travel clockwise on the cycle from v8 to v1 within 6 steps, but not possible to travel clockwise on the cycle from v1 to v8 within 6 steps, P1 can choose to hide h1 and display h8 in the leftmost position in the row:

P2 now knows that the hidden card belongs to the suit H.
To instruct P2 to find out the number value of the hidden card, he fills up the remaining positions of the row with the remaining cards in the order (c, b, a), where a has the lowest deck value and c has the highest deck value. In this case, the sequence (c, b, a),  yields (s3,s1,c13). So P1 displays:

By comparing the deck values of the rightmost 3 cards, P2 now understands that he must make six jumps from vertex v8 on C in the clockwise direction. He does so through a mental calculation and arrives at v1. He now knows that the hidden card has a number value of 1. With this information in hand, he deduces that the hidden card is h1, or Ace of Hearts.

(28 Feb 2013, Dorigny in the Switz)

Wednesday, May 22, 2013

Nicknames I gave to things

The Switz - Switzerland
The Lux - Luxembourg
The Liech - Liechtenstein
Czechland - Czech Republic
Unicorn Skittlefarts Land - Sweden
Dudetown - Dudelange (the Lux)
Dootztown - Vaduz (the Liech)
I-forgot-what-this-place-is-called - Paris

Swiss Cheese - Rolex Learning Center EPFL
Kangaroo Clacks Tunnel - Renens Gare CFF Underpass
Harpist's Tunnel - Same underpass, but more recent
Earthworm Path - Dirt path from Marcolet to Epenex Metro Station
Gangster Path - Rue des Alpes, Crissier and Renens