Tag Archives: math

Happy New Year!

Unlike last year, I don’t have any puzzle planned. I’m constructing an LMI test for April or May, and considering that I just finished my first semester of university a week or so ago, I’ve been taking the holiday for my usual computer stuff: programming, browsing the net, playing some games…

So what have I done in 2013?

Continue reading →

Two real numbers

Initially found from xkcd’s blog, then got a link to MathOverflow.

Suppose you are playing a game with Alice. She uses some probability distribution to pick two distinct real numbers and writes them in two envelopes. You then choose either of the envelope and opens the number inside the envelope. Is there a strategy that guarantees you a strictly larger than 50% probability to guess correctly whether the chosen real number is the greater or the lesser, for any probability distribution that Alice uses?

This is my take on the problem; feel free to comment, discuss, or argue with me! As long as the discussion is kept civil.

The answer is yes.
Continue reading →

Greedy Queens Problem

In the famous Queens Problem, you need to put n chess queens on an n x n chessboard so no two queens attack each other. It has been proven that a solution exists for all n except n=2,3.

One of the methods (albeit an ineffective one) to solve it is by greedy algorithm, which does a depth-first search. In this case, a queen is placed on the first row, on the first column. The next queen is placed on the second row, starting from the first column. As it attacks a previous queen, it is moved to the second column, and again to the third column. Now as they don’t attack, a third queen is placed from the leftmost column rightward, and so on. When a queen cannot be placed, the previous queen is removed and placed to the next column. This guarantees a solution, as it checks every possible board as long as no conflict has been made.

For example, with n=4:
First queen tries a1.
Second queen tries a2. Conflict with a1.
Second queen tries b2. Conflict with a1.
Second queen tries c2.
Third queen tries a3,b3,c3,d3 in order but conflicts each time. Second queen is retracted.
Second queen tries d2.
Third queen tries a3, conflict with a1.
Third queen tries b3.
Fourth queen tries a4,b4,c4,d4, all conflict. Third queen is retracted.
Third queen tries c3,d3, all conflict. Third queen is retracted. Second queen is retracted (cannot go further).
First queen tries b1.

This algorithm is run until the solution b1,d2,a3,c4 is found (the first solution found). In total, there are 26 queen tries.

For n=5, it can be verified that it takes 15 queen tries to arrive at a1,c2,e3,b4,d5.

Can you compute the number of queen tries for a given n effectively? In other words, is this problem in P? (Naively executing the algorithm gives a possible n^n steps, so it’s not polynomial. You need a better way.)

Extra Problem

A revised version of the algorithm doesn’t put a queen when it makes a conflict. So, for the n=4 example above, we have:

First queen on a1.
Second queen can’t go on a2,b2. Second queen on c2.
Third queen can’t go anywhere, second queen is retracted and go on d2.
Third queen on b3.
Fourth queen can’t go anywhere. Third queen retracted. Second queen retracted. First queen on b1.
And so on.

It takes 8 queen tries now. For n=5, it takes 5 queen tries, or in other words the exact number required.

Can you compute this number effectively too?

Antiderivative of tan x

I was toying with Problem 317 on Project Euler when I found a messy (but rather easy) antiderivative of a polynomial (with messy coefficients of course). Somehow whatever train of thoughts led me to think of the antiderivative of tan x. (That’s extremely sidetracked, but whatever. My initial guess of 2.4 million something was wrong anyway 😛 )

And it is pretty surprising.

Letting u = \cos x, we have du = -\sin x \,dx. Hence
\displaystyle \int \tan x \,dx = \int - \dfrac{-\sin x \,dx}{\cos x} = \int -\dfrac{du}{u} = - \ln |u| + C = - \ln |\cos x| + C.

Wild Logarithm appeared! But seriously. This is pretty amusing. Well, if you know \dfrac{d}{dx} \arctan x = \dfrac{1}{1 + x^2}, this is not that amusing, but still.

Math has always mesmerized me with its beautiful, unexpected results. However, it requires deep thought to actually understand it, hence a boatload of dislikes to math. In my class of 22 students, only one goes deep to math (namely me); one or two are good at school math, a few more okay, but that’s it; the rest are…uh…terrible. Of course, you cannot ask the opinion of a person who really digs math about math in these settings (aka the question about how his classmates are progressing in math); that’s biased.

