Putnam 2017 (Part 2)

Three hours gone in the morning. Three more hours to fight. Thankfully we had two-hour-break in between but I desperately needed coffee. Our proctor/Putnam coach (Prof. Stephen New) asked if anyone in the room needs more coffee and I was among the very few people who raised their hands, “you gonna finish most of them”, he joked to me.

Jokes aside, here’s section B. Assuming that the methodology of trying the first few problems actually works, I first looked at B1. “Easy”, I thought, “just use my trigonometric specialization that I had in my IMO journey back then right?” Unfortunately, there are just too many cases involved (point inside/outside the angle domain that gives positive or negative ratio), so I put it on hold and turn to B2.

B2 was another problem that looked routine: the first question we should ask ourselves was: what are the numbers that can be represented by sum of k consecutive positive numbers? Removing the constraint that a has to be positive, N has to be divisible by k if k is odd, and N-(k/2) divisible by k if k is even. Adding the “positive a” constraint simply means N is at least 1+2+…+k = k(k+1)/2. But what’s next? Hmm…well now N=2017m with m>=1008. If m is divisible by some odd prime p then k=p would work (come on, 2017m>=p(p+1)/2 shouldn’t be hard to prove). Otherwise, consider m=1024 and the smallest k>1 that is not 2017 is k=2048, but 2048*2049/2 > 1024*2017. This gives our desired form, and hence the answer a=16.

Turning back to B1, I wasn’t convinced that I could make my trigonometric argument work. But the next thing came into my mind: what if, we rotate a line around P and consider the ratio? As it turns out, this ‘covers’ all possible lambdas except zero, as desired.

Time for B3. First thought: prove that the sequence c_i must be eventually periodic for f(1/2) to be rational. There came my machinery: Fermat’s little theorem (every number 1/q with q odd can be written as p/(2^k-1) for some k and p integers, and 1/(2^k-1) is 0.000…1000…1… in binary form, with period k). Still…this looks messy, and I had to skip one final computation part and straight claim this identity directly. The rest wasn’t too hard to complete: if the series c_i is eventually periodic, then f(2/3) has odd denominator and cannot be 1/2. Yay, no? Oh well, not really (considering the minute details that ate up substantial amount of my time).

I couldn’t remember how much time left by then, but the aim was to kill another problem. Curiosity on how the pattern of sums for B4 dominated my mind, so I tried that first. On its first sight, rearrangement of the terms in the right-hand-side looks tempting because this trick simplifies computations substantially most of the times, according to my experience. No. I couldn’t do this arbitrarily: it doesn’t convergence absolutely so I had to do the rearrangement judiciously. But how? 😥

After the futile experimentation on B4, I proceeded with B5 instead (geometry ❤ ). So there were a few things to keep in mind: if we fix the line to partition the triangle into equal perimeters and vary it, then using extremal arguments each triangle must have at least one equalizer. Having that in mind, I continued to play with such lines, looking for the critical cases of the lines intersecting one of the three vertices of the triangle, and anything interesting in between. But I got myself into the whirlpool of cases, the most distinctive of which was whether the shortest side is at least a quarter of the perimeter of the triangle. Nervous. Can’t continue. Time’s up. Devastated. I couldn’t even squeeze time to look at B6.

In the short post-contest discussion, many peers claimed the first three, and concurred with me that B4 was hard (except the Putnam coach, Prof. Stephen New, who vanquished B4 rather instantaneously). There was one who additionally claimed B5, which gained him a bucket list of 8 problems solved. Oh well, I just had to hope that all my 7 solutions were good enough to earn full/near full credits.

Ps: B4 actually wasn’t that hard. If only I was a bit braver and try to avoid the convergence issue by thinking of partial sums…

Putnam 2017 (Part 1)

Prologue: it has been some time since I updated my posts (academic workloads…oh dear 😥 ), and why not start with something easier to write?

It’s Putnam season again (December 2). I felt hyped, not really because of me eyeing for the top prizes (aiming for the very top is unrealistic at this point, after all), but because it’s another chance for me to enjoy my mathematical contest wholeheartedly again. Amid the doodling my scratch papers with past-year problems and the problems handed at our problem solving sessions, the day came.

“10, 9, 8, …, 3, 2, 1, Go! Go! Go!” our proctor exclaimed in a bracing way that get us excited for the morning paper, section A.

As I opened the envelope, I was first intrigued by the statement of A1 that shadows many easy Olympiad problems. Not really. I scanned through the problems and A4 came instantly natural to me–so instant that I felt it really artificial (thanks to the problem A3 on the IMO 2016 shortlist, which I used a similar method). Here’s my work on Putnam A4:

(I described this problem in the setting of MATH 245 quiz to my friends, for fun 😛 )

