The culmination of laborious scribing

Here is THE list of quotes from a totally unknown source. It's *chh!* OP! *ss...*



"I told my doctor i broke my leg in two places. He told me to quit going to those places."

"Who is John Galt?"

"It takes only one drink to get me drunk. The trouble is, I can't remember if it's the thirteenth or the fourteenth."

"My doctor gave me two weeks to live. I hope they're in August." -Ronnie Shakes

"The greatest pleasure in life is doing what people say you cannot do." - Walter Bagehot

"The secret to creativity is knowing how to hide your sources." -Einstein

"Experience is a good teacher, but she sends in terrific bills." - Minna Thomas Antrim

"Go, and never darken my towels again." - Groucho Max

"Sometimes I think the surest sign that intelligent life exists elsewhere in the universe is that none of it has tried to contact."

"A boy can learn a lot from a dog: obedience, loyalty, and the importance of turning around three times before lying down." -Rob

"Students achieving Oneness will move on to Twoness."

"It's fun to charter an accountant, and sail the wide accountancy..."

"No opera plot can be sensible, for people do not sing when they are feeling sensible."

"If you believe everything thing you read, better not read."

"It is impossible to enjoy idling thoroughly unless one has plenty of work to do."

"Under capitalism, man exploits man. Under communism, it's just the opposite."

"Those who believe in telekenetics, please raise my hand."

"Never be afraid to laugh at yourself, after all, you could be missing out on the joke of the century."

"Assuming either the Left Wing or the Right Wing took control of the country, it would probably fly around in circles."

"Alcohol may be man's worst enemy, but the bible says love your enemy." -- Frank Sinatra

"When I was kidnapped, my parents snapped into action. They rented out my room." -- Woody Allen

"Kleptomaniac: A person who helps himself because he can't help himself."

"A good lawyer knows the law. A great lawyer knows the judge."

"Ninety percent of the politicians give the other ten percent a bad reputation."

"Just because nobody complains doesn't mean that all parachutes are perfect."

"Hard work never killed anybody, but why take a chance?" -- Charlie McCarthy

"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?" -- Jerry Bona

" 'I am returning this otherwise good typing paper to you because someone has printed gibberish all over it and put your name at the top. ' -- An English professor, Ohio University, also probably the fate of most of my essays"

"No one can have a higher opinion of him than I have, and I think he's a dirty little beast."

"The trouble with having a open mind, of course, is that people will insist on coming along and trying to put things into it."

"Isn't it interesting that the same people who laugh at science fiction listen to weather forecasts and economists?"

"Mistakes are part of the dues one pays for a full life."

"After all is said and done, a lot more will be said than done."

"Does this rag smell like chlorofoam to you?"

"Never try to tell everything you know. It may take too short a time."

"Brain: an apparatus with which we think we think"

"Income tax returns are the most imaginative fiction being written today." -- Herman Wouk

"We've heard that a million monkeys at a million keyboards could produce the complete works of Shakespeare; now, thanks to the Internet, we know that is not true." -- Robert Wilensky

"The direct use of force is such a poor solution to any problem, generally employed only by small children and large nations."


Cheers!

P.S. "dammit... foiled"

Paradox regarding infinities?

Mm… today I read about Cantor’s diagonalisation argument, arguing that there exists infinities which are bigger than others. At first, this sounds obvious, but when considering that for an infinity (let’s call it X), X+1=X, this suddenly seems a lot less obvious.

It would seem of utmost importance to give a general idea of the definition of equal sizes of 2 sets. For finite sets, this is already obvious by, in short, counting. The size of {1,2,3} is 3, which is less than the size of {-1,-2,-3,-4}, but for infinities, this is again less obvious (bah… infinities just have to be this hateful).

However, we note that it is possible to compare sizes of finite sets in a different way. Let’s just say that we wish to compare the sizes of the two abovementioned sets. We attempt to achieve a bijection between members of the 2 sets, say 1->-1, 2->-2, 3->-3, and lo and behold, we are stuck, for there is no other element in {1,2,3} left to biject to -4. So how do we know that it is impossible to choose a different mapping from the first set to the next that produces a bijection? In this case, it is simple, and trivial by Pigeonhole Principle (finite sets ftw!). However, as we shall see the in the case infinite sets, this is no longer as straightforward nor convenient (again, infinities are irritating; bzz…).

Firstly, let me brief explain why X+1=X. Suppose X is the cardinality (size) of the set of natural numbers, because other infinite sets are probably just analogous, but infinitely (pun!) more irritating to write an explanation for. So, a bijection is given as follows: let the new element representing the +1 be 0 (yes, 0 isn’t a natural number to me, now stop that argument already). A bijection (from set of natural numbers to the set also with 0) would be 1->0, 2->1, 3->2, …, n->n-1,… where n is, well…, any natural number.

