3 Nov 2002 Bram   » (Master)

garym: Your description of the current state of the software industry is, unfortunately, quite accurate, and it won't get much better any time soon. The problem is that only programmers can really tell whether other programmers are any good, and we aren't going to be put in charge of the industry any time soon.

I've achieved a modest degree of success as an open source developer, but my advice for those considering it as a career is, only do it if you have to out of some immovable internal need. We are only just beginning to see the phenomenon of starving artist programmers, and it will only get more pronounced in the future, possibly even becoming standard for the industry.

I've seriously considered attempting a career as a screen writer. Although I have no experience with it, I have a good work ethic, natural talent, and possibly most important, a willingness to write high concept work with happy endings. Unfortunately those attributes don't even vaguely gaurantee a decent living in that industry, so I've shelved any such plans until I either have enough money to not be worried about failure or have come to hate the computer industry so much that I just want out.

My current long term career plan is to get good enough at financial stuff that I can start a hedge fund or set strategies for one. Unfortunately there's a lot of luck and who you know involved in that industry, but at least it consistently pays well and, unlike screenwriting, the industry has a desperate need for real talent.

For now, I'm doing okay working on networking software, which unlike any of the above I have oodles of experience in. My other career option which involves something I'm already good at is juggling, but I find that a less appealing career path than any of the above.

I haven't even dreamt of getting payed for all the random weirdness I like posting to my advogato diary. That's only possible with a tenured university position, and the more time passes the farther away I seem to be from academia.

Bohemia

Here are the rules to an abstract board game I came up with called Bohemia -

The two players are the square and the bohemian, the square moves first.

Players alternate playing either white or black pieces on an n by n grid. Either player may place either color piece. The bohemian is allowed to pass.

If four pieces of all the same color get placed such that they form the corners of a square with horizontal and vertical sides, the square player wins. If the board gets filled up without that happening, the bohemian wins.

I'm not sure what size board gives even chances to both players. That should be determined through experimentation.

A conjecture strongly related to this game is that for a sufficiently large board size the square must always win regardless of how the pieces are placed. This can be generalized to more than two colors. Also to lattices of side k, for which a square is a special example with k=2. This is a two-dimensional version of van der Waerden's theorem, which can of course be further generalized to higher numbers of dimensions.

I can't even prove this for two colors, two dimensions, and lattices of size two. It seems likely that such a straightforward problem in ramsey theory has already been studied though.

Update: I figured out the following very nice proof of the simplest case of my conjecture.

First, we will demonstrate that for any number of colors, a sufficiently large lattice will contain three pointts of the form (a, b), (a + c, b) and (a, b + c) which are all the same color. I'll call these formations Ls.

By van der Waerden's theorem, a sufficiently large 2-colored lattice will contain an arithmetic progression of length three somewhere along its bottom row. Let us say that those points are at (a, 0), (a + c, 0) and (a + 2*c, 0). The point (a, c) must be the opposite color to avoid forming an L with (a, 0) and (a + c, 0). Likewise the point (a + c, c) must be the opposite color from (a, c) because of (a + c, 0) and (a + 2*c, 0). Now we can show by contradiction that there most be some monochromatic L - the point (a, 2*c) must either form an L with (a, c) and (a + c, c) or with (a, 0) and (a + 2*c, 0). Therefore for a sufficiently large 2-colored lattice there exist points (a, b), (a + c, b) and (a, b + c) which are all the same color.

We will now demonstrate that this is true for any number of colors by induction. Say we have shown for k colors that a lattice of size f suffices. By van der Waerden's theorem, a sufficiently large lattice colored with k+1 colors will have a monochromatic arithmetic progression of length 2*f along its bottom row, say that this is (a + x * c, 0) for 0 <= x < 2*f. Now consider the lattice formed by (a + p * c, c * (q + 1)) for 0 <= p < f and 0 <= q < f. Either some node in this lattice will be the same color as our arithmetic progression on the bottom row, in which case it forms an L with that, or it contains only k colors and hence contains an L by induction.

Now we will use the above lemma to prove our theorem. Say the size of a 2-colored lattice so that it must contain an L is g. Now make a sufficiently large lattice that if it's colored with 2 ** (g ** 2) colors, there must be an L, and substitute a square lattice with side length g for each of these, with colors corresponding to 2-color assignments within the sub-lattices. Call the offset between the L of squares which all contain the same pattern d. The lattice of offset d in both directions from the lower left must contain the exact opposite of every corresponding color or by construction form a square, so we will consider the case where it's the opposite. Since it's of size g, there must be an L in the lower left one of these, whose coordinates we will call (a, b), (a + c, b) and (a, b + c). It is now straightforward to show that by construction the points (a, b), (a + d + c, b), (a, b + d + c) and (a + d + c, b + d + c) are all the same color, hence there must be a monochromatic square.

This proof is so straightforward that I'd be extremely surprised if it isn't already known, but it's pretty and non-trivial enough that I'm happy to have come up with it.

Unfortunately the lower bound it gives is a little bit too big to be practical.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!