VMO training 2017 – Part 5


Các bạn có thể xem phần trước ở https://nttuan.org/2017/01/06/topic-852/


Trong bài viết này tôi sẽ giới thiệu một số lời giải của bài toán sau: Cho (s_n)_{n\geq 1}(t_n)_{n\geq 1} là hai dãy các số hữu tỷ thỏa mãn đồng thời các điều kiện sau:

1) (s_n)_{n\geq 1}(t_n)_{n\geq 1} không phải là dãy hằng;

2) \forall i,j\in\mathbb{N}^*,\quad (s_i-s_j)(t_i-t_j)\in\mathbb{Z}.

Chứng minh rằng tồn tại số hữu tỷ r sao cho r(s_i-s_j)\in\mathbb{Z}\dfrac{t_i-t_j}{r}\in\mathbb{Z},\quad\forall i,j\in\mathbb{N}^*.

Đây là bài toán số 6 trong đề thi chọn HSG QG của Mĩ năm 2009 (USAMO 2009).

Lời giải 1. Ta có ba nhận xét sau:

1) Nếu \sigma:\mathbb{N}^*\to \mathbb{N}^* là một song ánh thì hai dãy (s_{\sigma(n)})_{n\geq 1}(t_{\sigma(n)})_{n\geq 1} cũng thỏa mãn các giả thiết của bài toán;

2) Nếu s,t là các số hữu tỷ thì hai dãy (s_{n}+s)_{n\geq 1}(t_{n}+t)_{n\geq 1} cũng thỏa mãn các giả thiết của bài toán.

3) Tồn tại cặp chỉ số (i,j) sao cho (s_i-s_j)(t_i-t_j)\not=0.

Thật vậy, do dãy (s_i) không phải dãy hằng nên tồn tại (i,j) sao cho s_i\not=s_j. Nếu t_i\not=t_j thì (i,j) là cặp phải tìm. Nếu t_i=t_j, ta chọn k sao cho t_k\not=t_i, khi s_k=s_i ta chọn (j,k), khi s_k\not=s_i ta chọn (k,i).

Trở lại bài toán.

Bởi các nhận xét trên ta có thể giả sử s_1=t_1=0,s_2\not=0t_2\not=0.

Ta sẽ chứng minh tồn tại các số hữu tỷ dương  A,B sao cho AB, As_jBt_j là các số nguyên với mọi j.

Với mọi i,j ta có (s_i-s_1)(t_i-t_1)=s_it_i(s_i-s_j)(t_i-t_j)=s_it_i+s_jt_j-(s_it_j+s_jt_i), suy ra s_it_is_it_j+s_jt_i là các số nguyên. Viết s_j,t_j dưới dạng tối giản ta được \displaystyle s_j=\frac{p_j}{q_j},t_j=\frac{u_j}{v_j},\quad\forall j. Theo trên ta có s_2t_j+s_jt_2 là số nguyên với mọi j, suy ra với mọi j ta có q_j|u_2q_2. Chọn A=|q_2u_2|>0 ta có As_j là số nguyên với mọi j. Tương tự ta cũng tìm được số nguyên dương B sao cho Bt_j là số nguyên với mọi j.

Chọn cặp (A,B) như trên sao cho AB nhỏ nhất, ta thấy AB phải bằng 1 và khi đó bài toán sẽ được giải. Thật vậy, nếu AB>1 thì nó có ước nguyên tố p, suy ra ABs_jt_j=(As_j)(Bt_j) chia hết cho p với mọi j, do đó với mọi j thì As_j hoặc Bt_j sẽ chia hết cho p. Xét các trường hợp:

Trường hợp 1: p chia hết As_j với mọi j.

Ta thấy cặp (A/p,B) cũng thỏa mãn và có tích bằng \dfrac{AB}{p}<AB, vô lí.

Trường hợp 2: Tồn tại j để p không chia hết As_j.

Khi đó ta có Bt_j chia hết cho pBt_i không chia hết cho p với i nào đấy (do cách chọn (A,B)), suy ra AB(s_it_j+s_jt_i)-(As_i)(Bt_j)=(As_j)(Bt_i) không chia hết cho p, vô lí.

Lời giải 2. Đây là lời giải của Paul Christiano, huy chương Bạc tại IMO 2008.

Ta cho các số hữu tỷ trong lời giải này đều ở dạng tối giản.

