Finitude

I’ve been thinking a lot about the finitude of the world recently. What I mean by that is this: While we interact with the physical world as if it were infinitely variable – everything can be subdivided, including time and space – it seems scientifically quite likely that this is not in fact the case, that rather the world is finite, that there are finitely many particles in the universe, that each of them has finitely many positions, and thus that the universe has finitely many possible states – an absurdly large number, but still finitely many.

This possibility disturbs me, and I think I’ve figured out why. Mathematically speaking, if we have infinitely many points, we can find only one equation that fits it, for it is a smooth curve, a definite function – the universe would have only one explanation. But if we have finitely many points, there are infinitely many equations that would fit the given data – for example, if we just have the points (0,0) and (1,1), the equations y=x and y=x^2 both equally well describe the data. If we have (0,0), (1,1), and (2,0), both y=-(x-1)^2+1 and y=-(x-1)^4+1 work. Et cetera. And those were all just polynomials – there’s lots of other kinds of equations out there. So a finite universe means that the universe has many possible explanations, and even at the end of time, when all is said and done, there’s no way to know which one was correct.

So finitude somewhat scares me. Then again – if the universe is finite, there are many possible explanations, but one will, I hope, be much more elegant than the others, and that will be the “true” one… that, or, since by “the universe is finite” I really mean only the physical world, the atoms and quarks and leptons and dimensions of space and time, meaning will in the end be found not in the physical, but the metaphysical. That is, I suppose, what I believe – but I’d would like to be able to find meaning in both.

Does finitude scare anyone else, or is it just me?

Movie Review: The Cube

Several years ago, my parents and I watched a movie called Cube. It’s a “psychological thriller/horror/science fiction movie” from 1997 about seven people trapped in a giant grid of cubes, 14ft in each direction, with hatches on each face (including top and bottom) that lead to identical cubes (though each cube is colored, some red, some green, some blue, some white). They’re trying to find their way to the edge of the grid so they can escape, but some of the cubes have traps that kill you.

For some reason when I first saw the movie it made a huge impression on me. I actually made a model cube out of K’NEX, with hatches and everything, that could connect to identical cubes (though I think I only made one… maybe I made two, I don’t remember).

Anyway, I saw it again recently, so I think I can now give a good account of what struck me about it when I first saw it. It was the basic premise. It’s a perfect example of the microcosms I find so fascinating. The world is made up of hundreds of connected cubes, some of which are trapped; there are people trapped inside the cube, who have to escape before they die of dehydration; this is the world. Sure, the characters were originally from the “real world”, they did have backstories, but those aren’t important; in fact, the characters’ discussions with each other are mostly about whether or not the characters’ backstories are meaningful, and the movie ends up arguing that they’re not.

Also interesting is the mathematical aspect of it. Without ruining the plot, numbers play a big role in the cube – each cube has an ID number, and they keep trying to find some sort of system based on them to know where they are in the cube and avoid the traps – but, if you know much math and pay attention to the numbers given, the math doesn’t make sense. I suspect this was intentional on the writer’s part, just trying to mess with our heads. I found this really interesting, though perhaps in the end inexplicable and without explanation.

The final reason I liked the movie was that one of the seven characters, named Kazan, was an autistic man – not just Asperger’s or something, but severely autistic. He was also the only sympathetic character in the movie, in my opinion. And his reaction to being in the Cube is fascinating. My favorite quotation from the movie is: “This room is… green. I want to go back to the blue room.”

Now, given what I’ve just said about why I like it… is it really worth seeing? Well, yes, as long as you’re not expecting anything beyond what I’ve explained above. The acting and writing aren’t that good, the characters except for Kazan are rather dislikeable, and the special effects suck; but the movie’s only an hour and a half long, it has an interesting premise, and I would say, yes, it’s worth seeing. It’s certainly enjoyable. So watch it. If you don’t mind illegally downloading things you can probably find a torrent of it fairly easily. Otherwise, I dunno, find it on Amazon or something… though I’m not sure it’s worth paying $14 to buy a copy.

Spring Break, etc

Spring Break 2009 is here, my goals, in order of descending importance:

• Release Wesnoth 1.6-compatible Orbivm content (completed!)
• Read Parts 3&4 of Crime and Punishment
• Sketch an outline for an hour-long Math Colloquium talk
• Do math homework
• Begin philosophy paper
• Begin working on new Orbivm campaign
• Finish reading Wizard of Earthsea
• Check out the Book of the Short Sun and begin reading it

