Reading a solution using algebraic integers of a HMMT number theory problem

I tried to attack the following problem but eventually gave up.

Problem 1 (HMMT Ferb 2015 Team P9) Let {z=e^{\tfrac{2\pi i}{201}}} and {\omega= e^{\tfrac{2 \pi i}{10}}}. Prove that

\displaystyle A=\displaystyle \prod_{a=0}^{9}\prod_{b=0}^{100}\prod_{c=0}^{100}(\omega^a+z^b+z^c)

is an integer and find its remainder upon division by {101}.

The only idea I have is to expand this expression, but it was too complex to do. So I decided to read the solution using algebraic integers. I’m new at algebraic number theory and I don’t know much about algebraic integers. My only reference is Problems from the book (PFTB), Chapter 9.

In the second paragraph of the official solution (linked above), it said that the expression is “an integer-coefficient polynomial symmetric in the {\omega^j} (for the {r} residues {j \mod r}) and also syymmetric in the {z^k} (for the {p} residues {k \mod p})”. This is true according to the definition of symmetric polynomial, which I saw in PFTB. The next part is what takes me a quite a time to understand. By simply applying fundamental theorem of symmetric polynomials and the fact that {A} is symmetric polynomial in {\omega^j} and in {z^k}, {A} can be written as an integer-coefficient polynomial in the symmetric sums either of the {\omega^j} or of the {z^k}. However, the official solution wrote that {A} can be written as as an integer-coefficient polynomial in the symmetric sums of the {\omega^j} together with symmetric sums of the {z^k}? After a while, I found that this is indeed true. Here is the proof:

According to fundamental theorem of symmetric sums, there exists a polynomial {g} so that {A=g( S_1(1,z,z^2, \cdots , z^{p-1}) , S_2(1,z,z^2, \cdots , z^{p-1}), \cdots , S_{p}(1,z,z^2, \cdots , z^{p-1}) )} where

\displaystyle S_k(1,z,z^2, \cdots , z^{p-1})= \sum_{1 \le i_1 <i_2< \cdots <i_k\le p-1} z^{i_1}z^{i_2} \ldots z^{i_k}.

Let {f_i(1,\omega,\omega^2, \cdots, \omega^{r-1})} be the coefficient of {S_i(1,z,z^2, \cdots , z^{p-1})}, respectively. If we prove that {f_i} is symmetric polynomial (of course with integer coefficients) in {\omega^j} then {f_i} can be written as integer-coefficient polynomial in the symmetric sums of the {\omega^j}. This proves that {A} can be written as an integer-coefficient polynomial in the symmetric sums of the {\omega^j} together with symmetric sums of the {z^k}. So, let’s go prove this.

Assume that {a=b(\omega^0)^{x_0} (\omega^1)^{x_1} (\omega^2)^{x_2} \ldots (\omega^{r-1})^{x_{r-1}}} appears in {f_i} with {b \in \mathbb{Z}}. It suffices to prove that {a_{\sigma}=b (\omega^{\sigma(0)})^{x_0} \ldots (\omega^{\sigma(r-1)})^{x_{r-1}}} for any permutation {\sigma \in S_r} also appears in {f_i}. Indeed, assume the contrary that {a_{\sigma}} does not appear in {f_i}. Suppose that {a/b} appears in a total of {\ell} coefficients {f} of {g}, which obtain the sum of {h(1,z,z^2, \cdots , z^{p-1})}. This means coefficients of {a_{\sigma}/b} in {A} must also be {h} since {A} is symmetric polynomial in the {\omega^j}. Therefore, if {a_{\sigma}} does not appear in {f_i}, we can pull out all {a_{\sigma}/b} from all coefficients {f_i} of {g} and then add to all coefficients {f_i} that {a/b} is also in. In particular, if {a} is in {f_i} then we add {a_{\sigma}} to {f_i}, if {ac/b \; (c,b \in \mathbb{Z})} is in {f_j} then we add {a_{\sigma}c/b} to {f_j}. This is possible since coefficients of {a/b} and {a_\sigma/b} are both polynomial {h}. Thus, this will give us a new integer-coefficient polynomial {A=p} in the symmetric sums of {z^k} and {p \ne g} since the coefficient in {S_i(1,z, \cdots, z^{p-1})} of two polynomial is different. This contradicts to the unique representation of {g}, which is stated from fundamental theorem of symmetric polynomials. Thus, {a_{\sigma}} must appear in {f_i}. This proves that {f_i} is an integer-coefficient symmetric polynomial in the {\omega^j}, as desired.

I just realised this could be a generalisation of Fundamental theorem of symmetric polynomials:

Proposition 1 Let {A} be a ring and let {f \in A[x_1,x_2, \cdots, x_m, y_1,y_2, \cdots , y_n]} be a symmetric polynomial in the {x_i \; (1 \le i \le m)} and a symmetric polynomial in the {y_I \; (1 \le i \le n)}. Then we can find a polynomial {g \in A[x_1,x_2, \cdots, x_m, y_1,y_2, \cdots, y_n]} so {f(x_1, \cdots , x_m,y_1, \cdots , y_n)= g(S_1(x_1, \cdots, x_m), \cdots , S_m(x_1, \cdots , x_m)}, {S_1(y_1, \cdots , y_n), \cdots , S_n(y_1, \cdots , y_n)).}

Back to our problem, since we know that {(x-1)(x-z) \ldots (x-z^{p-1})=x^p-1} and {(x-1)(x- \omega) \ldots (x- \omega^{r-1})=x^r-1} so all symmetric polynomial in the {\omega^j} and in the {z^k} are all integers. This follows that {A} is an integer from the statement above.

To the next part, {A \pmod{p}}. Since {(x-1)(x-z) \ldots (x-z^{p-1})=x^p-1} so {\displaystyle \prod_{a,b,c}(\omega^a+z^b+z^c)= \prod_{a,b}(-1)^p((-\omega^a-z^b)^p-1)} is true. The next step is troublesome. The official solution uses {(u+v)^p \equiv u^p+v^p \pmod{p}} eventhough {u,v} are not integers. I read from their footnote that for {u,v} integers, if {\frac{u-v}{p}} is an algebraic integer if and only if {\frac{u-v}{p}} is an integer. This is true according to Theorem 9.5, chapter 9, PFTB, which states that if a rational number {a} is an algebraic integer then {a} is an integer. So, back to the problem, I guess they used {\displaystyle u=A= \prod_{a,b,c} (\omega^a+z^b+z^c)=\prod_{a,b}((\omega^a+z^b)^p+1)} and {\displaystyle v= \prod_{a,b}(\omega^{pa}+z^{pb}+1)= \prod_{a} (\omega^{a}+2)^p}. We’ve just proved that {u} is an integer and we can prove that {v} is an integer in a similar way. Now, it suffices to prove {\frac{u-v}{p}} is an algebraic integer. Indeed, note that

