Mgccl's Ivory Towerso tired

• Finish the reading list
• Do more ACM problems
• Learn analysis
• 25+ on Putnam 2010
• 6+ on ACM regionals
• 4.0 GPA semester wise for 2010 spring and fall
• Do well on the SAT(OMG writing is so hard :(), or forget about transferring

While on Google talk 3 in the morning, I received the following problem from Alex. He made it up, but he thought it's possible someone else have thought of that question too.

a) How many valid positions of the minute and hour hands are there on a standard 12-hour clock face, so that if you rearrange the minute and hour hands' position, you would still have a valid time?
(Poorly worded, sorry :P)
b) What is the first such position?
(First after 12:00)

This is in a generalization of "How many valid positions of the minute and hour hand meets?".(which is 11)
Solving the above problem is quite intuitive. Notice the minute hand only meet the hour hand once per 720/11 minutes. It's also valid to reason the hour hand meet the minute hand in every hour, except the 23rd hour, which is counted in the next hour. Both give the correct answer of 11.

I can't think of an approach of this problem similar to the above one. I used something else.
We can map the angle between a hand point at 12 and any other hand by how much of a 1 full revolution is required to move the hand pointing at 12 to the other hand. It can be used to define the position of a hand.
Thus we can create function and , . where and are position of hour and minute hand respectively.
Let and We are trying to find all the intersections between the images of and .
The plot is shown below.

Of course, there is no need to plot it with a computer, it is quite easy to imagine it is going to be a grid because is linear, and each mod does a translation. Thus it is 12 parallel lines for , and is reflection though the line . The out most lines intersects inside the image(if we consider t = 720), there are 144 intersections. Remove the one for t = 720 we arrive the answer 143.
I don't know anymore, since for some t, it generate 2 intersections. For example, maybe at time a, the hands can be flipped and get time b. At time t it generated 2 intersections. but at time b, it might also generated 2 intersections. If that's true, then the answer is 77, else it's 143. I didn't have the time to prove that's not possible. and it's not likely for me to prove it today because I need to go to sleep...
Silly me, it happens as one draw a plot of first, then draw , which only generate 1 intersection for each t.

If we trace the process of generating the plot, one can see 1 line is drawn from origin going up, then the 2nd is drawn, each is a translation of the original. Omitting the point where t=0, the first intersection would be either the leftmost point.
Formula for those 2 lines are
and
and . The solution is minutes after 12.

In fact, the nth one after 12 is minutes after 12. Notice how 143 = 13 * 11. The 13th position is the solution to the trivial hour meet minute hand problem.

How do you prove ? It is trivial to manipulate it algebraically and prove it.
Another way is plug in 1,2,3 for x, and one can find both side is equal for each of those values, thus the theorem is proven because any quadratic has only 2 roots.
It is also possible to plug in one number for x, when the number is sufficiently large.

I found the proof here[CHINESE].

How is this useful?
Unless there are places where we have to show 2 polynomials are the same but don't want to show it from algebra(because it's messy? idk...), I don't see how it's useful except it's a fun proof. This proof can also be applied to some other functions, like the exponential function.

However, the original post suggested there are people turning Euclidean geometry problem into analytical ones, then use the above method to prove the theorems instead of simplify the polynomials until the both side are the same form. A win for automated theorem proving.

If I'm not wrong, the post author was talking about Wen-tsün Wu's research on automated theorem proving. It is documented in this book.

On a related note, the author of the above book had introduced the point-elimination method also for the purpose of mechanical proofs. It is taught in some schools in China that designed for training math olympiad level students(I know one who first exposed me to it). It can solve every geometry problem where each elements are compass and straightedge constructions, and the theorem is equivalent to a rational function of some values of the elements(for example, area, length, trigonometric function of angles) that equals to a constant. The idea is to eliminate points by related values. The method isn't that groundbreaking because it was used long before Wu formally introduced it. For example, a common proof of angle bisector theorem shown below uses the method. It is only interesting because it can be apply mechanically.
The following algorithm is the method