Unfortunately, most of these are school-related, meaning I won’t have as much time as I’d like for the other things… ah well. Expect a review of Wizard of Earthsea as soon as I finish it (I’m halfway through right now).

Natural Talent

This is something interesting that I’m going to post here even though I wrote it for somewhere else first. On the Wesnoth forums, we’re discussing the question of natural talent, specifically in the disciplines of art and music. Is it actually natural? Are they related to each other? Etc. My answer to the (rather open-ended) question is as follows:

With respect to both art and music, I fall into the same category [as Eternal] – I naturally had above-average, but not exceptional skill, but was not motivated enough to actually pursue it, and so now I fall into the category of being better at it than everyone who never took it seriously, but worse than everyone who ever did take it seriously.

For music, for example, I’m pretty sure I was better than most people; in the school orchestra I would always make 1st chair (I play(ed) cello), make all-city and all-region, etc. But I never practiced more than an hour or so a week (they tell you to practice three). When I got to 11th grade, I kept playing it, but not as often because my high school didn’t have an orchestra and I had to take private lessons, which are only once a week and didn’t motivate me to practice as much. Now, I’m in college and haven’t picked up my cello for almost a year; if I picked it up now, I could probably carry a tune on it, be mostly in tune, and maybe even be somewhat musical in my performance, but I’d be much worse than anyone my age who played an instrument regularly.

So, right now I don’t consider myself an art or a music person, even though I sort of did when I was a kid. But it’s not that I wasn’t encouraged, or was disappointed by the realization that I wasn’t really very good and had a lot to improve (I knew that fairly soon) – it was more that I realized just how much damn effort would be required to actually become good at it, and decided I’d rather become good at other things. I could have tried to be a jack-of-all-trades, and become good at mathematics, writing, music, drawing, and maybe a few other things, but I decided to focus on a few.

And, actually, it really was Wesnoth that helped choose the things I would focus on – I started writing campaigns, and found I was decent at it and people kinda liked them, at a time when I was not nearly good enough at art to do portraits (though I tried for a while – the results can probably be found around the forum – and in theory I’m still trying to improve, just slowly) and nowhere near good enough musically to contribute (obviously – musicians here are amazing). So I kept writing, got better at it, and now am in love it and am willing to put a lot of effort into getting better.

I’m also a math nerd, though that doesn’t really show up on the Wesnoth side – but that’s also really more natural talent than actual willingness to put effort into it. I’m still doing math, and plan to major in it, but I don’t yet know whether I have enough internal motivation to keep me at it when I could be writing instead.

So, basically, (like most people here) I am fairly intelligent and, when you are young, that corresponds to being naturally good at most things you attempt. Art, music, writing, mathematics, science, whatever. It’s just a question of which ones you are motivated to get good at – because you can’t be good at all of them. I don’t think it’s so much a question of giving up on one, as of embracing another and thus necessarily abandoning the others along the way.

Tetris

Recently I have spent a considerable amount of my free time (and I have a lot of it, until Jan 22nd when school starts again) playing tetris – or, rather, Gnometris, a Free tetris clone. It is a form of procrastination, yes, but it is also a good de-stresser, and it exercises the brain, according to Wikipedia. So it isn’t a complete waste of time.

Anyway, it’s quite fun, like I said, but I have one complaint with it. The scoring is absurd. The reasoning being that making harder clears should be worth more, you get 40 points * level for clearing one row at a time, 100 points * level for clearing two rows at a time (a 20 point * level bonus), 300 points * level for clearing three rows at a time (an 120 point bonus), and 1200 points * level for clearing four rows at a time, the maximum (an 860 point bonus).

This makes sense on paper – accomplishing what is hard should be worth more, right? – but in practice it rewards poor tetris playing. Take a look at these two screenshots:

About to get one row and 40 points:

About to get four rows and 1200 points:

The former is playing tetris well – clearing lines quickly so as to get to a higher level and more points. The latter is playing tetris poorly – stacking up as many rows as possible and waiting for that line-shape (that might never come) so as to get that giant bonus. The good strategy works on any tetris level – and indeed, I can get up to level 14 using it. The latter crashes and burns by level 10 – you just can’t stack up bricks forever, you know? But at level 10, if I’m playing using my so-called “good strategy”, I’m nowhere near my limit.