\displaystyle \frac 1p \left[ (\omega^a+z^b)^p-\omega^{pa}-z^{pb} \right] = \sum_{i=1}^{p-1} \frac{1}{p} \cdot \binom{p}{i} \omega^{ai}z^{b(p-i)}.

Since {p \mid \binom{p}{i}} and {\omega,z} are algebraic integers so according to Theorem 9.4 from PFTB (which states that sum, product of two algebraic integers is an algebraic integer) then {(\omega^a+z^b)^p=\omega^{pa}+z^{pb}+ \alpha p} where {\alpha} is an algebraic integer. This will lead to {\frac{u-v}{p}} is an algebraic integer. Thus, that means {u \equiv v \pmod{p}}. It suffices to find {v \pmod{p}}. This part is not hard to understand so no further comment from here.

They did give a second solution but I’m to lazy to read now…

Yellowstone Permutation – St. Petersburg MO 2015, grade 9, 2nd round

This problem was given to the St. Petersburg Olympiad 2015, 2nd round, grade 9 and is known as Yellowstone Permutation. You can see here for the article about this sequence and here for the OEIS entry.

Problem. (Yellowstone Permutation) A sequence of integers is defined as follows: a_1=1,a_2=2,a_3=3 and for n>3, a_n is the smallest integer not occurring earlier, which is relatively prime to a_{n-1} but not relatively prime to a_{n-2}. Prove that every natural number occurs exactly once in this sequence.

M. Ivanov

Here is my proof for this interesting problem. Another proof can be found in the article given link above.

Claim 1. There are infinite even numbers in the sequence.