Shortly after my completion of solution writeup was to complete A1, which gave us the relation x in S -> x+5 in S (exercise for readers to prove). Thus all numbers in the form 5k+2 have to be in it (due to condition (i) ). Now 49->54->59->64->…are in S too, which also includes 8->13->18->… (because of 64). Finally we have 54^2->54^2+5->…, and this should be the full list.

No it’s not. Darn it. I was halfway writing through my solution before I realized that. 56^2 is in S so 56 must be too, and this gives 81 -> 9 -> … and 121->11->36->6, so all numbers greater than 1 and not divisible by 5 are in S. I couldn’t believe that my writeup of solution was a mess by then and had to cross out all of them before writing a new solution on the same paper. RIP 😥

The next obvious candidate was A2, which, on its first look, necessitates me to approach by brute force first: try the first few candidates. At n=6 or 7 I noticed that the “supposed polynomial” have coefficients following some binomial pattern, so I tried to prove them. Half and hour into the verification and virtually no progress on it, I realized that this was easier said than done.

Amid my panicking to fight against the time constraint, I realized something fishy: since the polynomial terms followed binomial pattern, why not write it as sum / difference of previous terms using properties of Pascal’s triangle? That’s how I discovered the tricky identity Q_n=xQ_(n-1)-Q_(n-2). That’s the key to the solution, without me being need to continue the tedious and unapproachable binomial work. QED.

30-45 minutes left, and it’d be great if I can kill one more. A3 looked difficult at its first sight, but A5 and A6 aren’t accessible either. With time being too short for quandary, I chose A3 to fight with. First thing into my mind was looking at places where f(x)>g(x), and show that the ratio f^(n+1)/g^n blows up in that area. No. I didn’t know how to make the argument convincing (or rigorous). My best bet was to try out the discrete summation version of the claim that the integral of f^2/g > the integral of f, as below:

See the relation between the two?

But…isn’t the second identity Titu’s lemma? Which can be arranged into Cauchy-Schwarz inequality. Does this mean that the Cauchy-Schwarz inequality can be used for integrals too? 20 minutes left. I didn’t think of verification anymore. Just quote it. As it turned out, I never believed how handy this theorem was when applied to solve this problem. 😀

At that point I didn’t even think of trying A5 and A6 (with < 15 minutes left), so I just had to make sure that my four solutions are good (rumors had that Putnam graders are very harsh with minor mistakes ).  That’s it for section A. I hadn’t heard anyone claiming A5 or A6 in Waterloo, but a few claims of all A1 to A4 like me, with some impressed me with their ingenuous approach to A3 that doesn’t involve any fancy inequality like mine.

How about section B in the afternoon? Stay tuned!

Ps: some trivia-comments on the problems:
A1: “A1 has trap”, said Prof. Kent Merryfield on AoPS. I have already delineated my struggle above with the crossing of my work and ending up writing on the front page “please only read what’s from the bottom of page 2, thank you very much 🙂 ”
A2: oh well, either you see it (Q_n = xQ_(n-1)-Q_(n-2) ) or you don’t. Ugh.
A3: A friend commented “one of the nicest problems because there are many solutions”. Indeed: Prof. Kiran Kedlaya posted 5 solutions to this problems on his website.
A4: Solvable by algorithmic approach (probably the favourite problem by the Computer Science geeks in my class, I guess)
A5: Looks innocent, but turns out really difficult (imagine roots of unity and complex numbers being involved in a probability problem: oh no…)
A6: “To get some ideas, I starred at the Putnam logo on the question paper, which is an icosahedron itself. Doesn’t work,” said one classmate. Laughter followed.

Evolution in maths

#randomthoughts #RIPgeometry

Last July (a month and a half before I departed to Waterloo), I had the privilege to attend an Expii seminar hosted by its founder, Prof. Po-Shen Loh (also the leader of the IMO Team USA which won two consecutive IMOs, and the head coach of Team CMU to the Putnam 2016 which finished first). The talk itself was refreshing, with descriptions of a unique approach of teaching maths  (with a demonstration of solving a puzzle involving 8 x 8 table efficiently).

The gist of the day, nevertheless, lies in the after session (courtesy to Mr. Yeoh and Mr. Eng, the fathers of two students into the IMO camp).

Since it was right after the conclusion of the 2016 IMO, I started off, “why is there only one geometry problem in this IMO?” and Prof. Loh replied, “why must there be two?” I was stunned: this is something that I always hoped for but I myself couldn’t tell why. He continued by saying that the team was quite ‘green’ (i.e. new to math olympiad) and the members won “only because the problems are rather unconventional”. I hardy recalled the exact content of the ensuing conversation, but I could attest that he was a proponent of getting non-traditional problems onto the paper: that was how the topic of evolution and change started. At one point we delved into the aspect of transportation, which I said how taxi drivers are disgruntled by the proliferation of ride-sharing services like Uber and Grab. He continued by something stronger: “who knows if these ride-sharing drivers will be replaced by autonomous cars in the future?” An interesting thought, indeed.

