Exam Season

 A. Wood
Lecturer: Prof. Zürcher from the Bernese Fachhochschule at Biel, specialising in Wood. Received woodblocks to play with, especially the Swiss Stone Pine (Pinus cembra) sample that I sniffed every night before going to bed. Visited wood labs in school. Witness wood welding twice. Started paying attention to trees at the sidewalk, and observed them grow. Cesko baked a cake out of pine nuts, and shared it with the class. Prof. Zürcher is calm and rational in disposition but betrays a disturbing affinity to crackpot theories (thankfully on things not concerning wood). Open book exam. Outcome: Most probably no flunk.

B. Seminar Series
Lecturer: Various. Monday afternoon seminars after lunch, mostly from materials experts, attended mostly by professors, doctorate students, etc. Prof. Niederburger from Zürich, whom we had met earlier in Materials Science Students' Day, appeared again to us one of those Mondays. The no-stick ketchup bottle group from Harvard gave a seminar. The guy who came from the place I was born in gave a seminar. Was tested on the contents of seminars. Outcome: Probably flunk.

C. Photovoltaics
Lecturer: Various, but mainly the Ballif. Exciting and edifying lectures on photovoltaics, scientific advances thereof, market dynamics thereof, and ergonomics and use thereof. Migraine-inducing review of semiconductor physics. Free train tickets for a visit to EPFL's labs at Neuchâtel. The Ballif has 'boss' written all over his face, and his teaching assistants (the Jonas, the Lorenzo, the Benedicte and the Andrea) are without exception dashing geniuses. Highly suspect that the exams is actually a recruitment pitch to the Neuchâtel labs. In any case... Outcome: Most probably flunk.

D. Project Presentation
Supervisor: Kislon. Made a program to count polymer-coated gold nanoparticles. Tough because the AFM and STM images look like porridge. Spent long hours on MATLAB and philosophising, even on my customary long trips around Europe. Working algorithm was achieved. People seem to be impressed by results. Looking for options for doctorate studies / contributions to the open-source STM image analysis software / any other logical next step. Outcome: Did not flunk.

E. Biomaterials
Lecturer: Various, but mainly the Lutolf. The Lutolf is now EPFL's favourite poster boy for Biomaterials, according to co-lecturer Kontos. The Lutolf has started a company selling activated gel with co-lecturers Drs. Rizzi and Sanctuary. Co-lecturer Prof Klok's super-exciting roller-coaster Computational Biology lecture was cancelled (which was bad, just to clarify). Crammed biology concepts in spare time. Critiqued a paper for homework. Open book exam. Outcome: Probably no flunk.

F. Lithography
Lecturer: The Muralt. The Muralt mumbles and laughs at his own jokes. The Muralt is like an angel / Santa Claus during exams, and is prone to small talk and laughter. The course featured labwork heavily, where we built microhotplates. Doctoral students Nachi and Emilie were our guides. Successfully handled hydrofluoric acid wet etch without dying or sustaining griveous injury. Did lab report and learned about a smashing new data analysis tool used by teammate Mohammad. Outcome: Most probably no flunk.

G. Graph Theory
Lecturer: Prof. Pach (Erdős number 1). Prof. Pach comes to every class with a window wiper, which he used to wipe the blackboard clean after running out of space (high-efficiency lifehack pro-tip). Teaching assistant is Filip, a gentle soul with an IQ that is up in the clouds. Relief teacher for two sessions is Bartosz, whom I might have seen one fine Sunday in church (not confirmed). Bonus questions at each exercise formed part of contest, as well as some of the posts on this blog. Less than 50% of the class are native math students. Less than 50% is also the score average of the mock mid-term paper. Highly recommended for EPFL juniors from their seniors for its high passing rate, but one should not let their guard down. Exam was noticeably easier than mid-term. Outcome: Probably no flunk.