Không mất tính tổng quát ta có thể giả sử s_1=t_1= 0, t_2\not=0s_2 = 1. Khi đó t_2=k là số nguyên (vì (s_2 - s_1)(t_2 - t_1) là số nguyên), và

(s_i - 1)(t_i - k) = s_it_i + k - (t_i + ks_i) \in \mathbb{Z},\quad i\in\mathbb{N}^*.s_it_i = (s_i - 0)(t_i - 0) = (s_i - s_1)(t_i - t_1)\in\mathbb{Z},\quad\forall i\in\mathbb{N}^*, suy ra t_i + ks_i \in \mathbb{Z},\quad \forall i\in\mathbb{N}^*. Ta thấy ks_i phải là số nguyên với mọi số nguyên dương i, thật vậy nếu tồn tại số nguyên dương i sao cho ks_i \not\in \mathbb{Z} thì mẫu của s_i có ước nguyên tố p không chia hết k, suy ra t_i+ks_i không phải là số nguyên vì mẫu của t_i cũng không chia hết cho p (do s_it_i là số nguyên), vô lí. Từ đó ta có t_i \in \mathbb{Z} với mỗi số nguyên dương i.

Nếu cần thì chia các số hạng của dãy (t_i) cho cùng một số nguyên dương và nhân các số hạng của dãy (s_i) với số nguyên dương đó, ta có thể coi ước chung lớn nhất của tất cả các số hạng của dãy (t_i) bằng 1, và tất nhiên, vẫn có số nguyên k\not=0 thỏa mãn ks_i\in\mathbb{Z} với mọi số nguyên dương i.

Ta sẽ chứng minh rằng s_i\in\mathbb{Z} với mọi số nguyên dương i, và khi đó bài toán sẽ được giải hoàn toàn. Thật vậy, giả sử tồn tại số nguyên dương i sao cho s_i không phải là số nguyên. Khi đó có số nguyên tố p là ước của mẫu của s_i. Gọi j là số nguyên dương thỏa mãn p không chia hết t_j (tồn tại j như thế vì ước chung lớn nhất của các t_n bằng 1). Vì s_it_i là số nguyên nên p chia hết t_i, do đó t_i - t_j không chia hết cho p. Vì s_jt_j là số nguyên và p không chia hết t_j nên p không chia hết mẫu của s_j, do đó s_i - s_j có mẫu không chia hết cho p. Nhưng khi đó (s_i - s_j)(t_i-t_j) có mẫu chia hết cho p, và bởi thế nó không phải là số nguyên, vô lí.

Lời giải 3. Đây là lời giải của jmerry trên AoPS.

Để thuận tiện ta coi hai dãy bắt đầu từ chỉ số 0 thay cho 1. Không mất tính tổng quát ta giả sử s_0=t_0=0.

Cho j=0 trong giả thiết ta có s_it_i là số nguyên với mọi i, cho i\neq j, ta có s_it_i+s_jt_j-(s_it_j+s_jt_i) là một số nguyên, do đó s_it_j+s_jt_i là số nguyên. Bởi vậy, với mọi số tự nhiên n,k ta có \displaystyle\sum_{\substack{i,j\le n\\ i+j=k}}s_it_j là một số nguyên.

Suy ra đa thức \Gamma_n(x)=(s_1x+s_2x^2+\cdots+s_nx^n)(t_1x+t_2x_2+\cdots+t_nx^n) là đa thức với hệ số nguyên. Chọn n đủ lớn sao cho hai đa thức thừa số khác đa thức 0 (chọn được vì hai dãy (s_i), (t_i) không phải dãy hằng), và gọi d_n là ước chung lớn nhất của các hệ số của đa thức \Gamma_n(x). Theo bổ đề Gauss, ta có thể viết tích này thành

\left(r_ns_1x+r_ns_2x^2+\cdots+r_ns_nx^n\right)\left(\frac{t_1}{d_nr_n}x+\frac{t_2}{d_nr_n}x^2+\cdots+\frac{t_n}{d_nr_n}x^n\right)d_n, ở đây r_i>0 với mọi i và các thừa số mới là các đa thức nguyên bản.