The after-session

As I thought further, one reason that I am an avid fan of geometry-heavy math Olympiad paper was my longing for the perpetuation of status quo. When I first stepped into the IMO training camp, Mr. Suhaimi talked about the sacrosanct position of geometry in the heart of mathematicians as people started understanding mathematics through geometric diagrams and partition of lands, “you should therefore love geometry to ace the IMO”, he continued, which indirectly inculcated the importance of geometry in our minds (disclaimer: that’s during the old good days when we had two geometry problems in each IMO contest).  My passion for geometry also comes from my relative strength on geometry compared to other topics, especially after my unexpected (magical, rather) discovery of trigonometric hacks in solving geometry problem. It’s just heart-wrenching to see my strongest and favorite subject being ruthlessly de-emphasized in the IMO.

Further explaining people’s fondness towards mathematics was the relative simplicity to train and excel in geometry compared to other topics. Indeed, to quote from a former IMO teammate (Ying Hong), “you will find yourselves breaking a math problem into a few smaller sub-problems, and finding them is itself a challenge. In geometry, finding the sub-problems are way easier”.

The discussion of conventionality extends beyond geometry itself. In inequality, for example, a classical trick is to use Muirhead’s inequality which required little ingenuity, albeit being more tedious due to terms expansion. That’s another reason why inequality today aren’t that solvable using Muirhead’s: as quoted from this Inequalities handout by David Arthur, juries are aware of the vulnerability of certain problems under this inequalities and will therefore avoid them. On the other hand, some other classical tricks like Cauchy-Shwarz are still being favoured: it requires more ingenuity to notice that an inequality problem can be vanquished by this trick, with some tweaking of terms necessary.

A serious question to ponder would be, given the types of problems favoured by the juries these days, how to excel in math Olympiad from time to time? (Well this question might not be relevant to me, but still worth a thought). In hindsight, an inherent weakness of myself in my math Olympiad journey was that my performance depended significantly on the types of problems given–especially in real contests when time constraint matters. My performance could fluctuate from solving IMOSL 2013 N6 in two hours to merely nailing problems 1 and 4 on the Spring 2014 Tournament Of Towns A-Levels (I have to concede that TOT isn’t really a contest I could easily thrive in compared to APMO and the then-IMO). How could legendary individuals like Alex Song, Lim Jeck and Lisa Sauermann kept vanquishing the IMO problems regardless of how bizarre they were? The key is, probably, to embrace the new types of mathematical tricks from time to time. This is easier said than done, but resembles a requisite for one to call themselves a true mathematician–to exhibit interest in every field in mathematics that is getting increasingly diverse every day.

Let me end this post with a question a friend asked me: “do you think math defines the world or world defines math?” Here’s my answer, edited for clarity:
“The answer is both. Math defines the world because some objects in the nature has heavy mathematical components in it (like the number of petals being Fibonacci number, and beehives being hexagonal). The world is determined by people, and sometimes it’s the people themselves who determine which types of math we do. E.g. look at the 2017 IMO, in which the dearth of geometry problems on Day 1 and the novel nature of Problem 6 suggests a high level of unconventionality.”

PS: let’s not forget the geometry diagrams that are aesthetically pleasing to eyes while cracking the problems. You shall be remembered.

IMO 2017

Let’s aim for a 35: this is what I should have gotten in IMO 2014 if I didn’t screw up my geometry problem 3 because I solved it eventually in a rather simple way. Forget it, 35 is only ‘reserved’ for the top 3 in the contest, as it turns out.

As usual, I ‘took’ the IMO 2017 paper. As usual, I never did well on the IMO when I try it at home instead of at the contest (IMO 2016 was still considered okay since I could have gotten a gold if not because of disbelieving my initial construction on problem 5). But the depression from this IMO is so strong that I doubt if I myself can even take it.

As it turns out, I was not alone. Problem 1 has the highest mean score in the recent contests, but the complete opposite also happened on Problem 3. The extreme difficulty on Problems 2 and 5 simply made the IMO unbelievably crazy and pull the gold medal boundary down to an unprecedentedly low of 25.

Day 1 : “okay, I am ready. On the goal to get 21 on it?” I opened the AoPS forum, only to be disappointed with the dearth of geometry on the paper.

My face when read the IMO Day 1 paper

