'(The Blog) With No Name', perhaps best described as a stream of notes and thoughts - 'remembered, recovered and (sometimes) invented'.

Friday, November 25, 2005

'Atomic' (?) Polygons

This is on a problem I worried quite a lot about a long time back:

Let us define 'tiling' of a polygonal region as cutting it up into *some finite number* of polygonal pieces (call these 'tiles') such that the tiles are identical ('congruent') to one another - the tiles *need not* be similar to the polygon being cut. I was trying to find polygons which do not admit *any* tiling.

I guessed at a quadrilateral (with all angles measuring irrational fractions of PI but summing to 2*PI) and tried to prove that it cannot be cut into any finite number of mutually identical tiles. The effort was but a partial success; however it resulted in this 'challenge'
at the 'Ponder This' column at IBM Research (where the problem has been presented a little differently; the solution given there is entirely theirs).

What has been worked out at 'Ponder' appears to be a stronger result than what I was trying to get. The quadrilateral described above not only is untile-able; it cannot be cut into a finite number of pieces which all have the same *set of angles*. ie, even if the tiles only need to have the same set of angles (ie. the *order* of the angles in each tile need not be the same), this quadrilateral cannot be tiled.

This implies perhaps that this example is an overkill - if one 'only' needed a polygon that resists breaking into identical tiles. For instance, one could perhaps easily find polygons which CAN be cut if only the sets of angles to be the same across all tiles but cannot be partitioned when the *sequence* of angles too needs to be same across the tiles (Just take a quadrilateral as above with irrational angles, take another with the same set of angles in a different order, scale one of these quadrilaterals a bit (scaling is probably not necessary) and weld them together at some edge. The new piece is very likely to resist any division that needs every tile to have the same sequence of angles. But if the sequence of angles in the tiles were not to matter, one simply needs to break along the weld).

Not sure if such an atomicity of polygons (as we saw above, one can think of different types of atomicities) with respect to tiling is of any further significance. But as far as I am aware, even very easy-to-state problems in this area are formidable; for instance, I guess it is open to decide if a polygon is a *'rep-tile'*, even for the case where the given polygon is a *'polyomino'* - a very strong restriction.

Note: 'Dissection' is a more precise word for cutting polygons but I don't know what to call the pieces resulting from a dissection!

Monday, November 14, 2005

'St. Mary's Cycle Works'

Logically speaking, Pappachan must be somewhere near 50 years of age but he does not look it; indeed, he looks pretty much like when I first knew him - around a quarter of a century ago. For as long as I can remember he has owned and manned a shop called 'St. Mary's Cycle Works', in the town of Chalakudi, Kerala. The shop has not changed much over the years either (except for a small ad for cellphone cards which it now presumably sells along with its usual assortment of articles ranging from bananas and cigarettes to soda water - yes, the soda bottles too have changed; one does not see those very massive bottles with glass marbles for stoppers anymore). And,contrary to the name of his establishment, Pappachan never sold or seriously repaired bicycles. His cycle-related activities have been strictly limited to refilling tyres and providing cycles on rent. It is this last mentioned service that I avail of whenever I visit home - an event that happens on an average twice a year.

In early November, Kerala experiences a very unique weather regime called 'Tulavarsham' - the mornings are clear; by midday it gets very sultry and the afternoon sees a rapid and massive buildup of clouds followed by a thunderstorm, which clears up in a couple of hours. The evenings are usually clear and humid.

Last Friday was no different. By 5, the rain has stopped for the day and the sky is a clean blue. Knowing there is nearly an hour of sunshine left for the day I walk down to St. Marys' and ask the usual question: "Got cycle?" (although I can see a few of them lined up). With a deadpan expression (he has always been a man of very few words and btw, he knows me fairly well) Pappachan pulls over one of his cycles and hands it over to me and then looks at an ancient clock on the wall (to note the time somewhere). With no further talk, I check the brakes and bell and within seconds am off on a trip I have always enjoyed.