Với hai số nguyên dương m>n đủ lớn ta có \dfrac{r_m}{r_n} là số nguyên. Thật vậy, các số r_ms_1, \cdots, r_ms_m là các số nguyên nên các số r_ms_1, \cdots, r_ms_n cũng là các số nguyên, nếu \dfrac{r_m}{r_n} không là số nguyên thì tồn tại số nguyên tố p chia hết cho mẫu nhưng không chia hết cho tử của nó, suy ra các số r_ns_1, \cdots, r_ns_n đều chia hết cho p, vô lí. Chứng minh tương tự ta có \dfrac{d_nr_n}{d_mr_m} là một số nguyên, suy ra d_n\geq d_m.

(d_i) là dãy gồm toàn số nguyên dương, suy ra tồn tại N để d_n=d_Nr_n=r_N với mọi n\ge N. Chọn r=r_N ta thấy số này thỏa mãn các điều kiện của bài toán.

Lời giải 4. Đây là lời giải của Hamster1800 và The QuattoMaster 6000 trên AoPS.

Với số nguyên tố p, ta ký hiệu v_p(x) là giá p-adic của số hữu tỷ x. Nghĩa là nếu x = 0 thì v_p(x) = +\infty, nếu x = \dfrac{a}{b}\not=0, p^k\parallel{}ap^l\parallel{}b thì v_p(x) = k-l. Sau đây là một vài tính chất của giá p-adic.

1) v_p(x+y) \geq \text{min}(v_p(x),v_p(y)),\quad\forall x,y\in\mathbb{Q};

2) Nếu x,y\in\mathbb{Q} thỏa mãn v_p(x) \neq v_p(y) thì v_p(x+y) =\min(v_p(x),v_p(y));

3) v_p(x) = v_p(-x),\quad\forall x\in\mathbb{Q};

4) v_p(xy)=v_p(x)+v_p(y),\quad\forall x,y\in\mathbb{Q}.

Như vậy ta có v_p(s_i-s_j) + v_p(t_i-t_j) \geq 0,\quad\forall i,j và phải tìm r \in \mathbb{Q} sao cho v_p(r) \geq -v_p(s_i-s_j)v_p(r) \leq v_p(t_i-t_j), với mọi số nguyên tố p và mọi chỉ số i,j.

Cố định một số nguyên tố p.

Xét hai số khác nhau t_xt_y. Lấy số nguyên d thỏa mãn v_p (t_x-t_y) < d, khi đó với mọi i thì v_p (t_i-t_x) < d hoặc v_p (t_i-t_y) < d. Suy ra với mọi i ta có v_p (s_i -s_x) >-d hoặc v_p (s_i-s_y) >-d, do đó dãy (v_p (s_i)) bị chặn dưới, và bởi thế, tập \{v_p (s_i-s_j)\} bị chặn dưới. Nhưng tập này gồm các số nguyên nên nó có phần tử nhỏ nhất, ta ký hiệu nó bởi \delta_p. Chứng minh tương tự ta cũng thấy tồn tại \delta'_p=\min \{v_p (t_i-t_j)\}.

Ta sẽ chứng minh rằng tồn tại cặp chỉ số (i,j) sao cho \delta_p=v_p(s_i-s_j)\delta'_p=v_p(t_i-t_j). Khi đó ta có \delta_p + \delta_p' \geq 0, suy ra -\delta_p \leq \delta_p' và ta có thể tìm v_p(r) để với mọi i,j, -v_p(s_i-s_j) \leq -\delta_p \leq v_p(r) \leq \delta_p' \leq v_p(t_i-t_j).

Giả sử ngược lại, lấy các chỉ số i,j,k,l thỏa mãn v_p(s_i-s_j) = \delta_pv_p(t_k-t_l) = \delta_p'. Xét các trường hợp sau:

Trường hợp 1: v_p(s_i-s_k) > \delta_pv_p(s_l-s_j) > \delta_p.

Ta có v_p(s_k-s_l) = v_p((s_k-s_i) + (s_j-s_l) + (s_i-s_j)) = v_p(s_i-s_j) = \delta_p, vô lí.

Trường hợp 2: v_p(s_i-s_k) > \delta_pv_p(s_l-s_j) = \delta_p.

Ta có v_p(t_l-t_j) > \delta_p', suy ra v_p(s_k - s_j) = v_p((s_i-s_j) + (s_k-s_i)) = v_p(s_i-s_j) = \delta_pv_p(t_k-t_j) = v_p((t_k-t_l) + (t_l-t_j)) = v_p(t_k-t_l) = \delta_p', vô lí.