Taking this one step further, now let us “prove” that X+X=X*2=X. Again, suppose that X is the cardinality of the set of natural numbers. Let the new X elements be a1, a2, a3,…. Now, a bijection (from the set of size X to the set of size 2X) is given by 1->1, 2->a1, 3->2, 4->a2, and so on, with n->(n+1)/2 if n is odd, and n->a(n/2) if n is even, for all natural numbers. (Ok, I admit set notation looks cooler, but I’m typing.)

As an attempted Mathematician, let me enthusiastically take this just one step further (the hour’s getting late!). The next thing in the series is to prove that X^2=X. This is cooler.

All right. Time out. I just thought of something to whine about infinities in general. The main problem with infinities is that unlike finities (is there such a word? O.o), inductive approaches do not work. For example:

1=1+0+0+0+0… = 0+1+0+0+0…=…=0+0+0+0+…=0 (?).

Clearly, there is a step in the middle where the induction just fails. Hence, infinities tend to refute everyday logic of things like… … … … … … … … … an irritating thing.

Back to proving X^2=X: now let us consider the set of positive rational numbers, given in (sometimes improper) fractions. A rational number is one expressible in terms of a/b, where a and b are integers. Hence, a positive rational number can be expressed as a/b, where a and b are rational numbers. Yay! Now we shall arrange the rational numbers in a square with a top left hand corner and the other corners at infinity. Being a nitpickish person, I shall arrange it as such:

1/1       1/2       1/3       1/4       …
2/1       ----       2/3       ----       …

3/1       3/2       ----       3/4       …

4/1       ----       4/3       ----       …

.           .           .           .

.           .           .           .

.           .           .           .

  Now, imagine a grasshopper from Bremen, Germany starting from the top left hand corner of the square. It hops in this order:

1          2          9          10        …

4          3          8          11        …

5          6          7          12        …

16        15        14        13        …

.           .           .           .

.           .           .           .

.           .           .           .

  Now we formulate our bijection in the order of the leaps our dear grasshopper makes:

1->1/1, 2->1/2, 3->2/1*, 4->3/1, 5->3/2, and so on. Now, every rational number has a corresponding natural and vice versa. Therefore, by our definition, X=X^2. Wonderful.

*since 2/2 has been nitpickily replaced by a dash for being the same as 1/1

  Readers are like, totally encouraged to attempt to prove that X=^XX (see tetration), and owing to the awesomeness of Conway, a->n->3, a->n->4 (see Conway’s chain notation). They, by the unjustified basis of scientific induction, should hold true as well.

Honestly, the original purpose of this post was to raise a contradiction I convinced myself of, but that has since been resolved. Nevertheless, it would probably be interesting to figure out where the mistake lies. Let the hunt for the fatal flaw begin.

Cantor’s diagonalisation argument (omg finally on to the point of the post) can roughly be stated as follows:

The power set of a set S refers to the set of all subsets of S (or so I believe). So, illustrating with a finite example, the power set of {1,2} contains the null set {}, {1}, {2}, and finally {1,2}, the set itself.

The argument concludes that the power set of any infinite set is larger than the set itself.

For the sake of convenience and easy reading, we shall assume that the infinite set involved is the set of natural numbers.

Firstly, a bijection between the power set and a real number (haven’t really thought much about this yet, might be wrong) between 0(inclusive) and 1(exclusive) can be established as follows:

Let such an arbitrary real number be denoted as 0.abcdefghijklmnopqrstuvwxyzα…, written in binary. Now let a subset of the natural numbers S map, in the bijection to the following real number: 0.abc… where a=0 if 1 is not an element of S and 1 otherwise, b=0 if 2 is not an element of S and 1 otherwise, and so on. Therefore, both the set of real numbers from 0 to 1 (yes, I might regret saying this) and the power set of the set of natural numbers are of the same cardinality.

Now let us prove that the cardinalities of the power set of the set of natural integers exceeds that of the set of natural numbers. We approach this via a proof by contradiction.

Suppose otherwise; i.e. there exists a bijection between the set of natural numbers and the power set of the set of natural numbers. Then there exists a bijection between the set of real numbers between 0 and 1 and the set of natural numbers. Let the bijection (from natural numbers to the power set) be as follows:

1->0.…

2->0.…

3->0.…

and so on, where (naturally) represents either 0 or 1.

  However, we observe that there is a real number between 0 and 1 that is definitely not equal to one of the real numbers already bijected to. A possible real number can be expressed as: 0.b1b2b3b4b5b6b7…, where b1 is NOT() (binary operators!), b2 is NOT(), b3 is NOT() and so on. Hence, the bijection is not a bijection, i.e. there exists a contradiction, meaning our original assumption of a bijection between the set of natural numbers and its power set is impossible.

Intuitively, a corollary is that 2^X>X, since the cardinality of the power set is larger than the cardinality of a set itself.

However, if we consider the powers of 2, we notice that there are an infinite number of perfect powers of 2, and for convenience, we shall call the infinity Y. Now, 2^Y and Y are not equal, meaning that this set is smaller than 2^Y, by the above argument. However, if we map n->2^n, we notice that the number of powers of 2 and the number of integers are in fact equal since the bijection holds. Therefore, 2^Y indeed equals the number of natural numbers. However, if we consider the first k powers of 2, there are 2^k natural numbers smaller than or equal to the largest power of 2 mentioned. By extension, the number of natural numbers is roughly equal to 2^Y (arguably with a factor of 2). But that gives 2^Y>=X/2=X=Y. Clearly, something is wrong somewhere. Can you find the fatal error?