1. Construct the original problem by compass and straightedge, make a list of points ordered by the order of construction, let it be L. Record which points are used in the construction of every point.
2. Translate the theorem into a equivalent form. It is a equation where there is a rational function in one side and a constant in the other. Let's call this equation E.
3. Eliminate a point P from end of L. For every P appears in E, substitute it with something using other points from L. For example, if we are proving about lengths, we might use area.
4. Substitute that with something else that eliminates the point P. For example, if in the step before, we substitute length to area, then we want to find something involve the length.
5. Do 3 to 4 over and over until it is obvious that E is true.

I don't know if the computer can do the construction efficiently given the description of the figure. Even if that's not likely, the above algorithm still works great for computers especially with some heuristic. It also works for humans if they have enough intuition(if you do a few wrong substitutions on a time limited exam, you are screwed).

Angle bisector theorem(Proof is originally here[CHINESE, DOC], this is what I translated)
Given: is the angle bisector of of triangle . Let denotate the area of triangle , and be the length of segment .
Prove:
Proof:
1. First construct . Then construct . The points in the list are .
2. The equivalent to the theorem is

3.
Eliminate the last point on the list. .
(substitute with area, thus relates D with 2 points of each triangle)
4.



thus (mechanically) proves the theorem

Around a year ago, I had a vision of a problem database(it's like wikipedia for problems). I made a prototype on top of Drupal.
It was nice, but there are many problems, one of them is to extend the attribute of every type of problem. This is not a difficult task. Drupal's CCK fixed this up rather nicely.
The relations between every problem are hard to map out. Soon I found Drupal's limit, and abandoned it for the project.

I try to write my own program for it. I found in order to make each type of problem have flexible set of attributes, I have to re-implement Drupal's CCK in my program. There must be a better way. In the end I'm convinced that a relational database doesn't suit my need, because of following reasons.
1. Each set of problem can have different set of properties. Some doesn't present in other .
2. Relational database are horrible for graph structures. In fact, relational database are horrible for any structure that can't be presented as a table naturally.

Then I found CouchDB and MongoDB. Both are document databases, it address problem 1 by schema free design. Problem 2 it cannot take care naturally, thus I have to write the code to handle the graph structures. It's still going to be slow.

Just today, I found there are graph databases. Like neo4j. neo4j store everything as graphs. The relations are mapped out as graph in the database. It is also schema free.
It addressed both problem 1 and 2. Awesome.

Looks like I got everything to build the thing I wanted. Hmm... The technology is as mature as I need.

First Putnam ever!

I did 2 problems
Problem set A was a total disaster. I thought I'm going to get a 0 on this Putnam :(. I told myself to not do math and concentrate on only computer science if I get less than 10. (makes sense...)

B1 and B2.

Statements:
B1. Show that every positive rational number can be written as a quotient of products of factorials of (not necessarily distinct) primes. For example,
B2. A game involves jumping to the right on the real number line, if and are real numbers, , the cost of jumping from to is . For what real number can one travel from 0 to 1 in a finite number of jumps with a total cost exactly .

Solution for B1.
are positive integers, , . is the largest prime divisor of or .

Let be a vector space consist of for . .
, where is just a coefficient, then form a basis of .
Thus can be written as a linear combination of . implies can be written as a product of and

Solution for B2.

The one I did during the contest... I basically draw a 3D diagram. Everything is in a unit cube. For x axis and y axis, I draw a square(size ) and the length , so we have a box, where the volume is the cost. It is then ez to see, all such box doesn't overlap and lies inside the unit cube, thus the upper bound is 1. The minimal volume is (if you draw the graph, it become very obvious. proof is not provided here because I need a diagram to show the proof.)

btw for B2, the better way is to do it in 2D, because it's pretty clear instead using the square , we can just use a segment of length , which also get us the upper bound, and as lower bound is even more obvious.

I also tried A1, I got a incomplete solution, it still need one step, which I just assumed it be true because I can't prove it. :( and I'm now pretty sure, it can't be proved because it is not true.