Trường hợp 3: v_p(s_i - s_k) = \delta_pv_p(s_l-s_j) > \delta_p.

Ta có v_p(t_i-t_k) > \delta_p', suy ra v_p(s_i-s_l) = v_p((s_i-s_j) + (s_j-s_l)) = v_p(s_i-s_j) = \delta_pv_p(t_i-t_l) = v_p((t_k-t_l) + (t_i-t_k)) = v_p(t_k-t_l) = \delta_p', vô lí.

Trường hợp 4: v_p(s_i - s_k) = \delta_pv_p(s_l-s_j) = \delta_p.

Ta có v_p(t_i-t_k) > \delta_p'v_p(t_l-t_j) > \delta_p', suy ra v_p(t_i-t_j) = v_p((t_k-t_l) + (t_i-t_k) + (t_l-t_j)) = \delta_p', vô lí.

Vậy ta có thể chọn được số “hữu tỷ hình thức” r=\prod p^{v_p(r)} thỏa mãn các điều kiện của bài toán.

Bài toán sẽ được giải nếu ta chỉ ra có thể chọn v_p(r) sao cho nó khác 0 chỉ với hữu hạn số nguyên tố p.

Xét hai cặp chỉ số (i,j),(k,l) sao cho s_i\not=s_jt_k\not=t_l. Ta thấy tồn tại tập hữu hạn Z gồm các số nguyên tố sao cho với các số nguyên tố p ở ngoài Z, v_p(s_i-s_j)=v_p(t_k-t_l)=0, suy ra \delta_p\leq 0,\delta_p'\leq 0, do đó \delta_p=\delta_p'=0, và với các p này ta chọn v_p(r)=0 là xong.

Lời giải 5. Đây là lời giải chính thức của ban tổ chức USAMO 2009.

Như các lời giải trước, ta giả sử s_1=t_1=0, s_2=1.

Ta có (s_n-s_1)(t_n-t_1)=s_nt_n là số nguyên với mọi ns_at_a+s_bt_b-(s_a-s_b)(t_a-t_b)=s_at_b+s_bt_a là số nguyên với mọi a,b. Mà (s_at_b)(s_bt_a) cũng là số nguyên, suy ra s_at_b là số nguyên với mọi a,b. Nói riêng, với a=2, ta có t_n là số nguyên với mọi n. Gọi g là ước chung lớn nhất của tất cả t_n. Theo bổ đề Bezout, g là một tổ hợp tuyến tính nguyên của hữu hạn phần tử của tập \{t\}. Khi đó cố định a trong s_at_b và chọn tổ hợp tuyến tính nguyên thích hợp ta có s_ag là số nguyên với mọi a. Do đó \{s\}g\{t\}/g là nguyên.

Lời giải 6. Đây là lời giải của Evan Chen.

Giả sử s_1 = t_1 = 0s_2=1. Ta có với mỗi i, j thì s_it_i \in \mathbb Zs_it_j + s_jt_i \in \mathbb Z. Nói riêng, t_2 là số nguyên, kí hiệu t.

Chú ý rằng nếu s_3 = \dfrac{a}{b} \neq 0 với (a,b) = 1t_3 = \dfrac{b}{a} \cdot r với r \in \mathbb Z thì t \cdot \dfrac{a}{b}  + r \cdot \dfrac{b}{a}\in\mathbb{Z}, suy ra b \mid t. Do đó tất cả các mẫu của các số hạng của \{s_n\} chia hết t. Nhân dãy \{s_n\} với bội chung nhỏ nhất của các mẫu ta có thể xem s_n \in \mathbb Z với mọi n, và \{s_n\} không có ước chung lớn hơn 1.

Ta chứng minh tất cả các số hạng của dãy \{t_n\} phải là số nguyên, và khi đó bài toán sẽ được giải. Giả sử tồn tại k sao cho t_k = \dfrac{a}{b} \neq 0 với (a,b) = 1p \mid b với số nguyên tố p. Khi đó p \mid s_k, mà ta có thể chọn một s_\ell không chia hết cho p, suy ra t_\ell không có nhân tử p ở mẫu. Ta có s_\ell t_k + s_k t_\ell là một số nguyên, để ý đến giá p-adic ta thấy vô lí.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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