Proof. Suppose that for all i \ge K then a_i is odd. Pick arbitrary large N so a_N is composite (it’s possible since we can’t have three consecutive primes in the sequence), we can substitute one of the prime divisor p of a_N by 2 to get \frac{2a_N}{p}. It’s obvious that \frac{2a_N}{p}< a_N and \gcd \left( a_{N+1}, \frac{2a_N}{p} \right)=\gcd \left( a_{N+1},a_N \right)= 1. If \frac{2a_N}{p} \ne a_i for all i \le K (we can pick sufficient large N to this happens) then a_{N+2} must be equal to some odd number that is less than \frac{2a_N}{p}<a_{N}. Note that this is only true when a_N is a composite. Similarly, we find a_N>a_{N+2}>a_{N+4}> \cdots > a_{N+2i}=p for some p. Such p prime must exist since there are finite odd numbers less than a_N (otherwise the sequence a_N,a_{N+2}, \cdots will keep going.

We can actually pick N so that 2p \ne a_i for all i \le K. Now, note that p \mid a_{N+2i+2} and so 2p \ne a_{N+2i+2}, this can only happen when 2 \mid a_{N+2i+1}, a contradiction to the assumption. Otherwise if 2 \nmid a_{N+2i+1} we will get a contradiction to the smallest value possible of a_{N+2i+2}. Thus, there are infinite even numbers in the sequence. \square

Claim 2. (the problem) Each natural number occurs exactly once in this sequence.

Proof. We prove by induction that each number occurs in the sequence. Suppose that 1,2, \cdots , t-1 appear in the the sequence in the following order a_{b_1},a_{b_2}, \cdots , a_{b_{t-1}} where b_i<b_{i+1} with 1 \le i \le t-2. We will prove that t is in the sequence. Assume not.

Case 1. If there exists a_k>t such that k>b_{t-1} and \gcd (a_k,t)>1 then we must have \gcd (a_{k+1},t )>1, otherwise a_{k+2}=t, the smallest number possible, a contradiction. Similarly, we find \gcd (a_l,t)>1 for all l>K. Now, we pick a prime p>t.

Suppose that there are h numbers less than pt and only receive prime divisors different from p, occurring in this sequence. Pick a_m<pt as one of such numbers where m is maximal. We will prove that there exists prime p>a_k in this sequence to give a contradiction in \gcd (a_l,t)>1 for all l>K. Indeed, if p occurs before a_m then we are done. If not, consider a_{m+2}. We follow a_{m+2}=dp where d\ne 1 is the least divisor of t, otherwise if a_{m+2}<dp then all prime divisors of a_{m+2}<pt are different from p, a contradiction to the maximum of m. Thus, dp=a_{m+2} is in this sequence, which follows a_{m+4}=p, a contradiction since \gcd (a_{m+4},t )>1.

Thus, we can’t have \gcd (a_l,t)>1 for all l>K, which means t is in this sequence.

Case 2. If for all a_k>t and k>b_{t-1} then \gcd (a_k,t)=1. If t is even then from Claim 1 we have a contradiction. Thus, t is odd. Assume that all h numbers less than 2t and relative prime to t have been listed on the sequence. We pick an even number that occurs after those h numbers, call it a_m. It obvious that \gcd (a_{m+1},2t)=1 and a_{m+2} \ge 2t. This follows a_{m+2}=2t, a contradiction since \gcd (a_{m+2},t)=t. Thus, this case can’t happen.

Thus, in all case, t is in the sequence. Hence, all natural number occurs exactly once in this sequence.         \square

I’m not sure I can solve this when I was in year 9, but it seems that in Russia, year 9 students are that good.

The normal approximation to the binomial distribution

A coin is flipped n times with probability of getting heads is p. This is a binomial approximation X \sim B(n,p). The Year 12 MATH B textbook gives an normal approximation to this: B(n,p) \sim N(np,np(1-p))=N(\mu, \sigma^2) where \mu=E[X] is the mean (or expected value) and \sigma is the standard deviation. Since the textbook doesn’t give a proof for this so I will go and prove.

According to the definition, the expected value (or the mean) of getting heads is \displaystyle E[X]=\mu= \sum_{i=0}^n i\binom{n}{i}p^i(1-p)^{n-i}. It suffices to prove that \displaystyle \sum_{i=0}^n i\binom{n}{i}p^i(1-p)^{n-i} =np. We have

\begin{aligned} \frac{1}{np}\sum_{i=0}^n i\binom{n}{i}p^i(1-p)^{n-i} & = \sum_{i=1}^n\frac in \binom{n}{i} p^{i-1}(1-p)^{n-i}, \\ & = \sum_{i=1}^n\binom{n-1}{i-1} p^{i-1}(1-p)^{n-i}, \\ & = \sum_{i=0}^{n-1}\binom{n-1}{i}p^i(1-p)^{n-1-i} = 1. \end{aligned}

Now, for \sigma^2, according to the definition, we have

\displaystyle \sigma^2= \sum_{i=0}^n(i-\mu)^2 \binom ni p^i(1-p)^{n-i}= \sum_{i=0}^ni^2 \binom ni p^i(1-p)^{n-i}-n^2p^2.

Hence, it suffices to prove that

\displaystyle \sum_{i=0}^ni^2 \binom ni p^i(1-p)^{n-i}= np(1+np-p).

Indeed, we have

\begin{aligned} \frac{1}{np}\sum_{i=0}^ni^2 \binom ni p^i(1-p)^{n-i} & = \sum_{i=1}^ni \binom{n-1}{i-1}p^{i-1}(1-p)^{n-i}, \\ & = \sum_{i=0}^{n-1}i\binom{n-1}{i}p^i(1-p)^{n-i-1}+\sum_{i=0}^{n-1}\binom{n-1}{i}p^{i}(1-p)^{n-i-1}, \\ & = (n-1)p+1. \end{aligned}

We are done.

IMO 2016

IMO 2016 was held from 6/7/2016 to 16/07/2016. Although I didn’t attend this, I just want to post my solutions and how I think about the difficulty of the problems, which can be found here. I will post my solutions on this post. Many awesome solutions can be found on AoPS.


Problem 2. Find all integers n for which each cell of n \times n table can be filled with one of the letters I,M and O in such a way that:

  • in each row and each column, one third of the entries are I, one third are M and one third are O; and
  • in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are I, one third are M and one third are O.

Note. The rows and columns of an n \times n table are each labelled 1 to n in a natural order. Thus each cell corresponds to a pair of positive integer (i,j) with 1 \le i,j \le n. For n>1, the table has 4n-2 diagonals of two types. A diagonal of first type consists all cells (i,j) for which i+j is a constant, and the diagonal of this second type consists all cells (i,j) for which i-j is constant.

Solution. Here is a solution using counting in two ways. The answer is all 9 \mid n.

It’s obvious that 3 \mid n. We consider all the squares indexed (3k+2,3l+2) and call it good square. Let a be number of good squares that are filled with I. We can see that every good square lies on both type of diagonals. So if we call D_1,D_2 be the set of all squares in first type, second type of diagonal that are filled with I, respectively. We will have |D_1 \cap D_2|=a and |D_1|=|D_2|= \tfrac 19 n^2. Hence,

|D_1 \cup D_2|=|D_1|+|D_2|+|D_1 \cap D_2|= \tfrac 29 n^2-a.

Hence, number of squares filled with I that either lie on first type of diagonal or second type is \tfrac 29 n^2-2a.

Now, these squares counted above doesn’t fill the columns indexed 3k+2 and rows indexed 3k+2. So we need to fill these squares with I. Let C be the set of squares in columns indexed 3k+2 that are filled with I, similar to set R of rows indexed 3k+2. We have

|C \cup R|=|C|+|R|-|C \cap R|= \tfrac 29 n^2-a.

From these, we find that the total number of squares filled with I is \tfrac 49 n^2-3a. Note that this is also equal to \tfrac 13 n^2 so this means 3a= \tfrac 19 n^2 implies 9 \mid n, which is the final answer.

This argument gives us a way to construct a 9 \times 9 table, which is first we fill all the good squares in a way such that one third of them are I, one third are O and one third are M. After that, we fill all the diagonals and then fill the remain squares. \square

A very simple construction for 9 \times 9 square of Evan Chen can be found in AoPS forum (link provided above). We can see that this is a direct counting problem, with a main notice is that if we exclude all diagonals (both types) then the remaining squares can only lie on either rows indexed 3l+2 or columns indexed 3l+2. I think I’ve seen this type of problem before (board problem and use direct counting), I will try to search if I can find it. This problem took me a whole night to solve.


Problem 3. Let P=A_1A_2\cdots A_k be a convex polygon in the plane. The vertices A_1, A_2, \ldots, A_k have integral coordinates and lie on a circle. Let S be the area of P. An odd positive integer n is given such that the squares of the side lengths of P are integers divisible by n. Prove that 2S is an integer divisible by n.

Solution. Yes, induction on k works.

For k=3 then it’s obviously true according to Heron’s formula.

If it’s true till convex polygon with k-1 vertices, we need to prove that it’s also true for convex polygon with k vertices. Indeed, we will show that there exists a diagonal A_iA_j such that \nu_p(n) \le \nu_p(A_iA_j^2) for odd prime divisor p of n. Assume contradiction, that means \nu_p(A_iA_j^2) < \nu_p(n) for all 1 \le i<j \le k and j-i \ne 1. Now, according to Ptolemy’s theorem for any four vertices A_x,A_{x+1},A_{y},A_{y+1} (denote a_{mn} as the length of side A_mA_n) with x+1<y we have

a_{(x+1)(y+1)}a_{xy}=a_{x(x+1)}a_{y(y+1)}+a_{(x+1)y}a_{x(y+1)}.

This implies

a_{(x+1)(y+1)}^2a_{xy}^2=a_{x(x+1)}^2a_{y(y+1)}^2+2a_{x(x+1)}a_{y(y+1)}a_{y(x+1)}a_{x(y+1)}+a_{(x+1)y}^2a_{x(y+1)}^2.

Therefore 2a_{x(x+1}a_{y(y+1)}a_{y(x+1)}a_{x(y+1)} \in \mathbb{Z}. From the contradict assumption, we have

\begin{aligned} \nu_p \left(a_{x(x+1)}a_{y(y+1)}a_{y(x+1)}a_{x(y+1)} \right) &  = \tfrac 12 \left[ \nu_p \left( a_{x(x+1)}^2a_{y(y+1)}^2 \right)+ \nu_p \left( a_{y(x+1)}^2 \right)^2+\nu_p \left( a_{x(y+1)}^2 \right) \right], \\ &  \ge \nu_p(n)+ \tfrac 12 \nu_p \left( a_{y(x+1)}^2 \right)^2+\tfrac 12 \nu_p \left( a_{x(y+1)}^2 \right), \\ &  > \nu_p \left( a_{y(x+1)}^2 \right)^2+ \nu_p \left( a_{x(y+1)}^2 \right)=\nu_p \left( a_{(x+1)y}^2a_{x(y+1)}^2 \right). \end{aligned}

and n^2 \mid a_{x(x+1)}^2a_{y(y+1)}^2 so that means

\begin{aligned} \nu_p \left( a_{(x+1)(y+1)}^2 \right)+\nu_p \left( a_{xy}^2 \right) & = \nu_p \left( a_{(x+1)y}^2a_{x(y+1)}^2 \right), \\ &  = \nu_p \left( a_{y(x+1)}^2 \right)+\nu_p \left( a_{(y+1)(x)}^2 \right). \end{aligned}

Since this equality is true for all 1 \le x<y-1 \le k-1 so we add all up and get a contradiction.
This means there will exists 1 \le m<h-1 \le k-1 such that \nu_p \left( A_mA_h^2 \right) =\nu_p \left( a_{mh} ^2 \right) \ge \nu_p(n). We divide the big polygon in to two smaller polygons with areas S_1,S_2 by the diagonal A_mA_h. From the inductive hypothesis, we have \nu_p(n) \le \nu_p(2S_i), which follows \nu_p(n) \le \nu_p(2S). Thus, we obtain n \mid 2S. \square

This is the strangest problem in the competition and also the most beautiful problem. It combines between number theory and geometry. I think what makes this problem hard to solve during the competition is because of it is unfamiliar, that’s all. If you read the solution above, you can see that the idea process is very familiar in olympiad number theory: induction + prove mod p to obtain mod n. The rest is just mainly comparing \nu_p using some knowledge in geometry (in above I used Ptolemy’s theorem, there are many other ways, like using Inversion – Jeck Lim’s solution on AoPS). This problem took me 2 days to solve, mainly because I was too focus on some stupid calculation of sides of polygons. I should’ve thought of induction sooner.

Updated: silouan (AoPS) found a very similar problem to problem 3, use the same method to solve:

[IMO Shortlist 2004, N7] Let p be an odd prime and n a positive integer. In the coordinate plane, eight distinct points with integer coordinates lie on a circle with diameter of length p^{n}. Prove that there exists a triangle with vertices at three of the given points such that the squares of its side lengths are integers divisible by p^{n+1}.


Problem 6. There are n\ge 2 line segments in the plane such that every two segments cross and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it facing the other endpoint. Then he will clap his hands n-1 times. Every time he claps,each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them will every occupy the same intersection point at the same time.

(a) Prove that Geoff can always fulfil his wish if n is odd.

(b) Prove that Geoff can never fulfil his wish if n is even.

Solution.

I can only solve 6(a): choose a line \ell and place a frog on a line anywhere. For all other lines \ell',
– if frog on \ell passes D= \ell \cap \ell' on even clap, place frog on \ell' such that it passes D=\ell \cap \ell' on odd clap.
– vice versa.
Choose any two lines \ell_1 and \ell_2 and a simple geometry argument shows that two frogs pass \ell_1 \cap \ell_2 in claps of different parity, which means the frogs cannot occupy  the same intersection at the same time.

My construction for a) is the same as qwerty414’s post in #4. From this one, it suffices to prove that for any two lines \ell_1, \ell_2 \ne \ell, they can’t occupy the same intersection point at the same time.

Let \ell be A_1B_1, \ell_1 be A_2B_2 and \ell_3 be A_3B_3 and the frogs start with A_1,A_2,A_3. Assume contradiction that A_2B_2,A_3B_3 occupy the same intersection point Z at the same time. Hence, number of jumps from A_2 to Z must have same parity with number of jumps from A_3 to Z.

A note that from the construction, number of jump from A_1 to X must have different parity with number of jumps from A_2 to X, similarly to A_1 to Y and A_3 to Y. From these, in all cases, we must have either number of jumps from X to Y, Y to Z, Z to Z are all even or one of these three are even, the remain two are odd. Thus, if the call a,b,c be number of points between X and Y, Y and Z, Z and X then we always have 2 \nmid a+b+c.

bb24507037055c51d095a218b9a64e4335eabaab

On the other hand, since if a line passes through XY,YZ then it can’t cut ZX, vice versa. So that means there exists m,n,p such that a=m+n,b=n+p,c=p+m where m be number of points that pass through XY,ZX, similarly to n,p. Thus, 2 \mid a+b+c, a contradiction.

Therefore, A_2B_2,A_3B_3 can’t occupy the same intersection at the same time. Thus, for n odd, Geoff always fulfil his wish. \square

My idea to solve (a) doesn’t work with (b). Actually, all (a) and (b) can be solved using a trick: drawing a circle containing all the intersections of lines. This idea, which can be viewed on AoPS, make it very easy for anyone who knows (that’s why many people – not me – said IMO this year has the easiest problem 6). This idea came cross my mind once but I can’t notice the main point why we should do that, so I failed to apply it. Instead, I found a different approach for (a). I think there is some problems using this trick before. Anyway, part (a) took me 7-8 hours to solve (I try to attempt for few hours and fell hopeless so I went to sleep, and after I wake up, I find this idea). An open question is that what if instead of lines, the frogs go in a polygon way?


Problem 4. A set of postive integers is called fragrant if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements.  Let P(n)=n^2+n+1.  What is the least possible positive integer value of b such that there exists a non-negative integer a for which the set

\{P(a+1),P(a+2),\ldots,P(a+b)\}

is fragrant?

Solution. Consider P(x) and P(x+y). We note that in order to p \mid P(x) and p \mid P(x+y)-P(x) we must have p \mid x^2+x+1 and p \mid y(2x+y+1). It is obvious that p \equiv 1 \pmod{6} since p \mid n^2+n+1 \mid (2n+1)^2+3 or \left( \tfrac{-3}{p} \right)=1.

If y=1 then p \mid 2x+2 implies p \mid x+1. WLOG, we can let x=p-1 and see that p \nmid x^2+x+1. So there doesn’t exists x so that \gcd \left( P(x),P(x+1) \right)>1.

If y=2, we find p \mid 2x+3 and we let x=\tfrac{p-3}{2}. Hence, from p \mid x^2+x+1 we get p=7. So there is one prime p=7 such that \gcd \left( P(x),P(x+2) \right)>1.

If y=3, it is obvious that p=3 satisfy and is the only answer.

If y=4, we do the similar thing and get p \mid 2x+5 and p \mid x^2+x+1 so p=19.
Now, back to the problem, since there doesn’t exists any prime p for y=1 so b \ge 3. The only prime for y=2 is p=7 so if we choose 7 \mid P(x+1), 7 \mid P(x+3) then there will be a number 7 \nmid P(x+2) remains. This means b \ge 5 since we need a prime p \mid P(x+2) and p \mid P(x+y) but y \ge 5 since p \ne 7.

If b=5, we consider two cases, where there are two numbers that are divisible by 19 (which means 19 \mid P(x+1), 19 \mid P(x+5)), the middle-three numbers P(x+2),P(x+3),P(x+4) we can’t find a way make each two of them have common prime factor. If no two are divisible by 19 then they can only be divisible by 7,3, but it can’t cover all 5 “consecutive” numbers.

If b=6 then we can pick 19 \mid P(x+2),P(x+6), 3 \mid P(x+1), P(x+4), 7 \mid P(x+3), 7 \mid P(x+5).

So the final answer is b=6. \square

I was spoiled by the answer for this problem, took me 40 min to solve. However, I still think this problem is not hard. It applies classic number theory idea (CRT, gcd, mod prime). I see that this problem is just a small case, so the open question is if the property of fragrant set change to: “each of its elements has a prime factor in common with at least k of the other elements” or maybe “each of its elements has at least two prime factors in common with at least one of the other elements” then what will be the best bound for b?


Problem 5. The equation

(x-1)(x-2)\cdots(x-2016)=(x-1)(x-2)\cdots (x-2016)

is written on the board, with 2016 linear factors on each side. What is the least possible value of k for which it is possible to erase exactly k of these 4032 linear factors so that at least one factor remains on each side and the resulting equation has no real solutions?

Updated: I found a problem that looks like problem 5:

[Australia MO 2015] Determine the number of distinct real solutions of the equation

(x-1)(x-3)(x-5) \cdots (x-2015)=(x-2)(x-4)(x-6) \cdots (x-2014).

I was spoiled to much (on AoPS) in problem 5 so I just read the solution on AoPS anyway. I solved problem 1 (geometry problem) but after seeing more than 50 posts in here, I lost my motivation in posting my solution. It is a nice figure though, but the problem is stated with too many points. Problem 1 took me about an hour and a half to solve. Again, I think I can solve this less than an hour but I was too focus on stupid calculation of sides instead of trying to find new properties of figure sooner.


In difficult orders, I would say 4<1<2=5<3<6. Many people would order problem 6 as easy problem, but for me, it’s a hard one, harder than 3 (in how to think of that idea). Although I didn’t attempt problem 5, but I think it would be around same level with problem 2 (hopefully).

In quantity orders, I think 4<1<2<5<6<<3. Yes, problem 3 is the most beautiful one, no doubt about that. I don’t have any other comments about other problems.

Basically, IMO2016 has many interesting problems (3,5,6). I think it would be nicer if the judge could replace problem 4 by a geometry problem.

Bài hình học Tuần 4 tháng 12 – 2015 của thầy Trần Quang Hùng

Thầy Trần Quang Hùng có một chuyên mục Mỗi tuần một bài toán trên blog của thầy. Dưới đây là bài toán của thầy Hùng đưa lên trong Tuần 4 tháng 12.

PROBLEM. Cho tam giác ABC nhọn với đường cao AH và tâm ngoại tiếp O. Đường thẳng qua H vuông góc với OH lần lượt cắt CA,AB tại E,F. Gọi M,N theo thứ tự là trực tâm của tam giác OFBOHBP,Q theo thứ tự là trực tâm tam giác OEC, OHC. Chứng minh rằng MN,PQ,EF đồng quy.

Sau đây là lời giải của tôi được đưa lên trong topic Mỗi tuần một bài toán trên DDTH.

Lời giải của tôi.

Không mất tính tổng quát, giả sử C nằm giữa AE. Khi đó F nằm giữa AB. Gọi A_1,B_1,C_1 thứ tự là trung điểm BC,CA,AB.

Screen Shot 2015-12-25 at 10.37.56 pm

Ta có BN \parallel CQ ( \parallel EF), MF \parallel NH \; ( \perp OB), \; QH \parallel PE\; ( \perp OC)M,P thứ tự thuộc trung trực AB,AC (do OM \perp BF, OP \perp CE). Q,N thuộc trung trực BC (do OQ \perp HC, ON \perp HC) và đối xứng với nhau qua A_1 (do BN \parallel QC \; (\perp OH)). Ta cũng có các tứ giác OHFC_1,OHEB_1 nội tiếp do có \angle OC_1F= \angle OHF= \angle OHE=\angle OB_1E=90^{\circ}.

Gọi K là trực tâm tam giác ABC, T là hình chiếu từ K lên EF. Do OH \perp EF, OC_1 \perp AB, OB_1 \perp AC(HC_1B_1) cắt AF,AE lần thứ hai tại H_c,H_b nên ta suy ra K chính là điểm đẳng giác của O đối với tam giác AEF.

Do \angle KHT= \angle OHA_1(=90^{\circ}- \angle KHO) nên \triangle KTH \sim \triangle OHA_1\triangle OHA_1 \sim\triangle QA_1C nên \triangle KTH \sim \triangle QA_1C dẫn đến \frac{TH}{KT}= \frac{QA_1}{A_1C}= \frac{2QA_1}{BC}. Mặt khác, ta cũng có \angle QHC= \angle COA_1 (do Q là trực tâm \triangle OHC) suy ra \triangle QHA_1 \sim \triangle COA_1, dẫn đến \frac{QA_1}{NH}=\frac{QA_1}{QH}= \frac{A_1C}{OC}= \frac{BC}{2OC}. Như vậy \frac{TH}{KT} \cdot \frac{QA_1}{NH}= \frac{QA_1}{OC} suy ra \frac{TH}{NH}= \frac{KT}{OC}. \qquad (1)

Do K,O là hai điểm đẳng giác đối với tam giác AEF nên \triangle KTF \sim \triangle OC_1F dẫn đến \frac{KT}{FT}= \frac{OC_1}{FC_1}. Mặt khác, ta lại có \angle FMC_1 \equiv \angle FMO= \angle ABO (do M trực tâm \triangle OFB). Từ đây ta có được \triangle MC_1F \sim \triangle BC_1O suy ra \frac{OC_1}{FC_1}= \frac{BO}{MF}. Kết hợp hai đẳng thức ta có được \frac{KT}{FT}= \frac{BO}{MF} hay \frac{KT}{OC}= \frac{FT}{MF}. \qquad (2)

Từ (1)(2) ta suy ra \frac{TH}{NH}= \frac{FT}{MF}. Kết hợp với điều kiện MF \parallel HNF,T,H thẳng hàng ta suy ra M,T,N thẳng hàng. (chỗ này chắc phải lập luận thêm tí nữa rằng N,M nằm hai nửa mặt phẳng đối nhau bờ EF). Chứng minh tương tự T,Q,P thẳng hàng. Như vậy MN,PQ,EF đồng quy tại T. (điểm thú vị là điểmT thuộc luôn đường tròn Euler của tam giác ABC).

—————————————

Tôi có tìm thấy một số tính chất khác ở hình này, ban đầu tôi định dựa vào các tính chất này để chứng minh bài toán nhưng dần đến ngõ cụt, thế là phải chuyển sang một hướng mới như trên. 🙂

Chứng minh M,A,P thẳng hàng.

Thật vậy, ta có

\angle MAB= \angle MBA= \angle MOF= \angle C_1HF.

Tương tự \angle PAC= \angle B_1HE. Do đó

\angle MAB+ \angle PAC= 180^{\circ}- \angle C_1HB_1=180^{\circ}- \angle C_1A_1B_1= 180^{\circ}- \angle A.

Ta suy ra \angle MAF+ \angle FAE+ \angle EAP=180^{\circ} dẫn đến M,A,P thẳng hàng. \blacksquare

Chứng minh M,F,E,P cùng thuộc một đường tròn.

Do tứ giác C_1FHOC_1B_1A_1H nội tiếp nên

\begin{aligned} \angle HOF & = \angle HC_1F \\ & =180^{\circ}- \angle AC_1B_1- \angle HC_1B_1 \\ & = 180^{\circ}-\angle B- \angle B_1A_1C \\ & = 180^{\circ}- 2 \angle B= 180^{\circ}- \angle AOC. \end{aligned}

Từ đây ta suy ra \angle AOF+ \angle HOC=180^{\circ}.

Mặt khác, do \angle MAB= \angle MOF (= \angle MBA) nên tứ giác MAFO nội tiếp. Ta suy ra \angle AOF+ \angle AMF=180^{\circ} dẫn đến \angle HOC= \angle AMF. Ta lại có

\angle AMF= \angle HOC= \angle A+ \angle HOA_1 = \angle QHC+ \angle CHE = \angle QHE=180^{\circ}- \angle QHF.

Do PE \parallel QH nên \angle QHF= \angle FEP dẫn đến \angle FEP+ \angle AMF=180^{\circ} suy ra M,F,E,P cùng thuộc một đường tròn. \blacksquare

—————————-

Thầy Trần Quang Hùng và anh Nguyễn Tiến Dũng đã có một lời giải khác rất hay và ngắn gọn, có sử dụng tính chất K,O là hai điểm đẳng giác trong tam giác ABC. Hai lời giải được đưa ra tại Tuần 5 tháng 12 và topic Mỗi tuần một bài toán tại DDTH.

Bạn Nguyễn Minh Quang lại có một lời giải khác nữa sử dụng bổ đề thú vị tại đây. Theo nhận xét của anh Ngô Quang Dương trong Tuần 5 tháng 12 thì bài toán vẫn đúng với hai điểm đẳng giác bất kì.

Tồn tại một số bằng tổng hai số

PROBLEM. Let n be a positive integer and \{A,B,C\} a partition of \{1,2,\ldots,3n\} such that |A|=|B|=|C|=n. Prove that there exist x \in A, y \in B, z \in C such that one of x,y,z is the sum of the other two.

Chia các số từ 1 đến 3n vào 3 nhóm, mỗi nhóm n số. Chứng minh có thể chọn ở mỗi nhóm 1 số sao cho trong 3 số được chọn có 1 số bằng tổng 2 số kia.

Link. đây (VMF)

Bài này làm tôi tốn rất nhiều thời gian để nghĩ ra lời giải. 😀 Sau đây là lời giải của tôi.

Lời giải của tôi. Giả sử rằng tồn tại một cách chia nhóm mà không có số nào trong mỗi nhóm bằng tổng của hai số lần lượt thuộc hai nhóm kia. Gọi các nhóm và các số trong nhóm lúc đó là các tập: A= \{ a_1,a_2, \cdots, a_n \}, \; B= \{ b_1,b_2, \cdots , b_n \}, \; C= \{ c_1,c_2, \cdots , c_n \}. Không mất tính tổng quát, giả sử 1 \in A. Khi đó b_i \pm 1 \in A \; \text{or} \; B.

Bước 1. Chứng minh 2 \in A.

Giả sử phản chứng rằng 2 \in C.

Nếu trong B tồn tại hai số b_y,b_x \; (b_y<3n) thoả b_y-b_x=1. Khi đó (b_y+1)-b_x=2. Ta suy ra b_y+1 \not\in A vì nếu b_y+1 \in A2 \in C, b_x \in B suy ra điều mâu thuẫn với điều giả sử ban đầu. Vậy b_y+1 \in B. Chứng minh tương tự b_y+2, b_y+3 \in B, \cdots , 3n \in B. Ta cũng có b_y-1=b_x \in B nên b_y-(b_x-1)=2 suy ra b_x-1=b_y-2 \in B. Như vậy b_y-1,b_y-2, \cdots, 1 \in B. Do đó |B|=3n, mâu thuẫn.

Nếu trong B không tồn tại hai số b_y,b_x \; (b_y<3n) thoả b_y-b_x=1. Khi đó b_i \pm 1 \in A \; (1 \le i \le n-1) suy ra |A| \ge 2n-2, mâu thuẫn.

Vậy 2 \in A.

Bước 2. Chứng minh 3 \in A.

Ta đã có 1,2 \in A nên b_i \pm 1,b_i \pm 2 \in A \; \text{or} \; B. Giả sử phản chứng rằng 3 \in C.

Nếu trong B tồn tại hai số b_y,b_x \; (b_y<3n) thoả mãn b_y-b_x=1. Khi đó b_x,b_x+1 \in B nên b_x+3 \in B (vì b_x+3=(b_x+1)+2 nên b_x+3 \not\in C và nếu b_x+3 \in Ab_x \in B, 3 \in C sẽ suy ra ngay mâu thuẫn). Tương tự b_x+4, b_x+6,b_x+7, \cdots , ... \in Bb_x-2,b_x-3, \cdots \in B. Từ đây ta dễ dàng dẫn đến là b_x+3l, bx+3l+1 \in B với mọi l \in \mathbb{Z} sao cho bx+3l,bx+3l+1 \le 3n. Nếu tồn tại số k=b_x+3m+2 \in C thì khi đó do b_x+3m+1 \in B1 \in A1+(b_x+3m+1)=b_x+3m+2 nên ta suy ra ngay mâu thuẫn.

Nếu trong B không tồn tại hai số b_y,b_x \; (b_y<3n) thoả b_y-b_x=1. Khi đó b_i \pm 1 \in A \; (1 \le i \le n-1) suy ra |A| \ge 2n-2, mâu thuẫn.

Như vậy 3 \in A.

Bước 3. 1,2, \cdots , n-1 \in A. Chứng minh n \in A.

Như vậy ta đã có 1,2, \cdots , n-1 \in A suy ra b_i \pm 1, b_i \pm 2, \cdots, b_i \pm (n-1) \in A \; \text{or} \; B. Giả sử phản chứng n \in C.

Nếu trong B tồn tại hai số b_y,b_x \; (b_y<3n) thoả mãn b_y-b_x=1. Khi đó b_x,b_x+1 \in B nên b_x+n \in B (vì b_x+n=(b_x+1)+(n-1) nên b_x+n \in A \; \text{or} \; B mà nếu b_x+n \in A, lại có n \in C, b_x \in B thì suy ra ngay mâu thuẫn). Tương tự b_x+n+1, \in B. Cứ như thế ta suy ra b_x+nk,b_x+nk+1 \in B với k \in \mathbb{Z} thoả mãn 1 \le b_x+nk,b_x+nk+1 \le 3n. Xét có một số m= b_x+ny+r \in C \; (0 \le r \le n-1, r \ne 0,1). Ta có số b_x+ny+1 \in B(b_x+ny+1)+(r-1)=b_x+ny+r với 1 \le r \le n-2 nên r-1 \in A. Từ đây suy ra mâu thuẫn.

Nếu trong B không tồn tại hai số b_y,b_x như thế. Khi đó b_i \pm 1 \in A \; (1 \le i \le n-1) suy ra |A| \ge 2n-2, mâu thuẫn.

Như vậy n \in A.

Ta có được A= \{ 1,2, \cdots , n \}. Giả sử hai tập B,C có dãy

\begin{array}{l} b_{x_1}-b_{y_1}= b_{x_2}-b_{y_2}= \cdots = b_{x_k}-b_{y_k}=1, \\ c_{m_1}-c_{p_1}= c_{m_2}-c_{p_2}= \cdots = c_{m_l}-c_{p_l}=1. \end{array}

Trong đó b_{x_1}, c_{m_1} tương ứng là hai số lớn nhất trong hai dãy. Không mất tính tổng quát, giả sử b_{x_1}<c_{m_1} \le 3n. Khi đó luôn tồn tại một số T \le 3n sao cho T \not\in BT-b_{x_1}=1. Hiển nhiên T \not\in A, T \not\in B (do điều kiện lớn nhất của b_{x_1}) nên T \in C. Từ đây dẫn đến mâu thuẫn với điều kiện giả sử ban đầu.

Như vậy, điều giả sử phản chứng sai. Hay nói cách khác, luôn tồn tại một số trong 1 nhóm mà bằng tổng của hai số lần lượt thuộc hai nhóm còn lại. Bài toán được chứng minh. \blacksquare

Tôi mới phát hiện được ra bài toán này là India TST 2003. Dưới đây là lời giải của thành viên Sayan bên AoPS.

Second solution. We say that the triple (a, b, c) is good when a \in A, b \in B, c \in C and one of the numbers is the sum of two others. We may suppose that 1 \in A, that smallest number, say k, which is not in A is in B. Suppose that there is no good triplet.
We first show that for all x \in C, we have x-1 \in A. Indeed, there exists x \in C such that x-1 \notin A then, since (1, x-1, x) must not be good, so x-1 \notin B, and so x-1 \in C. In particular x-1> k. but as neither of the two triples (x-k, k, x) and (k-1, x-k, x-1) is good, x-k \notin A and x-k \notin B. and therefore x-k \in C. Similarly, by considering the triples (x-k-1, k, x-1) and (1, x-k-1, x-k), we deduce that x-k-1 \in C.
We can then repeat this reasoning, and prove by induction that for all i> 0, the numbers x-ik and x-ik-1, as they are strictly positive, both belong to C. but for one well chosen i, one of these numbers is necessarily less than or equal k, which implies that it belongs to A or B. This is a contradiction.
If we put C = \{c_1,c_2,\cdots,c_n\}. By previous property, and since |A| = |C| = n, so it is that A = \{c_1-1,c_2-1,\cdots,c_n-1\}. But for all i we have c_i> k> 1 then c_i-1> 1, contradicting that 1 \in A. Thus the proof is complete. \blacksquare

“R.K. Guy writes in his Unsolved Problems in Number Theory, E11

E. and G. Szekeres and Schönheim have considered what Bill Sands calls an un-Schur problem. Call a partition of the integers \{1,2,\ldots,N\} into three classes admissible if there is no solution to x+y=z with x,y,z in distinct classes. There is no admissible partition with the size of each class > \dfrac {1} {4} N.”

Một bài toán về chứng minh tồn tại trong số học

Bài toán số học trong Đề kiểm tra trường Đông toán học miền Nam 2015.

PROBLEM. a) Tìm tất cả các số nguyên dương lẻ t thoả mãn tính chất: với mọi số nguyên dương k, tồn tại số nguyên dương a_k sao cho a_k^2+t chia hết cho 2^k.
b) Chứng minh rằng tồn tại dãy số nguyên dương (a_k)_{k=1}^{\infty} sao cho a_k^2+7 chia hết cho 2^k với mọi k\frac{a_{k+1}^2+7}{2^{k+1}} chia hết cho \frac{a_k^2+7}{2^k} với mọi k=1,2,3, \cdots