My solution is given in (hopefully) the same colour as the background below. Highlight to review.

Whoever said that the power set of an arbitrary infinity X had cardinality 2^X? The combinatorial argument for this does not appear to hold for infinities as it is inductively based. See what I mean about infinities being irritating and counterintuitive?

YAY LAME JOKE

Q: Why don't students brush their teeth before big exams?
A: Because they want to cheat during exams via yellowtooth.

Random Cchess match

Truly random.

1. C2.5 c8.5 2. H2+3 h8+7 3. R1+1 r9.8
4. R1.6 a4+5 5. R6+7 h2+3 6. R6.7 c2+2
7. P7+1 r8+8 8. A6+5 a5+4 9. H8+7 a6+5
10. H7+6 c2.8 11. R9.8 c8-3 12. C8+7 a5-4
13. H6+4 h7-5 14. R7+1 h5-3 15. C5+4 a+-5
16. H4+5 e7+5 0-1

RJT chess -- General Ideas 2 (Attack series)

Here is a nice picture I made using screenshot and Qianhong (Go try it.), showing a position (well... yea) with red to move.



Red appears to be winning. However, if for example, R2=5, K5=6, and there is (for now) no mate! And in this game, that's a scary thought. It's tiring to think of a mate...
Instead, there exists a (hopefully I'm correct...) miraculous move in this situation! Can you find it? (Yes you can...)

C1-1!

This move prevents the shi from being any useful in the defence of the king. Amazing move!... right?

Let's assume black totally does not see the danger of this, and plays a random move!

... P5+1

Suddenly...
R2=5+
...K5=6 (K5=4 is just suicidal)
R5-1+
...K6-1 (forced)
C1=4, planning R5+1 the next move. Good game; well played!

Edit: Swapping the first and second moves totally appears to work better. Awww...

RJT chess -- General Ideas (Attack series)

Notice that I did not call it strategies, as the ideas I shall mention are really quite vague, but nevertheless somewhat (surprisingly) applicable to a real match of RJT chess.

This post focuses on the attacking madness bit of RJT chess, and (hopefully) another post will eventually be made (might not be by me) on the defensive bits of RJT chess and its strategies.

Big strategies
--------------
1) Getting in sufficient firepower:

Firstly, it is practically impossible to kill with just a single piece, no matter how menacing it may look, under general conditions, as any piece may interpose and hence stop its rampage. *sad face*

Hence, an important attacking idea is to ensure that at least a few pieces (depending on how good your tactical skills are as well as how blind you think your opponent is) can get in to a threatening distance of your opponent's king. (usually as long as it restricts the movement of some of your opponent's defenders; for example, a cannon (pao), as denoted conveniently by C, may pin 2 pieces to your opponent's king. Similarly, A single well placed piece may disrupt the movement of advisors (shi, denoted by A) in the palace.)

Hence an important concern is how to get sufficient firepower next to your opponent's king.

2) Make your opponent commit:

With an action as simple as stuffing a chariot (R) in front of your opponent's king, you typically would have made him commit as to which side he is keeping open and which side is more closed to attacks. Hence, it is more convenient to marshall your forces as you know where they would want to go.

3) Remember your small (but not unimportant at all) BINGS (P):

When your attack looks like it's stalling, bring in the P if there are still open lines and 'ma's (H) if there are no open lines. Since you have 5*P, that can really tie down a good portion of your enemy's pieces especially if he does not defend strategically.

4) Crowd a place when all else fails:

If your normal attacks are not going through, it is possible (and has worked before with great success) to crowd out your last checks with pieces (power of the bing!) and hence win the game by claiming that you are left with no checks at all.

Small strategies
----------------
1) Attempt to get your C directly into the line of sight of your opponent's K with absolutely nothing in between. Since nothing may be stuffed in between, a final strategic single check may prove to be absolutely fatal. Plus this really messes up your opponent's defensive formation. Also, it sounds like a good idea to move your C rather far back to create a zone where your opponent absolutely cannot place his pieces. Happiness ensues.

2) Liberate your horses! They are typically the pieces which finally gets in the important check, as it is rather simple to block off checks from all other pieces with just... well 6 defenders (2 on each side) of the king.

That's all the attacking ideas I can think of for now, and I will (may) return to give more details on each of the strategies at a later date when I finally manage to conjure up semi-professional-sounding ways to explain the how and why of each strategy. That or when I get bored again.

Last Minute Vocabulary Mugging