In a few minutes, I reach the railway crossing that marks the end of the town. What lies ahead is not real country but a swathe of suburbia - an almost continuous succession of houses set back from the road in green compounds which grow in area in proportion to the distance from the town. Occasionally, the road skirts or crosses vast rice fields and ponds choked with weeds and water lilies and fringed by stands of trees. Smokestacks of brick-kilns could be seen rising above the darkening tree-line and into the sky - a flood of twilight colors. The air is very still and very humid and misty vapors hang low over the waters. Even at normal pedaling speed, I am working up quite a bit of (very welcome) sweat.

By nightfall, I reluctantly turn back. A pale three-quarters-moon provides enough light to find one's way back to the more familiar town streets.

Pappachan is preparing to shut shop and looks relieved to see me - and his cycle - back. He checks the clock and his log and says matter of factly: "seven bucks" ('aint it cheap,' I muse, 'seven Indian rupees for over an hour and a half of cross-country biking?').

As I hand Pappachan the dough, he allows himself a question in the (now, to self) strangely musical local dialect: "'Ppevadeyaa?" (this means the whole of "Where are you based at present?". And this is the only 'extra-professional' thing I have heard from him over all these years). "Pooneylu" ("In Pune") I reply, trying awkwardly to achieve the same musical effect, an act that has become increasingly difficult with Time. And yes, unlike the sameness of Pappachan's query, the answer has changed over a dozen times, tracing out my erratic trajectory.

Note: Pappachan's tribe is dwindling, at least in Kerala. Now, even in villages, one hardly sees shops which rent out bicycles. Here is wishing 'St. Mary's' luck; and longevity.

Monday, November 07, 2005

The Wells of Mohenjo Daro

I have been looking thru a set of (very) slim volumes by (primarily) the eminent historian Irfan Habib, titled 'A People's History of India'.

The second volume of the series 'The Indus Civilization' has an interesting cover. It shows a water well from Mohanjo Daro, the (excavated and exposed) brick walls of which are over over 20 feet tall, making it look like a cylindrical tower! Inside, there is another well-photo from the same place, showing a smart piece of ancient brickwork. These pictures reminded me of the time when I asked Pop: "Can the wells overflow their walls if there is heavy rain?"

(There is much stuff at wikipedia, if one starts the search with 'water well'; there are articles on 'aquifer', 'water table', Artesian well' and so on. It is quite a trip! And wikipedia seems to indicate that Habib's claim that the Indus culture was the first to use wells is a bit suspect)

Wonder why these wells were ROUND. The Indus people seem to have used specially crafted, wedge-shaped bricks to give very neat circular rims for the wells, rather than simply use their standardized rectangular bricks (yes, in this ancient culture, they had standards for almost everything) to make square walls around them.

I guess there are deep village wells in the drier regions of India which are not necessarily circular - the ornate and centuries-old 'stepped wells' in Gujarat are probably rectangular. The 'kokkarni' of laterite regions of Kerala is somewhere between a well and a deep swimming pool - it has steep steps leading you to the water and no walls above ground level; and it is usually, again, rectangular. So why the Mohanjo Darans took the trouble to make their wells so neatly rounded is a bit of a mystery.

It can be argued that they had found out (maybe the hard way!) that the circularly aligned brickwork resists collapse better - the same principle as that of the structural arch. But then that begs a further question. The Indus people had the basic idea of the arch and they also used bitumen and gypsum as concrete (very advanced for their time; I quote from the same book), then why did they NOT make proper arches (maybe they did and the trick was 'lost')? Indeed why did India (have to) wait for so long (until around 1000 AD(*)) to adopt the arch? And how does one explain the vast gap (over a thousand years) between the decline of Indus and the next oldest 'pukka' architecture in India?

Note (*) -the arch and the vault appear prominently as decorative elements in the 'caves' at Karla, Bhaja and other places slightly before Christ. But they are not 'structural' - not formed by cut stones put together properly.

Friday, November 04, 2005

"You Are No Longer A Student!"

Re-establishing contact with Suresh has brought a tide of vivid memories of 'good old' days - when one was much younger and when many things used to appear in a very different (and more flattering) light than they do now. Here is how my first day in the so-called IT-Industry went:

[Background: On completing my Masters in Computer Science at Hyderabad, I face some trouble finding a job; A former Teacher of mine helps by recommending me strongly to a Software firm in Chennai where he had some serious 'influence'. I am interviewed by a bright, young manager (let me call him Sid) and a couple of others - I am told this is an essential formality - and am offered a S/W engineer's post. I soon reach Chennai and camp with Suresh - the idea is to stay (illegally) at IIT for a few days till I find an apartment - and report at their office for my very first day at work]

"Well, welcome to ---!" Sid says as I am ushered into his presence. "Sit, sit.. Today we will be introducing you to various aspects of the work we have for you. But, at the outset,... (there is a pause), some plain talk will be in order. You have been appointed .... you know, on an experimental basis. Your credentials and experience do not quite match your age, you are almost 30, right?" I nod, deciding against mentioning the correct number.

"Incidentally that is more than my own age!" Sid continues "Anyways, you do not have much background in programming except for that short MTech Degree. And you don't know C++, right?" I nod again.

Sid pauses ominously and takes a (very audible) sip from a steaming cup. "Btw, do you want some coffee?" "no thanks" I say, wondering what is to follow.

He continues: "You will need to show a lot of energy to learn things which are new to you and ramp up to the level of some of our bright young people, who have, compared to you, the advantage of youth and also technical skill. Unless, this energy is shown, well, I won't have any use for you; you know, you can leave the company!"

I am bit shaken but manage to sit tight and (hopefully) show a straight face. "Well, you know what is what now. I have some work to attend to. Please wait outside in the guest cubicles. When I am free I shall tell you more and introduce you to people." Sid concludes. I step out, wondering what exactly is going on.

As I sit in one of the guest rooms, a guy who was on my Interview panel with Sid (let us call him, well, Dick!) passes by and says "Hi, you joining today?". I reply in the affirmative. A few further pleasantries having been exchanged, he moves into the next room and has a short talk with some other chaps who are presumably lounging there. The language is Tamil and the tone, a bit hush-hush but rather audible since the partition is of wood. I listen since there is nothing else to do (and since I do know Tamil); and listen with progressively greater intensity as things pick up...

A voice: So, this new guy has joined up, he is from IIT ... right, Dick?

Dick: IIT? Bullshit! He is just another 'Mallu'; out here that's enough, right?....this company has too many of them.

voice: But then, you took his interview. And he must have done ok, else he wont be here!

Dick: ****( expletive)! For even simple questions, he had no idea; like, I asked him how to triangulate a polygon and he gave a stupid 5 minute lecture. I switched off and nodded politely. That is all.
(there is a pause)

Dick (continuing): Actually, he HAD to be selected. Sid said he had no choice, really. The chap was recommended by ---- who has too much of this Mallu-Mallu thing going.

Voice: Bad scene, really. But then,... I think I did hear he has done something at IIT!

Dick: Bah, he has done ****(one more expletive) at IIT!

A pause; the conversation veers to other matters and I switch off.

My wait continues. No one talks to me except an office assistant who asks politely: "Sir, want some 'water-keeter'?". Eventually, I smell food and hear chatter from the other side of the partition. I note that the time is past 1. I tell the assistant that I shall be back soon and step out to grab a bite.

Back at the visitor's room (I try a different seat this time), the indefinite wait continues. Tired and bored, I search my bag and fish out a half-read copy of 'Daivathinte Vikritikal' ('God's Caprices', I guess would be an okay translation) a Malayalam novel. I proceed to read it slowly and with some relish right thru the afternoon. The novel (which has had a promising beginning) goes thru a very evocative development of events and characters but unfortunately, melts down in a very unsatisfying and contrived anti-climax. By now, the time is well past 5; I prepare to pack up for the day and ask the office assistant for Sid. I am once again taken to his room. "So, how was your day?" says Sid. "I was waiting.." I answered. "What for? "Sid interrupts. Then probably recalling our morning talk he says: "Oh, yes, I had a meeting so could not spend time with you. We shall do something tomorrow. Anyways, hope things are more productive hereon!"

Back in 'Brahms, 308', Suresh asks me how my first day went. "Very peaceful, actually. I had nothing to do but wait and wait; so sat back and finished 'Daivathinte Vikritikal!". "Scandalous!" He exclaims (the actual word he uses is 'Konaappu!', a difficult to translate Mallu word) "what a thing to do on your first day at office! At least you could have tried to read some C++ or something. Careful, Bhai! people would have been watching you! And ... well, you are no longer a student!"