Preparation on August Test

Selection on Hong Kong IMO Team

The selection process of the Hong Kong Team for IMO starts annually with the Hing Kong preliminary selection contest in May a year before. The contest consists of 20 short answered within 3 hours. The 100 most outstanding contestants are selected for an eight-month training programme, begins at mid-July and consist three-hour weekly class and four selection tests, three of which are prepared by the committee and held in August, October and December, with the last being Hong Kong China Mathematical Olympiad (CHKMO). All proof based, and 3 hours given to solve each of test. And the last selection test is the Asian Pacific Mathematical Olympiad serves as the last selection test. After APMO…

Wait, Why I am saying this?

Ah, yes. The first selection test, known as the August Test, are prepared to be held 2 days later.

Badly prepared status

However I am in a very badly prepared status, I have a running nose right now and I haven’t memorized the formulas of Complex numbers and barycentric coordinates. Oh for god sake, Look I have nothing. Geometry? I literally haven’t solve a single problem of geometry. Hence coordinate geometry, complex numbers please. Combinatorics? I have nothing but an unconvincing confidence. Algebra and Number Theory is likely okay. Oh holy god, I haven’t learnt primitive roots, quadratic reciprocity… Also I am quite angry that I can’t hand in the problems solved in Mathematical Excalibur(Today is the deadline), oh I am really sorry to Dr. Kin Y Li…I thought to myself, I won’t hand in any solutions if I can’t solve it all. Hence in physically and psychologically, I am absolutely nothing compare to the team member going to IMO. Fine, 2 days left, right?

Argentina 2006 Team Selection Test

Tonight I select the Argentina 2006 TST, not only because it should not be hard, but more it have solutions in Art of Problem Solving Community, and it have 2 days each have 3 problems, and august test have 6 problems in 3 hours too. Hence it makes me a perfect choice… I hope they are not hard…math ahead

Problems are:

Problem 1. Let $ A$ be a set of natural numbers in which if $ a$ , $ b$ belong to $ A$ ($ a>b$) then either $ a+b$ or $ a-b$ belong to $ A$ ( both cases may be possible at the same time). Decide whether there is or not a set $ A$ consisting on exactly $ 100$ elements which has four elements $ x$, $ y$ , $ z$ , $ w$ ( not necessarily distinct) that satisfy $ x-y=512$ and $ z-w=460$

Problem 2. Given 365 cards, in which distinct numbers are written. We may ask for any three cards, the order of numbers written in them. Is it always possible to find out the order of all 365 cards by 2000 such questions?

Problem 3. In a circumference with center $ O$ we draw two equal chord $ AB=CD$ and if $ AB \cap CD =L$ then $ AL>BL$ and $ DL>CL$
We consider $ M \in AL$ and $ N \in DL$ such that $ \widehat {ALC} =2 \widehat {MON}$
Prove that the chord determined by extending $ MN$ has the same as length as both $ AB$ and $ CD$

Problem 4.Find all integers solutions for $ xy+yz+zx-xyz=2$

Problem 5. Let $p$ be a prime with $p>5$, and let $S=\{p-n^2 \vert n \in \mathbb{N}, {n}^{2}<p \}$. Prove that $S$contains two elements $a$ and $b$ such that $a \vert b$ and $1<a<b$.

Problem 6. Let $ n$ be a natural number, and we consider the sequence $ a_1, a_2 \ldots , a_{2n}$ where $ a_i \in (-1,0,1)$ If we make the sum of consecutive members of the sequence, starting from one with an odd index and finishing in one with and even index, the result is $ \le 2$ and $ \ge -2$
How many sequence are there satisfying this conditions?

After an hour killing problems (I gave up after a hour, I should note it down). Only 2 problems solved (And I didn’t write it down formally).

My first thought is to do problems 4 first. Turn out it’s quite simple, I used up 10 minutes trying lots of inequality bonding, don’t work apparently. But when I tried (x-1)(y-1)(z-1)=xyz-xy-yz-zx+x+y+z+1, and I substitute a=x-1, b=y-1, c=z-1, and finished.

Problem 5 stuck me around, here is the solution.

We show that the smallest possible $a$ works.

Let $n= \lfloor \sqrt p \rfloor$. If $n^2+1=p$, then we set $a=p-(n-1)^2=n^2+1-n^2+2n-1=2n$ and $b=p-1^2=n^2$. This works, because surely $p$ is odd, so $2|n$ giving $a=2n|n^2=b$.

In all other cases we can set $a=p-n^2>1$. There are three cases:
a) $n^2+n > p$: Then we set $c=n^2+n-p>0$. Additionally $n^2 < p$ gives $c=n^2-p+n<n$.
b) $n^2+n=p$: this implies $n|p$, impossible.
c) $n^2+n < p$: Then we set $c=p-n^2-n>0$. Additionally $p < (n+1)^2$ gives $c=p-n^2-n=p-(n+1)^2+n+1<n+1$. If $c=n$, then we would have $n=p-n^2-n$ giving $n|p$, impossible. So again $c<n$.

In all possible cases, we now set $b=p-c^2$ and get $b=p-c^2 \equiv p- (\pm n)^2 \equiv p-n^2 \equiv 0 \mod (p-n^2)$, being the result.