H. Numerical Analysis
Lecturer: Ricardo. Ricardo is a nice guy who couldn't teach / gave up trying. The Godfather of Numerical Analysis in EPFL is Alfio Quateroni, who worked at NASA until EPFL lured him across the Atlantic with high pay, but is still nowhere to be seen. Our course materials / textbook are all Quateroni's work. The course used to be taught by him until he gave up trying and re-delegated all that sh-t to poor Ricardo. Skipped most Friday morning lectures / attended only when I need to update myself on the progress. The course is the only one in my list that is taught in French, and is (to some relief) more similar to Engineering Math than to Pure Math. Bonus test happened near the end of school term, where I came in third in a class of 91 people. Final exam coming next Thursday.

Blogging from Reykjavik

I am blogging from Reykjavik, from the hostel next to the city bus terminal called Hlemmur. This is the place from where Josef takes the number 5 to work. An record shop by Smekkleysa is a short walk westwards, plus a shitload of pubs. Reykjavik is the unofficial most underrated nightlife locations in Europe, if I can say that Iceland is part of Europe with a straight face.

Today the plan is to get to Snæfellsjökull through Borgarnes. On Saturday we might go to Þórsmörk for a short walk in the south. On Sunday we get to Þingvellir and all the waterfall stuff near to the capital, and on Monday we go to the Dickmuseum. After that in the evening we shall scram back south to the Burgh. More to follow.

The QMP Team

My very own Finlandbike

Alexander left the team at Aalto Applied Physics for home in Cuba, two weeks after I arrived. They sent him off with an ashtray designed by the great Alvar Aalto himself. They concluded that Aalto made a lot of trashy designs, and then they lol'ed. I gave him a cigarette holder which was the parting gift from a Romanian painter who shared my dorm in the hostel, because I did not smoke.

Before I left for home in August, Mari baked me a pie, which we all shared. The teammates gave me an Angry Birds Space plushie. I was moved to figurative tears.

A Chinese dude joined the team after I left. He bought for himself the same bike that I had sold back to Greenbike. I wonder how much the Greenbike dude had marked up the price when he sold it to him. I wish I heard from the team more often.

Mothers and Daughters

Problem from Session 10: Prove that if mankind will live forever, then there is a woman alive today who will have a daughter who will have a daughter who will have a daughter... for eternity!

Preface
In the field of human genetics, the most recent common ancestor of all living humans in the matrilineal line is termed the Mitochondrial Eve, so termed because the mitochondrial DNA (which is only passed from the mother to her children) of all living humans can be traced back to her. This concept draws attention to the fact that for every person alive today, there is an unbroken chain of mother-daughter relationships that links Mitochondrial Eve to their mother or to themselves, if the person is female. Today, we prove that this unbroken chain can be sustained forever, insofar as humanity survives forever.

Reasonable assumptions
1. No-one develops time-travel for the rest of eternity, so no one gives birth to her own grandmother or the like nonsense.
2. Humans will never attain immortality, hence the need for reproduction.
3. Everyone who will ever live must inherit one set of genes from each parent (one male, one female).

Model
We consider the entirety of humankind living from the present time and indefinitely into the future, ignoring the people who lived in the past, as a graph G. Each person is modelled as a vertex. Two persons are connected by an edge if one of the persons is directly descended (genetically, at least) from the other.

Proof: The matrilineal subset F of G is a forest
We now extract a subset of G containing only the matrilineal lines of descent, and call it the matrilineal graph F. To prove that F is a forest, it is sufficient to prove that F contains no cycles. First, note that we only consider edges that join a mother and daughter, and not those that join fathers to sons or daughters, or those that join mothers to sons. For the sake of simplicity, we can eliminate the male person-vertices from F.

Now suppose F is not a forest. Then, the matrilineal graph will contain a cycle. In this case, there will be a woman who gives birth to a daughter, who in turn gives birth to her granddaughter, and so on, until one of the (grand-)ndaughters eventually gives birth to the first woman. Time-travelling speculation aside, this makes no sense and so we should discount the possibility of a cycle occurring in F. Thus, F is a forest i.e. a graph in which all connected components are trees.