I went on, nevertheless, and instantly got Problem 1 in two minutes after trying out small cases (like 3k, 3k+3, … that will give you the sequence of 3,6,9,3,6,9,… eventually, and 3k+1, 3k+4,… that will eventually make 3m+2 into the sequence and the numbers will not repeat themselves again!) Oh yeah, life is good.

But Problem 2 (for the non-constant case) wasn’t a safe sailing, unfortunately (I only get the case of f:integer to integer, which should merit a few marks I guess?) The first thing to do is to substitute 0 into both x and y (which served me right and I got f(c^2)=0 if c=f(0) ), and a few more experimenting gave me f(kc^2)=(1-k)c. “If only the question asks for integers to integers instead of reals to reals”, I whined silently to myself. I kept playing around with the substitution, got a whirl of bizarre terms like f(c^k)=0 for every k a power of 2, only to notice that they wouldn’t help at all (unless we are told that c is an integer). It took me long to get f(1)=0, after which I didn’t feel like proceeding any further.

It’s not until I saw (from a solution) the crucial step of proving that f(b)=0->b=1 by the slick substitution of (b, b/(b-1)) which yields f(f(b)f(b/(b-1))=0 (imagine if f(b) is 0 and b is not 1, then f(0)=0->f is a constant!) There were a few more steps to go, but looks like this step is bringing us there. Whatever, I am too tired/frustrated to try it.

Meme extracted randomly 😛

Problem 3? A beautiful problem I should concede, but the fact that only 7 contestants attained nonzero score (with a lowest-ever mean score of 0.042/7) dissuaded me from trying it. 😛

Day 2: looks more bearable, with geometry as Problem 4. For some reason it took me quite long (35 minutes I guess?) until I saw the fact that AT and RK are parallel (via some angle chasing), and the solution can be completed using some properties of triangle similarities.

Now the next step (according to my plan) wasn’t to try Problem 5 (some algorithmic combinatorics) but Problem 6 instead (number theory, which matches more closely in my favour). In fact, that was the problem that kept me awake at 4am when all the computations happened in my brain. Here I went:
-The determinant (name it K) of the square matrix with x^(n-1), x^(n-2)y, …, y^(n-1) on each column (for n different pairs of (x,y) ) is the product of (x[i]y[j]-x[j]y[i]), running over all possible i and j with i<j (or the other way round?) This means it cannot be zero so the system of equation has a unique rational solution (Yay, no?)
-Now let’s try to expand n to make it more reasonable. Honestly speaking, I thought the struggle would end really really soon when I (mistakenly) conjectured that all we need is to find an n big enough (say phi(K) ) and a and b such that ax+by is relatively prime to K for all pairs of such (x,y). Therefore the system of equation (i.e. (ax+by)^n) has remainder 1 when divided by K, and we can play around with the coefficients to make the values actually 1. Oh well, this is wrong. We need it to have remainder 1 when divided by Kx^(n-g) where g is the number of such pairs. (Neh…that sounds impossible)

Finally, with much chagrin I should say that I haven’t found an algorithm to Problem 5, but a few pitfalls instead. (Oh well this isn’t exactly the type of IMO paper I want to see…). Thanks to the generous partials given on Problem 2 can I be sure to say that I could medal with 16 points (or maybe silver at 19, if I am lucky enough to get garbage points in Problem 6 as well). RIP gold.

Congrats to my Team Malaysia which improved it ranking from 56 to 37, in any case. 🙂

About maths, again

#APMO_2017

Most acquaintances of mine know about my immense obsession with maths. I remembered the moments when I just spent a few hours in a row to crack just a tough mathematical Olympiad problem, merely to enjoy the relief as I finally tackled it successfully. The diminishing occurrences of myself immersing in the sea of mathematical thoughts after IMO 2014, therefore, made me question myself “where did my mathematical passion go?”

In fact, it wasn’t because I didn’t want to do math again. Rather, it was due to practical reasons like time consumption, academic workload, and the application to universities (back then) and internships (right now). It was also because of my obsession with competitive coding, due to my research in graph theory right now and my will to ace my subsequent internship applications. This explains the gradual blending of HackerRank and Codeforces into my regular routine, and the kick-staring of my contest participation on Codeforces after my ascending to O(1) rating (top 1%) on HackerRank (with two gold medals on Week of Code 24 and 32).

My attempt on APMO 2017 was worth a mention in this respect, whereby I tried for no more than 2 hours on the 4-hour paper (during which I captured the main idea of problems 2 to 4 since problems 1 and 5 looked hard). As usual, the “90 degree observation” on problem 2 suggested me to use trigonometric bashing, and the bijection methodology of problem 3 jumped out of itself after expanding the series of 2^x-1 into 1+2+…+2^(x-1). Problem 4 simply relies on the fact that if p divides a+b+c and two of a,b,c are divisible by p, then the the third one is also divisible by p. This leads to the conclusion that the exponent of each prime in the numerator part of c is divisible by (x+y)/gcd(x,y), leading to the solution. The apparent difficult looking of Problem 1 dissuaded me from spending time on it, until I read the solution that outlines its vulnerability under the manipulation of greatest common divisor (gcd) and infinite descent. Meanwhile, problem 5 rendered me clueless, and I didn’t know where to begin (after fake-solving once in my head, only to realize that my proposed invariant did not hold).

This serves to tell something: math still matters for me, but now it’s just not the right time to allocate a few hours in a day just for it. Come Putnam contest preparation, and I will devote more time for you (math) again. ❤

In any case, here’s a mischievous conversion of problem 3 into an algorithmic problem that returns the bijective image from A to B, and vice versa:

Function a->b(array arr) is:
Let n=size(arr), k[i]=log_2(arr[i]+1)
Let array bar[k[0]]
bar[i]=max(sum(exp(k[j]-i-1))
where exp(n)=2^n for n>=0 and 0 for n<0
return bar

Function b->a(array bar) is:
Let n=size(bar)
Let vector arr(0)
Let temp[n],
Foreach i do temp[i]<-bar[i]
while temp[0]>0 do:
let k=0
while (k<n and temp[k]>0) do:
k<-k+1 (so k is the maximum index such that temp[k-1]>0)
arr: push back (exp(k)-1)
where exp(i)=2^i
Foreach i from 0 to k-1 (inclusive) do
temp[i]<-temp[i]-exp(k-i-1)
return arr

The beautiful blending between linear algebra and probability

#Putnam 2016:http://www.artofproblemsolving.com/community/c375980_2016_putnam

As usual, I would write about a math contest that I took part (and passionate about). However now I would hand-pick one problem that I thought beautiful, mainly because it mixes both the concept of determinant/permutation and probability/expectation in an exquisite manner:

One big square, named A, is divided into identical smaller squares, such that there are equal number of squares each column and each row. Moreover, the number of squares in each row is even (so for example we have 2 times 2, 4 times 4, 6 times 6, and so on).  For every smaller square in A (henceforth named cell), we write either 0 or 1 onto it, such that there’s equal chance of we writing 0 or 1 in that square. Consider A’ as another big square, same size as A, formed by reflecting each cell across the diagonal joining the cell in the first row, first column and the last cell, last column (henceforth called main diagonal), and let B be the matrix formed by subtracting numbers in each cell of A by the number in corresponding cell of A’ (i.e. same coordinate). Considering all such possible B, what is the average value of determinant of B?

My approach examines each term in counting the determinant of B (valid because of linearity of expectations), with these observations:
-each number written in the main diagonal is 0
-for each number written in other cells, it has half of the chance of being 0, quarter of chance being 1 and quarter of chance being -1. Implication: the average number written is 0.
-for a cell C and its image C’ across the main diagonal, the number written on C is the negative of that of C’ (i.e. the sum of these two numbers is 0).
-for any two cells X and Y such that neither of them lies on main diagonal and such that X and Y are not the image of each other in the reflection across the main diagonal, the number written in X and that in Y has no impact on each other (we call these numbers independent).

(Terminology: term means the product of entries such that exactly one entry is picked from each row and each column. Factor means the individual cells in each term).

Here’s an illustration how the numbers in cells will look like when we have 4 times 4 squares:

a,b,c,d,e,f can be -1, 0, 1 with chances 1/4, 1/2, 1/4 respectively

In view of the first observation, we can omit those terms that involve any of the cells on the main diagonal. If, for some cell, its image is not in the equation (i.e. we picked a, d, f, -c as inside the diagram) then the every other cell chosen as the term are independent of this cell. Due to this independence we have:

Average of the term =average of the entry * average of the product of the rest of factor in this term.

Also the average value of each entry is 0, so average of this term is 0. We can then disregard this case.

Which terms do we need to care? The case when we choose nobody from the main diagonal and for each cell we choose, its image across the main diagonal is also chosen. Say, in the picture, we choose a, -a, f, -f. In this case, we are examining the average value of (-a^2)(-f^2). Now -a^2 and -f^2 each has half chance to be 0 and half chance to be -1, so af has quarter chance to be 1 (and the rest of chance 0). In general if we have 2n*2n grid then the term chosen has 1/2^n chance to be 1 for n even, or -1 for n odd, so the average is 1/2^n * (-1)^n. Also the permutation of the term has the same parity with n: n swaps from the identity permutation are involved (e.g. in the grid we have 4*4 grids so n=2, and the permutation a, -a, f, -f is definitely even since two swaps from the identity permutation are involved). So the expected value of this term in counting the determinant is actually 1/2^n.

Finally, how many such useful terms we have? It’s (2n Choose 2)*(2n-2 Choose 2)*…*(2 Choose 2)/n!. Reason: in terms of ordered pairs we have (2n Choose 2) ways to choose the first pair, then (2n-2 Choose 2) ways to choose the second pair, and the list goes on. Of course, each pair has been counted n! times (hence the division by n!) Summing up, the expected value, or the average, is (2n Choose 2)*(2n-2 Choose 2)*…*(2 Choose 2)/n! times 1/2^n which is (2n!)/(4^n).

Aside: this can never pass the eyes of a professional mathematician (at least I didn’t write in this manner during the contest) but I intend to make my wordings more accessible to general public (which also explains why I reword the problem).

When I took the IMO paper…again

July has been highly mathematical for me. The release of IMO 2015 shortlist, my unstoppable penchant for trying out problems, the endless journey of searching for mathematical topics to teach,…all drive me to a unprecedented craze for mathematics. Above all, however, was the annual mathematical festival that captivated me–the International Mathematical Olympiad.

Here they came: the problems.

Problem 1: Too many points clustered into a single diagram, which makes the problem rather unconventional. Never mind, just draw the semicircle circumscribing triangle BCF and all is set, because X and D will be on this circle as well (I used trigonometry to established that, only to discover an elementary solution using similar triangle a week after). Moreover, E, X, D will be on the same line parallel to CF, and EM parallel to DC (easy to prove: EA=MX=MC=MF, the circumradius of BCF). If we let DC intersect FX at R then ME bisects RF (by parallel+midpoint argument above). Simple angle chasing yields BD bisects FX, too. Done.

Comment–not an easy geometry; I believe there should have been prettier geometry problems on the IMO 2016 shortlist.

Problem 2: 3 divides n (don’t ask me why), but obviously 3 doesn’t work–I initialized the middle square as M and quickly filled up the diagonals, only to have this diagram:

IMO
MMM
IMO

Wait a minute, can’t you see … that I (key to construction) gonna fall from the stars, straight into your arms… I quickly understood the construction for 9*9 with nine 3*3 similar grid above, only to modify the middle grids of each 3*3 squares.

Construction for n=9. For multiples, just replicate the diagram.

It turned out that 9 must divide n: let n as 3k. First count the entries in each column and each row, then count the entries in diagonals. Now split them into k^2 3*3 grids, and we have those in the centre of grids counted 4 times, corner: 3 times and sides 2 times. If m of the k*k entries are M, then counting 2nd, 5th, 8th,…3k-2th column and 2nd, 5th, 8th, …, 3k-2th column gives all sides and centered grids, so: 2(k^2-c) M’s on the sides, leaving k^2+c M’s on corners. But each M is counted 8k*k times! Summing up, c is k*2/3, and k is a multiple of 3.

Comment: Beautiful puzzle, with difficulty extremely suitable for Problem 2. I’m actually amazed by how fast I tackled the problem.

Problem 3: Attempted, but no work. It turned out to be the toughest nut to crack in the entire IMO paper, and I’m convinced that it will remain a conundrum until I read the solution.

This significantly redefined my view on number theory problems: I had always thought that I have decent mastery in Olympiad number theory, but this NT problem doomed me. Can the unconventionality of the problem be an excuse? No.

Problem 4: Let’s see primes that potentially divide P(n) and P(n+k) for at least one n. k=1, none. k=2…only 7 (take n=7x+2), k=3…only 3 (take n=3x+1), and 19 is good for k=4. (Take n=19x+7). Easily seen that b=2,3,4 can’t work (just take the middle elements and you can’t ‘pair’ all of them), with b=5 more work to do. b=6 can be constructed, however: 19x+7, 7y+2, 3z+1, 7y+4, 19x+11, 3z+4 — they exist by Chinese Remainder Theorem.

Comment: Cute puzzle in number theory, and I enjoy the problem.

Problem 5: Wanted to construct total of 2016 linear factors, but my thinking wafted to an awry position. x-1, x-4, x-5, x-8,… on one side and x-2, x-3, x-6, x-7 on the other side? No no no my mind said it can’t work (disproved on AoPS forum) so I mistakenly ditched it. I experimented on things like x-1 to x-c (c odd), then x-2016 to x-2016+c-1 on one side, and the rest on the other side. Sadly, this pushed me into the black hole of futile verification, and time’s up (4.5 hours mark) before I could tell whether this works.

As it turned out, the modulo 4 construction that wafted through my mind can be simply verified using product telescoping (remember, that, (x-1)(x-4) and (x-2)(x-3) always differ by 2 !)

Comment: Another non-traditional polynomial problem with slight combinatorial flavour.

Problem 6: I did (a), out of the contest time frame. To do this, find three lines and form a triangle, then set a direction for one line. For the other lines, identify the rays which has even and odd points on sides with a reference line, and if the direction of travel is from the even side for a reference point, do the opposite for this new point (and vice versa). There will be no contradiction between different sets of triangles (use Menelaus’ theorem), and this is of course valid (for if the frogs land on the intersection points at the same time, then they had travelled the same number of points before, which means coming from both odd or even sides!) How about 6(b)? Maybe not within my capability, lol. (I intended to show that there are two lines whose ‘midpoints’ coincide, but an AoPS user gave a counterexample 😦 )

Trivia: It’s hilarious to see the different names (instead of Geoff) used in papers of different language: for Malay version, it’s Suhaimi. 😛

—

Overall, this try wasn’t particularly great when the performance is roughly at the borderline silver/bronze (worst case scenario: 770700; should have managed 770772).

The prime generator

The 6th problem in IMO 1987 reads like this:

Given a number k. If (n-squared)+n+k is prime for all n=0,1,… up to square root of a third of k, then this number is prime for n=0,1, all the way up to n=k-2.

Unconventional problem that asks for proof that the numbers are prime, but a little gimmick gets us out of the conundrum. The solution looks like this:

The more intriguing part, of course, is to find such k.

I remembered from doing this problem that 41 fits, but any prime thereafter up to 150 fails. I later tried using computer program, hoping to test this from 2 up to 16 million. Here’s the code:

And the output? 2,3,5,11,17,41. That’s all.

Surprising, isn’t it? Only that few numbers out of the enormous sea that contains millions of numbers work. To quench my thirst, I actually generated the primes (mainly for the 41-series since there are 40 primes emerging from nowhere.) Here they are, based on the 6 sequences defined above.

Mathematically tired

Wait…I was hot on the problems and the Romanian Masters of Mathematics (2016) : Problem 5 and problem 1 are both geometry. Despite having the former substantially harder than the latter, I had a quick solve on the former, comparatively. Then I searched for the geometry problems I have done, ranging from our Junior Olympiad to the IMO, just to regain my feel for them. Reason? I would be presenting a geometry lecture in the IMO camp on 5th March.

Which means I had to prepare handout.

I rushed myself to complete the notes that encompassed enlargement, harmonic bundles, poles and polars, some examples of applications and practice problems. In the meantime I did first round of checking for a confidential project, and coded on Ideone using C++ language (oops I’m still a beginner and am still struggling with stacks). The camp came on 4th March, and I forced my eyes open till 4am on that night with Yi Kye and Mr. Suhaimi for the final check on that project. Then lecture delivering on the next morning! With only 3.5 hours of sleep, I should consider myself unlocking an achievement. 😀

Here went the rest of the camp, having need to stay up later than the students did to finish marking the test papers and wake up early in the morning. By the time the camp ended on 8th, I felt the strong urge from my body to ask for more sleep and slumped into slumber on my way back.

What moved me to facilitate the camp? First of all, math. It was impossible to spend the moment I went through during the IMO camps in 2011-2014 again, and all those memories have been ingrained deeply in my heart. The struggles when confronted my problems, competition between me and the time while solving problems, and the sudden enlightenment upon reading solutions…I really missed that moments. If not these, what else could explain my penchant for occupying myself with problems from the Internet, from the camp assignments and from the tests, even I’m not a participant of the camp? (I actually got my hands dirty on the APMO problems when the contest was running, as an invigilator :P)

The people there delighted me further: looking at them discussing problems made me reminisce the times when I ardently talked maths with Justin, Si Yu, and many more during my IMO times. Although the conversations were closely related to ‘templates’ like: “the problem looks so easy/so hard”, “direct bashing using xxx theorem!”, “this problem trolls!”, they were enough to recall my past memory for me to long for it.

The meeting with the past Malaysian IMO committee members like Prof. Arsmah, Prof. Daud, Prof. Jamal and Ms. Jamilah  during a dinner in Shah Alam added  excitement to the camp experience, although it means travelling back and forth for 3 hours in total (Ms. Masita couldn’t make it to the gathering, but I managed to contact her via Whatsapp). Not much chatting, but it was just too wonderful to see them again. Not forgetting other trainers like Dr. Tan and Zhi Kin, where each talked about research at Cambridge and teaching maths to children. It was just too exciting to meet all of them.

The camp has ended, and I’m going back to normal daily schedule. But the (extended) memories will last!

Solving IMO 2015 problems

The only reason I post is to show how disastrous this IMO contest is (although not participating). Here it goes, problems by problems:

1. Create four triangles using six points, but I could go no more. I turned to (b) and think: hmm the if P_(AB)A=P_(AB)B then P_(AB), P_(AC),…,P_(AZ) must be different (anyway Z here means the last point, like how we denote it as the last alphabet 😛 ) so  {P_(AB), P_(AC),…,P_(AZ)}={B,C,…Z} (with some permutation) and each point represents n-1 such P’s. But if we pair PA and PB (with PA=PB and P in S) then we have (n-1)/2 pairs. OK n must be odd (and trying n=5, the star graph leads to the configuration of regular polygons HAHAHA). Back to (a). Knowing that even n fails for (b) the best is to think of equilateral triangles with a universal center. Seems doable with all points on circle except one, which is the centre O of circle. But how about AO? Here’s it: add three points A,B,C on circle with AOB=BOC=60 deg, and add two points at a time that make an angle 60 deg with the centre. Done.

2. (2,2,2) and (2,2,3) are obtained in seconds, so assume a,b,c distinct. Notice that case where a,b,c even can be happily eliminated too (why? play with powers of 2 you get two of the following is true: p(ab)>p(c) (implying p(ab-c)=p(c) ), p(bc)=p(b)+p(c)>p(a), p(ca)>p(b) where p(x) is the highest power of 2 dividing x. So if p(ab-c)=p(c) and c=d.2^k with d odd, then ab-c=2^k and we have ab-c<c, or ab<2c, so a,b<c. See the contradiction?) But no one can stay happy forever because the case 2 even and 1 odd has already confound me into the spiral of case-by-case analysis (though this implicates c=ab-1). Now replace a with 2^2k.a and b with 2^2k.b, where one of a,b odd. What do we have? 2^2k a(b^2)-(a+b) and 2^2k (a^2)b-(a+b) are powers of 2. The difference is 2^2k (a-b), and a+b cannot be odd-> a and b both odd. Take the difference 2^2k (b-a) 4 divides a+b but not b-a, and if a<b then 2^2k (a^2)b-(a+b)=2^(2k+1). We are close! Now a^2b-(a+b)/(2^2k)=2, from which we obtain (2,6,11). OK now we are left with a,b,c odd, which I haven’t done. The answer (3,5,7) was obtained fortuitously, and after some try, I surrendered.

3. Q,H,M collinear. If X is midpoint of QH then OX bisects angle QXK. Then MH.MQ=BM^2. Is that all? Yes with dilapidated compasses. I tried perpendicular bisector intersection (to locate circumcentre), play with nine point circle, draw a tangent line to circle QKH at K, hit BC at U, hoping to prove UK^2=UF.UM. All failed. I bought myself a pair of new compasses and thought of constructing another circle tangent to circle QKH and passing through FM, which turned out perfectly to be circumcircle of HKM. Now I can conveniently draw perpendicular to QM at H to meet MC at R, the radical centre of circles QKH, KFM, HFM, and now everything reduces to RXO=90 deg. But this can be bashed by using squares of length!

Well this P3 is the most beautiful problem for this olympiad (in my eye 😛 ) *Side note: IMO Problems 3 were geometry for three consecutive years since 2013, while never so for IMOs 2004-2012. What happened?

4. People said it as “ugly” but “fast killed by angle chasing”. I testified this successfully even without a decent compass.

5. STOP! TROLLERS CROSSING! Now f(0)=2 or 0. It used me hours for first case, but the idea was straightforward to understand: just prove f(1)=1, x+f(x) is always a fixed point (which is same for f(0)=0), and if f(k)=k then k=1 (using some substitution involving k). Now the second case. I get: all integers are fixed points, and (2^k)f(x) is fixed point for nonnegative k. But however hard I tried I couldn’t establish any of the three which would kill the problem directly: f is injective/surjective/continuous. No more progress? Game over. (An advice: always verify that your functions work. In this case they are x or 2-x.)

6. “At one point, the mean of the sequence stabilizes”. I didn’t want to try this actively on paper, considering it as a P6. But as mental exercise I thought of set {k+a_k} and concluded that only at most 2015 positive integers (including the hopeless 1) do not belong to this set. And what? Intuitively this number of such integers is the b we are searching for, and N can be taken far away from those “missing numbers”. Of course I’ll need to rigorise the proof onto paper, but I’m there (which was strange: can P6 be something solvable directly by one trick? This trick wasn’t easy to think of, but a problem stemming solely on one hard trick shouldn’t be in IMO).

—

Looked like I can handle 4 problems (1,3,4,6), but how well can I do in competition? P3 took me hours, while P6 can easily be obscured by P5 under exam conditions. In the worst case, I would have 1 and 4 -> can I have 5 more points anywhere to qualify for a silver medal? I don’t know.