# 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

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}. 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 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 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} then all prime divisors of $a_{m+2} 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 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 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 so we add all up and get a contradiction.
This means there will exists $1 \le m 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$.

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 $OFB$$OHB$$P,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 $A$$E$. Khi đó $F$ nằm giữa $A$$B$. Gọi $A_1,B_1,C_1$ thứ tự là trung điểm $BC,CA,AB$.

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 HN$$F,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ểm$T$ 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_1FHO$$C_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.

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 A$$2 \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 A$$b_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 B$$b_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 B$$1 \in A$$1+(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}. Khi đó luôn tồn tại một số $T \le 3n$ sao cho $T \not\in B$$T-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_k$$2^{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+t$$2^{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.