parochial: A narrow view on things
squander: Waste
beset: Trouble or threaten persistently
stiflying: Restraining
rabid: Fanatical
wanton: Deliberate and unprovoked
craven: Completely lacking in courage
ebullience: Exuberance
insinuate: Suggest or hint in an indirect or unpleasant way
felicity: Intense happiness
cutthroat: Fierce and intense, often ruthless
misanthrope: A human who dislikes mankind and avoid society
audacious: 1) Imprudent 2) Showing a willingness to take risks
indubitably: Undoubtedly
pontificate: Expressing one's opinions in a very pompous manner
purport: To claim to be or do something, often falsely

Ok I got lazy. Good luck for GP tomorrow!

Comments on statement "Instead of the pursuit of the truth, science has become the pursuit of profit."

Science was once a branch of philosophy, but has evolved into a field of its own, defined by the pursuit of truth through the scientific method, which fundamentally derives from the method of scientific induction, which predicts phenomenons through past observations. What science pursues is not the absolute truth, but rather a workable truth, in fact the simplest truth, that is consistent with our observations, a philosophy known as Occam’s razor. The other defining characteristic of science is the setting up of experiments to observe specific phenomenons while complying to the principles such as reproducibility, which ensure that science is the same throughout the universe and any truths found are universal. Ever since leaving the branch of philosophy, science has been “contaminated” with various less philosophical aspects to it, such as applied science, which revolves around making science more applicable. This has also attracted firms to take up research in order to utilise science in their pursuit of profits, be it through the increase of competitiveness through product innovation, or to increase the efficiency of their workers and hence maximise their profits. Examples of firms utilising science for a profit motive include GlaxoSmithKline, Monsanto, and more ubiquitously, Airbus.
Instead of exclusively pursuing truth, science has now been utilised by companies in their pursuit of profits. This largely stems from science’s effectiveness in producing visible results in the real world. This effectiveness can be said to stem from a unique characteristic of science, as new generations of scientists build upon the observations and theories of the past, leading to the constant and rapid improvement of science. Furthermore, science is now in a golden age; ever since the advent of computers and especially the Internet, the storage and transmission of information from scientific research and experiments has never been so easily archived and shared, and building upon another’s work has never been so convenient. As such, firms today tend to find it irresistible to engage in scientific research. This is evident in how companies such as GlaxoSmithKline pour billions of dollars into developing cures to specific diseases in order to reap the profits that come with a monopoly on the production of a medicine.
Furthermore, for scientists, research is now a globally accepted field which has been known to come with huge financial remuneration, as firms gradually recognise how scientific research can put their balance sheets in better light. In today’s materialistic world, there has undoubtedly been more than just a handful of scientists who forsake the pursuit of pure science for applied sciences for the sake of financial remuneration. In an extreme case, in order to secure his job as a researcher Huang Woo-suk had faked numerous papers about his stem cell research in order to impress his employers. This can, to a certain extent, explain why scientific research is trending towards the goal of profit seeking.
However, there remains strong support for the “pure” sciences, especially in fields such as physics, where physicists all over the world are currently devoting great efforts to find out about the fundamental nature of the universe, and the search for elementary particles, while not having much obvious practical use, has called for extreme measures such as the development of a cross-border project: the famous Large Hadron Collider. Such research is clearly for the sake of the pursuit of truth, and it would be a sweeping statement to conclude that science has degenerated into the search for profits.
Besides, the pursuit of profits in science may not be totally without its merits. The science of today contrasts from science of the past in one superficial but nevertheless striking way: that it is much more elaborate and hence expensive. For example, while a basic physics lab fifty years ago might have been equipped with rulers, stopwatches and mirrors, the basic physics lab of today involves more sophisticated instruments such as the travelling microscope, the data-logger and polaroids. At the advanced level, this distinction is particularly glaring as modern physicists today have spent billions of dollars creating extreme conditions such as freezing temperatures close to the Absolute Zero, where no heat exists, the acceleration of electrons to near-light speeds through large potential gradients, as well as the creation of extremely powerful lasers which require large quantities of tailor-made lenses and surfaces. Without the commercialisation of science, the traditional sources of funding such as donations will definitely be insufficient to fund the extravagance needed for the optimal progress of science today. Hence, the commercialisation of science does indeed bring about its own benefits.

Poem Writing Exercise 2

Driving By Woods on a Hungry Morning

There was once a bear called Barr
Who likes to drive a big red car
He drives the red car through the woods
Foraging around for food.

One day, he met a honey bee,
who got frightened, and stung his knee.
But Barr the Bear was undefeated,
"ME WANT MORE FOOD", he repeated.

So though the forest the bear roamed,
In search for the honey hive
At last he spotted what he seeked
And into the hive he dived.

But alas, it was not to be,
For angry wasps were waiting for him.
Basically, he got pwned
By the nasty little wasp stings.

Hungry, beaten, stung and stunk,
Barr the Bear was still unfazed.
"I'll BE BACK", he chanted,
There're still ten acres for him to raze.

Poem Writing Exercise 1

How does Marken write such nice poems? I want to learn!

Ok let's try.

Scrambled eggs are cool
Cos when they splatter
They make a good meal
On your platter.


Unsheath your sword!
Charge across the landscape!
Kill those minions!
Oops, its runescape!