Lời giải của tôi.

a) Ta sẽ đi chứng minh tất cả các số t thoả mãn đều có dạng 2^{2x}(8y+7) với x,y \in \mathbb{Z};x,y \ge 0.
Thật vậy, nếu t chẵn, ta không khó để suy ra rằng 2 \mid v_2(t) vì nếu 2 \nmid v_2(t) thì chọn ngay k=v_2(t)+1 ta suy ra v_2(t)=v_2(a_k^2)=2v_2(a_k) mâu thuẫn.

Ta chỉ cần tìm tất cả t lẻ vì nếu t chẵn, ta có thể đưa về trường hợp t lẻ bằng cách chọn a_k=2^{v_2(t)/2}b_k. Ta có 2^k \mid a_k^2+t nên với k \ge 3 ta suy ra t \not\equiv 1,3,5 \pmod{8} suy ra t \equiv 7 \pmod{8}. Bây giờ ta sẽ chứng minh t=8l+7 thoả mãn với mọi l \in \mathbb{N}, l \ge 0 bằng cách xây dựng một dãy (a_k)_{k=1}^{\infty} thoả mãn 2^k \mid a_k^2+8l+7.

Chọn a_1=1 thì 2 \mid a_1^2+8l+7=8(l+1). Chọn a_2=a_3=1.
Nếu 2^k \mid a_k^2+8l+7 thì ta tìm a_{k+1} sao cho 2^{k+1} \mid a_{k+1}^2+8l+7 như sau: Nếu a_{k}^2+8l+7=2^m \cdot B \; (2 \nmid B,m \ge k) thì a_{k+1}=2^{m-1}B-a_k. Khi đó