The problem is, playing using the so-called “good strategy”, my high score is 47520 (and I think I got lucky there and got a four-clear without intending to). After I sat down and decided to play a game using the “bad strategy” – without any practice at it, mind you – I got 79840 points, blowing my previous high score out of the water. This makes sense, after all; at those low levels, the blocks move so slowly you can afford to use that strategy, and doing so racks up an enormous number of points before you even get to a decent difficulty level. Someone using my “good strategy” simply can’t keep up.

It might be excusable if the “bad strategy” was advisable for the first ten or so levels, and then you had to switch to the “good strategy”. But this is simply not the case. The number of points possible in levels 10-14 using my “good strategy” is significant, but nothing compared to how many would result from one lucky four-clear, so the best strategy would still be the “bad” one.

Now, if the “bad” strategy works and the “good” one doesn’t, why am I calling it “bad”? Because it doesn’t require skill in the same way that the good strategy does. You play by stacking up as high as possible and leaving narrow craters for l-shapes to fall in, not by trying to keep the blocks as low as possible and leaving yourself room to maneuver. If I could capture video off my desktop, I would film myself playing using the good strategy and then the bad one. One clearly requires skill, and the other doesn’t. It feels wrong to have to play in a style that requires no skill in order to rack up points – when that’s necessary, it means the way points are given out is flawed.

So what would I suggest? Well, the bonuses could work if they were reasonable – 1200 points for a four-clear and only 40 points for a one-clear is absurd, and, like I said, leads to bad tactics, but 40 points for a one-clear, 90 points for a two-clear, 150 points for a three-clear, and 220 points for a four-clear, or something similar, might work.
Even better, though, would be to remove the bonus for clearing multiple rows at a time altogether. The fact that you’ve reduced the height of the structure by several rows and thus gained valuable maneuvering space is reward enough, and you shouldn’t gain extra points for getting into a bad situation and then escaping it. If you insist on having scoring variation – not a flat 40 points * level for clearing a row – give bonuses for dropping the bricks quickly. That actually takes skill – being able to decide quickly where the next block should go.

P.S.: The Tetris effect is very real. I see multicolored tetraminos…

Academia (Dezember)

Heute ist Samstag, der erste Dezember.

If that’s correct – and it’s quite possible it isn’t – I just said “Today is Saturday, the first of December”.

Well obviously, you say. So what? Well – it means that today I took the Putnam today. It was a lot of fun. I think I got five questions correct (out of twelve). Not bad for a freshman, if I say so myself.

But now I won’t get to participate in any math contests until next December, when the Putnam comes around again. That’s one thing I miss about high school – we had various contests every few months or so, and if you didn’t do well on one of them, there was always another one coming up. I’m going to get to take the Putnam just three more times, and then I’ll be done with math contests. Yes, that’s three years away, but still – I don’t think I’m going to want to stop doing these sorts of things in three years. They’ve been a major part of my life for quite a while.

That sentiment seems to be one I’ve had a lot recently. Other freshmen are already talking about their plans for getting a job after college. My current plan is to go to graduate school, get a math PhD, and then teach math for the rest of my life (doing creative writing on the side, of course). In other words, I want to stay in academia for the rest of my life. I want to keep doing what I’m doing now, forever. (In fact, I had originally considered graduating from college in three years – I could do so fairly easily, I think – but now I wonder, why the heck would I want to get out of college and into the real world sooner rather than later?)

This sounds like a character from Orbivm to me. Who? Ptolenai, the mathematician. He isn’t in any campaigns, for a number of reasons – he lived in the Age of the Spear / Saecula Gentorum, he was a philosopher/mathematician not a political figure, and his story is not particularly dramatic. He lived in the Dardanoi version of the Academy his entire life. His main accomplishment, from what I’ve written so far, is his mis-calculation of the radius of the earth, which indirectly leads to the Apocalypse. Perhaps that’s a clue as to how my subconscious views academia – in which case, perhaps I ought to consider a different career path…

The astute among you will notice that Ptolenai is quite similar to the historical figure Ptolemy, though with several important differences I won’t go into here.

Why Base 10?

We (at least the math nerds among us) are having an interesting discussion on the Wesnoth forums about why we use base 10 rather than, say, base 6 or base 12. Some interesting ideas have emerged. They all have to do in some way with what base we count in. There’s in a sort of order here, but I’m not trying to make an argument for or against something, I’m just presenting some concepts. Feel free to read some parts but not others.

First off, some notational issues
Talking about bases is hard because we’re so used to thinking in base 10. There’s no real reason for this. In fact, if we had grown up using what we currently term base 6, we would call it “base 10″, because the symbol “10″ would then represent the number we currently represent by “6″. What we currently call base 10 we would call “base 14″.

