Postgraduate Journal 3.12.6

Faithside: This semester has actually been pretty good on my side, despite the emotional low point miasma that stuck around when the semester started and I hauled ass right back to the school residence. Part of this is because I resumed my old practice of joining daily mass in the church across the road from my residence hall. I first joined (and committed to) daily mass in a panic during a particulary severe depression pang when I was working in Nebraska, whereafter the affliction was cured within two weeks. For this I credit the very reassuring presence of Jesus in the tabernacles and also the connections that I have built with members of the Nebraskan and Singaporean faithful who have stayed by my side and have been real champs. In November the church remembers the faithful departed and I have found joy in telling people the story of Tina and keeping her in the realms of the remembered. I am also especially grateful to Amanda and co. and their newly-fromed Ubi Caritas group in Yale-NUS College, a place where the spirit of rigorous enquiry and willingness to tackle big scary questions of faith has been nurtured and maintained. Guys, if you are reading this, I heart you all; this semester is gone too soon!

In other news, (1) daily Rosary was instated on the NUSCSS side, to the point that a small group of us, myself included, are doing it out of sheer force of habit. October was the month of the Rosary, not November, but it does not seem to matter any more to the diehards. (2) I have started a three-year programme of marking daily readings in the bible, because I heard an extraordinary claim that church readings cover the entire bible in three years, and I just have to see if that is really the case.

Scienceside: I have now a co-supervisor from Physics, a very kind and agreeable old professor dude, and am now caught in the thickets of computational physics. I actually prefer being snagged in the brambles of calculation than sucked into the quicksands of experimentation. One reason for this was that experimental people I have had to work with seemed to have scant interest in finding out how things actually work, and seemed to be bent on making things work by sheer power of will and by working themselves into a state of delirium (in which case anything at all can be thought plausible). The more important reason was that I sucked at experimental work while at the same time was passably good at calculation, having dabbled in computational techniques since my undergrad days. But even then, calculations sometimes don't work, and in fact at this moment none of my projects are working, and I have increasingly found myself compelled to cram undergraduate theoretical physics in order to understand the inner workings of my software, with its myriad weird error messages, (contra)indications, and acrobatic tricks.

I have been taking a course where I have learned to do computational physics from scratch. It started with some simple linear algebra and then swiftly degenerated into a mad scramble to write a working program with C that does high-powered stuff like Quantum Monte Carlo and the Metropolis Algorithm on Ising models and Schrodinger Equation solvers. Sad to admit but sometimes I fail to produce a working code (the Hydrogen molecule project has been especially disastrous), and the physics students are all pwning my arse at every turn. But I am positive, because my stated mission for this PhD adventure is to punch way above my weight, and this semester shall be no exception.

My first attempt at Monte-Carlo

Postgraduate Journal 3.2.4

A moonlight picture of the "America" taken Christmas night, 1901, Baldwin-Ziegler Polar Expedition

(Semester 3, week 2, Thursday)
It is my style now to write about things from which I have been a bit detached, be they things that had happened in the past, ephemeral thoughts, or other things not concerning myself. I was mainly worried about appearing egotic on the internet. However, the need arose for me to put them in order when depression cycles happen too often to be amusing anymore, so a friend has recommended that I start writing again.

My life is a mystery to people now.

I have to clarify that I am now working towards a PhD. I have had to repeatedly explain that I didn't go through a Masters course. Sometimes I suspect that the same people come back to ask me the same questions again, and that even so they leave with a vague incomprehension.

The undergrads do not know. My family does not know. Doctoral students not from my lab do not know. Groupmates probably know, but they don't know anything else about my life. Not one person would know enough. And then I fade into the background of every setting.

A big gathering of my undergrad friends happens. It is in the daytime. I have lab.
A big gathering of my working friends takes place. It is on Tuesday, Wednesday, or Friday night. I have night lessons.
It happens on Sunday. I am at church or refusing to do anything if not with my family.

The fact is that my acquaintances are becoming strangers, deep friendships are becoming superficial, and that I am shedding my circles. It is like being in a room with walls that are closing in, like a ship sailing in a sea that is freezing over. It always feels like my schedule is to blame, or the inability of others to accommodate it, or that no one would bother to do so.

Me: Aren't you free at all?
Them: We are undergrads. We have classes, we have work.
Me: So do I, but I have decided to put them aside, if only for two hours.
They recede. They disappear. The echoes of their revelry fade away.
I go back to work.

What is the meaning in what I do?

So now I have work instead of a whole bunch of acquaintances. The work is usually something the prof has thought up.