a_{k+1}^2+8l+7=\left( 2^{m-1}B-a_k \right)^2+8l+7= \left( a_k^2+8l+7 \right)+ 2^mBa_k+2^{2(m-1)}B.

Ta có v_2(a_k^2+8l+7)=v_2(2^mBa_k)=m nên 2^{m+1} \mid \left( a_k^2+8l+7 \right)+2^mBa_k2^{m+1} \mid 2^{2(m-1)}B nên

2^{k+1} \mid 2^{m+1} \mid a_{k+1}^2+8l+7.

b) Ta xây dựng dãy tương tự như câu a. \blacksquare

Việc phát hiện ra các số t thoả mãn tốn khá là nhiều thời gian, đặc biệt là việc phát hiện ra đoạn 8y+7. Tôi đã phải thử với một số t nhất định rồi đoán già đoán non + thử xây dựng dãy dựa trên kết quả đoán mới biết được t=2^{2x}(8y+7) ;). Thực ra chính câu b đã cho ta một gợi ý là số t=7 thoả mãn, ban đầu số 7 cho tôi liên tưởng tới 2^3-1 nên tôi cứ đoán là t=2^x-1. Tuy nhiên, tôi thử với t=3=2^2-1 thì lại không thoả mãn. Cũng may là việc đoán sai t=2^x-1 đã dẫn tôi tới việc xét mod 2,4,8,16 cho t. Rồi từ đó tìm ra một đầu mối là nếu t lẻ thì t \equiv 7 \pmod{8}. Tuy nhiên, đến lúc đó, tôi vẫn chưa mường tượng được rằng mọi t \equiv 7 \pmod{8} đều thoả mãn. :no: Tôi đi thử với t=15=8+7 để xem có thoả mãn không. Nếu nhớ không nhầm thì tôi thử từ k=2 đến k=6 và dường như tôi luôn tìm được số a_k thoả mãn. Lúc này tôi mới bắt đầu có suy nghĩ rằng mọi t=8y+7 thoả mãn. Sẽ rất tốn thời gian nếu đi thử thêm một số t \equiv 7 \pmod{8} nữa nên tôi quyết định thử xây dựng một dãy a_k thoả mãn với t=8y+7. Được ăn cả ngã về không. 😀