Because of this, I’m not going to use the notation “base 10″, “base 12″, etc. That supposes a system based on the number that equals 5+5. But what to use instead? We have to use something. Since we want a base that presupposes nothing, the most logical choices are the unit base (base 1), and base infinity. In base 1,
1=1
2=11
3=111
…etc

But this gets very cumbersome very quickly. Base infinity, on the other hand, requires new symbols for every number. This sounds excessive, but it’s definitely possible. In this post, the sequence of symbols will be 0,1…9,A…Z,a…z, which brings me up to 6bA. That’s high enough for the purposes of this post. So I’m going to use base infinity. (Unfortunately the symbol “b” represents both that the next number is the base we’re in, and the number 37. But hopefully it won’t ever be ambiguous.)

As you may have noticed, I slipped in this thing 61bA. I’m going to use that notation to represent numbers as written in a given base. If I don’t give a base, then the number is base infinity. Obviously, I’m going to use base infinity to represent what base I’m in – that’s why I wrote bA instead of b10. b10 is meaningless – obviously whatever base you’re in can be thought of as b10, but that doesn’t give any information.

I don’t use bA especially in this post except for decimals. This is because you can’t really write decimals in base infinity, and I might as well use bA for them rather than some random base that no one will understand. However, I won’t use bA for the part of the decimal to the left of the decimal place, only for the part to the right. I hope that made sense.

Incidentally, the reason this post is marked “language” as well as “mathematics” is that the question of how to represent numbers when writing them on a page is really one of language just as much as it is a mathematical one. It has to do with how we convert information from symbols – written, spoken, whatever – to abstract ideas.

Why we currently use bA
“Because we have ten fingers”. Perhaps. But A fingers could just as easily lead to base B – we count up to A on our fingers, and then say “10!”(bB) when we put all of our fingers down again. Or we could not count the thumbs, and thus get base 8. Or go one hand at a time, and get either base 5 or base 6. And clearly this argument about it being based on the hand isn’t really applicable, because different cultures have used different bases throughout history, many of which weren’t based on the number of fingers we have:

• base 8 (Native americans)
• base K (Mayans)
• base y (Babylonions)
• base 2 (Vikings)
• base C (Imperial- system, Nigeria, Nepal)
• base 2 (specific Australian Aboriginal nations)
• base As (Romans, Chinese, Hindus)

(list courtesy of appleide)

So it seems that the reason we use base A is just that Rome, which took over Europe, China, which dominated the Far East, and India, which dominated southern Asia, used it. Mathematics, like history, is written by the victor.

Advantages of using other bases
Firstly, it seems advantageous to have the base have a large number of factors. It makes both multiplication and division easier. Now, A has only two factors (other than 1 and itself) – 2 and 5. Another proposed base, C, is slightly higher, but it has four factors – 2, 3, 4 and 6. Base 6 would give us only two factors, 2 and 3, but that would be fully half of the possible factors. So either of those bases has an advantage over A in terms of factors.

An often-raised objection against base 6 is that, since 6<A, the number of digits required to show a number b6 will increase much quicker than the number of digits for the same number represented bA. This is true to an extent, but the number of extra digits isn’t really that high. Taking the multiplicative inverse of the log base A of 6 gives us
1/log6(A) = 1.285097209...
So about 4 digits b6 for every 3 digits bA. That’s not an excessive amount.