Beware of dragons
for they breathe fire
that will surely melt
those plastic tyres.


Bleh, looks like it's not working :(.

Ah well, let's tell a knock-knock joke instead.

A: Knock Knock!
B: Who's there?
A: You know.
B: You know who?
A: Yes.

New random rant (about symmetry)

I was thinking about a universe which was symmetric about a plane (across space 3D) and without quantum randomness (ie. the future is uniquely determined by the state of each particle now).

Imagine a person near the plane, staring at himself from the other side of the universe, although with exactly the same laws. He cannot go over, because any part of him cannot possibly cross over without hitting its counterpart.

A simplistic "solution" might be to agree with himself on the other side to both stick out their right hand across the plane of symmetry. This would have worked, if in his part of the universe, right had not been left (dang!).

It would appear that this symmetry can never be broken, just like a mirror, so I wondered a few things:

1) Is it really true that this symmetry cannot be broken?
2) How do we know that the mirrors we see on the wall are not planes of symmetry in the universe (assuming the daily notions of laws of physics)?

For question 2, I realised a rather trivial solution. A key difference between a mirror and a possible plane of symmetry is basically the property about a normal mirror that it is breakable. Planes of symmetry cannot break apart just like that.

For question 1, it would appear that the relation between electricity and magnets provides a solution, because reversing both magnetic field and electric field does not reverse direction, and hence both forces can be in the same direction, but is that really true? o.O I have no idea.

More whats.

Well, after the chaos of the previous visit's events, I decided to chance another trip to the H > P club. And sure enough, the management had the players running rings round them so fast they were like Saturn. In an ingenious twist of plot writing, the players had formed cliques with other players who preferred certain openings, and even the bouncers of the management took part in the squabble. I found out the following:

0. An individual may be in any number of cliques, and be a bouncer or a player, it matters not which for the below conditions.
1. All the bouncers alone formed the clique of the Sicilian O'Kelly. "And we are all good chessplayers who know better!" they rallied.
2. All the players alone vehemently insisted the Benko Gambit was better. "And we are all poor chessplayers!" they yelled somewhat ironically.
3. Each individual had a favourite opponent, and an opponent he most despised (not the same person; they're not that insane.)
4. Given any clique, all individuals whose favourite sparring partner/opponent/punchbag was on the clique, formed their own clique.
5. Ditto of 4, just replace "favourite" with "most despised".
6. Given any 2 cliques, there was at least one individual (let's call him Sad) whose favourite opponent thought Sad was on one clique, and whose most depised opponent thought Sad was on the other clique.

Well, this wouldn't do. Amidst the rat-tat-tat of Alekhine's Gun and the table-turning (sacrifices) that formed part of a huge brawl, I talked to the manager (wisely taking no part in this, hiding under a hedgehog.)

Me: "Are all your bouncers sane?!"
Manager: "Yes, at least they're supposed to be! What the heck is going on!"
Me: "Interesting! Do you know, there's at least one person who deserves to be thrown out of this establishment?"
Manager: "You think!?!!"


The Frighteningly Mad Professor Edalpo: Well, this is a rather queer parable. But indeed, the narrator was absolutely right; can you prove that there was some individual who shouldn't be there in that stead? Remember, all bouncers are supposed to be sane, while any poor chessplayers should not be allowed in.

What

I believe separately in all the following statements:

- Sane people have true beliefs.

- Insane people have false beliefs.

- Questions are asked only by questioners, who may be sane or insane.

- Type A questioners ask questions that they believe the answer to which must be true. Type B, false.

- Questioners may be sane or insane.

- Everyone utters what they believe is true.

Well then. Hello. So, I believe you know that I am insane? I'd have to be to be posting here, after all. So, to alleviate the boredom spent in the land of the mushroom clouds, here is a nice little set of questions, adapted from a little book of such.

So I took a little stroll to the H > P chess club down the street, where they had a couple of sane and insane players. Some were good players, some poor players. The good players believed the value of H > P, the poor ones believed H =< P. Due to the name of the chess club, it was obvious that the management would kick out the dissenters, but they were doing a lousy job of it! Can you spot all the infidels/heretics/cannon-lovers from the following interactions? [The management, represented by M, are all sane type As.]

M: You seem to be a good player.

Turtler: Thanks, but I believe I'm quite poor at this, really. Do bings move like queens?

M: *facepalms* [To M's opponent, Sacr] Is that why you're losing?

Sacr: I'll be kippered, 'tis so! Aren't you a smart one, laddie! I must be 'orrible at chess to not pick that up!

Turtler [To M]: You're saying bings don't move like queens?

M: *sigh* Am I the type who could lie about that? Now, if you're not convinced, ask him.

C. King: Do you believe I am the type who could ask you if you're insane?

Turtler: He's talking like a nutcase.

M: Tell it to him, CK. Just leave me out of this madhouse. *walks away*

C. King: You're a rather poor player to get into this position.

Turtler: For a good player, you're thoroughly insane. I'm winning!

Sacr [To Turtler]: Who're you to judge, madman?

*fight* *All 3 were thrown out for rowdiness*

The Frighteningly Sane Doctor Tarrfether: So, is everyone a good player? Or were there poor players? Am I the type who could ask you these questions? Am I sane? Are you? Is the writer of this post? [All can be answered.]

Big numbers

We once learned to count, and for a while, 10 seemed like a big number. Then 100 seemed the limit of numbers, until one thousand came...

As we learn how to count without a limit (you do know what forty-five thousand, six hundred and seventy-eight plus one is right...), it seems that we have mastered all ways of expressing numbers, no matter how big. Yet, this is often nearly not the case in practice. When writing out the rest mass of an electron, we do not write 0.000000000000000000000000000000911 kg. (Well usually we don't, don't be a weird person)

Instead, we use a more powerful, space saving notation for numbers of this small magnitude: 9.11*10^-31. Neat. This also works for larger numbers, like 3.14*10^8=314000000. Looks perfect, but is not quite the best yet.

This is also clearly a use (abuse) of the power notation, where a^b= a*a*a*a*a*a... b times. So how about we get a little creative.

Note:
a*b = a+a+a+a+a+a+a+a... b times
a^b = a*a*a*a*a*a*a*a... b times

We shall define tetration as a b, where the power is applied b times. And we notice that we can extend it further. Hmm... Conway chain notation... ...

Too mind-bogglingly big, and suspect usefulness. Ah well. But anyway, a rather skimpy list of functions in order of bigginess:

+ < */polynomial < ^ < ! < tetration

Nice DP lecture

I think the book is nicer though.

Number theory

I found a nice Number Theory question, so for those people who want to attack it directly, here it is:

Prove that exp 2^2(x) is eventually constant mod n (as x increases), where n is an arbitrary positive integer.

But since I expect few to solve it from there (main because of notation), I guess I should explain the weird notation.

exp 2^2(x) actually came from my interpretation of the Wikipedia article (wanted to add Knuth's up arrows, but I'm a lazy person). So what it's supposed to mean is 2^2^2^2..., with x number of 2s. This might not be standard notation, but it's what I got from Wikipedia.

Next mod n, for those who don't know, is basically asking what the remainder when the number is divided by n, eg 42=19 (mod 23), and 31 = 5 (mod 26).

So before I go on hinting like a maniac, it's time to talk about number theory in general. Number theory, in general, talks about the properties of integers. For example, number theory attempts to describe the properties of primes. However, Wikipedia lists at least 5 fields of number theory, such as algebraic number theory. In general, fields such as analytic number theory are more for research problems, which are still relatively open problems, but elementary number theory has a large number of solved problems which have elegant solutions and are light to solve (well, not as bad as researching a problem for months).

Number theory is rather interesting; when you look at a problem, it's hard to tell whether it might be easy or hard, with some messes quickly reducing to workable expressions, but stuff like proving that x^n+y^n=z^n has no integer solutions for n>=3 looks simple, but involves elliptic curves (see Fermat's Last Theorem). However, in this case, it both looks easy and is pretty doable.

Now, for people who have done some kind of number theory before, for the original question in this post, it helps to define it as a recurrence relation, with a1=2 and a2=2^a1 = 2^2 = 4. Then it suffices to prove that 2^ai = 2^a(i+1) (mod n) for any sufficiently large i.

Next, it helps to know Euler's Theorem, but is completely unnecessary (really).

The next important thing to know is the idea of induction. The general format of induction can go something like this: Student 1 is a boy. If Student i is a boy, then Student i+1 must necessarily be a boy as well. Therefore, Student 2 is a boy, therefore Student 3 is a boy, et cetera. We thereby conclude that Students 1 to the last student are all boys.

There is a similar form of induction, which works backwards. This works by say, concluding that Student i is a boy if Student i-1 is a boy. Student i-1 is a boy if Student i-2 is a boy, and this traces all the way back to Student 1, who is a boy. We are done.

An important thing to know is that the sequence 2, 4, 8, 16, 32, 64, ... enters a cycle mod n. To prove this, the most primitive way I can think of is to think of the ith term and the (i+1)th term. Say the remainder when i/n is x. This means that 2^i=kn+x, for some integer k. Therefore, 2^(i+1) = 2kn+2x, which when divided by n, gives a remainder solely defined by x. Hence, one can think of walking the remainders like a path, and with finite number of destinations to visit, one must eventually go back to the same point. Since the direction from any starting point is uniquely defined (ie you're forced to walk the same way from any same point), once you get back to the same point, there is no way you're ever going to break out from the cycle.

The substep to prove is that the length of the cycle is less than n. (Hint: consider 0 mod n)

Bad Spoiler Alert: (highlight to see)
Following this, you may realise that if the length of the cycle mod n is x, then the value of 2^i mod n is dependent on the value of 2^i mod x, where x is smaller than n. This is the induction step.

Don't forget your base case when induction though.

P.S.: This post is shorter than I expected it to be, my essay spamming skills must have deteriorated. Ohnoes.

Yet another 26 move chess match

START{
1. H2+3 p3+1 2. P3+1 h2+3 3. C2.1 c2.1
4. R1.2 c8.9 5. C8.7 h8+7 6. C7+3 e3+5
7. C7+1 r9+1 8. H8+7 r1.2 9. E7+5 r9.4
10. C7.3 h3+4 11. A6+5 r2+7 12. R9.6 r2.3
13. H3+4 h4+6 14. C1.7 r4+8 15. A5-6 h6-7
16. R2+3 c1+4 17. C7.9 h++6 18. C9+4 h6+4
19. C9.7 h7+6 20. R2-2 c1+3 21. E5-7 h6+5
22. R2+2 h5-7 23. R2.6 h7+6 24. K5+1 h6-4
25. K5.6 e5+3 26. C7.1 c9.4 }END

Just a chess match

1. H2+3 c2.5 2. H8+7 p7+1 3. C8.9 h2+3
4. R9.8 h8+7 5. P7+1 h7+6 6. R8+5 c8+2
7. R8+1 r1.2 8. R8.7 r2+2 9. C2.1 c8-3
10. R1.2 c8.3 11. R7.9 r2+6 12. R9-1 h6+7
13. R9.3 h7+9 14. E3+1 r9+1 15. R3+4 h3-5
16. R3-4 c3+6 17. E1-3 r9.6 18. R3+1 r6+7
19. A4+5 r2.3 20. E7+5 r3.4 21. A5-4 c5.2
22. C9.8 c2.4 23. A6+5 r4.2 24. R2+7 r2+1
25. A5-6 r6.4 26. A4+5 c3+2 }END

Extended Euclidean Algorithm

Yay, today I learnt (more precisely, relearnt) Extended Euclidean Algorithm. Yay, I can start solving Diophantine Equations again :D

void EGCD(int a,int b){
 if(a < 0 || b < 0){
  EGCD(abs(a),abs(b));
  if(a < 0) x = -x;
  if(b < 0) y = -y;
 }
 else if(b == 0){
  x = 1;
  y = 0;
 }
 else{
  EGCD(b,a%b);
  x1 = y;
  y1 = x-(a/b)*y;
  x = x1;
  y = y1;
 }
}

Below is random experimentation with HTML tags and javascripts on blogs
This is Google



HOW DO I ENABLE ALL THE RANDOM LANGUAGES AND SCRIPTS???

Post drought

To stop this post drought (while the next article on RJT Chess is tentatively being written), I shall post an error code arising from my randomings on C++.

invalid types 'int [((unsigned int)((int)(X*Y)))][]' for array subscript

That's quite a lot of brackets towards the middle.

Sails (IOI 2007 Problem)

The problem roughly goes: You have a ship with N<=100,000 flagpoles, and each flagpole has an integer height up to 100,000. Each flag can only occupy a height of the flagpole at integer heights. Because the ship should be as aerodynamic as possible, air resistance comes into play. For each flag (don't question the question), it contributes a drag of X Newtons, where X is the number of flags behind it (w.r.t. direction of movement) flying at the same height. Your task is to write a program to determine the minimum amount of drag induced by the flags in total given the height and number of flags on each flagpole.

Here is my proposed algorithm: subject to flaws major and minor:

We make a few random observations that I'm not too sure where they appear in the solution, but let's just list them down first:

1) Total drag = summation x(x-1)/2, where x is the number of flags at each height.
1.1) It doesn't matter what order the flagpoles are arranged in.

2) There exists an optimal solution where the number of flags in each height is non-decreasing as the height gets lower.
Proof: Consider an optimal solution (if it exists) where two consecutive heights are such that the higher height has more flags, then the flags can be shifted down (by Pigeonhole Principle or something, because on the same pole there will exist space for the flags to move down)