Với k=1,2,3 tôi dễ dàng xây dựng được a_1=a_2=a_3=1 để 8 \mid a_k^2+8y+7. Tôi để ý rằng 2^k \mid a_k^2+t2^{v_2(a_k^2+t)}=2^m \mid a_{k+1}^2+t nên 2^k \parallel a_{k+1}^2-a_k^2=(a_{k+1}-a_k)(a_{k+1}+a_k). Như vậy, cứ giả sử rằng ta đã tìm được a_k thoả mãn và điều cần làm làm là tìm một a_{k+1} thoả mãn. Từ 2^m \parallel (a_{k+1}-a_k)(a_{k+1}+a_k) hoàn toàn có thể suy ra được 2^{k+1} \mid a_{k+1}^2+t. Vậy thì tôi đưa về việc tìm a_{k+1} sao cho 2^m \parallel (a_{k+1}-a_k)(a_{k+1}+a_k). Điều này không khó, chỉ việc chọn a_{k+1}+a_{k}= 2^{m-1} \cdot (2A+1) khi đó ẳn hẳn 2 \parallel a_{k+1}-a_k. Như vậy là câu a đã xử lí xong.

Câu b tương đương với 2^{k+1} \mid 2(a_k^2+t) \mid a_{k+1}^2+t hay nói cách khác nếu B \mid a_k^2+t, 2 \nmid B thì B \mid a_{k+1}^2+t hay B \mid (a_{k+1}-a_k)(a_{k+1}+a_k). Như thế chỉ cần chọn a_{k+1}+a_k=2^{m-1} \cdot B là được. Câu b như thế là xong.