Vietnam TST 2023/6

Trong bài này tôi giới thiệu một lời giải của bài 6 trong đề thi chọn đội tuyển IMO 2023. Đây là lời giải của tác giả bài toán, không phải lời giải của tôi. Nếu có chỗ sai trong lời giải dưới đây thì đó là lỗi của tôi.

Với mỗi số nguyên dương $m$ , ký hiệu $[m]$ là tập gồm $m$ số nguyên dương đầu tiên.

Bài toán (Vietnam TST 2023/6). Cho số nguyên $n>2$ . Xác định số $k_n$ lớn nhất sao cho với mỗi họ $k_n$ tập con có $3$ phần tử của $[n]$ , luôn tô màu được các phần tử của $[n]$ bởi hai màu để không có tập con nào trong họ có ba phần tử cùng màu.

Lời giải. Với $n=3$ và $n=4$ thì $k_n=C_n^3$ , bởi vì ta có thể tô $2$ phần tử của $[n]$ xanh và $n-2 \leq 2$ phần tử còn lại màu đỏ và không có tập con ba phần tử cùng màu nào cả.

Với $n \geq 5$ thì $k_n \leq 9$ , bởi vì với $10$ tập con có $3$ phần tử của $[5]$ thì với mọi cách tô màu các phần tử $[5]$ bởi $2$ màu luôn có $3$ phần tử cùng màu. Với $n=5$ thì $k_5=9$ , vì với $9$ tập con $3$ phần tử tùy ý luôn có $1$ tập con $3$ phần tử không được chọn, ta có thể tô màu $3$ phần tử này màu xanh và $2$ phần tử còn lại màu đỏ, cách tô màu này thỏa mãn bài toán. Với $n=6$ , ta cũng có $k_6=9$ , vì ta có thể chia $20$ tập con $3$ phần tử của $[6]$ thành $10$ cặp, mỗi cặp là $2$ tập con bù nhau. Với $9$ tập con $3$ phần tử tùy ý của $[6]$ , luôn có $1$ cặp $(A, B)$ mà $A,$ $B$ không được chọn, ta tô $3$ phần tử của $A$ xanh, $3$ phần tử của $B$ đỏ và cách tô màu này thỏa mãn bài toán.

Mệnh đề 1. Với $n\geq 7$ thì $k_n \leq 6$ .

Chứng minh. Tồn tại $7$ tập con có $3$ phần tử của $[7]$ đôi một chung nhau không quá $1$ phần tử. Thật vậy, biểu diễn $1$ , $2, \ldots$ , $7$ là $7$ đỉnh một $7-$ giác đều. Chọn $B_1=\{1,2,4\}$ và $B_i$ là ảnh của $B_1$ quanh tâm đa giác với góc $\frac{2 \pi}{7} \times(i-1)$ . Rõ ràng các $B_i$ (như một tam giác) đôi một không có cạnh chung.

Giả sử tô màu được các phần tử của $[7]$ bởi $2$ màu sao cho không có $B_i$ nào có các phần tử cùng màu. Khi đó mỗi $B_i$ có đúng $2$ cạnh mà $2$ đỉnh của chúng khác màu. Suy ra ta có một đồ thị lưỡng phân $G[X,Y]$ , với $X$ là tập các phần tử xanh và $Y$ là tập các phần tử đỏ, có $14$ cạnh. Điều này không thể xảy ra vì $\mid X\mid +\mid Y\mid =7$ . $\Box$

Mệnh đề 2. Với $n \geq 5$ thì $k_n \geq 6$ .

Chứng minh. Ta chứng minh bằng qui nạp theo $n$ . Theo phần trình bày ở trên thì mệnh đề đúng với $n=5$ và $n=6$ . Với $n \geq 7$ , ta xét một họ gồm $6$ tập con có $3$ phần tử của $[n]$ . Tồn tại hai phần tử $a$ và $b$ của $[n]$ sao cho chúng không cùng thuộc một tập của họ này, vì $C_7^2=21>6 \times C_3^2=18$ . Bỏ $a$ , $b$ và thêm $c$ vào $[n]$ , ta có một cách tô màu thỏa mãn bài toán theo giả thiết quy nạp. Bỏ $c$ và cho lại $a, b$ về tập $[n]$ , sau đó tô màu $a$ và $b$ bởi màu của $c$ , ta có cách tô màu thỏa mãn bài toán. $\Box$

Từ mệnh đề 1 và mệnh đề 2, ta có $k_n=6$ khi $n \geq 7$ . $\Box$

Hanoi mathematical olympiad

Trong bài này tôi sẽ giới thiệu một số đề thi chọn HSG lớp 12 của Hà Nội. Mỗi năm có khoảng 500 học sinh tham gia kỳ thi này, khoảng 100 học sinh có điểm cao nhất sẽ tham gia kỳ thi chọn đội tuyển của Hà Nội dự thi chọn HSG QG (VMO).

Đề thi chọn đội tuyển Hà Nội các bạn có thể xem ở https://nttuan.org/2023/06/23/hanoitst/ .

HSG 12 Ha Noi – Nam hoc 2013 2014 Download

HSG 12 Ha Noi – Nam hoc 2014 2015 Download