Instead I solved Problem 1, I got frustrated considering the two conditions, it’s too messy considering either $ a+b$ or $ a-b$ belong to $ A$, so I construct the so call image set B a subset of integers, where contains only elements in  $ A$ and adding minus sign to elements in  $ A$. Hence we can eliminate one of the condition. After proving 2 is an element in B , boom done.

Problem 2 is like something bubble sort. However I failed (My method is to do induction on n, I think my combinatorical argument need bush up) The answer is also like that: Suppose we have $3n$ cards. We divide the cards into $3$ groups and sort each of them independently, so that we obtain one group $a_1<a_2...<a_n$, another $b_1<b_2...<b_n$ and the last group $c_1<c_2...<c_n$. So I ask a question about $a_1,b_1,c_1$, and whichever is the smallest must be the smallest in the entire list, WLOG $a_1$, then I ask a question about $a_2,b_1,c_1$ so whichever is the smallest out of these will be the next smallest in the entire list, and I can keep adding $1$ element in order, and with $3n-2$questions the entire list will be in order (since for the last $3$ I add them all at once). Now just keep applying the above strategy and you get the recursion $f(3n)=3f(n)+3n-2$

We shall count for $405$ after noticing that $5$ cards you can do it in $4$ questions
For $405$ it would take $403 + 3(133) + 9(43) + 27(13) + 81 (4) = 1864$, and so for $365$ we can do it in less than $2000$ questions for sure.

I actually don’t know what is  $ \widehat {ALC} =2 \widehat {MON}$, oh my geometry sucks.

Let $OM$ and $ON$ cut line segment $BC$ at $E$ and $F$ respectively.And let $P$ and $Q$ be projections of $O$ to $AB$ and $CD$respectively.$AB=CD$ and $ABCD$-cyclic implies that $ABCD$ is isosceles trapezoid.$BL=CL \implies AL=DL \implies \angle BAD=\angle CDA = \angle DCB = \angle ABC$. $OP \perp AB$ and $OQ \perp CD$implies that $AP=PB$ and $QD=QC;AL=DL$ implies that $PL=QL \implies \angle LPQ = \angle LQP= \angle ABC$ which implies that $BC || PQ ;OL \perp PQ \implies \angle MOP= \angle NOL$ and $OL \perp BC \implies \angle DCB = \angle NOE \implies CENO$-cyclic and similarly we get that $BFMO$ is cyclic and from $OB=OC$ we get that $\angle OBC= \angle OCB \implies \angle OCN =\angle OBM=\angle OEN=\angle OFM$ which implies that $MEFN$ is cyclic $\implies \angle OFE=\angle OMN$ and $\angle MOP=\angle NOL$ implies that $\angle OFE=\angle OMP \implies \angle OMP=\angle OMN \implies \angle OMX= \angle OMB$ if $MN$ cuts circle at $X$ and $Y$. Let angle bisector of $\angle BOX$ cut $XM$ at $K$ and let $WLOG$ $K$ lies between
$X$ and $M \implies \angle OMX+\angle KOM =\angle OKX=\angle OKB$
$\implies \angle OKB >\angle OMX=\angle OMB$ which is contradiction thus we get that $M=K \implies MB=MX \implies AXBY$is isosceles trapezoid which implies that $XY=AB$.

And I have no idea in problem 6.I search AoPs and just someone thought.

“I didn’t have time to make all the calculations but here’s some thoughts:
Since I couldn’t find any nice combinatorial argument I thought of a “brute force approach”. We see that each pair has a sum in $ S=\{-2,-1,0,1,2\}$ but we have three types of $ 0$, two types of $ \pm 1$ and one type of $ \pm 2$.
Let $ F(n)$ be the number of sequences we are looking at. Let $ f(n)$ denote the number of sequences of length $ n$ with entries in $ S'=S/\{0\}$ (taking different types into account) so that all consecutive sums have absolute value $ \le 2$, so that we have
\[ F(n)=\sum_{k=0}^n3^{n-k}f(k)\binom{n}{k}\]
Now let $ g(n),h(n),g'(n),h'(n)$ be respectively the number of sequences of length $ n$ with entries in $ S'$ so that the absolute value of the sum of consecutive terms doesn’t exceed 2 and so that the sums of the first $ r$ terms ($ 1\le r \le n$) lies in $ \{-2,-1,0\},\{0,1,2\},\{-2,-1,0,1\},\{-1,0,1,2\}$ respectively.
Then we have
\[ f(n)=g(n-1)+h(n-1)+2g'(n-1)+2h'(n-1)\]
\[ g(n)=h(n-1)+2g'(n-1),h(n)=g(n-1)+2h'(n-1)\]
\[ g'(n)=2g(n-1)+2h'(n-1)+h(n-1),h'(n)=2h(n-1)+2g'(n-1)+g(n-1)\]
If we let $ a(n)=g(n)+h(n)$ and $ b(n)=g'(n)+h'(n)$ we have
\[ f(n)=a(n-1)+2b(n-1)\]
\[ a(n)=a(n-1)+2b(n-1)\qquad ,\qquad b(n)=3a(n-1)+2b(n-1)\]
Now everything can be computed recursively and with some algebra we should be able to get the answer.”

Oh my holy Chloe.















Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s