But why? I always ask! Why this in particular?
The prof says: read these papers.
The prof says: it can be applied to such-and-such.
The papers make: no sense
The applications are: castles in hot air

Is there a meaning? How does one get about business? I ask my senior, who have been through more and therefore should know better.

The senior says: just do whatever boss tells you.
And I leave this husk of a human being alone, feeling none the wiser. I have no desire to get chewed up in this system and get spat out as a cynic.
The meaning must be arrived at through work, it must come with pain. Those do not matter, but there has to be a meaning.

Can I quit and do something else?

I can, and then I pay back a year's worth of stipends, and then try to find some job. I have no idea what.
I still feel that doing science is my life's calling.
I can quit next year, and then pay back two year's worth of stipends. It will be as if I had never lived in these two years.

A certain Dr. R. came to talk to us youngsters this Monday. He had found a way around this whole depression brouhaha while he was a student himself. The message is this: light, light is at the end of this tunnel, seek and you shall find! Glumness and despondency seem to be a common affliction across the board for those who have decided to trod this path. I had scoffed at this thought in the beginning, but I think the gravity of the situation is pretty clear to me now.

I stay at an apartment in school. I am dismayed to learn that some of my roommates have been positively antisocial. I have no desire to get chewed up in this system and get spat out as a psychopath.

Can I reach out to anyone?

I reach, but they are elusive. They fly away to fairyland with sunshine and flowers. They have no capacity to understand sadness. They yawn at my morosity.

I reach, but they have very important business to attend to. They go, they get married, they travel. They forget.

After a few tries, I give up.

I sometimes pray to Bubska who is lost at sea. I have no way of telling if she hears me or if she is passing it on. I can only hope.

A treasury of stories and memories are bottled up inside of my mind. They have to be told to listening ears, or they may wilt in this tight, crowded space. I write, but even this blog may be an echo chamber.

Postgraduate Journal 1.9.4

A small bottle of water from Lourdes, a gift from Jonathan

(Semester 1, Week 9, Thursday)
It has been six weeks since I took off on a path to myself. People have joined the path and branched off since then, and now is a time when I see no one on the path. I am alone again. A Greek dance plays on my phone, in a language that the world has forgotten, a tongue that no one understands. In my mind I dance again, lonesome as a hermit in the wastes, trotting, toeing, the fine line between rapture and insanity.

The night prayer is written on my wall, serving as a rough template for my prayers for each night. It is a short one, each line written down after a meditative session at a retreat or a cell group meeting:

Lord, take me, break me, feed me to the crowds
Put me in the path of all in need
Let me be there, let me bear everything gracefully
I must decrease; You must increase

It's time to be serious about being fed to the crowds now.
Work has limited my contact with large groups, thinning down my social contact to one person at a time, sometimes even less. Old graduate friends become less responsive over messaging services. "Put me in the path in need" seemed to have put less people on my path, not more.

"Let me be there, let me bear everything gracefully." Maybe I haven't been there, maybe I haven't borne anything as gracefully as I imagine I should.

"I must decrease; You must increase."
So it's not about me. If only it was all not about myself!

All these will take time to sink in.

Tomorrow morning, hopefully, I will wake up as usual. My morning prayer is written on the same wall, and consists of a single pious ejaculation:

Lord, I am overjoyed to find myself still breathing. Take my day: it is yours!

Some days I strike out "overjoyed" mentally while making this prayer. Some days are just like that.
Time to sleep.

[Bedtime reading: Evangelii Gaudium]

Román népi táncok, Sz. 56, BB68: Arrangement Notes