HSG 12 Ha Noi – Nam hoc 2015 2016 Download

HSG 12 Ha Noi – Nam hoc 2016 2017 Download

Continue reading →

Hanoi team selection test

Trong bài này tôi sẽ giới thiệu các đề thi chọn đội tuyển của Hà Nội dự thi chọn HSG QG (VMO).

(1) Đề thi năm học 2015 – 2016

HaNoiTST20152016 Download

(2) Đề thi năm học 2016 – 2017

HaNoiTST20162017 Download

(3) Đề thi năm học 2017 – 2018

HaNoiTST20172018 Download

(4) Đề thi năm học 2018 – 2019

Continue reading →

Lucas sequences and Vietnam TST 2023/4b

Cho $P$ và $Q$ là hai số nguyên lẻ nguyên tố cùng nhau thỏa mãn $D=P^2-4Q>0.$ Dãy Lucas $(U_n)$ và dãy Lucas đồng hành $(V_n)$ với tham số $P$ và $Q$ được xác định như sau: $U_0=0,U_1=1,U_n=PU_{n-1}-QU_{n-2},\quad\forall n\geq 2,$ và $V_0=2,V_1=P,V_n=PV_{n-1}-QV_{n-2},\quad\forall n\geq 2.$ Khi $P=1$ và $Q=-1$ ta có $(U_n)$ là dãy số Fibonacci. Vào quãng năm 1996, Paulo Ribenboim và Wayne L. McDaniel đã chứng minh được kết quả:

Định lí. Nếu $n$ là số tự nhiên sao cho một trong bốn số $U_n,2U_n,V_n$ và $2V_n$ là số chính phương thì $n<13.$

Phương pháp của họ như sau. Chẳng hạn giả sử $U_n$ là số một chính phương, khi đó với mỗi số nguyên dương lẻ $M$ nguyên tố cùng nhau với $U_n$ ta có ký hiệu Jacobi $(U_n\mid M)=1.$ Với hầu hết $n,$ họ chọn được các modulo $M_i$ sao cho $\prod (U_n\mid M_i)=-1,$ suy ra $U_n$ không phải là số chính phương, vô lý! Bạn đọc quan tâm có thể đọc trong bài:

$\text{[P-W]}$ Paulo Ribenboim and Wayne L. McDaniel, The Square Terms in Lucas Sequences. Journal of number theory 58, 104 -123 (1996).

Mục đích chính của tôi khi viết bài này chỉ là giới thiệu $\text{[P-W]}$ đến các đồng nghiệp và các học sinh. Trong đó có nhiều kết quả sơ cấp về dãy Lucas và dãy Lucas đồng hành, những dãy số mà chúng ta biết ít hơn so với dãy số Fibonacci. Tiếp theo tôi giới thiệu một lời giải cho bài toán sau, nó là ý b trong bài 4 của đề thi chọn đội tuyển IMO 2023.

Bài toán (TST2023/4b). Cho hai số nguyên dương lẻ $a>2$ và $b$ nguyên tố cùng nhau. Xét dãy số $(x_n)_{n\geq 0}$ xác định bởi $x_0=2,x_1=a,x_{n+2}=ax_{n+1}+bx_n,\quad\forall n\geq 0.$ Chứng minh rằng không tồn tại bộ ba số nguyên dương $(m,n,p)$ sao cho $mnp$ chẵn và $\displaystyle \frac{x_m}{x_nx_p}$ là số chính phương.

Lời giải. Với giả thiết của bài toán ta thấy $(x_n)$ là dãy Lucas đồng hành với tham số $P=a$ và $Q=-b,$ bởi vậy chúng ta có thể dùng các kết quả trong $\text{[P-W]}$ . Giả sử $(m,n,p)$ là một bộ ba số nguyên dương sao cho $mnp$ chẵn và $\displaystyle \frac{x_m}{x_nx_p}$ là số chính phương. Khi đó $x_n\mid x_m$ và $x_p\mid x_m,$ suy ra theo (9) trong $\text{[P-W]}$ (trang 107) ta có $m/n$ và $m/p$ là các số nguyên dương lẻ. Do đó cấp $2-$ adic của $m,n$ và $p$ bằng nhau, để ý thêm $mnp$ chẵn ta có $m,n$ và $p$ đều chẵn. Bây giờ theo bổ đề 1 trong $\text{[P-W]}$ ta có $(2\mid D)=1,$ điều này không thể xảy ra vì $(2\mid D)=(-1)^{\frac{D^2-1}{8}}=-1.$

Bài toán được giải.

—

Vậy tôi giải được bài toán này nhờ tôi biết nhiều, chứ không cần điều gì đặc biệt. Có đúng không các bạn học sinh? 🙂

—

18/04/2023: Anh Nguyễn Xuân Thọ (Đại học Bách Khoa) cho tôi biết là kết quả TST2023/4b này đã có trong Colloquium Mathematicum, Vol. 130, No. 1, 2013.

Một điểm không phù hợp nữa của bài toán này là đoạn đặc trưng các cặp $(m,n)$ sao cho $x_m\mid x_n$ đã có trong đề thi chọn HSG QG năm 2018, cụ thể là Bài 6.