Organising the ladies in F into tiers
Having decided on the nature of the matrilineal graph F, we now try to organise the ladies into tiers, so that the ones who are alive today can be treated apart from those who will be born in the distant future. We sort every woman whose mother is no longer alive today into tier 1, their daughters into tier 2, their granddaughters into tier 3, and so on.  All the vertices in F can thus be assigned a tier, as no cycles are present.

Proof: There will be infinite tiers in F
Suppose there will only be a finite number of tiers of women in F. This means that after a number of generations of humankind, there will be no new women in the world. By assumption 2, all the existing women will eventually die, leaving only men. By assumption 3, this means that humankind will die out, because men are incapable of reproduction without women. This contradicts the supposition that mankind will live forever. Therefore, the number of tiers in F is infinite.

Proof: There is a path from any vertex in tier N to a vertex in tier 1 (for all natural numbers N)
We perform a proof by induction on N from N=2. Every woman in tier 2 is descended from at least one woman in tier 1, thus they are connected to tier 1 by a path that consists of one edge. Suppose now that there is a path that connects everyone from tier K to tier 1. As everyone in tier K+1 is descended from at least one woman in tier K, they are connected by a path to tier 1 that consists of the path from tier 1 to their mothers and the edge shared between themselves and their mothers. By induction, there is a path connecting every woman in tier 2 or higher in the graph F to a person in tier 1 for any number of tiers.

No matter how much time passes and how many new generations are born, there will be a path linking a living person to a certain ancestor in tier 1, who is alive today. This shows that the existence of a certain unbroken mother-to-daughter lineage will hold indefinitely.

□!

(22 May 2013, Dorigny in the Switz)

Coin Table

Question from Session 7: There are 1900 one-Swiss-franc coins lying on an enormous table. Some of them might touch each other, but they don't overlap. Show that you can always choose 475 of them such that no two chosen coins touch each other. Can you always choose 601 such coins?

Part I: Can we find 475 non-touching coins?
Yes, we can always find 475 coins that do not touch one another.

We model a graph G in which each one-Swiss-franc coin is a vertex and in which there exists an edge between each pair of coins that touch each other. As the coins are on a table (presumably flat) and do not overlap, we can assume that the graph G is planar. By the four-colour theorem, G can be coloured with four colours.

Let i be a colour such that i∈{1, 2, 3, 4} and let G_i be the subgraph of G containing the vertices coloured i. Then the average size of the subgraph of all the four colours is always:

We consider first the case that G_i=475 for all i∈{1,2,3,4}. Then we can find that all of the G_i are of size 475. This means that all four sets of 475 coins are found such that no coins in the same set touch each other. If there is a certain G_i greater than 475, we can always find a subset of G_i that contains 475 coins such that no coins in the subset touch each other.

We next consider the case that we find a certain G_i less than 475 for another i such that the average subgraph size is 475 and not below 475. It follows that we can find a set of 475 coins from this larger subgraph in which no two coins touch each other.

Part II: Can we find 601 non-touching coins?
We can find 601 coins that do not touch one another in the case where the coins are maximally packed.

It has been proven by Lagrange in 1773 that a lattice arrangement of circles with the highest density is the hexagonal packing arrangement. When the coins are maximally packed, the graph G becomes such that the internal facets of the graph can only be equilateral triangles.

There exists a uniform colouring in three colours (123) for a hexagonal packing arrangement. The 2-colourability of the graph  G of the infinite hexagonal packing is provable by demonstrating 3-colourability on a unit cell of the hexagonal lattice and then tesselating the unit cell indefinitely:

Fig 1. 3-coloured unit cell in the infinite lattice

Then, following the line of thought in the first part, we let i be a colour such that i∈{1,2,3} and let G_i be the subgraph of G containing the vertices coloured i. Then the average size of the subgraph of all the four colours is always:

We can always find a certain G_i such that |G_i|>633 and none of the coins in G_i touch one another, and a subset of 601 non-touching coins can always be found in G_i.

□!

(24 Apr 2013, Dorigny in the Switz)