The Concert, 16 March 2014: This semester's concert by GENUS began and wrapped up in the Conservatory's concert hall. It was marketed by Randy's dashing profile as the Man, Consumed By Wanderlust, Embarks On An Odyssey To Eleven Countries Around The World. My assignment for this round is Bartók Béla's Román népi táncok. The song has been filed in as the second last piece in the concert as well as the encore (to everyone's horror). It was only on the day of the concert that I was aware that the title of the piece had become Six Romanian Dances, but if that means that our emcee Ajay doesn't trip up his sexy baritone voice in the weird Hungarian consonants, I think it's a fair compromise.

Background to the Piece: Bartók Béla composed the first Six Romanian Dances in 1915, based on folk tunes gathered from Transylvania. Transylvania was a region in the Kingdom of Hungary at the time of composition, but was lost to the Romanians in the Treaty of Trianon of 1920. It was at this point when the slightly bummed Bartók presumably shrugged and changed the title from Romanian Folk Dances from Hungary to Romanian Folk Dances. This also why explains why this Romanian piece has a Hungarian name like the composer's, and why five of the movements have two unpronounceable titles instead of just one.

The Six Movements and Where They Come From:
All six songs can be nailed down to a map of Transylvania, or the half of Romania situated to the north and west of the Carpathian mountains.

1. Bot tánc / Jocul cu bâtă / Stick Dance: from Mezőszabad village (now Voiniceni)
2. Brâul / Sash Dance: from Igriș (village within walking distance from Bartók's hometown)
3. Topogó / Pe loc / Standing Still: also from Igriș
4. Bucsumí tánc / Buciumeana / Dance from Bucsum: from Bucium
5. Román polka / Poarga Românească / Romanian Polka: from Belényes (now Beiuș)
6. Aprózó / Mărunțel / Fast Dance: First part from Belényes, second part from Nyágra (now Neagra)

Working Material: The arrangement relied heavily on the piano original, to which the scores are available free of charge on the IMSLP database. Arthur Willner's string orchestra arrangement also accounted for some of the inspiration; I referred chiefly to the 2010 rendition of this piece by Danubia Orchestra and the folk group Muzsikás, who have unrepentantly butchered this piece from its original state, even adding their own movement between Dances 5 and 6:

The work on the guitar ensemble arrangement started on the day of the concert Food for Thought in 18 September 2013. A workable draft was produced in November, and then playability issues were mopped up in the finalised version in 15 January 2014, after negotiation with section leaders.

Technical Issues:
1. Instrumentation:
Wan Ching was roped in to lead the ensemble in movement 2, play a solo in movement 3, and follow along the ensemble in movements 5 and 6 with the Yangqin, a close approximation to the Hungarian hammered dulcimer. Anna led the ensemble in the later half of movement 3 and then movement 4 and then closes with all the rest in movement 6 with the glockenspiel. Movement 3 is extended by half a movement to make space for the Yangqin solo. Everything else was guitars. There were no percussion parts.

2. Speed: 
It appears that the tempo indicated for the later movements was the main reason why people hated the song so much at first. I used Bartók's metronome marks in the piano scores, which most piano players already don't follow. Ultimately, the ensemble decides how fast they would play the songs.

Robert, our conductor, has taken the liberty to play movement 6 part 2 faster than part 1, despite Bartók's recommendation to take it one notch slower.

3. Rubato
I put some segments of movements 2 and 3 for the Yangqin player to play not to any specific tempo, but in any way she damn well likes. This is because I found the movement 2 original to be boring and want to spice it up, and also to force everyone to look at the conductor when they play. The short (angled) fermata at the end of the first two lines are recommended to be held for just long enough for the audience to start feeling impatient and cheated, but not longer.

The speed at which the movement 3 Yangqin solo is to be played is up to the player. Anything other than a regular beat is fine.

4. Chords: 
Chords are chosen according to those in the piano scores. I used the fretboard function in Sibelius 6 to determine if a chord is playable. Even then, a lot of changes had to be made to the chords after the first print to make them easier to play. I have known that the alto players to be allergic to chords, so have minimised chords in alto parts. Much apologies to the basses.

Heng Zhong (Prime 2) accompanied the glockenspiel in the second half of movement 3 with strummed chords. Those things are seriously easier than they look in the scores. Also to whoever plays this part, I don't actually recommend looking at the scores, but instead to write down something like this that fits on a post-it note:

... | Bm | " | G | " | Bm | D/A | " (+G#) | " | D/A | ...

The strum rhythm written in the score is just a recommendation, and one can afford to throw that page away after he has learned the chords by heart and figured out his favourite strumming pattern.

Signed off
8 April 2014

The Adventures of Professor Oliver and the Principle of Uniformitarianism

Professor Oliver read the student's answer. The student had not deigned to fill in any of the blanks; instead, he had opted to scrawl the phrase "THE PRESENT IS THE KEY TO THE PAST" repeatedly, haphazardly, and in big bloody letters across the page. Hnph! Professor Oliver snorted, evidently unimpressed. Nevertheless, he relented and gave the student one point for sympathy.

The Adventures of Yusuf Al-Muʾtaman ibn Hud and Giovanni Ceva

[Source]

Wrote the great Yusuf Al-Muʾtaman ibn Hud, the King of Zaragoza, in his magnum opus, the Kitab al-Istikmal: "... Thus, I have proven that if these three ratios on the triangle give a product of one, then these three lines in the triangle meet in a point!"

After having read this proof, the scholars in his court exclaimed: "Truly, this is an important proof! O, great King Yusuf Al-Muʾtaman ibn Hud, you are indeed called the Sage of Zaragoza; your name shall be spread far and wide, even down all the generations!"

Six hundred years later, in a dusty university room in Mantua, the Jesuit Professor Giovanni Ceva realises, with a serendipitous spark of inspiration, the same truth that had been discovered by the great Yusuf Al-Muʾtaman ibn Hud. He publishes it and we now name it Ceva's Theorem because his name is easier to pronounce.

Adventures with Brahmagupta and his Algebraic Proof

Question: Prove Brahmagupta's Formula i.e. that if a cyclic quadrilateral has sides a, b, c, d, and semi-perimeter s, then its area K is given by (...).

Answer:

Professor's commentary: Everything is correct here. However, the proof is not very interesting as you have opted to prove it algebraically rather than with graphical explanation. In fact, it is really boring. In fact, my cat has just thrown up on my trousers and then died of boredom after having read your proof. I am enraged! Zilch marks for this assignment.

Prof János Pach's Bonus Questions

 

Old Königsberg and its bridges

A compilation of my answers in Graph Theory class:

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. Answer

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. Answer

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? Answer

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? Answer

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! Answer

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.

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)

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)

