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

## Friday, May 31, 2013

## Monday, May 27, 2013

### Flatplanet

*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

_{1}, L

_{2}, L

_{3}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

_{1}

^{+},L

_{2}

^{+},L

_{3}

^{+}as the points that are less than 1 fkm away and L

_{1}

^{e}, L

_{2}

^{e}, L

_{3}

^{e}as the points that are exactly 1 fkm away from the nearest point in L

_{1}, L

_{2}, and L

_{3}respectively. We also define the sets X

_{1}, X

_{2}, X

_{3}, each representing a topologically connected piece of Axis territory.

Now we can remodel the map as a graph G containing the points l

_{1}, l

_{2}, l

_{3}, x

_{1}, x

_{2}, x

_{3}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

_{n}l

_{m}in G. Given the known information and the testimony of our correspondent, every edge x

_{n}l

_{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 graphWe 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

_{1}→x

_{2}→l

_{2}→x

_{1}→l

_{1}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 graphThis 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 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

_{2}→v

_{4}→v

_{12}→v

_{36}→v

_{252}→v

_{2772}

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

_{1}→v

_{2}→v

_{4}→v

_{16}→v

_{22}→⋯→v

_{1024}

As 1024 * 2 = 2048 > 2013, the graph terminates. 1024 being 2

^{10}, 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

_{3}→v

_{6}→v

_{12}→v

_{24}→v

_{48}→⋯→v

_{1536}

As 1536 is 3 * 2

^{9}, 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

_{5}→v

_{10}→v

_{20}→v

_{40}→v

_{80}→⋯→v

_{1280}

As 1280 is 5 * 2

^{8}, 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.*

**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

_{1}, x

_{2}, x

_{3}, …,

_{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 c

_{2}is more valuable than c

_{1}). 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

_{1}, v

_{2}, v

_{3},…, v

_{13}, one for each number value of the card as follows:

_{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

_{1}, c

_{13}, s

_{1}, s

_{3}, h

_{8}}. 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

_{8}to v

_{1}within 6 steps, but not possible to travel clockwise on the cycle from v

_{1}to v

_{8}within 6 steps, P1 can choose to hide h

_{1}and display h

_{8}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

_{3},s

_{1},c

_{13}). 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

_{8}on C in the clockwise direction. He does so through a mental calculation and arrives at v

_{1}. 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

_{1}, 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

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

Subscribe to:
Posts (Atom)