Another base that appeals to me is b8. The concept of “subitizing” is that you can almost instantly determine the size of any set of objects with up to 4 objects in it. An example – when playing cards, in a game where you have, say, 13b10 cards, the easiest way to make sure you have the right number is to look at it as 31b4 and go “1234-2234-3234-and1″. Each set of 4 is counted almost instantly. Try it – it takes must shorter than going “1-2-3-4-5-6-7-8-9-10-11-12-13″. Given that fact, b4 would sound good, except 4 is probably too small (there’s 1.66096…(bA) digits per digit bA. So b8 is the next logical choice.

Strange Base Choices
So it seems that you want bases that have many factors, are fairly low (so that you don’t have to memorize a whole bunch of symbols), but aren’t too low (so that the number of digits per number isn’t too high). But there’s no reason you have to do this. I’m using base infinity a lot in this post. You can also do things like negative bases, fractional bases, and even irrational and transcendental bases.

Consider base e, ~2.718, (as distinct from e, =40bA). In theory it sounds like a good idea because e is the natural base of logarithms. No reason to have to memorize two different bases for two different contexts. But the problem with that is…
(b10)|(be)
1=1
2=2
3=10.2817...
4=11.2817...
5=12.2817...
6=20.5634...
7=21.5634...
8=22.5634...
OR 100.6109...
9=101.6109...
A=102.6109...

I find it interesting how 8 can be written 22.5634 OR 100.6109. this is because 8 = 2*e+2.5634 but it also equals e^2 + 0.6109, both of which would be valid under be.

Another, um, interesting thing to try is a negative base. Here’s b-6 analyzed:
(bA)|(b-6)
1=1
2=2
...
5=5
6=150
7=151
...
11=155
12=140
13=141
...
35=115
36=100
37=101
...
42=250
...
216=15000
You go up two decimal places at a time, and count backwards, sort of.

Now, let’s try a base between 0 and 1. How about base 1/2?
(bA)|(b1/2)
0.25=10.0
0.50=01.0
0.75=11.0
1=0.1
2=0.01
3=.11
4=0.01
It’s essentially inverted binary. Bases from numbers 0<number<1 function like base number^-1 but written right to left instead of left to right.

Another interesting idea isn’t exactly a legal base. It involves using both positive and negative numbers. It only works with odd numbers, I think. Here’s how you do it with b3. You have three symbols, say, “!, 0, 1″, representing “-1, 0, 1″. Then numbers are written
(bA)|(odd base)
0=0
1=1
2=1Z
3=10
4=11
5=1ZZ
6=1Z0
7=1Z1
8=10Z
9=100
...etc

Any other ideas for strange ways to represent numbers?

Well, I’m Back

I’ve been on vacation for the past two weeks in a small cabin with no internet access (in the Texas hill country around Austin, in case you’re wondering). Thus my lack of postings. But now, as Sawise Gamgee said, “Well, I’m back”.
During that time I got a decent amount of reading done – less than I could have, but a decent amount… here’s a rather short review of the three books I read.

Book 1 – Gamma: Euler’s Constant, by Julian Havil. 4/5 stars.

I’ve read mathematical history books before, and this one was a bit more mathematically intensive than any I’ve read before. Which made it more challenging to read. it was definitely worth it, though it took me about three months to get all the way through it (I often set it down for weeks at a time for various reasons).

One of the strange things about this book, I thought, is that it is supposedly about the number gamma (0.57721… ), but halfway through the book it switches to just talking about the harmonic series in general. This appears to be because the number gamma is too mysterious currently to say much about. We don’t even know if it’s rational, algebraic or transcendental…

Book 2 – The Lord of the Rings. by J.R.R. Tolkien the Mythopoeist. 5/5 stars.

I hadn’t read LotR in a few years so I decided to sit down and go through it. I’ve obviously already read it, and my opinion on it didn’t change, but I did notice some things that I had forgotten about that are worth mentioning.

The poetry! I had forgotten how many poems there were in the books – and how much of the Silmarillion material was contained in them. It would have been very interesting, I think, to have first read LotR in the years before 1973, before you could easily figure out who exactly Elbereth was, or Earendil. As it is, I already knew what the poems were referring to before I read it.

The connection between Aragorn and Arwen is much less emphasized in the book proper than I had remembered. It must be the movies screwing with my memory. The possible romance between Eowyn and Aragorn is much more ambiguous in the books, I thought.

I read through all the appendices (yes, ALL of them – including the ones about the calendars, the languages and the alphabets). There were actually some things I had never known before – for example, about the Forodwaith and the history of Arnor. That was cool, learning that. There was also some kind of disconcerting stuff about the languages of Rohan and the hobbits. it is clear that the Rohirrim don’t actually speak Anglo-Saxon, nor the hobbits English. I understand why they are presented as doing so. Still, it seems odd to me that the characters’ names as presented in the books are not those they actually had. I’m OK with “Frodo” actually being “Froda” – but, for example, I find it odd that “Merry” was actually “Kalimac”, and that “Eomer” and “Eowyn” were almost certain something completely different. Whatever.

Anyway, the rest of the book was just as cool as I remembered.

Book 3 – Atonement, by Ian McEwan. 2/5 stars.

I honestly don’t know why I read this book. I don’t often read modern fiction, which this certainly is. My basic judgement is – extremely well written, but not very substantial. Which I guess the author intended, since the book is really about the act of writing and it’s very self-referential.

It isn’t that I think it is a bad book, because it’s not. And it deals with some issues I’m interested in (though a lot of it I’m not). But overall I don’t plan on reading more like it.

6-0-0

Last Wednesday (the 20th) I was at the Rangers baseball game where “Slamming” Sammy Sosa hit his 600th home run.

That was cool, I admit, but the very idea of celebrating the 600th occurance of something makes me think about the fact that the 600th occurance of something is only worth celebrating because we happen to use a counting system based on the number 10. If we had evolved with 3 fingers and a thumb instead of 4, we would have celebrated his 512th home run (though we would have called it home run number 1000), his 576th (=1100th), and, if he gets it, his 640th (=1200th).

And even given that we evolved the way we did, there’s no need for us to use base ten. The Babylonians used base twelve. (Incidentally, Tolkien’s Numenoreans did so as well.) And we could have counted base six on our hands just as easily as we do base ten. Use one hand for the ones digit and the other for the tens (well, sixes) digit, and you can count up to 100 in base six (36 in base 10). That seems to me considerably more efficient than using base ten, where you can only get up to 10 (that would be 14 in base six) on your hands. If you couldn’t tell, I’m partial to base six. Count with me now – one, two, three, four, five, ten, eleven, twelve, thirteen, fourteen, fifteen, twenty… fifty-four, fifty-five, one hundred!

My basic point is that the number ten has absolutely no significance. We use it only because we happen to have ten fingers and happen to have decided to count on our hands in one particular way (and not a particularly good way). It is absolutely meaningless when it comes to actual mathematics.

Yet we cannot escape from it, because we were brought up to count base ten, and it is very hard to change that habit. I don’t have any proposal to change that; and it isn’t like switching to a different base would really fix anything. But we could at least stop emphasizing in our culture the significance of insignificant things, by stopping this inane celebration of events that are only meaningful because they are divisible by the number 10 or some multiple thereof.

So some part of me wants to say – do not celebrate Sammy Sosa’s 600th home run. It is no greater an achievement than his 599th, or his 598th, or his 601st which he hit last night. We shouldn’t be comparing ballplayers against meaningless standards like 500 or 600 home runs, or 5000 strikeouts, or 300 wins, or 3000 hits. We should be comparing them against each other. Much more interesting than Sammy hitting 600 would be Barry Bonds passing Hank Aaron with 756. Celebrate (or boo, as I will) that as much as you want.

USAMO

I am very happy – I scored well enough on the AMC12 and AIME to make the USAMO.

Of course, practically, this isn’t a very good thing. In essence, it means that I get to spend nine hours after school taking a mathematics competition when I could be home doing more productive things. And, while it is certainly impressive to have qualified for the USAMO, I somehow doubt it will be all that useful to put that on my résumé.

But it is still very cool to be able to qualify for such a contest, and perhaps – if I am either extremely lucky or much better at math than I thought I was – I will even be in the top six in the nation and make the American IMO team. I would get to go to Vietnam for a week.

Here’s a sample problem from the 2003 USAMO:

Given a sequence S₁ of n+1 non-negative integers, a₀, a₁, … , a_n we derive another sequence S₂ with terms b₀, b₁, … , b_n, where b_i is the number of terms preceding a_i in S₁ which are different from a_i (so b₀ = 0). Similarly, we derive S₂ from S₁ and so on. Show that if a_i ≤ i for each i, then S_n = S_n+1.

The solution:

Note that the derived sequence b_i also satisfies b_i ≤ i (since there are only i terms preceding b_i). We show that b_i ≥ a_i for each i. That is obvious if a_i = 0. If a_i = k > 0, then since each of the first k terms (a₀, a₁, … , a_k-1) must be i ≥ k.

Next we show that if b_i = a_i, then further iterations do not change term i. If b_i = a_i = 0, then none of the terms before a_i differ from 0, so all the terms before b_i are also 0. But that means the corresponding terms of the next iteration must also all be 0. If b_i = a_i = k > 0, then since a₀, a₁, … , a_k-1 all differ from a_i, the remaining terms (if any) a_k, a_k+1, … , a_i-1 must all be the same as a_i. But that implies that each of b_k, b_k+1, … , b_i-1 must also be k. Hence if the next iteration is c₀, c₁, … then c_i = k also.

Now we use induction on k. Clearly term 0 is always 0. Considering the two cases, we see that term 1 does not change at iteration 1. So suppose that term i does not change at iteration i. If term i+1 does change at iteration i+1, then it must have changed at all previous iterations. So it must have started at 0 and increased by 1 at each iteration.

This will be an… interesting contest. Hopefully I’ll be able to answer at least one of the problems.