3) The objective is to try to spread flags out as far as possible.
"Proof": 3+5>4+4 (by 1 Newton of drag), since well, can't be bothered to explain this.

4) Assuming a/b>c/d, a,b>c,d>0,0 (improvised notation ftw), then (a-c)/(b-d)>c/d.

Proposed Solution Part 1: Definitions
-------------------------------------
Define the highest level of the highest flagpole to have height 1, the second highest level to be 2 and so on, until n.

Define g(i) to be the maximum number of flags you can fly at equal to or higher than the level i.

Define f(j,k)= |g(j)-g(k)/(k-j)| (modulus function ftw).

Proposed Solution Part 2: Calculating g(i)
------------------------------------------
Raise all flags to the maximum. The number of flags at or above height i is now g(i).

To calculate all g(i) in O(N) time, we let the flags at each flagpole by represented by a range (after being raised to the maximum).

The sum of the total length of all parts of all ranges above i is then g(i).

Hence, at the start of each range, we add 1 to an array, and minus 1 after the end of each range. (ie a[0]=0, a[1]=a[0]+number of ranges starting at 1 - number of ranges ending at 0)

g(i) is then the sum of a[0]+a[1]+...+a[i] (or something like that).

Proposed Solution Part 3: The Idea
----------------------------------
Since we wish to spread out the flags among heights evenly, we will try to see whether we can do this 100% efficient. As it turns out, we cannot, because the higher levels will not fit as many flags.

