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

Flatplanet

https://twitter.com/flatplanetHQ

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?

Model
Assuming that our correspondent’s testimony is true, we model each Allied nation L₁, L₂, L₃ as a topologically connected set of points in euclidean space. As has been provided, they do not share borders. We define sets of points L₁⁺,L₂⁺,L₃⁺ as the points that are less than 1 fkm away and L₁^e, L₂^e, L₃^e as the points that are exactly 1 fkm away from the nearest point in L₁, L₂, and L₃ respectively. We also define the sets X₁, X₂, X₃, each representing a topologically connected piece of Axis territory.
Now we can remodel the map as a graph G containing the points l₁, l₂, l₃, x₁, x₂, x₃ with the following rule: If the set X_n shares at least one point with the set L_m^e (and does not share any point with L_m⁺), then there is an edge x_nl_m in G. Given the known information and the testimony of our correspondent, every edge x_nl_m (n,m∈{1,2,3}) is an edge existing in G. The resultant graph turns out to be identical to the complete bipartite graph K_3,3.

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

Proof that K_3,3 is not a planar graph
We aim to prove by contradiction that K_3,3 is not a planar graph. Assume that K_3,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 l₁→x₂→l₂→x₁→l₁ 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 K_3,3 is planar graph. Hence, K_3,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 K_3,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)

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 v_n. A vertex v_n connects to another vertex v_m only if m is divisible by n. For example, one such possible directional path in this graph would be:
v₂→v₄→v₁₂→v₃₆→v₂₅₂→v₂₇₇₂

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 v_n→v_m. We use the smallest number of the set, 1, as the starting vertex for this path:
v₁→v₂→v₄→v₁₆→v₂₂→⋯→v₁₀₂₄

As 1024 * 2 = 2048 > 2013, the graph terminates. 1024 being 2¹⁰, 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:
v₃→v₆→v₁₂→v₂₄→v₄₈→⋯→v₁₅₃₆

As 1536 is 3 * 2⁹, 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:
v₅→v₁₀→v₂₀→v₄₀→v₈₀→⋯→v₁₂₈₀

As 1280 is 5 * 2⁸, 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)

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.

Definitions
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 x₁, x₂, x₃, …, ₁₃ 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 c₂ is more valuable than c₁). 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 x_n and x_m, it is possible for P1 to choose x_n as hidden card, and then to place x_b 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 x_m 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 v₁, v₂, v₃,…, v₁₃, 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 x_m), 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 x_n as the card to hide if it is possible to travel clockwise on C from v_m to v_n within 6 steps.
With these rules, the suit, as well as the number value of x_n, 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 {h₁, c₁₃, s₁, s₃, h₈ }. 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 v₈ to v₁ within 6 steps, but not possible to travel clockwise on the cycle from v₁ to v₈ within 6 steps, P1 can choose to hide h₁ and display h₈ 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 (s₃,s₁,c₁₃). So P1 displays:

By comparing the deck values of the rightmost 3 cards, P2 now understands that he must make six jumps from vertex v₈ on C in the clockwise direction. He does so through a mental calculation and arrives at v₁. 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 h₁, or Ace of Hearts.

□!

(28 Feb 2013, Dorigny in the Switz)

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