Question! (And answer)

Notation:

!=     ------------>     not equal to (a relic from C++)
iff     ------------->     if and only if
||     ------>     modulus; the absolute value of.
-1     ------------>     This was supposed to be in superscript, but I can't find the how to make them appear.  Also used for footnotes.


Question:

Does there exist a function f(x) mapping from rational numbers to positive integers such that:
(1) f(x)=f(y) iff x=y
(2) For any given real R, there exists a rational number x such that e>|R-x|*f(x) for any e>0.

Notes about question:
1) Criteria (1) for f is basically constructing an ordering of the rational numbers.
2) It is relatively simple to construct an ordering of the rational numbers such that (2) is heuristically "probably true", but this is vague to define and prove. This is because for any e, the "area", including overlaps, containing the set of reals between x-e*f(x) and x+ e*f(x) goes to infinity as long as we have solutions for f(x)=N for any positive integer N.
(See http://en.wikipedia.org/wiki/Harmonic_series_(mathematics) .)



Solution:

Lemma 1: The above question is equivalent to the following question:


     Does there exist a function f(x) mapping from rational numbers in [0,1) to positive integers such that:
     (1) f(x)=f(y) iff x=y
     (2') For any given real R in [0,1), there exists a rational number x such that e>|R-x|*f(x) for any e>0.

Let f1 be one such function that satisfies (1) and (2') and in particular has an inverse 1.
Let f2(x-1) = f1(x), f3(x+1) = f1(x),
      f4(x-2) = f1(x), f5(x+2) = f1(x),
      ...etc.

Now we construct a function g(x) that also maps from rational numbers to positive integers, where g(x) is defined as follows:


f1-1(x) = g-1(2x-1)
f2-1(x) = g-1(4x-2)
f3-1(x) = g-1(8x-4)
and in general:
fk-1(x) = g-1(2^k * x - 2^(k-1)) for all values of x and k.

We notice that g-1(x) is taken from f1-1 if x=1 (mod 2), f2-1 if x=2(mod 4), etc., so g-1(x) is uniquely defined for all x.

Then g(x) satisfies conditions (1) and (2). 2

Using lemma 1, all that's left to do is construct one such f1.
This can be done as follows:

Construct a function h that maps from positive integers to rational numbers, where h(1), h(2), h(3),... are
-42, 0,     0, 1/2,     0, 1/2, 2/8, 3/8,     8/16, 9/16, 10/16, 11/16, 12/16, 13/16, 14/16, 15/16,     ...


Specifically, h(1) = -42 3, h(2) = 0+0*(1-0),

h(3) = 0+0*(1/2-0), h(4) = 0+1*(1/2-0), h(x)= 1/2+(x-5)*(1-1/2) for 5<=x<=8,

h(x)= 0+ (x-9) * (1/4-0) for 9<=x<=16, h(x)= 1/4+ (x-17) * (2/4-1/4) for 17<=x<=32,

... for 65<=x<=128,

h(x)= 0+ (x-129)* (1/8-0) for 129<=x<=256, ... etc.


where the underlining separates the definition of functions into recognizable groups. Furthermore, within each group as partitioned by the underlining, it is possible to bound the maximum |R-x|*h-1(x) by half. 4

f1-1 can be generated by taking the next nonrepeated term in the sequence of h(1), h(2),... etc.



1 That this is a valid assumption (because it relaxes the conditions) is left as an exercise to the reader.
2 Again left to an exercise for the reader. It's quite evident, but horrid to type out.
3 A null element for the sake of a convenient proof.
4 This is left as an exercise to the reader as well... nah just kidding, will hopefully post a somewhat rigorously written (and readable) proof at a later date.

Edit: A final note... it was a lot more readable from the luxury of a wide page, so perhaps one should try pasting it onto notepad with wordwrap.

Technical framework up

  Good day.

  Today, I am proudly presenting... nothing!... since this marks the start of the making of the simulation game. As for names, there hasn't been any good ones coming to mind yet, so for now I shall just summon my powers to connect random words and call this game... BalalaikaOpus! (BO for short).

  As of now, there is currently no world to live in, but nevertheless, the npcs have been created and are currently paddling through space, and been given stats (Athleticism, Age, Creativity, Deftness, Learning, Resilience for now). Mindsets have also been implemented, for now j perseverance and morality. Some skills have also been implemented: Walking (What a undervalued skill!), Running (just for the sake of juxtaposition), Cooking, Painting, Fighting and Life Experience (for whatever can't quite fit... stone-skipping skills anyone?). As can be seen, most of such skills are broad, and hence implementation has been done on the basis of possible future subskills, e.g. cooking.baking.

  The difference for classification into stats, mindsets and skills is basically to make the concept clearer, since although the variables are be treated as equal, the way the variables behave are fundamentally different. Stats in general do not change (age aside), mindsets change slowly, and skills change quickly. Moreover, skills do not decrease, while external interaction can, and likely will change mindsets. Also, while skills have dependencies on stats, mindsets do not, and as for individual actions taken, they will be based off mindsets and skills solely (with stats only being indirectly involved).

  Each npc is planned to have a set of stats, skills and mindsets, although if the skillset gets too large and that creates a problem for computer memory, some of those might have to be ignored and estimated based on situational need (e.g. pancake flipping skills, while not implemented, is likely to be related to the cooking skill).

  P.S. I forgot to mention the inclusion of goals, which are objectives an npc tries to pursue. For now, there is wealth, attention and fame.

  Coming up: Planned vague goals, to account for unconventional objectives, such as promoting the joy of eating chocolate. Such goals will be given just an ID, instead of a name, and are set to be randomly generated by the computer.

Simulation of a society

Fact:  I enjoyed Roller Coaster Tycoon immensely (the original version, created 1999). Parts of what I enjoyed about it were the simplicity of design, together with the "interesting" details microscopically (such as when you observed a single guest) and macroscopically (while managing the entire theme park).

  As such, I have on different occasions thought of how a simulation of a society (in the sense of a group of people, probably isolated, living together) would function.

  I imagined it being a wonderful simulation (my ideal), where one got to observed the macroscopic panorama of the layout of the structures sprawled over space, as well as the individual simulated citizens going about their daily lives. It would also include the intrinsic concept of progress, since it is the basis for many games, whether RPG, Sim, strategy or shooter. This would come in both microscopic and macroscopic forms, respectively being the way an individual pursues his or her goals, and achieves (or doesn't achieve) them eventually, and the way a society progresses over time, with definite short-term direction but not necessarily with a fixed long-term route to follow.

  As such, I have planned to pen down (and give a structure to... concretise?) the ideas for a sim (i.e. those that I remember at the time of writing). This is again a short-term direction, and may (and probably will) suffer from the lack of follow-up.

  In the next post of this series (if it exists) I shall cover various (at least one) specific aspect of the sim of my imagination, probably written in the form of a design note (design notes are awesome!)

Largest area given a fixed perimeter (Part II)

Over the week, I have found a few more things of note to bring to the metaphorical discussion table. Firstly, there is a most welcome patch to the squabble over the proof of necessity of convexity in maximizing area, and secondly, a proposed sketch of a definition of "inside", used when defining area. However, it is still not clear how the definition can be used explicitly in the proof apart from "obvious"-style handwaving at the moment.

Firstly, the patch:

Consider the following 2 propositions:

1) A larger fixed perimeter will yield a larger maximal area.
2) A straight line is the shortest path between 2 fixed points.

For (2), there is not much to say, and is more or less a take-it-or-leave-it axiomatic definition, due in part to the triangle inequality.

For (1), consider 2 fixed perimeters P and P', with P'>P. Consider the shape with the maximal area for P, S. Define S' similarly. Clearly Area(S')>= Area (similar shape to S with perimeter P')* > Area (S), since Area (S)>0 (consider a square, for example). In fact, Area (similar shape to S with perimeter P') = Area (S) * (P'/P) ^2.

Consider a concave (used here possibly loosely to mean non-convex) shape S. Assume it has maximal area.

Then consider of it, two points on its outline A and B such that there exists a point P on line segment AB such that P is not in the shape.

Next, consider the shape S', which is S with arc AB replaced with line segment AB.

Now, consider the shape S'', which is the union of the set of points contained in S and S'.

The area of S'' is clearly greater than that of S, since there is at least one point contained in S'' not contained in S (P), and whatever is contained in S is by definition contained in S''.

3) The perimeter of S'' is also not more than that of S.

<Proof of (3):

Assume otherwise. If so, then there exists an arc CD in between such that its length is less than line CD. This contradicts (2). We are done.>

Hence, S'' has greater area but less than or equal perimeter to S, and hence a shape S''' similar to S'' but with perimeter equal to S with have greater area than S, contradicting the original assumption that S had maximal area for its perimeter.

Finally, on to part 2 of this post, the definition of "inside":

All points at infinite are outside. Consider any line. Each time it intersects the perimeter of the shape indicates a border between "inside" and "outside". The area of a shape is the sum of areas of all "inside" points.

* Similar as in similar figures, used in the same context as congrurent

Largest area given a fixed perimeter

The question is simple: given a fixed perimeter of say P, find the shape that gives the largest possible area. The answer is somewhat equally simple: a circle gives the largest area for a fixed perimeter. The proof, is not so clear. The definition is a trickier problem, which I shall not care to resolve (I define the center of the circle to be the outside of the perimeter...).

Browsing the internet yields more than just one proof and references to proofs that exist. One of which I trust to be rather unambiguously true is referenced to as the proof by calculus of variations, which I suppose works, since calculus is such an overpowered sledgehammer. However, yet another interesting proof presents itself, of which the outline is presented below:

Define X to be a shape that maximizes the area for a given P.

1. X is convex.

Proof: If X is not convex, then let C be a point outside of X, and A and B be points on the perimeter of X such that C lies on AB. Moreover, let there be no points on the outline of X, say Q, such that Q lies on line segment AB. In that case, if we reflect the outline AB about the line AB, the area increases. This contradicts the maximality of area X. Q.E.D..

Attack: What if we cannot pick A and B such that there are no points of the outline of X, Q, such that Q lies between A and B? (a.k.a. fractals)

2. Any polygon with a fixed number of sides N has maximum area when it is regular. (more or less indisputable).

Corollary: A regular polygon with i sides has greater area than one with j sides given a fixed perimeter iff i>j. (Think of degenerate polygons)

3. Therefore, as the number of sides N goes to infinity, the area increases, and we get a circle, and therefore a circle maximizes area for a fixed perimeter P.

Attack: Where did that come from? Can we even apply rule number 2 to "polygons with infinite sides" (a.k.a. shapes with curves)?

Is there a reasonable patch to the leap from part 2 to part 3? I would agree that it is intuitively very probably true that the argument *sort of* works, and just need formalisation, but with infinities I would not be very sure, ever since the last time I saw 1=1+0+0+...=0+1+0+...=0+0+1+...= ... =0+0+0+...=0. Therefore 1=0. Instead I would probably work towards a more geometry-based idea, described handwaving-ly all the way through, since I have not worked out a full "proof" yet:

Lemma 1 remains, despite the attack. Fractals can be dealt with separately, ... some other time... some other person.

2. The outline of X is smooth. (i.e. no line segments anywhere) random rantings.

Imagine the outline as a wire. Now divide the wire into 2 parts of equal length, and call the parts, with direction, AB and BA respectively (i.e. starting with A and going say clockwise to B and starting with B and going clockwise to A respectively). Define the area enclosed by arc AB and line segment BA be called ABA and BAB be defined similarly. if ABA > BAB, then copy ABA over with symmetry on like AB. X clearly does not have this property since otherwise the operation would produce a shape with the same perimeter and larger area. Hence for X, ABA=BAB for every choice of A and B. Now notice that the reflection does not change the area for X, even though it might change the shape. This does not bring us to an immediate conclusion, since X might not be a unique shape. Also, reflecting about AB must result in another convex shape. This fixes X as a circle... somehow? Good night.

Constrained Writing

I've been wanting to post this for quite some time. In fact, such some time that I can't exactly remember whether I actually ever got round to writing a post about constrained writing, but knowing me and my laziness, as well as the latest spate of blog-neglect, I shall assume that I never had.

First: before talking about what it was I think I wanted to talk about, I shall acknowledge the main source of my inspiration for this post: namely the Pilish work Cadaeic Cadenza (starting from the poem "Near A Raven"). It is an epic work of constrained writing, mainly that the number of letters of each word corresponds to digits in pi, i.e. Pilish. As if such an undertaking was not enough, the author (writer? composer?) saw fit to add other constraints into his writing through different parts of his story. Ridiculously, the story is coherent and (somewhat) elegantly written, if a bit awkward due to abuse of synonyms at numerous points. As an illustration, "Books inhabited each table, shelf, and nook.". Inhabited? Interesting use of word, of course with this particular instance of "nook". Also, "A madrigal; tell a marcher," seems a little arcane to me.

So, to the point of this post, which at some point became to evaluate the technical niceness of a piece of constrained writing. This is clearly subjective, but nevertheless, some indicators can be objectively evaluated (somewhat like standard of living indicators pointing to the quality of life).

Firstly, of course, there is the freedom that the constraints allow. For example, a constraint that you may not use the word gneiss is hardly a constraint at all under most normal circumstances, since English grammar does not commonly necessitate the use of such a word under most contexts. Writing without using any forms of the word "be", on the other hand, might be a challenge, since there ARE many situations where such a word IS used in the syntax of English.

Then there is, of course, coherence, where the text has to make sense. "For a dime, I would do proper Maths." is, for example, much more coherent than "Fly a poke: a flail or uneven table", despite that the two share the same constraint of Pilish. This is naturally highly subjective. I AM going to be contradicted... right?

Lastly, there is length. A good length makes any piece of constrained writing more impressive, since the whole idea is sort of a challenge upon yourself, and any lengthy piece could be compared to a marathon instead of a 100-metre race, which would be more than 422 times more impressive if traversed at the same velocity.

And once again, I conclude a post hastily, due to sudden lack of inspiration in the midst of composing (I recall there being a more... uncommon *inimitable is a synonym!* word for it). I would nearly apologise for this, but then that necessitates far more apologies to come, which would get old. 

Anagram a margana

Well, I can't let myself be beaten here. (Despite failing to satisfactorily solve even half of those anagrams ph42 gave...) Here's a fresh sampling of anagram hell.

strobe
sunboule
tacuics (Inaccurate tactics lead to death!)
gneiss (I could've given the other word instead, but nobody knows gneiss...)
cretins
liminiac
shidap
morphias
glintei

All popped into my head while trying to solve those 14 below. So yeah. A response.

Anagram List

May be edited to expand it. But meanwhile...

1. Naruto
2. Sungei (Malay for swamp I believe)
3. SacLose
4. ProBash (Warning: obscur-ish word)
5. NaEight
6. EpicSac
7. Tactics (Ah well...)
8. ProBing (Eh already a word. Too self-evident, apparently)
9. Chariot
10. Minister
11. Positional (Eh whaaaaat?)
12. Rating (Again, may be somewhat obscure)
13. Tortoise
14. Silver (3+ solutions)

Setting a chess puzzle

I was delighted this week, when I thought I managed to construct a delectable Chinese chess puzzle, pretty much by accident and chance. It contained a somewhat less commonly used theme as well as an accidentally set sacrifice. Happily, I chugged it into the engine for sidelines, and maddeningly, about 3 strange defences materialised out of thin air, defences I had never considered. In the end, I hereby resign to my sad puzzle-setting fate and present you the somewhat correct (but not a mate) puzzle.

Uhh... how do I write the plaintext for it again? Meh.

###AK#PR#
####A##H#
EP#######
##P#P##H#
P####P##H
#########
P#####PPR
####E####
######RP#
R####K###


Red to move and win, of course.


More on how my puzzle failed in a later blogpost, if I remember and can be bothered to make the effort. It's late and I'm braindead too. But in the meantime, enjoy the puzzle.


Just in case I remembered my own notation wrongly, the one presented is as follows:
P -- the most important, powerful, and prevalent piece (Darwin's theory!) on the board.
E -- elephant, minister, whatever. The mascot of Chinese Chess (Xiang Qi)
A -- The advisor, or "shi".
R -- Rook, or "ju", but probably not "che"
K -- The lousiest piece on the board -- never have I lost a game not because of it
H -- Knight (or was it N?). Either way, the "ma".
C -- Not featured in this puzzle, the sneaky cannon, or "pao".

A badly played Chinese Chess match

Clearly I haven't been playing Chinese Chess seriously in quite some time; I'm blundering pieces left, right, and center, for the most trivial of reasons. But the thing that takes the cake (it's a lie group!) is that I've not been sacrificing for initiative as much as I probably should. That will take some time to reset. And being cooped up in a place without access to the Internet (well, not much of it) for five days every week (all right, maybe six), I don't think I'll have time for quality chess any time soon. However, I did manage to find an average-ish player on a particular chess website today, and lo and behold! -- here is the chess match, with a slight bit of commentary on why I moved certain moves and my failings.

(As a side excuse, it was a 5 0 game.)
Black: Me            Red : ???

 1. C2.5 c8.5   2. H2+3 h8+7   3. R1.2 r9+1
 4. C8.7 h2+1   5. H8+9 r1.2

At this point I was waiting for the response R9.8 to play C2+4. No I don't remember the theory, but that kind of moves look theory-ish. Also, we probably had deviated from main theory lines by then, so...

 6. P9+1 r9.4
 7. A4+5 c2.3  

 At this point I rather liked my setup. Sure I wasn't exactly winning, but it looked like I might have an attack along the right side (in my POV).

 8. R2+4 p5+1

The start of my troubles.

 9. P5+1

Doh!

 9 ... a6+5

 ?? move. Now I'm in a little bit of trouble. Sigh. Since the formatting looks a bit weird, I guess I'll just take this space to comment on my next few moves. His pao, sitting on the middle, is strong and attacking my king. Even though my cannon is pretty much doing the same thing, I have insufficient coordination, and hence I thought it might be safer to just trade every thing off the board... and my cannon could easily be replaced anyway. Following that, I just threatened to kill his xiang as best as I could, and I would even have happily sacrificed my ma for it, but... he just didn't accept. Aw... so much for being an aggressive maniac.

10. P5+1 c5+5  11. E3+5 c3.5  12. R2+2 r4+7
13. E5-3 r2+4  14. C7.5 c5+5  15. E3+5 r2.5
16. R2.3 h7+5

Yet another occasion that I played a dubious move. Now my xiang dies. And before his. Better was probably R5+3 R3+1 R5=7 R3+2+ A5-6, and now I'm threatening a stupid one move mate, and his shuai must move out, whereupon I can check him and put his king in an extremely dubious place vulnerable to harassment by the side, which is rather sneaky and difficult to defend against. My usual defence against this kind of things is just hoping my opponent doesn't see. Either that or trade off the 'ju's off the board and run away in fear.


17. R3+3 a5-6  18. H3-4 h5+ 19. P3+1 h7+5


Just moving my ma along with the flow. I wanted to go there anyway. Yet the bing move was somewhat necessary to prevent a faster check (which could be fatal since his shuai cannot move).

20. R9.8 h5+7  21. H9+8 h7+9

And I thought I was being obvious. Not obvious enough, apparently :(.

22. H4+3 h9+7

Oops, unstoppable mate out of nowhere in particular. And from this moment on I was just being an irritating troll warlord. But he resigned :(. Aww.

23. K5.4 r5.6  24. A5+4 r4+1
25. K4+1 r6+3  26. K4.5 r4.5  27. K5.6 r6+1

0-1

In conclusion, I was still down by a bing at the end. This reflects a deterioration of my skills. *sigh*

Till next time then.

Vocabulary (from a different person)

Thought I might as well post something after yet another long period of inactivity. Definitions come from google. Words come from... hmm?
Extolling: Praise enthusiastically
Ember: A small piece of burning or glowing coal or wood in a dying fire
Penumbra: The partially shaded outer region of the shadow cast by an opaque object
Inimitable: So good or unusual as to be impossible to copy; unique
Forevermore: Forever (o.O)
Foreboding: Fearful apprehension; a feeling that something bad will happen
Threescore: Sixty
Perchance: By some chance, perhaps
Afore: Before
Hereinbefore: Before this point in this document
Repose: Temporary rest from activity, excitement, or exertion, esp. sleep or the rest given by sleep
Thence: As a consequence
Pallid: Pale, typically because of poor health
Dissonance: A tension or clash resulting from the combination of two disharmonious or unsuitable elements
Intoning: Say or recite with little rise and fall of the pitch of the voice
Forlorn: Pitifully sad and abandoned or lonely
Corvus: A small Southern constellation (the Crow or Raven), south of Virgo
Heretofore: Before now
Maven: An expert or connoisseur
Dirge: A mournful song, piece of music or poem
Wherefore: As a result of which
Entreated: Ask earnestly or anxiously for
Nefarious: Wicked or criminal
Delectable: Extremely beautiful
Emancipate: Set free
Spurned: Reject with disdain
Mirth: Amusement

OMG I necro'd the blog...

It's been such a long time since I posted, and I have had a break from the school of school. For these two years anyway. As such, I have mostly stopped writing, and right now it feels a little unnatural to be typing over here, being inactive for the past 5 months or so. As such, my writing style would probably have changed, but it matters not, for it is the same person bringing you time-wasting paragraphs of contentless rants!

Nevertheless, I am sad to say that my brain has degenerated in fields of... everything ranging from sudoku to maths to even... *drumroll* chess! And as such I have actually not thought of material to post here. However, I hope that I will be able to think of more content soon, and resume the monotony of chess, chess, chess, maths and chess posts. In the meantime, a random link: http://www.kongregate.com/games/Tukkun/anti-idle-the-game?acomplete=anti+idle. Wonder where this goes...