So, we will probably wish to stuff as many flags into the higher levels as possible before moving on to the lower levels.

Say for the highest 6 levels we can fit 5, 14, 14, 16, 17, 18 flags respectively. Then clearly the most optimal solution involves putting 3 flags in each level (assuming there are a lot of flags past the 6th level).

After that, we realise we have reduced the problem, but the condition "(assuming there are a lot of flags past the 6th level)" is a bit iffy, so let's formalise it.

If g(k)/k is minimal among all k from 1 to n, then:
1. The heights above k can have either floor(g(k)/k) or ceiling (g(k)/k) flags.
2. That is the most optimal way of arranging the flags.

Hence, if we can find the minimal g(i)/i, we can reduce the problem.

Proposed Solution Part 4: The Problem
-------------------------------------
If the i that minimises g(i)/i is say, 1, then the reduced problem will have different g(i)/i, since the maximal number of flags above a certain level j in the reduced problem is actually equivalent to |f(i,j)*(i-j)| (stupid definitions). Or I think I should say, f(i,j) is not equal to f(0,j). Yep. That makes more sense. Hence the next minimal f(i,j) might not be the minimal f(0,j). Which means that we have to recalculate everything, which is a lot too slow (O(n^2)).

Proposed Solution Part 5: The Win
---------------------------------
We shall pretend we are stupid (slightly) to solve the problem.

At each height, if f(i, i+1) is more than the previous minimum f(a,i), then we plonk it into a list of minimums. (Like, if say g(3)/3 is the true minimum value of g(i)/i, then f(3,4) may be the minimum value of f(3,i) .

If f(i, i+1) is less than the previous minimum f(a,i), then it must be true (by Observation 4) that f(a,i+1)
After this mess, we now know the minimum g(i)/i. We also know the minimum g(i)/i in the reduced problem, the doubly-reduced problem and so on. Hence, we can calculate the minimum drag the flags add to the ship.

Chess Match

FORMAT WXF
RED meeeep ; 1219 ;;
BLACK fishballwhite ; 1069 ;;
RESULT 1-0
DATE 2011-01-02 10:45:41
EVENT KGP Game ; 10m+0s
START{
1. C2.5 h2+3 2. P7+1 c2.1 3. H8+7 r1.2
4. R9+1 r2+6 5. E7+9 c8.5 6. H2+3 c1+4
7. R9.6 r2.3 8. R6+1 c1.5 9. H3+5 c5+4
10. A4+5 a6+5 11. C8+4 e7+5 12. R1.2 h8+7
13. R2+7 r9.7 14. P7+1 e5+3 15. R6+4 r3+1
16. R6.7 r3.1 17. R7+1 e+-5 18. C8.3 h7-6
19. C3-2 r1-1 20. K5.4 r7+4 21. C5.7 r7.6
22. A5+4 r6+3 23. K4.5 e3+1 24. C3.8 r1.2
25. C8+3 e5-3 26. C8+1 e3+5 27. R7.5 r2.3
28. C8+1 e1-3 29. C7+7 r3-6 30. R5.8 r6-1
31. R2.7 r3.2 32. R8+2 c5-2 33. R8-3 r6.5
34. K5.4 r5.6 35. K4.5 h6+8 36. R8.5 r6.5
37. K5.4 r5.6 38. K4.5 h8+6 39. R7-3 r6.7
40. R7.2 r7.5 41. K5.4 k5.6 42. R2+5 k6+1
43. R5.3 r5.6 44. K4.5 h6+8 45. R2-1 }END

Feeseeks Quest ion

The story goes like this. A person (Let's call him Suicy, since he is feeling suicidal.) wants to get knocked down by a car. Therefore, He wants to run onto the road and get knocked down by a car. Currently, he is standing A units away from the road, and a car is X units away from that point. This is better illustrated in the picture below.

<--------------X------------>
C
______________________________________________________
                            ^     | 
                            |     | 
                            |     | (A) 
                            |     | 
                            |     | 
                                  S

In the diagram above (I hope all the spacings work out fine), C represents the car, while S represents Suicy. The car will travel towards the right at constant speed, while Suicy can travel in any direction at constant speed too. However, the car always travels K times as fast as Suicy. So Suicy is lazy. He only wants to start moving at the latest possible moment. He wants to find the minimal X such that he will still be able to move in such a way that he will be able to crash into the car.

Just an example. Suppose Suicy just travels head-on. That means that he moves in the direction shown by the arrow in the picture above. Then X must be at least K*A. If not, Suicy will not hit the car. Obviously, that's not the optimal solution (Because WOODHEAD wants to suan your brain =P), so you need to think of the optimal solution.

In case you are wondering, OBVIOUSLY THE CAR TRAVELS FASTER THAN YOU (Note, that means K > 1)

PS: I noticed that I can write code here. Allow me to amuse myself.
P^2S: Edited out the nonsense.