Recently, namely 2.5 hours ago, I’ve just finished tutoring seven of my classmates for about 5.5 hours about math. Tomorrow is math (and history) finals exam, and it involves four topics: antiderivatives and integrals, matrices, vectors, and geometric transformation. I almost gave a very terrible problem (find the area enclosed between y = e^x - 1 and y = \ln (x+1), later revised to be base 2 instead of e); it’s terrible just because finding the intersection points will be a nightmare for them. Although I’m positive that most readers of this post can solve the problem without too much effort (note that the former is convex and the latter is concave, so they cut at at most two points, and they can be found easily).

Appreciating math (or any subject for that matter) is hard. I tend not to appreciate Indonesian (mostly because of severely flawed and broken “opinion-type” questions, where English should have anyway but our English focus more on grammar and reading); there might be someone out there who loves Indonesian more than their spouse (if there is any). Sometimes someone simply doesn’t appreciate any subject at all. I don’t have any right to judge; it might be that they like something else.

However, if you have the patience and logic to grasp the hidden beauty of math masked by mindless exercises such as \int x \sin x + x \sin x^2 \,dx, you might just stare in awe (or in confusion; again note that you need logic) of the beauty of math. You might even be amazed of the wonders of antiderivatives; note that the above example employs both partial integration (for first term) and integration by substitution (for second term) while differing only a number in its expression. So beautiful, so orderly.

Now that I’ve written too much, I might better sleep and prepare for tomorrow. It’s going to be a big day. (Those seven will come again for tutor on Tuesday’s Physics. 😛 )

Long time no post

And hence I should let my readers to know that this blog is not dead.

Things I learn:

– Double negative (2C – 2D!, 2H – 3C!) is bad for games. 3H is down 1, although we hold like 8 or 9 hearts (I forgot) and stoppers in two side suits. Yeah, only two side suits. The other has two losers before I get it void.

– In Virtual Villagers 5: New Believers, HEATHENS CAN DIE. I’m not sure where my Heathen Master Scientist went, but it certainly made me unable to complete the puzzle involving them and another involving the Chief. Which means no earthquakes. Ugh, I don’t even get revive. No fish + 43 people = 0 food. Currently restarting.

– In osu!, streams are hell. In Pachelbel’s Canon (Funtastic Power!), Canon difficulty, I failed at the last 5 seconds of the song because apparently I sped up my rhythm during the last stream, missing the later notes and eventually the attempt. 😦

– Making sufficiently hard geo problems is hard 😦 Making sufficiently hard combo is easy though 😀 (written by the mind of a combo-lover-and-geo-hater olympiad math person)

– I can’t make good room designs 😦 This means I will rarely post Surveyors Heyawake. I’m absolutely sure it has more tricks than what I have in Puzzle 4 though.

– Yay. What do you call it if you have a memory card filled with DS games? Whatever it is, here’s a story. I have two DS, and I also have a MicroSD-to-computer “hub” or something. So, I copied my save data of Pokemon Platinum to computer (and also backed up the contents of one memory card), then do a trade (well, eight trades to be precise) between my Pt and HG. Later, after I finished moving all I want to HG, I’ll see the result of replacing back the back up as my actual Pt data. So, cloning in a new form perhaps? The Pokemon that will disappear along with the temporary Pt are worthless ones. Oh hey I haven’t caught a Magikarp in HG.

– Also in conjunction with above, I used whatever the “cheat-by-toggling-which-cheats-you-want-to-use-when-you-load-the-game-by-the-OS-(or-whatever)” to get the three event items in Pt (Member Card, Oak’s Letter, Azure Flute). I caught Darkrai and Shaymin, but Arceus is Lv80 and my team is only Lv74 at most 😦 Whatever. And hey Shaymin. Yeah I sent it to my HG too. Currently training.

– I decided to recruit people as “development team” of URLQuest 3. If you have ideas of what to make a good online riddle website, e-mail me. Did I write my e-mail in the About page?

Limits

Yay first post about my school

So we learn limits in math class now. As I expected, the teacher didn’t explain properly (like the concept was kinda off), so almost everyone* didn’t understand and asked everyone who understood.

* All except me and one other person, obviously besides the teacher