Lausanne Mesologue

Here be a record of teachings I find to be worth repeating to the internet.
Yes, sober, serious information for the studious gentleman; it has solved many a world's problem and kicked many an ass. Courtesy of the professors and fellow students of EPFL, and many other people who are around.

More to follow

Photovoltaics
Photovoltaics Stop Press: Prof. Balliff returns from China! He reports a scene of carnage in the industry: The price war for solar cells are keeping prices artificially low, and crashing many a small company. The selling price is 57¢_CHF/Wp, way below the production+sales cost of 75-80¢/Wp. This is good news for consumers i.e. electrical engineers but quite bad news for people who make these things i.e. materials engineers.

Today we were taught how to bend over backwards and make architects happy by turning solar cells a cheerful shade of orange to suit the (Swissy) houses, at a cost of energy efficiency.

Wood
So this is how a tree grows: from a layer under the bark, where there be stem cells that differentiate to become the sapwood or the bark. A tree grows layers and layers out of itself, each new layer heralded by the budding.

The budding just happened here (friggin' everywhere).

In the course of the year, there is a period for which the tree grows quickly, and a period for which the tree grows slowly. The wood that has grown during the lull makes a dark ring that is visible in the severed trunk. A hardwood that grows quickly is less dense than normal, while a softwood that grows quickly is more dense than normal, and is more valued for timber for a variety of reasons.

Wooden crates have doubtful standards of hygiene when used for food packaging, all things considered.

Notes on Opacity

Silica xerogel from the exploding gel lab
(disclaimer: this is not the sample that was blown up)

Before school started, a friend asked me what makes a material transparent. And despite me being from Materials, the question got me stumped. To understand why, here's a summary of what stories people have come up with to explain it.

Prof Li, NUS Materials: A material is transparent if it is amorphous. For example, in glass, the molecules form a network structure, allowing light to pass through the holes.

Prof Moriarty, Nottingham Physics: No, no, that's rubbish! A material is transparent if it is a semiconductor, with a bandgap energy well higher than the range of visible light.

Prof He, NUS Materials: A polymeric material is opaque because of the electron density differences between crystalline and amorphous regions. (At this point I wished my Finland bosses were around so that they could feel my excitement)

Prof Kasap, Univ. of Saskatchewan: Attenuation of light in a dielectric medium is explained through the complex permittivity of the dielectric material.

How to Travel with a Salmon

The Finnish national bookstore (Suomalainen Kirjakauppa) sold copies of Umberto Eco's 2010 novel The Prague Cemetery, despite him having told his interviewers that Queen Loana was to be his last one. Yesterday in central library I found the version in English. I put the book down after a couple of chapters. His novels were such fun to read! but by now the atheism has become pretty grating. I borrowed home a compilation of his short essays.

Eco's stories are long and soaked through in the pages with entertaining medieval miscellany, though the endings are let-downs. To understand why, here's a spoiler list (WARNING) of every Eco novel ever except for Prague Cemetery:

The Name of the Rose (1980): The abbey burns down.
Foucault's Pendulum (1988): The secret templar code which everyone was trying so hard to crack turns out to be a laundry list.
The Island of the Day Before (1994): Roberto della Griva never gets to the island. Instead, he drowns himself.
Baudolino (2000): Everything in Baudolino's story turns out to be made-up. Niketas declines to put it down to writing.
The Mysterious Flame of Queen Loana (2005): Giambattista Bodoni dies after spending the whole book in a coma.

Eco's books sit on a shelf near the stairwell, in the same space as Dante and just neighbouring Borges and Neruda, writers from Argentina and Chile whose works I have heard good things of but never read until yesterday. They are just one shelf away from the French authors. ~10 shelves down in the study room direction would be the Russian novels, where Lukyanenko's series are placed side by side with Dostoyevsky and Pushkin and what have you. The German novels are at the far end, some untranslated. I have tried to read some of them, but LAG1201 does not equip you enough for doing that. Laxness' works are in closed stacks, except for this one:

A Short Route to the Faculty of Science

For people coming in from Engineering, Arts, or Nussuland and going to Faculty of Science in NUS.

1. The bridge links Engineering and the libraries. Go to the east (libraries') end. There you will find LT4. LT4 has a back door. Go to the right of the back door. You find a place called CDTL, the Centre for Development for Teaching and Learning, but as far as I have asked no one really knows what the hell the place is supposed to be for. Upper Kent Ridge road starts here.

2. Pass by the Acoustic Labs and the Centre for Protective Studies, namely the place where they explode all the things. Pass the Y-junction.

3. To the left and right, there are steps that lead down, paved by bricks. Take the left one to S1. At the time of writing, much of S1/S2/S3 are under renovation. Turn right into S2. Pass by the Biological Sciences offices, some of which are staying in the building.

4. Pass by the Chemistry tutors' offices. Enter the Pharmacy labs. Today I could see some of the undergrads at work and minding their own business. I felt a bit strange because I have always enjoyed doing my own labs undisturbed by outsiders (E3A is very isolated corridors-wise). From time to time one of them would look up at me with a puzzled expression. I left that place quickly.

5. Take the stairs 1 floor down to Science Library entrance.

Junior Journal 3.5.R1

1. Housekeeping

So the blog is eight years old, having survived August 18 2012 with that silly French thing I wrote. I do write less now not because there is less time but because I spend my free time doing something else, namely being prisoner to the Internet. This must not continue.

Does anyone read what I write? Maybe, but I have no way to know because I have turned comments off. I have turned comments off because of spammers. I happen to know that spambots visit my page because more people from the United States visit this place than is absolutely plausible.

Am I going to keep writing? Well yes. But you readers will have to bear with lower-quality stuff for the first couple of months. Now excuse me while I try to redirect my smartmouthing habits away from Facebook.

2. Not Housekeeping

The UROP (Undergrad Research) project is finished. The project is about (and I have had in the Real World to explain it many times) Transmission Electron Microscopy. So the idea is:
1. There is a sample of something.
2. You shoot electrons through it though a beam
3. You focus the electron beam on the other side in some way
At this juncture (3), depending on how you focus, you may get:
4a. An image of the thing, magnified
4b. A modern-art pattern
At this juncture (4b), depending on whether you converge the beam, you may get
4bi. Dotsies arranged in a way that reflects the symmetry (if a crystal)
4bii. Bright circles.
At this juncture (4bii) dark lines appear in the circles and we call it HOLZ lines
HOLZ lines do not make any sense, unless the computer happens to know which crystallographic plane it arises from. So I spend time in the Professor's office because his computer is the only one in the whole wide school with the software installed, without managing to touch the actual microscope, which is only for experts.
Well as I have said I have finished the project, and as I type my junior Nengduo has enrolled in UROP also and working under the same Prof. Tearfully I say to you, my junior friend, do us undergrads proud! (Disclaimer: Nengduo probably doesn't read the blog)

The VIP (Vacation Internship) report was also completed recently, but not so recently in a way I can write about it in too much detail. It was about the Density Functional Theory in solids, because electron density is very importen'.

3. Assorted stuff

My UROP prof also teaches Dielectric and Magnetic materials. He is very thorough but wreaks sleepy havoc on the students. Actualnuh, I can not complain because there was another prof to whom I almost turned violent at for not being thorough enough, and for always using fluffy language 90 percent of the time.

The prof teaching Materials Design and Selection (read. Realpolitik for Nerds) actually encourages us to use fluffiness in the same spirit as Business Management students, but at least he is truthful in saying it.

The prof who teaches Ceramics is full of off-colour comparisons and wisdom. Under his inspiration, I am now running at least once a week with friends.
The prof who teaches Corrosion is often too soft to be heard
The prof teaching Metals stutters quite badly

I am supposed to be studying and stuff. I should go home and spend time with my sisters. And then sleep.