Thuật toán tham lam (Greedy Algorithms)

Thuật toán tham lam là thuật toán để giải quyết một bài toán trong đó ta chọn phương án tối ưu cho các bước địa phương, từ đó đạt được tối ưu toàn cục. Đó chưa hẳn luôn là phương án tối ưu cho bài toán nhưng thường sẽ được đạt được cực trị.

Ý tượng là trong mỗi bước, ta xét các phần tử (thuộc dạng tốt nhất, xấu nhất, lớn nhất hay nhỏ nhất) để đạt được các mục tiêu cần giải quyết.

Ví dụ ta có một xấp tiền gồm các tờ 1k, 2k, 5k, 10k, làm sao ta có thể đổi một số tiền 57k thành các tờ tiền này sao cho số tờ tiền là ít nhất.

Rõ ràng ta cứ chọn các tiền lớn nhất có thể, thuật toán là

Chọn lớn nhất $x \in 1, 2, 5, 10$ thỏa $x \leq M$ .
Tiếp tục thuật toán cho $M - x$ .

Khi đó ta có

$x_{1} = 10$ , $M_{1} = 47$ , sau lần 1.
$x_{2} = 10, M_{2} = 37$
$x_{3} = 10, M_{3} = 27$
$x_{4} = 10, M_{4} = 17$
$x_{5} = 10, M_{5} = 7$
$x_{6} = 5, M_{6} = 2$
$x_{7} = 2, M_{7} = 0$

Vậy tập cần tìm là ${10, 10, 10, 10, 10, 5, 2}$

Trên đây là một ví dụ đơn giản về thuật toán tham lam, tiếp theo ta xét một số ví dụ khác để các bạn có thể hiểu rõ hơn về thuật toán này.

Ví dụ 1. Chứng minh rằng mọi số nguyên dương $n$ thì đều có thể biểu dưới dạng một lũy thừa của 2 hoặc một tổng các lũy thừa của 2, và sự biểu diễn là duy nhất.

Lời giải

Nếu $n$ là lũy thừa của 2 thì coi như xong. Nếu $n$ không là lũy thừa của $2$ ta chọn một lũy thừa của 2 nhỏ hơn $n$ và gần $n$ nhất, giả sử là $2^{a_{k}}$ . Ta có $2^{a_{k}} < n < 2^{a_{k} + 1}$ .
Tiếp theo áp dụng thuật toán cho số $n - 2^{k}$ , rõ ràng thuật toán dừng vì ta có dãy giảm và bị chặn bởi 0.
Khi đó ta có $n = 2^{a_{1}} + \dots + 2^{a_{k}}$ .
Ta chứng minh sự biểu diễn này là duy nhất. Giả sử tồn tại hai cách biểu diễn $2^{a_{k}} + \dots + 2^{a_{1}} = 2^{b_{m}} + \dots 2^{b_{1}}$ . Nếu $a_{k} > b_{m} \Rightarrow a_{k} \geq b_{m} + 1$ . Khi đó $a^{k} > a^{b_{m} + 1} - 1 =\geq 2^{b_{m}} + 2^{b_{m} - 1} + \dots 2^{1} + 1$
Do đó $V T > V P$ (vô lí)
Nếu $a_{k} = b_{m}$ , chứng minh tương tự cũng có 2 dãy $a_{1}, \cdot a_{k}$ và $b_{1}, \dots b_{m}$ là trùng nhau. Nên sự biểu diễn là duy nhất.

Ví dụ 2. Cho một đồ thị đơn, trong đó $d$ là bậc cao nhất. Chứng minh rằng có thể tô màu các đỉnh của đồ thị bằng $d + 1$ màu sao cho hai đỉnh kề thì khác màu.

Lời giải

Giả sử các màu được đánh số từ 1 đến $d + 1$ . Ta thực hiện cách tô màu như sau
Chọn 1 đỉnh ta tô màu nhỏ nhất mà không xuất hiện trong các đỉnh lân cận với đỉnh đó. Việc tô màu này luôn thực hiện được vì bậc của mỗi đỉnh không hơn hơn $d$ .

Ví dụ 3. Cho các tập $A_{1}, A_{2}, \dots, A_{2022}$ là các tập con có 3 phần tử của $X = {1, 2, \dots 2022}$ . Chứng minh rằng ta có thể tô màu $674$ phần tử của $X$ sao cho với mọi tập $A_{i}$ có một phần tử không được tô màu.

Lời giải

Ta có thể làm ngược lại, tô màu các số sao cho với mỗi tập $A_{i}$ có ít nhất một số được tô màu, ta chứng minh là số phần tử cần tô không vượt quá $1348$ số.
Ta thực hiện cách tô sau: Chọn phần tử xuất hiện nhiều nhất trong các tập, tô màu phần tử đó. Lặp lại thuật toán đến khi không có tập hợp nào không có phần tử được tô màu
Ta chứng minh số phần tử được tô màu không vượt quá 1348 phần tử
Giả sử ta tô được $k$ phần tử, và các tập còn lại đều phân biệt rời nhau, có $m$ tập hợp. Rõ ràng vì mỗi bước thực hiện đều giảm được ít nhất 2 tập nên $k \leq \frac{2022}{2} = 1011$ . (Vì cách chọn số phần từ xuất hiện trong nhiều tập nhất nên ít nhất là 2). Và các tập còn lại phân biệt rời nhau, mỗi tập có 3 phần tử nên $m \leq 1011 / 3 = 337$ .\
Khi đó ta tô màu mỗi phần tử trong $m$ tập còn lại thì sẽ thỏa đề bài, do đó số phần tử cần tô màu là $k + m \leq 1011 + 337 = 1348$ .
Do đó ta có cách tô màu thỏa đề bài.

Ví dụ 4. Cho một bảng $2 \times n$ , người ta điền vào bảng các số dương sao cho tổng hai số trong cùng một cột bằng 1. Chứng minh rằng ta có thể chọn mỗi cột một số sao cho các số trên mỗi dòng không lớn hơn $\frac{n + 1}{4}$ .

Lời giải

Ta sắp xếp từ trái sang phải theo thứ tự tăng dần các số ở hàng thứ nhất $a_{1} \leq a_{2} \leq \cdot \leq a_{n}$ , hàng dưới tương ứng là $1 - a_{1}, 1 - a_{2}, \dots, 1 - a_{n}$ .

Ta chọn các số ở hàng trên từ trái qua, nhiều nhất sao cho tổng $S$ không lớn hơn $\frac{n + 1}{4}$ . Ta chứng minh tổng các số ở hàng dưới trong các cột còn lại không lớn hơn $\frac{n + 1}{4} - S$ .

Giả sử chỉ số $i$ lớn nhất thỏa $a_{1} + a_{2} + \dots + a_{i} \leq \frac{n + 1}{4} .$ Ta cần chứng minh
$\frac{n + 1}{4} \geq (1 - a_{i + 1}) + (1 - a_{i + 2}) + \dots + (1 - a_{n}) = (n - i) - (a_{i + 1} + a_{i + 2} + \dots + a_{n})$

$a_{i + 1} + a_{i + 2} + \dots + a_{n} \geq \frac{3 n - 1}{4} - i$
Từ $a_{1} \leq a_{2} \leq \dots \leq a_{i + 1}$ , ta có
$\frac{a_{1} + a_{2} + \dots + a_{i + 1}}{i + 1} \leq a_{i + 1}$

và từ $a_{i + 1} \leq a_{i + 2} \leq \dots \leq a_{n}$ , ta có
$\frac{a_{i + 1} + a_{i + 2} + \dots + a_{n}}{n - i} \geq a_{i + 1}$
Từ đó ta có
$\frac{a_{i + 1} + a_{i + 2} + \dots + a_{n}}{n - i} \geq \frac{a_{1} + a_{2} + \dots + a_{i + 1}}{i + 1}$

$a_{i + 1} + a_{i + 2} + \dots + a_{n} \geq (n - i) \cdot \frac{a_{1} + a_{2} + \dots + a_{i + 1}}{i + 1} > (n - i) \cdot \frac{\frac{n + 1}{4}}{i + 1}$
do cách chọn $i$ lớn nhất.

Ta cần chứng minh $\frac{n - i}{i + 1} \frac{n + 1}{4} \geq \frac{3 n - 1}{4} - i .$

hay $(n - 1)^{2} \geq 4 i (n - i - 1)$ , áp dụng AM-GM $2 \sqrt{i (n - i - 1)} \leq i + (n - i - 1) = n - 1$ , ta có điều cần chứng minh.

Ví dụ 5. (IMOSL 2001) Một tập có 3 số nguyên phân biệt không âm ${x, y, z}$ thỏa $x < y < z$ được gọi là tập có tính chất P nên ${z - y, y - z} = {a, b}$ với $0 < a < b$ nguyên dương cho trước. Chứng minh rằng tập các số nguyên không âm được viết thành hợp các có tính chất P đôi một phân biệt.

Lời giải

Ta thấy có 2 trường hợp là $z = y = b, y - x = a$ hoặc $z - y = a, y - x = b$ hay tập có tính chất $P$ sẽ có một trong hai dạng {x, x+a, x+a+b} hoặc {x, x+b, x+a+b} với $x$ nguyên dương.

Với mỗi tập có tính chất $P$ là {x, y, z} ta tô màu $x$ đỏ, $y$ xanh $z$ vàng.

Ta tô màu các số nguyên dương như sau:

Xét số dương $k$ nhỏ nhất chưa được tô màu.
Nếu $k + a$ chưa được tô màu thì ta tô màu cho tập {k, k+a, k+a+b}.
Nếu $k + b$ chưa được tô màu thì ta tô màu cho tập {k, k+b,k+a+b}.

Ta chứng minh với cách tô màu như trên thì các tập đều phân biệt và số nào cũng được tô màu. Giả sử ta đã thực hiện tới bước thứ $n$ với phần tử $x_{n}$ là nhỏ nhất được tô màu. Ta tiếp tục thực hiện với kế tiếp với phần tử $x_{n + 1}$ chưa được tô màu. Ta cần chứng minh các phần tử $x_{n + 1} + a$ hoặc $x_{n + 1} + b$ chưa được tô màu và $x_{n + 1} + a + b$ chưa được tô màu trước đó.

Thật vậy rõ ràng là $x_{n + 1} + a + b$ chưa được tô màu vì nó lớn hơn tất cả các số được tô màu. (Ở bước thứ $n$ thì $x_{n}$ được tô màu, nên $x_{n} + a + b$ là số lớn nhất được tô màu.
Nếu $x_{n + 1} + b$ được tô màu thì không thể là màu đỏ, nếu xanh thì $x_{n + 1} + b - a$ được tô màu đỏ, vô lí. Nếu màu vàng thì $x_{n + 1} + b - a - b = x_{n + 1} - a$ được tô màu đỏ, khi đó $x_{n + 1}$ được tô màu, vô lí.

Một số bài tập rèn luyện

Bài 1. (Đức 2000) Có một số đá tổng cộng là 9 tấn cần được vận chuyển bằng xe tải. Mỗi tảng đá không nặng quá 1 tấn, mỗi xe tải chở không quá 3 tấn. Hỏi còn ít nhất bao nhiêu xe tải để chở hết số đá này cùng lúc.

Bài 2. Chứng minh rằng với mọi số nguyên dương $n$ tồn tại các số nguyên dương $a_{1}, a_{2}, \dots,$ sao cho $a_{i} \leq i$ thỏa

$n = a_{1} \cdot 1! + a_{2} \cdot 2! + \dots + a_{k} \cdot k!$

và sự biểu diễn này là duy nhất.

Bài 3. Gọi S là tập hợp n điểm trong mặt phẳng tọa độ. Nói rằng một cặp điểm thẳng hàng nếu hai điểm đó có cùng tọa độ x hoặc y. Chứng minh rằng S có thể được phân chia thành các tập con rời rạc sao cho

(a) mỗi tập con này là một tập hợp các điểm thẳng hàng,
và (b) tối đa $n^{3 / 2}$ cặp điểm phân biệt không có thứ tự trong S thẳng hàng nhưng không nằm trong cùng một tập con.

Bài 4. (IMOSL 2013). Cho $n$ là một số nguyên dương. Tìm số nguyên $k$ nhỏ nhất thỏa mãn tính chất: Cho bất kỳ số thực $a_{1}, \cdot \cdot \cdot, a_{d}$ sao cho $a_{1} + a_{2} + \cdot \cdot \cdot + a_{d} = n$ và $0 \leq a_{i} \leq 1$
với $i = 1, 2, \cdot \cdot \cdot, d$ , có thể phân chia các số này thành $k$ nhóm (một số có thể trống)
sao cho tổng các số trong mỗi nhóm nhiều nhất là $1$ .

Bài 5. (IMO 2014). Với mỗi số nguyên dương n, Ngân hàng Cape Town phát hành tiền xu có mệnh giá $\frac{1}{n}$ . Đưa ra một bộ sưu tập hữu hạn các đồng tiền như vậy (không nhất thiết phải có mệnh giá khác nhau) với tổng số giá trị nhiều nhất là $99 + \frac{1}{2}$ . Chứng minh rằng có thể chia bộ sưu tập này thành 100 nhóm hoặc ít hơn, chẳng hạn như mà mỗi nhóm có tổng giá trị nhiều nhất là 1.

Trắc nghiệm phép đếm

Leave a reply

[WpProQuiz 20]

Đáp án thi chọn Đội Tuyển Trường PTNK năm học 2013-2014

Leave a reply

Đề thi và đáp án kì thi chọn đội tuyển Toán trường Phổ thông Năng khiếu – ĐHQG TPHCM được tổ chức vào tháng 10 năm 2013, chọn ra 6 học sinh dự thi kì thi HSG Quốc gia năm 2014. Các thí sinh từ các lớp 11, 12 (chủ yếu là học sinh chuyên toán), thực hiện bài thi trong 2 ngày, mỗi ngày 4 bài, mỗi bài 180 phút. Sau đây là đề thi và đáp án thực hiện bởi Star Education.

Ngày thi thứ 1

Bài 1. Tìm tất cả các hàm số $f : R \to R$ thoả mãn

$f (x^{3} + y + f (y)) = 2 y + x^{2} f (x), \forall x, y \in R$

Bài 2. Cho dãy ${u_{n}}$ thoả mãn $u_{1} = 2013, u_{n + 1} = u_{n}^{3} - 4 u_{n}^{2} + 5 u_{n} \forall n \in N^{*}$ . Tìm tất cả các số nguyên tố $p$ là ước của $(u_{2014} + 2009)$ và $p \equiv 3 (mod 4)$ .

Bài 3. Trong một hội nghị khoa học có 5000 đại biểu tham dự, mỗi một đại biểu biết ít nhất một thứ tiếng. Một uỷ ban gồm một số đại biểu được gọi là “uỷ ban làm viẹc” nếu tất cả thành viên trong uỷ ban đều biết chung một thú tiếng; gọi là “uỷ ban thách thức” nếu không có hai thành viên nào của uỷ ban biết chung một thứ tiếng (uỷ ban có thểgồm 1 thành viên; uỷ ban này gọi là làm việc họ̆c thách thức đều được). Chứng minh rằng có thể chia các đại biểu thành 100 uỷ ban rời nhau (mỗi đại biểu thuộc một uỷ ban) sao cho các uỷ ban này họ̆c là uỷ ban làm việc hoặc là uỷ ban thách thức.

Bài 4. Tam giác $A B C$ có $B, C$ cố định còn $A$ di động sao cho $A B = A C$ và $∠ B A C > 60^{\circ} .$ Đường thẳng đối xúng với $B C$ qua $A B$ cắt AC tai $P$ . Trên đoạn $P C$ lấy $M$ sao cho $P M = P B$ . Gọi $N$ là giao điểm của $A B$ với phân giác ngoài góc BCA. Chứng minh $M N$ luôn đi qua một điểm cố định.

Ngày thi thứ 2

Bài 5. Cho 2014 số thực $x_{1}, x_{2}, \dots, x_{2014}$ thỏa mãn điều kiện $\sum_{i = 1}^{2014} x_{i} = 0$ và $\sum_{i = 1}^{2014} x_{i}^{2} = 2014$ . Tìm giá trị lớn nhất của biểu thức $P = x_{1} x_{2} \dots x_{2014}$ .

Bài 6. Cho dãy số $u_{n}$ xác định bởi $u_{1} = 1, u_{n + 1} = \frac{u_{n}}{\sqrt{u_{n}^{2} + 1} + \sqrt{2}}$ với mọi $n \in N^{*}$ . Tìm giới hạn $lim \frac{u_{n + 1}}{u_{n}}$ .

Bài 7. Cho n nguyên dương và A là tập con khác rỗng của $X = 1, 2, \dots, n$ .

Tính giá trị của tổng $S (A) = \sum_{E C X} \cdot (- 1)^{| E \cap A |}$ ,trong đó $E$ lấy trên tất cả các tập con của tập $X$ (kể cả tập rỗng).
Cho $m \in N^{*}$ ,xét $m$ tập con khác rỗng của $X$ là $A_{1}, A_{2}, \dots, A_{m}$ và $m$ số nguyên khác không là $a_{1}, a_{2}, \dots, a_{m}$ sao cho $a_{1} + a_{2} + \dots + a_{m} < 0$ . Chứng minh tồn tại tập con $E$ của $X$ sao cho $\sum_{i = 1}^{m} (- 1)^{| E \cap A |} a_{i} > 0$ (Kí hiệu $| A |$ chỉ số phần tử của tập $A$ , số phần tử của tập rỗng là 0 ).

Bài 8. Cho tam giác $A B C$ nhọn có $H$ là trực tâm và $P$ là điểm di động bên trong tam giác $A B C$ sao cho $∠ B P C = ∠ B H C$ . Đường thẳng qua $B$ và vuông góc với $A B$ cắtPC tại $M$ .Đường thẳng qua $C$ và vuông góc với $A C$ cắt $P B$ tại N. Chứng minh rằng trung điểm I của $M N$ luôn thuộc một đường cố định.

Hết

Giải

Bài 1.

Trong phương trình đã cho, thay $x = y = 0$ , ta có $f (f (0)) = 0$ . \medskip

Lại thay $y = 0$ thì $f (f^{3} + f (0)) = x^{2} f (x), \forall x .$

Thay $y = f (0)$ thì $f (x^{3} + f (0)) = 2 f (0) + x^{2} f (x) .$

Từ đây suy ra $f (0) = 0$ . Thay $y = 0$ vào đẳng thức đã cho ta được $f (x^{3}) = x^{2} f (x)$ . Do đó ta có $f (x^{3} + y + f (y)) = 2 y + f (x^{3}) hay f (x + y + f (y)) = 2 y + f (x) . \eqno (*)$
Thay $y$ bởi $- y$ , ta được $f (x - y + f (- y)) = - 2 y + f (x) .$
Với $x$ bất kì, ta lấy $2 y = f (x)$ ta được $f (x - y + f (- y)) = 0$ suy ra $x - y + f (- y) = 0$ . Do đó, ta được $f (- x) = f (- y + f (- y)) = - 2 y = - f (x) .$
Từ đây suy ra
$f (x + f (y) + f (f (y))) = 2 f (y) + f (x) .$
Trong $(*)$ thay $x = - y$ ta được $f (f (y)) = 2 y + f (- y) = 2 y - f (y)$ , kết hợp với đẳng thức trên, ta được $f (x + 2 y) = 2 f (y) + f (x) .$ Đến đây cho $x = 0$ ta được $f (2 y) = 2 f (y)$ nên ta được $f (x + y) = f (x) + f (y)$ , tức là $f (x)$ cộng tính.
Đến đây ta sẽ tính $f ((x + 1)^{3} + (x - 1)^{3})$ theo hai cách như sau

$f ((x + 1)^{3} + (x - 1)^{3}) = f (2 x^{3} + 6 x) = 2 x^{2} f (x) + 6 f (x) .$
$f ((x + 1)^{3} + (x - 1)^{3}) = (x + 1)^{2} f (x + 1) + (x - 1)^{2} f (x - 1) = (x + 1)^{2} (f (x) + f (1)) + (x - 1)^{2} (f (x) - f (1)) = 2 x^{2} f (x) + 2 f (x) + 4 x f (1) .$

So sánh hai đẳng thức trên, ta được $f (x) = x f (1) = a x$ với mọi $x$ . Thử lại ta được $a = 1, a = - 2$ . \medskip

Vậy các hàm cần tìm là $f (x) = x, f (x) = - 2 x$ .

Bài 2.

Ta có
$\begin{aligned} u_{n + 1} - 2 & = (u_{n} - 2) (u_{n - 1} - 1)^{2} \\ = (u_{n - 2} - 1)^{2} (u_{n - 1} - 1)^{2} (u_{n - 2} - 2) \\ = (u_{n - 1} - 1)^{2} (u_{n - 2} - 1)^{2} \dots (u_{2} - 1)^{2} (u_{1} - 2) . \end{aligned}$

Do đó $u_{2014} + 2009 = 2011 [(u_{2013} - 1)^{2} (u_{2012} - 1)^{2} \dots (u_{2} - 1)^{2} + 1] .$

Gọi $B$ là biểu thức trong dấu ngoặc vuông thứ hai. Ta có bổ đề quen thuộc là nếu $a^{2} + b^{2}$ chia hết cho số nguyên tố $p = 4 k + 3$ thì $a, b$ cùng chia hết cho $p .$ Từ đây suy ra số $B$ có dạng $a^{2} + 1$ nên nó sẽ không có ước nguyên tố dạng $4 k + 3$ . \medskip

Vậy $u_{2014} + 9$ chỉ có một ước nguyên tố $p \equiv 3 (\mod 4)$ duy nhất là $2011$ .

Bài 3. Trước hết, ta chứng minh bổ đề sau \medskip

Định lý Ramsey Với $s, t$ là các số nguyên dương, gọi $R (s, t)$ là số đỉnh ít nhất cần có của một graph để trong đó luôn tồn tại một tập độc lập $s$ đỉnh hoặc một graph con đầy đủ $t$ đỉnh. Khi đó
$R (s, t) \leq C_{s + t - 2}^{s - 1} . \eqno (*)$

Chứng minh
Ta sẽ chứng minh rằng $R (s, t) \leq R (s - 1, t) + R (s, t - 1) .$
Để ý rằng với $s = 1$ hoặc $t = 1$ thì $R (s, t) = 1$ . Do đó, nếu chứng minh được đánh giá này thì chỉ cần dùng tính chất của tam giác Pascal để có $R (s, t) \leq C_{s + t - 3}^{s - 2} + C_{s + t - 3}^{s - 1} = C_{s + t - 2}^{s - 1} .$
Đặt $n$ là vế phải của (*) và xét graph $G$ có $n$ đỉnh. Xét $v \in G$ thì

Nếu như có ít nhất $R (s, t - 1)$ đỉnh kề với $v$ . Khi đó, theo định nghĩa thì trong tập đỉnh đó, sẽ luôn có một tập độc lập $s$ đỉnh hoặc một graph con đầy đủ $t - 1$ đỉnh, ghép thêm đỉnh $v$ vào thì thỏa mãn điều kiện của $R (s, t) .$
Nếu như có ít nhất $R (s - 1, t)$ đỉnh không kề với $v$ . Tương tự trên, trong tập đỉnh đó, cũng sẽ có một một graph con đầy đủ $t$ đỉnh hoặc tập độc lập $s - 1$ đỉnh, ghép thêm đỉnh $v$ vào thì thỏa mãn điều kiện của $R (s, t) .$
Từ đó, ta thấy graph $G$ này thỏa mãn điều kiện của $R (s, t)$ nên theo tính nhỏ nhất thì $R (s, t) \leq n .$

Trở lại bài toán, \medskip

Xét graph đơn vô hướng $G = (V, E)$ đại diện cho hội nghị khoa học đã nêu, trong đó $V$ là tập hợp các đại biểu và hai đỉnh được nối nhau nếu hai đại biểu tương ứng quen nhau. Ta gọi $T$ là tập hợp đỉnh biểu diễn cho thành viên của ban tổ chức. \medskip

Khi đó một ủy ban gồm $5$ thành viên là đại diện nếu như đó là một graph đầy đủ, còn đó là thách thức nếu đó là graph không có cạnh. Ta gọi các graph con như thế là graph con “chuẩn”. \medskip

Trong các đỉnh $V ∖ T,$ ta xóa dần dần các graph con chuẩn đến khi không thực hiện được nữa. Ta gọi tập hợp còn lại là $S .$ Ta sẽ chứng minh rằng $S \cup T$ có thể phân hoạch thành các graph con chuẩn như trên. \medskip

Theo định lý Ramsey, rõ ràng $| S | \leq C_{8}^{4} = 70$ . Xét một đỉnh $v \in S$ thì giả thiết, $v$ kề với cả $280$ đỉnh của $T$ nên ta chọn ra trong đó $4$ đỉnh để ghép với $v$ tạo thành một graph con “chuẩn”. Cứ như thế thực hiện cho đến hết các phần tử của $S$ , còn lại bao nhiêu phần tử trong $T$ thì chia đều ra thành các graph con “chuẩn” là được. \medskip

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

Bài 4.

Tam giác $P B M$ cân tại $P$ nên bằng biến đổi góc, ta có

$∠ P B M = ∠ P M B \Rightarrow 2 ∠ A B C - ∠ M B C = ∠ A C B + ∠ M B C .$

Do đó $∠ A B C = 2 ∠ M B C$ nên $B M$ là tia phân giác của $∠ A B C .$ Theo tính chất đường phân giác thì
$\frac{M C}{M A} = \frac{B C}{B A} = \frac{B C}{A C} .$

Lại có $C N$ là phân giác ngoài của $∠ A C B$ nên ta cũng có
$\frac{N A}{N B} = \frac{C A}{C B} .$ Gọi $I$ là trung điểm của $B C$ thì $I$ là điểm cố định. \medskip

Xét tam giác $A B C$ với $I$ thuộc $B C$ , $M$ thuộc $A C$ và $N$ thuộc $A B$ với

$\frac{I B}{I C} \cdot \frac{M C}{M A} \cdot \frac{N A}{N B} = 1 \cdot \frac{B C}{A C} \cdot \frac{A C}{B C} = 1$

thì theo định lý Menelaus đảo, ta có $M, N, I$ thẳng hàng. \medskip

Vậy $M N$ luôn đi qua điểm $I$ cố định.

Bài 5.

Rõ ràng có thể chọn giá trị các biến thích hợp để $P > 0$ nên để tìm giá trị lớn nhất của $P$ thì ta chỉ xét các số $x_{1}, x_{2}, \dots, x_{2014}$ đều khác $0$ và số các số âm là chẵn. Không mất tính tổng quát, giả sử
$x_{1} \geq x_{2} \geq \dots \geq x_{2 m} > 0 > x_{2 m + 1} \geq \dots \geq x_{2014} .$
Đổi dấu các số $y_{k} = - x_{k} > 0$ với $2 m + 1 \leq k \leq 2014.$ Khi đó ta viết lại
${\begin{aligned} x_{1} + x_{2} + \dots + x_{2 m} = y_{1} + y_{2} + \dots + y_{2 n} = A \\ x_{1}^{2} + x_{2}^{2} + \dots + x_{2 m}^{2} + y_{1}^{2} + y_{2}^{2} + \dots + y_{2 n}^{2} = 2014 \end{aligned}$
trong đó $m + n = 1007$ (ngoài ra $m, n > 0$ vì các số đã cho không thể toàn bộ là dương hoặc toàn bộ là âm). Theo bất đẳng thức Cauchy-Schwarz thì
$2014 \geq \frac{A^{2}}{2 m} + \frac{A^{2}}{2 n} nên A^{2} \leq 4 m n .$
Lại theo bất đẳng thức AM-GM thì
$\begin{aligned} P & = (x_{1} x_{2} \dots x_{2 m}) (y_{1} y_{2} \dots y_{2 n}) \leq {(\frac{A}{2 m})}^{2 m} {(\frac{A}{2 n})}^{2 n} \\ = \frac{A^{2 m + 2 n}}{2^{2 m + 2 n} m^{2 m} n^{2 n}} \leq \frac{{(4 m n)}^{m + n}}{2^{2 m + 2 n} m^{2 m} n^{2 n}} = {(\frac{m}{n})}^{n - m} . \end{aligned}$

Do $m, n$ khác tính chẵn lẻ nên với vai trò bình đẳng của $m, n,$ ta có thể giả sử $m < n$ nên $n - m \geq 1$ và $m \leq 503.$ Khi đó, áp dụng bất đẳng thức Bernoulli thì

${(\frac{n}{m})}^{n - m} \geq 1 + (\frac{n}{m} - 1) (n - m) = 1 + \frac{{(n - m)}^{2}}{m} \geq 1 + \frac{1}{503} = \frac{504}{503} .$
Suy ra $P \leq {(\frac{m}{n})}^{n - m} \leq \frac{503}{504} .$ Đây chính là giá trị lớn nhất cần tìm, dấu bằng xảy ra khi
$m = 503, n = 504$ và $x_{1} = x_{2} = \dots = x_{1006} = \sqrt{\frac{504}{503}}, x_{1007} = x_{1008} = \dots = x_{2014} = - \sqrt{\frac{503}{504}} .$

Bài 6.

Xét hàm số $f (x) = \frac{x}{\sqrt{x^{2} + 1} + \sqrt{2}}$ với $x \in R$ thì $f^{'} (x) = \frac{1 + \sqrt{2 + 2 x^{2}}}{\sqrt{1 + x^{2}} {(\sqrt{2} + \sqrt{1 + x^{2}})}^{2}} > 0$ nên hàm này đồng biến trên $R .$
Dãy số đã cho được viết lại thành
${\begin{aligned} u_{1} = 1, \\ u_{n + 1} = f (u_{n}), n \geq 1 \end{aligned}$ thì $u_{1} < u_{2}$ nên dễ dàng chứng minh quy nạp được rằng dãy này giảm. \medskip

Do dãy này bị chặn dưới bởi $0$ nên nó có giới hạn, đặt giới hạn đó là $L \geq 0$ . Trong biểu thức xác định dãy, cho $n \to + \infty,$ ta được $L = \frac{L}{\sqrt{L^{2} + 1} + \sqrt{2}}$ nên $L = 0.$
Từ đó suy ra
$lim_{n \to + \infty} \frac{u_{n + 1}}{u_{n}} = lim_{n \to + \infty} \frac{1}{\sqrt{u_{n}^{2} + 1} + \sqrt{2}} = \frac{1}{1 + \sqrt{2}} .$

Bài 7.

(a) Nếu $A = X$ thì $S (A) = \sum_{E \subset X} (- 1)^{| E |} = C_{n}^{0} - C_{n}^{1} + C_{n}^{2} - \dots + (- 1)^{n} C_{n}^{n} = 0.$

Còn nếu $A \neq X$ , do $S (A)$ chỉ phụ thuộc vào số phần tử của $A$ nên không mất tính tổng quát, ta giả sử rằng $A = {1, 2, \dots, k}$ với $k < n$ . Khi đó, ta có
$\begin{aligned} S (A) & = \sum_{E \subset X - {k}} (- 1)^{| E \cap A |} + \sum_{E \subset X - {k}} (- 1)^{| (E \cup {k}) \cap A |} \\ = \sum_{E \subset X - {k}} (- 1)^{| E \cap A |} - \sum_{E \subset X - {k}} (- 1)^{| E \cap A |} = 0. \end{aligned}$
Vậy $S (A) = 0, \forall A \subset X$ . \medskip

(b) Đặt $f (E) = \sum_{i = 1}^{m} (- 1)^{| E ⋂ A_{i} |} a_{i}$ . Giả sử $f (E) \leq 0, \forall E$ . Mà ta cũng có
$\sum_{E \subset X} f (E) = \sum_{i = 1}^{m} a_{i} S (A_{i}) = 0.$
Suy ra $f (E) = 0, \forall E \subset X$ , nhưng điều này là không thể vì $f (\emptyset) < 0$ . Vậy luôn tồn tại $E$ sao cho $f (E) > 0$ .

Bài 8.

Vẽ đường kính $A A^{'}$ của đường tròn $(A B C)$ . Vì $A^{'} B ⊥ A B$ nên $B, A^{'}, M$ thẳng hàng. Tương tự thì $C, A^{'}, N$ thẳng hàng. Giả sử
$B A^{'}, C A^{'}$ cắt lại $(B H C)$ lần lượt tại $E, F$ . Mặt khác

$∠ N P M = 180^{\circ} - ∠ B H C = ∠ A = 180^{\circ} - ∠ B A^{'} C = ∠ M A^{'} N$

nên $P A^{'} M N$ là tứ giác nội tiếp.

Ta sẽ chứng minh trung điểm của $A^{'} F, A^{'} E, M N$ là thẳng hàng. Theo định lý Menelaus đảo thì điều nào tương đương với $\frac{\overset{―}{A^{'} F}}{\overset{―}{A^{'} N}} = \frac{\overset{―}{E A^{'}}}{\overset{―}{E M}} \Leftrightarrow \frac{\overset{―}{A^{'} F}}{\overset{―}{A^{'} E}} = - \frac{\overset{―}{A^{'} N}}{\overset{―}{E M}} \Leftrightarrow \frac{A^{'} B}{A^{'} C} = \frac{A^{'} N}{M E} . \eqno (*)$

Vì $∠ B N A^{'} = ∠ C M E$ và $∠ N B A^{'} = ∠ M C E$ nên hai tam giác $B N A^{'}, C M E$ đồng dạng với nhau. Do đó
$\frac{A^{'} N}{M E} = \frac{A^{'} B}{C E}$ .
Mặt khác, bằng biến đổi góc, ta cũng có $C A^{'} E$ cân tại $C$ nên $C E = C A^{'} .$ Ta có được $\frac{A^{'} N}{M E} = \frac{A^{'} B}{A^{'} C} .$
Do đó, khẳng định $(*)$ là đúng. Vậy nên điểm $I$ luôn nằm trên đường trung bình của tam giác $A^{'} E F$ là đường cố định.

Bạn đọc có thể tìm thêm nhiều cách giải cho bài 8 này tại

link sau

Tham khảo từ sách “Tuyển tập đề thi môn Toán đội tuyển và dự tuyển trường PTNK”

Đáp án thi chọn Đội Tuyển PTNK năm học 2012-2013

Leave a reply

Kì thi chọn đội tuyển thi HSG Quốc gia của trường PTNK năm học 2012 – 2013 được diễn ra trong hai ngày, mỗi ngày 4 bài làm trong 180 phút.

Ngày thi thứ 1

Bài 1. Giải hệ phương trình:

${\begin{cases} x + y & = 3 \\ x z + y t & = 5 \\ x z^{2} + y t^{2} & = 41 \\ x z^{3} + y t^{3} & = 121 \end{cases}$

Bài 2.Cho dãy $(u_{n})$ giảm và có giới hạn bằng 0 . Xét hai dãy số sau

$\begin{matrix} v_{n} = u_{1} + u_{2} + \dots + u_{n} - n u_{n + 1} z_{n} = u_{1} + u_{2} + \dots + u_{n} \end{matrix}$

Chứng minh nếu $(v_{n})$ bị chặn thì $(z_{n})$ hội tụ.

Bài 3. Cho tập $X = 1; 2; 3; \dots; 4 n .$ Hai tập con $A$ và $B$ của $X$ được gọi là không giống nhau nếu $| A Δ B | \geq 2 n + 1$ . Trong đó $A Δ B = (A ∖ B) \cup (B ∖ A)$ . Cho ${A_{1}; A_{2}; \dots; A_{m}}$ là tạp con của $X$ gồm $m$ phần tử đôi một không giống nhau.

Chứng minh $m \leq 2 n$ .
Chứng minh $m \leq \frac{4 (n + 1)}{3}$ .

Bài 4. Cho $△ A B C$ với $M, N$ thuộc cạnh $B C$ sao cho $∠ B A M = ∠ C A N = α$ (M nằm giữa $B, N)$ . Gọi I là trung điểm BC. Kẻ BH $⊥ A M, C K ⊥ A N$ lần lượt tại $H, K$ .

Chứng minh tâm đường tròn (IHK) luôn thuộc một đường thẳng cố định.
Tính $α$ theo $∠ A B C$ và $∠ A C B$ sao cho $(I K H)$ tiếp xúc với đường tròn đường kính $AB$ hoặc đường tròn đường kính $AC$ .

Ngày thi thứ 2

Bài 5.

Chứng minh rằng với mọi $x > 0$ thi $2 (x^{\frac{4}{3}} + \frac{1}{x^{\frac{4}{3}}} + 1) \geq 3 (x + \frac{1}{x})$ .
Tim số thực dương a nhỏ nhất sao cho $2 (x^{a} + \frac{1}{x^{a}} + 1) \geq 3 (x + \frac{1}{x})$ với mọi $x > 0$

Bài 6. Tìm $n$ tự nhiên sao cho $A_{n} = 1 + 3^{20 (n^{2} + n + 1)} + 9^{14 (n^{2} + n + 1)}$ là số nguyên tố.

Bài 7. Tìm hàm số $f : N * \to N$ * thỏa mãn đồng thời hai điều kiện sau:

i) $f (m f (n)) = n^{6} \cdot f (m n)$

ii) Với mọi $m, n$ là các số nguyên tố cùng nhau thì $f (m), f (n)$ cũng nguyên tố cùng nhau.

Bài 8. Cho tam giác $A B C$ có $A B = A C$ . Gọi $H$ là chân đường vuông góc hạ từ A xuống $B C$ . ( $C)$ là một đường tròn đi qua $H$ có tâm $I$ di động trên đoạn $A H . (C)$ cắt $A B$ tại $M, N$ và cắt $A C$ tai $P, Q$ sao cho $M$ nằm giữa $A$ và $N, P$ nằm giũa $A v \dot{a} Q$ . $B P$ và $B Q$ cắt $(C)$ tại $E, F$ . Chúng minh rằng giao điểm $D$ của $N E$ và $M F$ là một điểm cố định.

Giải

Ngày thi thứ 1

Bài 1.

Gọi 4 phương trình của hệ lần lượt là $(1), (2), (3), (4) .$ Nếu $z + t = 0$ thì khử $t$ ở các phương trình.

Ta có $x + y = 3$ và $(x + y) z^{2} = 41$ nên $z^{2} = \frac{41}{3}$ .

Mặt khác $z (x - y) = 5$ và $z^{3} (x - y) = 101$ nên $z^{2} = \frac{101}{5},$ từ đây ta có điều vô lý.

Do đó, ta chỉ cần xét $z + t \neq 0$ . Từ $(2),$ ta có

$(x z + y t) (z + t) = 5 (z + t),$

sau khi khai triển, sử dụng $(1), (3)$ , ta được $41 + 3 z t = 5 (z + t) .$

Từ $(3),$ ta có $(x z^{2} + y t^{2}) (z + t) = 41 (z + t),$

lại khai triển, sử dụng $(2), (4)$ , ta được $101 + 5 z t = 41 (z + t) .$

Do đó, ta có một hệ phương trình theo biến $z t, z + t$ nên giải ra được $z + t = 1, z t = - 12$ . Từ đây ta có $(z, t) = (4, - 3), (- 3, 4) .$

Nếu $z = 4, t = - 3$ thì dễ dàng tính được $x = 2, y = 1.$
Nếu $z = - 3, t = 4$ thì ta cũng tính được $x = 1, y = 2.$

Vậy hệ phương trình có hai nghiệm phân biệt là $(x, y, z, t) = (1, 2, - 3, 4), (2, 1, 4, - 3) .$

Bài 2.

Do $z_{n}$ là dãy tăng nên ta chỉ cần chứng minh nó bị chặn trên là được.

Giả sử $L$ là chặn trên của $v_{n}$ , ta có do $x_{n}$ giảm nên

$z_{n} - n x_{n + 2} \leq v_{n + 1} = x_{1} + x_{2} + \dots + x_{n} + x_{n + 1} - (n + 1) x_{n + 2} \leq L .$

Suy ra $z_{n} \leq L + n x_{n + 2} .$

Tương tự, $z_{n} - n x_{n + 3} \leq v_{n + 2} = x_{1} + x_{2} + \dots + x_{n} + x_{n + 1} + x_{n + 2} - (n + 2) x_{n + 3} \leq L$

nên ta được $z_{n} \leq L + n x_{n + 3} .$

Qua hai bước trên, làm tương tự, cho $n$ cố định, ta suy ra được $z_{n} \leq L + n lim_{N \to \infty} x_{N} = L .$

Ta có điều phải chứng minh.

Bài 3.

(a) Ta giải bằng phương pháp đếm bằng hai cách. Giả sử ngược lại, tồn tại tập $M$ gồm $2 n + 1$ tập con đôi một không giống nhau. Ta đếm số các bộ $(x, i, j)$ với $i < j$ mà $x \in A_{i} Δ A_{j} .$ Theo giả thiết, số bộ này ít nhất là

$(2 n + 1) \frac{(2 n + 1) 2 n}{2} .$

Với mỗi $x,$ giả sử có $k$ tập con $A_{i}$ chứa $x$ và $2 n + 1 - k$ tập con không chứa $x .$ Khi đó số cặp $A_{i}, A_{j}$ mà $x \in A_{i} Δ A_{j}$ sẽ không quá $k (2 n + 1 - k) \leq n (n + 1) .$ Như vậy số bộ này nhiều nhất là $4 n \cdot n (n + 1) .$ Từ đó ta suy ra bất đẳng thức $(2 n + 1) \frac{(2 n + 1) 2 n}{2} \leq 4 n \cdot n (n + 1) .$

Suy ra $1 \leq 0,$ vô lý, kéo theo $m \leq 2 n .$

(b) Xét tập $M = {A_{1}, A_{2}, \dots, A_{m}}$ gồm $m$ tập con đôi một không giống nhau của $X .$

Đặt $X^{'} = X \cup 0 .$ Ta thiết lập các tập $A_{i}^{'}$ theo nguyên tắc sau đây

Nếu $| A_{i} |$ chẵn thì $A_{i}^{'} = A_{i},$
Nếu $| A_{i} |$ lẻ thì $A_{i}^{'} = A_{i} \cup {0} .$

Khi đó ta có $| A_{i}^{'} |$ chẵn với mọi $i .$ Từ đó, do

$| A Δ B | = | A | + | B | - 2 | A \cap B | nên | A_{i}^{'} Δ A_{j}^{'} | .$

Mà ${A^{'}}_{i} Δ {A^{'}}_{j} \supseteq A_{i} Δ A_{j}$ nên $| {A^{'}}_{i} Δ {A^{'}}_{j} | \geq | A_{i} Δ A_{j} | \geq 2 n + 1.$ Từ đây, do tính chẵn, suy ra $| A_{i}^{'} Δ A_{j}^{'} | \geq 2 n + 2.$

Lại áp dụng lập luận tương tự (a) cho tập $M^{'} = {A_{1}^{'}, A_{2}^{'}, \dots, A_{m}^{'}}$ thuộc $X^{'},$ ta có số bộ $(x, i, j)$ với $x \in A_{i}^{'} Δ A_{j}^{'}$ một mặt sẽ có ít nhất là $(2 n + 2) \frac{m (m - 1)}{2} .$ Mặt khác sẽ không vượt quá $(4 n + 1) \cdot \frac{m^{2}}{4} .$ Từ đó suy ra bất đẳng thức

$\begin{aligned} (2 n + 2) \frac{m (m - 1)}{2} \leq (4 n + 1) \cdot \frac{m^{2}}{4} \\ \Leftrightarrow 4 (n + 1) (m - 1) \leq (4 n + 1) m \\ \Leftrightarrow m \leq \frac{4 (n + 1)}{3} . \end{aligned}$

Bài 4.

(a) Gọi $A T$ là đường cao của tam giác $A B C$ với $T \in B C .$ Suy ra tứ giác $A H T B$ và $A T K C$ nội tiếp.

Do đó $∠ H T I = ∠ B A H = α = ∠ C A K = ∠ I T K .$ Suy ra $I, H, T, K$ đồng viên. Do đó, tâm $(I H K)$ thuộc trung trực của $T I$ cố định.

(b) Gọi $(ω)$ là đường tròn đường kính $A B .$ Ta có tứ giác $A H T B$ nội tiếp $(ω) .$ Do đó $(ω)$ giao $(I H K)$ tại $T$ và $H .$

Giả sử $(ω)$ và $(I H K)$ tiếp xúc thì $T \equiv H$ dẫn đến $A M$ là đường cao của tam giác $A B C .$

Khi đó ta tính được $α = 90^{\circ} - ∠ A B C .$

Hoàn toàn tương tự nếu $(I H K)$ tiếp xúc với đường tròn đường kính $A C .$

Ngày thi thứ 2

Bài 5.

(a) Đặt $x^{\frac{4}{3}} = a, x^{- \frac{4}{3}} = b$ thì ta có $a b = 1$ và cần chứng minh rằng

$2 (a^{4} + b^{4} + 1) \geq 3 (a^{3} + b^{3}) .$

Ta cũng có

$a^{4} + b^{4} = ((a + b)^{2} - 2)^{2} - 2$ và $a^{3} + b^{3} = (a + b)^{3} - 3 (a + b)$ .

Đặt $t = a + b \geq 2$ thì ta cần có

$2 ((t^{2} - 2)^{2} - 1) \geq 3 (t^{3} - 3 t)$ .

Biến đổi tương đương bất đẳng thức này, ta được

$(t - 2) (2 t + 1) (t^{2} - 3) \geq 0.$

Bất đẳng thức này đúng do $t \geq 2$ .

(b) Ta chứng minh hằng số nhỏ nhất là $α_{0} = \sqrt{3 / 2} .$ Không mất tính tổng quát, giả sử $x \geq 1.$ Đầu tiên, vì hàm $h (α) = x^{α} + \frac{1}{x^{α}}$ tăng nên ta dễ thấy $α > 1.$ Bây giờ ta sẽ chứng minh bằng hai bước. \medskip

Bước : $α = \sqrt{3 / 2} = α_{0}$ thì bất đẳng thức đúng. Thật vậy, ta cần chứng minh

$\frac{2 (x^{α_{0}} - 1)^{2}}{x^{α_{0}}} \geq \frac{3 (x - 1)^{2}}{x},$

tương đương $f (x) = x^{α_{0}} - \frac{1}{x^{α_{0}}} - α_{0} x + \frac{α_{0}}{x} .$

Ta có

$f^{'} (x) = α_{0} (x^{α_{0} - 1} - 1) (1 - \frac{1}{x^{α_{0} + 1}}) \geq 0 \forall x \geq 1,$

nên $f (x) \geq f (1) = 0.$

Bước 2: Chứng minh $α = \sqrt{3 / 2} = α_{0}$ là hằng số nhỏ nhất. Thật vậy, giả sử tồn tại $1 < α < α_{0}$ sao cho bất đẳng thức ở đề bài thỏa mãn với mọi $x \geq 1.$ Khi đó tồn tại $m > n$ nguyên dương sao cho $α < \frac{m}{n} < α_{0} .$ Khi đó $h (α) < h (\frac{m}{n}) .$ Từ đây suy ra

$2 h (\frac{m}{n}) + 2 \geq 3 h (1),$

tương đương

$\frac{2 (y^{m} - 1)^{2}}{y^{m}} \geq \frac{3 (y^{n} - 1)^{2}}{y^{n}} \forall y \geq 1,$

với $y = \sqrt[n]{x} .$ Bất đẳng thức trên có thể được viết lại với $y > 1$ như sau

$g (y) = 2 (y^{m - 1} + y^{m - 2} + \dots + 1)^{2} - 3 y^{m - n} (y^{n - 1} + y^{n - 2} + \dots + 1)^{2} \geq 0, \forall y > 1.$

Vì $g (y)$ liên tục nên ta có

$lim_{y \to 1} g (y) \geq 0 ⟺ 2 m^{2} \geq 3 n^{2},$

mâu thuẫn do $m / n < \sqrt{3 / 2} .$

Vậy hằng số nhỏ nhất cần tìm là $\sqrt{3 / 2} .$

Bài 6.

Đặt $a = 3^{4 (n^{2} + n + 1)} \geq 81$ thì ta có $A = t^{7} + t^{5} + 1$ . Phân tích biểu thức này thành nhân tử, ta có

$A = (t^{5} - t^{4} + t^{3} - t + 1) (t^{2} + t + 1) .$

Dễ dàng chứng minh được $t^{5} - t^{4} + t^{3} - t + 1 > t^{2} + t + 1 > 1$ nên biểu thức trên không thể là số nguyên tố được.

Vậy không tồn tại số $n$ nào thỏa mãn đề bài.

Bài 7.

Trong $(i),$ thay $m = 1$ , ta có

$f (f (n)) = n^{6} f (n) . (*)$

Từ đây dễ suy ra $f$ đơn ánh. Tiếp tục thay $m$ bởi $f (m),$ ta có

$f (f (m) \cdot f (n)) = n^{6} \cdot f (f (m) \cdot n) = (m n)^{6} \cdot f (m n) = f (f (m n)) .$

Kết hợp với tính đơn ánh, ta có $f (m) \cdot f (n) = f (m n)$ nên $f$ nhân tính. \medskip

Tiếp theo, giả sử tồn tại $n$ sao cho $gcd (f (n), n) = 1$ suy ra $f (f (n))$ và $f (n)$ nguyên tố cùng nhau. Từ $(*)$ ta được $f (n) = 1$ và $f (1) = n^{6}$ . Lại có $gcd (f (1), 1) = 1$ nên $f (1) = 1$ . Do đó $gcd (f (n), n) \neq 1, \forall n \geq 2.$

Xét số nguyên $n$ bất kì. Giả sử $f (n)$ có ước nguyên tố $q$ sao cho $q$ không là ước của $n .$ Khi đó $gcd (n, q) = 1$ và $gcd (f (n), f (q)) \neq 1,$ trái với điều kiện $(i i) .$ \medskip

Xét số nguyên tố $p$ bất kì. Khi đó $f (p) = p^{k}, k \geq 1$ do $(f (p), p) \neq 1$ . Suy ra $f (f (p)) = f (p^{k}) = f (p)^{k} = p^{k^{2}} .$

Thay vào $(*)$ ta được $p^{k^{2}} = p^{6} \cdot p^{k} \Rightarrow {\begin{cases} k = 3 \\ f (p) = p^{3} \end{cases} .$

Từ đây, kết hợp với tính nhân tính của $f$ và ta cũng biết rằng mỗi số $n$ đều có thể biểu diễn thành tích của các số nguyên tố, ta có được $f (n) = n^{3}$ với mọi $n \in N .$

Bài 8.

Giả sử $M F$ cắt $B C$ tại $T$ , ta có $(C)$ tiếp xúc với $B C$ tại $H$ nên $T H^{2} = T F \cdot T M .$

Ta lại có $N Q ∥ B C$ vậy nên $∠ T B F = ∠ F Q N = ∠ T M B,$ suy ra $T B^{2} = T F \cdot T M .$ Từ đó, suy ra $T$ là trung điểm $H B$ . Tương tự, ta cũng chứng minh được rằng $N E$ cắt $B C$ cũng tại trung điểm $B H$ .

Suy ra $N E, M F, B C$ đồng quy tại $T$ là trung điểm $B H$ , là một điểm cố định.

Nhận xét: Bài toán này cũng có một phiên bản tương tự khi thay tam giác tam giác cân bởi tam giác bất kỳ, và đường tròn cắt tại hai điểm trên cạnh thành đường tròn nội tiếp. Cụ thể là:

Cho tam giác $A B C$ có đường tròn nội tiếp $(I)$ tiếp xúc với các cạnh $B C, C A, A B$ lần lượt tại $D, E, F .$ Đường thẳng qua $E, F$ song song với $B C$ lần lượt cắt lại $(I)$ tại $G, H$ . Giả sử $B G, C H$ cắt lại $(I)$ tại $P, Q$ và $E F$ cắt $B C$ tại $T$ .

a/ Chứng minh rằng $P E, Q F$ cùng đi qua trung điểm $K$ của $D T .$

b/ Chứng minh rằng $(K B P), (K C Q)$ cùng tiếp xúc với $(I)$ và hai đường tròn này cũng cắt nhau tại một điểm nằm trên $(A B C)$ .

Đề thi chọn đội tuyển PTNK năm học 2010-2011

Leave a reply

Ngày thi thứ 1

Bài 1. Giải hệ phương trinh: ${\begin{cases} \frac{5 (x + y)}{x + y + 6 x y} + \frac{6 (x + z)}{x + z + 5 x z} = 4 \\ \frac{6 (z + y)}{z + y + 4 z y} + \frac{4 (x + y)}{x + y + 6 x y} = 5 \\ \frac{4 (x + z)}{x + z + 5 x y} + \frac{5 (y + z)}{y + z + 4 y z} = 6 \end{cases}$

Bài 2. Tìm tất cả các hàm $f : R \to R$ thỏa mãn

$f (| x | + y + f (y + f (y))) = 3 y + | f (x) |$ với mọi $x, y \in R$

Bài 3. Cho $p$ là số nguyên tố lẻ và $n = 2 p + r$ với $r \in 0, 1, 2, \dots, p - 1 .$ Đặt $X = 1, 2, \dots, n$ . Ánh xạ $f : X \to X$ được gọi là có tính chất $P$ nếu $f$ không phải là ánh xạ đồng nhất và $f (f \dots (f (f (k))) \dots) = k$ (ánh xạ hợp plần) với mọi $k \in X .$ Đạt $A_{f} = k \in X ∣ f (k) = k$ .

Chứng minh rằng nếu $f$ có tính chất P thì $| A_{f} | \equiv r (mod p)$ .
Gọi $d$ là số các ánh xạ $f$ có tính chất $P$ . Chứng minh rằng $d$ không là ước số của n!.

Bài 4. Cho tam giác $A B C$ nội tiếp đường tròn $(O)$ có $A$ cố định và $B, C$ thay đổi trên $(O)$ sao cho $B C$ luôn song song với một đường thẳng cố định. Các tiếp tuyến của $(O)$ tại $B$ và $C$ cắt nhau tại $K$ . Gọi $M$ là trung điểm $B C, N$ là giao điểm của $A M$ với $(O)$ . Chứng minh rằng đường thẳng $K N$ luôn đi qua một điểm cố định.

Ngày thi thứ 2

Bài 5. Cho $a, b, c$ là độ dài các canh của một tam giác. Chứng minh rằng $(2 a + 2 b - c) (2 b + 2 c - a) (2 a + 2 c - b) > 25 a b c$

Bài 6. Cho dãy số $u_{n}$ thỏa mãn $u_{1} = \sqrt{2}, u_{n + 1} = \frac{2 u_{n}^{2} + 5 u_{n} + 5}{2 u_{n} + 4}, n \geq 1$ . Tính giới hạn sau $lim \frac{u_{n}^{2} - 3 u_{n} + 5}{3 n^{2} + 4 n - 1}$ .

Bài 7. Xét số tự nhiên $n > 1$ . Bắt đầu từ bộ số $1, 2, \dots, 2 n - 1, 2 n$ ta thực hiện phép biến đổi sau: chọn hai số $a, b$ bát kì sao $a - b > 1$ , xóa hai số này và thay bởi hai số $a - 1$ và $b + 1$ . Với bộ số mới này ta lại tiếp tục thực hiện phép biến đổi tương tự.

Chứng minh rằng ta sẽ đạt đến trạng thái dừng, tức là không thể thực hiện phép biến đổi như vậy được nữa.
Gọi $k$ là số lần phép biến đổicần thực hiện để đạt đến trang thái dừng. Tìm giá trị nhỏ nhất và lớn nhất của $k$ .

Bài 8. Cho đường tròn $(γ_{1})$ dường kính $A B$ và đường tròn $(γ_{2})$ tâm $A$ cắt $(γ_{1})$ tai $C$ và $D$ . Điểm $M$ thay đổi trên cung $C D$ (nằm bên trong $(γ_{1}))$ của $(γ_{2})$ , $B M$ cắt $(γ_{2})$ tại $N$ (N khác $M$ và B). Tìm giá trị nhỏ nhất của $\frac{N C + N D}{N M}$ .

Lời giải

Bài 1. Đặt $u = \frac{x + y}{x + y + 6 x y}, v = \frac{y + z}{y + z + 4 y z}, w = \frac{z + x}{z + x + 5 z x}$ thì ta có hệ
$$\left\{ $\begin{aligned} 5 u + 6 w = 4 \\ 6 v + 4 u = 5 \\ 4 w + 5 v = 6 \end{aligned}$ \right.\Leftrightarrow \left\{ $\begin{aligned} 8 u = 1 \\ 4 v = 3 \\ 16 w = 9 \end{aligned}$ \right.. $S u y r a$ \left\{ $\begin{aligned} 7 (x + y) = 6 x y \\ 3 (y + z) = 12 y z \\ 7 (z + x) = 45 z x \end{aligned}$ \right.\Leftrightarrow \left\{ $\begin{aligned} a + b = \frac{6}{7} \\ b + c = 12 \\ c + a = \frac{45}{7} \end{aligned}$ \right.,$$ trong đó $a = \frac{1}{x}, b = \frac{1}{y}, c = \frac{1}{z} .$
Giải hệ trên, ta thu được $a = - \frac{33}{14}, b = \frac{45}{14}, c = \frac{123}{14}$ nên $(x, y, z) = (- \frac{14}{33}, \frac{14}{45}, \frac{14}{123}) .$

Bài 2.

Dễ thấy $f$ toàn ánh. Giả sử $f (a) = 0$ và thay $x = 0, y = a,$ ta có
$0 = 3 a + | f (0) | .$
Suy ra $a$ tồn tại duy nhất và $a = - \frac{1}{3} | f (0) | \leq 0.$ Lại thay $x = y = a,$ ta có $f (0) = 3 a \leq 0.$
Lại thay $x = - a, y = a$ thì chú ý rằng $| - a | + a = 0$ , ta có $f (0) = 3 a + | f (- a) |$ nên $f (- a) = 0$ , điều này kéo theo $a = - a$ hay $a = 0$ (do tính duy nhất ở trên). \medskip

Thay $y = 0$ thì $f (| x |) = | f (x) |$ nên $f (x) \geq 0, \forall x \geq 0.$
Xét $x > 0$ và $y = - \frac{f (x)}{3}$ , ta có $f (x - \frac{f (x)}{3} + f (- \frac{f (x)}{3} + f (- \frac{f (x)}{3}))) = 0$ nên
$- \frac{f (x)}{3} + f (- \frac{f (x)}{3} + f (- \frac{f (x)}{3})) = - x$ với mọi $x > 0.$
Trong đề bài, thay $x = 0$ thì $f (y + f (y + f (y))) = 3 y$ . Thay $y \to - \frac{f (x)}{3}$ thì
$f (- \frac{f (x)}{3} + f (- \frac{f (x)}{3} + f (- \frac{f (x)}{3}))) = - f (x)$ .
So sánh hai đẳng thức trên, ta có $f (- x) = - f (x), \forall x > 0$ nên $f$ là hàm số lẻ. \medskip

Từ tính chất hàm số lẻ, ta có $f (\frac{f (x)}{3} + f (\frac{f (x)}{3} + f (\frac{f (x)}{3}))) = f (x)$ với mọi $x > 0.$
Trong đề bài, xét $x \geq 0$ và $y \to \frac{f (y)}{3}$ , ta có
$f (x + \frac{f (y)}{3} + f (\frac{f (y)}{3} + f (\frac{f (y)}{3}))) = f (y) + f (x)$ hay
$f (x + y) = f (x) + f (y)$ với mọi $x, y > 0.$
Vì $f$ cộng tính trên $R^{+}$ nên ta có $f (x) = a x, \forall x > 0.$ Lại do tính chất hàm lẻ, ta suy ra $f (x) = a x, \forall x \in R .$ Thay vào đề bài, ta có $a = 1.$ \medskip

Vậy tất cả các hàm số cần tìm là $f (x) = x .$

Bài 3.

a) Ta có
$| A_{f} | \equiv r (\mod p) \Leftrightarrow | X ∖ A_{f} | chia hết cho p .$
Điều này tương đương số phần tử của tập hợp $Missing \left or extra \right$ là bội của $p .$
Đặt $f_{m} (x)$ là ánh xạ hợp $m$ lần. Xét $x \in B$ thì cũng có các số $f (x), f_{2} (x), \dots, f_{p - 1} (x) \in B$ . Thật vậy, \medskip

Gỉa sử tồn tại $1 < m < p$ sao cho $f_{m} (x) = x$ với số $x \in B$ nào đó, ta chọn $m$ là số nhỏ nhất như thế. Vì $p$ nguyên tố lẻ nên $p$ không chia hết cho $m .$ Do vậy tồn tại số $t$ sao cho $0 < p - t m < m$ . Lại có $f_{m} (x) = x \Rightarrow f_{t m} (x) = x \Rightarrow f_{p - t m} (x) = f_{p} (x) = x$ (mâu thuẫn với tính nhỏ nhất của $m$ ). Vì thế nên với mọi $m$ mà $1 < m < p$ thì $f_{m} (x) \neq x$ . Từ đó suy ra với mọi $1 < k < l < p$ thì $f_{k} (x) \neq f_{l} (x)$ , tức là $x, f (x), f_{2} (x), \dots, f_{p - 1} (x)$ là $p$ số khác nhau thuộc $B .$ \medskip

Xét số $y \in B$ và $y$ khác tất cả $p$ số ở trên. Khi đó, ta cũng sẽ có $y$ sinh ra một bộ $p$ số phân biệt mới. Giả sử rằng có $f_{i} (x) = f_{j} (y)$ với $i < j$ nào đó thì sẽ có $f_{p + i - j} (x) = f_{p} (y) = y$ , mâu thuẫn. Suy ra trong $B$ sẽ có $1$ hoặc $2$ bộ $p$ số rời nhau, chứng tỏ rằng số phần tử của $B$ chia hết cho $p .$ Suy ra đpcm. \medskip

(b) Từ đây ta thấy rằng để đếm số ánh xạ $f$ có tính chất $P,$ trước hết, ta chọn ra $r$ hoặc $p + r$ vị trí cố định. Ta xét hai trường hợp như sau:

Nếu $| A_{f} | = p + r$ thì có $C_{n}^{p + r}$ cách chọn ra các số này, còn lại $p$ số thì $f$ phải là song ánh trên tập con đó. Do đó trong trường hợp này có $p! C_{n}^{p + r}$ cách.
Nếu $| A_{f} | = r$ thì tương tự trên, ta cũng đếm được $(p!)^{2} C_{n}^{r} C_{2 p}^{p}$ .

Từ đó suy ra số ánh xạ tính chất $P$ là $d = p! C_{n}^{p + r} + {(p!)}^{2} C_{n}^{r} C_{2 p}^{p} .$ Ta sẽ chứng minh số này không là ước của $n! .$ Ta viết số $d$ dưới dạng khai triển
$d = p! \frac{n!}{(p + r)! p!} + {(p!)}^{2} \frac{n!}{r! (2 p)!} \cdot \frac{(2 p)!}{{(p!)}^{2}} = \frac{n!}{(p + r)!} + \frac{n!}{r!} .$
Đặt $(p + r)! = k \cdot {(r!)}^{2}$ với $k = \frac{(p + r)!}{{(r!)}^{2}} = \frac{p!}{r!} \cdot \frac{(p + r)!}{p! r!} = \frac{p!}{r!} C_{p + r}^{r} \in Z$ . Khi đó, ta viết lại
$\frac{n!}{d} = \frac{r! (p + r)!}{r! + (p + r)!} = \frac{k \cdot {(r!)}^{3}}{(1 + k \cdot r!) \cdot r!} = \frac{k \cdot {(r!)}^{2}}{k \cdot r! + 1} .$
Dễ thấy số này không thể nguyên vì $k \cdot r! + 1$ nguyên tố cùng nhau với $k \cdot {(r!)}^{2}$ . Từ đó ta có $d$ không là ước của $n! .$

Bài 4. Giả sử $K N$ cắt $(O)$ tại $I$ thì tứ giác $B N C I$ điều hòa.

Do đó $A (B C, N I) = - 1,$ mà $A N$ chia đôi $B C$ nên $A I ∥ B C,$ tức là $A I$ có phương cố định. Từ đó ta thấy $I$ là điểm cố định cần tìm.

Bài 5. Đặt $a + b - c = x, b + c - a = y, c + a - b = z$ thì $x, y, z > 0.$ Ta đưa về bất đẳng thức
$(4 \cdot \frac{x}{y + z} + 1) (4 \cdot \frac{y}{z + x} + 1) (4 \cdot \frac{z}{x + y} + 1) > 25.$
Không mất tính tổng quát, giả sử $0 < x \leq y \leq z .$ Đặt $S = x + y + z .$ Ta đưa về
$(S + 3 x) (S + 3 y) (S + 3 z) > 25 (S - x) (S - y) (S - z) .$
Khai triển và rút gọn, ta được
$S^{3} - 4 S (x y + y z + z x) + 13 x y z > 0.$
Chú ý rằng $S^{3} - 4 S (x y + y z + z x) = S (S^{2} - 4 (x y + y z + z x)) = S ({(x + y - z)}^{2} - 4 x y)$ nên ta đưa về $S {(x + y - z)}^{2} + x y (13 z - 4 S) > 0$ .
Bất đẳng thức cuối đúng vì $13 c - 4 S = 9 z - 4 (x + y) > 0.$

Bài 6.

Lời giải. Ta thấy rằng $u_{n} > 0, \forall n$ và $u_{n + 1} - u_{n} = \frac{u_{n} + 5}{2 (u_{n} + 2)} > 0$ nên dãy tăng. Giả sử dãy bị chặn trên thì nó hội tụ về $L > 0$ , suy ra
$L = \frac{2 L^{2} + 5 L + 5}{2 L + 4} \Leftrightarrow L = - 5$
vô lý. Suy ra $lim_{n \to + \infty} u_{n} = + \infty$ . Từ đó, ta được
$lim_{n \to + \infty} (u_{n + 1} - u_{n}) = lim_{n \to + \infty} \frac{u_{n} + 5}{2 (u_{n} + 2)} = \frac{1}{2}$
nên theo định lý Stolz, ta suy ra $lim_{n \to + \infty} \frac{u_{n}}{n} = \frac{1}{2}$ và $lim_{n \to + \infty} \frac{u_{n}}{n^{2}} = 0 .$ Do đó, trong biểu thức cần tính giới hạn, chia tử và mẫu cho $n^{2}$ rồi áp dụng kết quả trên, ta có
$lim_{n \to + \infty} \frac{u_{n}^{2} - 3 u_{n} + 5}{3 n^{2} + 4 n - 1} = lim_{n \to + \infty} \frac{{(\frac{u_{n}}{n})}^{2} - \frac{3 u_{n} - 5}{n^{2}}}{3 + \frac{4}{n} - \frac{1}{n^{2}}} = {(\frac{1}{2})}^{2} \cdot \frac{1}{3} = \frac{1}{12}$

Bài 7.

(a) Xét đại lượng $S$ là tổng bình phương các số thu được sau mỗi thao tác biến đổi. \medskip

Ta thấy rằng từ $(a, b)$ với $a - b > 1,$ ta đưa về bộ $(a - 1, b + 1)$ thì tổng trên thay đổi một lượng là
$a^{2} + b^{2} - {(a - 1)}^{2} - {(b + 1)}^{2} = 2 (a + b - 1) > 0.$
Do đó, tổng $S$ giảm ngặt, và rõ ràng $S$ phải luôn dương nên thao tác trên chỉ thực hiện được trong hữu hạn lần.
\medskip

(b) Rõ ràng tổng trên không đổi khi không còn cặp số $a, b$ nào mà $a - b > 1.$ Điều này đồng nghĩa với việc các số thu được trong trạng thái cuối chỉ nhận hai giá trị liên tiếp nào đó. Ta thấy rằng tổng các số đã cho luôn không đổi và là $1 + 2 + \dots + 2 n = n (2 n + 1) .$ \medskip

Giả sử cuối cùng, ta có $x$ số $m$ và $y$ số $m + 1$ thì
$$\left\{ $\begin{aligned} x + y = 2 n \\ m x + (m + 1) y = n (2 n + 1) \end{aligned}$ \right..$$
Suy ra $2 m n + y = 2 n^{2} + n \Rightarrow n | y .$ Tuy nhiên, nếu $y \in {0, 2 n}$ thì vô lý vì vế phải không chia hết cho $2 n .$ Do đó $x = y = n$ và $m = n,$ tức là ở trạng thái cuối, ta còn $n$ số $n$ và $n + 1.$

Tổng bình phương của chúng là $S = n \cdot n^{2} + n \cdot {(n + 1)}^{2} = n (2 n^{2} + 2 n + 1) .$
Tổng bình phương ban đầu là $S_{0} = 1^{2} + 2^{2} + \dots + {(2 n)}^{2} = \frac{n (2 n + 1) (4 n + 1)}{3} .$

Suy ra $S_{0} - S = \frac{2}{3} (n^{3} - n) .$ \medskip

(b) Để thực hiện được nhiều lần nhất thì giá trị giảm đi ở mỗi lần phải ít nhất. Theo câu a) thì giá trị đó sẽ là $2 (a + b - 1) \geq 2.$ \medskip

Suy ra số lần nhiều nhất sẽ là $\frac{1}{3} (n^{3} - n)$ . Để thực hiện được điều này, ta sẽ cố gắng trong mỗi thao tác tạo ra nhiều giá trị nhất có thể và đồng thời làm giảm số lượng các giá trị ở hai biên đi. Từ đó ta được $k_{max} = \frac{1}{3} (n^{3} - n) .$ \medskip

Để thực hiện được ít lần nhất, ta sử dụng ý tưởng tham lam, mỗi lần, ta sẽ chọn các cặp số nằm về hai phía của $n, n + 1.$ Khi đó, giá trị của các số $1, 2, \dots, n - 1$ sẽ dần dần được tăng lên, trong khi giá trị của các số $n + 2, n + 3, \dots, 2 n$ dần dần sẽ giảm đi. Tổng khoảng cách từ các số nhỏ hơn $n$ đến $n$ là $1 + 2 + \dots + n - 1 = \frac{n (n - 1)}{2}$ . Tương tự thì tổng khoảng cách các số lớn hơn $n + 1$ đến $n + 1$ cũng là $\frac{n (n - 1)}{2}$ . Ta thấy mỗi lần thao tác thì các số này sẽ thu hẹp khoảng cách đúng $2$ đơn vị nên số lần thao tác tối thiểu phải là $\frac{1}{2} (\frac{n (n - 1)}{2} + \frac{n (n - 1)}{2}) = \frac{n (n - 1)}{2} .$ \medskip

Để đạt được giá trị này, mỗi lần, ta chỉ cần chọn các cặp số có dạng $(t, 2 n + 1 - t)$ với $1 \leq t \leq n - 1$ là được. Suy ra $k_{min} = \frac{n (n - 1)}{2} .$

Bài 8.

Theo định lý Ptolemy cho tứ giác $B C N D$ nội tiếp trong $γ_{1}$ thì
$B C \cdot N D + B D \cdot N C = B N \cdot C D .$
Vì $A C = A D$ nên $B C = B D = m$ và $C D = n$ là các giá trị cố định.

Ta có
$m (N C + N D) = n \cdot B N \Rightarrow N C + N D = \frac{n}{m} \cdot B N .$
Suy ra $\frac{N C + N D}{M N} = \frac{n}{m} \cdot \frac{B N}{M N} .$ Ta đưa về tìm giá trị nhỏ nhất của $\frac{B N}{M N} .$ \medskip

Xét phương tích từ $B$ đến $γ_{2}$ thì $B M \cdot B N = B K \cdot B A = c$ là hằng số nên
$(B N - M N) B N = c$ .
Do đó $\frac{M N}{B N} = 1 - \frac{c}{B N^{2}}$ nên
$\frac{B N}{M N} min \Leftrightarrow \frac{M N}{B N} max \Leftrightarrow \frac{c}{B N^{2}} min \Leftrightarrow B N^{2} max .$
Dễ thấy $max B N = A B$ , xảy ra khi $N \equiv A$ hay $M \equiv K .$ Khi đó $\frac{N C + N D}{M N} = \frac{A C + A D}{A K} = 2$ chính là giá trị nhỏ nhất cần tìm.

Giới thiệu sách: Đề thi học sinh giỏi các nước.

Leave a reply

Gửi các bạn một số Booklet của các nước.

1/ Đề thi Trung Quốc. các năm 2010, 2011 – 2014 có sách bản quyền. Các năm về sau chưa thấy sách.

Mathematical_Olympiad_in_China-Problems_and_Solutions 2003 2006

mathematic-olympiad-in-china2007-2008-problems-and-solutions

2/ Đề thi Bulgari.

Một số sách đề thi Bulgari có nhiều bài hay được lấy làm đề thi tuyển sinh vào 10, đề thi học sinh giỏi trong nước.

Bulgarian Mathematical Competitions 2003-2006

BulgarianMO1960_2008

3/Đề thi khu vực Balkan https://vi.wikipedia.org/wiki/Balkan

Balkan MO 2008-20 EN with solutions

(Còn nữa)

Phương pháp chứng minh phản chứng (P2)

Leave a reply

Bài 1.

Cho tập $B = 1, 2, 3, \dots, 16$ . Người ta ghi các số của tập B thành một vòng tròn (mỗi số ghi một lần). Hỏi có cách ghi để tổng thỏa:

a/ Tổng của hai số kế nhau bất kì lớn hơn hoặc bằng 17 được không? Tại sao?

b/ Tổng của ba số kế nhau bất kì lớn hơn 24 được không? Tại sao?

Lời giải

a/ Giả sử tồn tại cách ghi thỏa mãn. Khi đó, gọi 2 số kề với 1 là a và b.

Theo giả thiết, ta có:

${\begin{cases} 1 + a ⩾ 17 \\ 1 + b ⩾ 17 \end{cases} \Rightarrow {\begin{cases} a ⩾ 16 \\ b ⩾ 16 \end{cases} \Rightarrow$ Mâu thuẫn.

Vậy không tồn tại cách ghi thỏa mãn.

b/ Giả sử tồn tại cách ghi thỏa mãn.

Khi đó, ta tách số 16 ra và chia 15 số còn lại thành 5 bộ 3 số kề nhau. Và tổng của 16 số này phải lớn hơn hoặc bằng: $16 + 5 \cdot 25 = 141$

Mà $1 + 2 + 3 + \dots 16 = 136 \Rightarrow$ Mâu thuẫn

Vậy không tồn tại cách ghi thỏa mãn.

Bài 2.

Có tồn tại hay không một cách điền các số $0, 1, 2, 3, \dots, 9$ vào các đỉnh của một đa giác 10 đỉnh sao cho hiệu hai số ở hai đỉnh kề nhau chỉ có thể nhận một trong các giá trị sau: $- 5, - 4, - 3, 3, 4, 5$ .

Lời giải

Giả sử có cách xếp thỏa mãn.

Xét các số $0, 1, 2, 8, 9$ không thể đứng kề nhau và có đúng 10 số nên 5 số còn lại phải đứng xen kẽ với 5 số $0, 1, 2, 8, 9$ .

Xét số 7:

Khi đó hai số kề số 7 phải thuộc tập hợp ${0, 1, 2, 8, 9}$

Mà theo giả thiết 2 đỉnh kề nhau bất kì nhận một trong các giá trị – 3, – 4, – 5, 3, 4 hoặc 5 nên 2 số kề nhau với 7 đều bằng 2 $\Rightarrow$ Mâu thuẫn.

Vậy không có cách xếp nào thỏa mãn.

Bài 3.

Trong mặt phẳng tọa độ thì một điểm mà hoành độ và tung độ đều là các số nguyên được gọi là điểm nguyên. Chứng minh rằng không tồn tại tam giác đều nào mà các đỉnh đều là điểm nguyên.

Lời giải

Giả sử tồn tại tam giác đều có các đỉnh là các điểm nguyên.

Xét hình chữ nhật có các đỉnh là các điểm nguyên, sao cho đỉnh của tam giác đều thuộc cạnh của hình chữ nhật. Khi đó dễ dàng suy ra diện tích tam giác đều là số hữu tỷ.

Ta có diện tích tam giác đều $S = \frac{a^{2} \sqrt{3}}{4}$ với $a^{2} = x^{2} + y^{2}$ là số nguyên, $\sqrt{3}$ là số vô tỷ

Do đó, S là số vô tỉ $\Rightarrow$ Mâu thuẫn $\Rightarrow$ đpcm.

Bài 4.

Điền các số 1,2,3,…,121 vào một bảng ô vuông kích thước $11 \times 11$ sao cho mỗi ô chứa một số. Tồn tại hay không một cách điền sao cho hai số tự nhiên liên tiếp sẽ được điền vào hai ô có chung một cạnh và các tất cả các số chính phương thì nằm trong cùng một cột?

Lời giải

Giả sử tồn tại một cách điền số vào các ô thỏa yêu cầu đặt ra.

Khi đó bảng ô vuông được chia thành hai phần ngăn cách nhau bởi cột điền các số chính phương. Một phần chứa $11 n$ ô vuông $1 \times 1$ , và phần còn lại chứa $110 - 11 n$ ô vuông $1 \times 1$ , với $0 \leq n \leq 5.$

Nhận thấy rằng các số tự nhiên nằm giữa hai số chính phương liên tiếp $a^{2}$ và $(a + 1)^{2}$ sẽ cùng nằm về một phần và các số tự nhiên nằm giữa $(a + 1)^{2}$ và $(a + 2)^{2}$ sẽ nằm ở phần còn lại.

Ta có số lượng các số tự nhiên nằm giữa 1 và 4, 4 và 9, 9 và 16,…,100 và 121 lần lượt là $2, 4, 6, 8, \dots, 20$ .

Do đó một phần sẽ chứa $2 + 6 + 10 + 14 + 18 = 50$ số, phần còn lại chứa $4 + 8 + 12 + 16 + 20 = 60$ số.

Cả 50 và 60 đều không chia hết cho 11 $\Rightarrow$ Mâu thuẫn.

Vậy không tồn tại cách điền số thỏa yêu cầu đề bài.

Bài 5.

Mỗi phần tử của bảng vuông $25 \times 25$ hoặc là $+ 1$ hoặc $- 1$ . Gọi $a_{i}$ là tích của tất cả các phần tử của hàng thứ $i$ và $b_{j}$ là tích của tất cả các phần tử của cột thứ $j$ . Chứng minh rằng $a_{1} + b_{1} + \dots + a_{25} + b_{25} \neq 0$

Lời giải

Giả sử $a_{1} + b_{1} + \dots + a_{25} + b_{25} = 0$ .

Vì mỗi ô vuông chứa -1 hoặc 1 nên $a_{i}, b_{i} \in {1, - 1}$

Do đó trong 50 tích $a_{i}, b_{i} (i = \overset{―}{1, 25})$ sẽ có 25 tích có giá trị -1 và 25 tích có giá 1.

Khi thay thế một phần tử -1 trong bảng bằng 1 thì số các tích ngang dọc có giá trị -1 sẽ tăng 2 hoặc giảm 2 hoặc không thay đổi. Như vậy số các tích $a_{i}, b_{i}$ có giá trị -1 luôn là số lẻ (1)

Ta sẽ tiếp tục thay thế các phần tử -1 trong bảng bằng 1 cho đến khi tất cả các phần tử trong bảng đều bằng 1 thì khi đó số các tích ngang dọc $a_{i}, b_{i}$ có giá trị -1 là 0 $\Rightarrow$ Mâu thuẫn với (1) $\Rightarrow$ đpcm.

Bài tập số chính phương – Lớp 9

Leave a reply

Bài 1. Chứng minh rằng

a) Một số chính phương chia 3 dư 0 hoặc 1.
b) Một số chính phương chia 4 dư 0 hoặc 1.
c) Một số chính phương chia 5 dư 0, 1 hoặc 4.
Bài 2. Chứng minh rằng một số là số chính phương khi và chỉ khi số ước của số đó là một số lẻ.

Bài 3. Chứng minh rằng nếu tổng hai số chính phương chia hết cho 3 thì tích của nó sẽ chia hết 81.

Bài 4. Chứng minh rằng với $n$ là số tự nhiên thì $3 n - 1, 5 n + 2, 5 n - 2, 7 n - 2, 7 n + 3$ không phải là số chính phương.

Bài 5. Tìm tất cả các số tự nhiên $n$ sao cho $n {.2}^{n + 1} + 1$ là một số chính phương.

Bài 6. Chứng minh rằng nếu $x^{2} + 2 y$ là một số chính phương với $x, y$ nguyên dương thì $x^{2} + y$ là tổng của hai số chính phương.

Bài 7. Chứng minh rằng nếu $3 x + 4 y, 3 y + 4 x$ là các số chính phương thì $x, y$ đều chia hết cho 7.

Bài 8. Cho các số nguyên dương $a, b$ . Giả sử các số $a + 2 b, b + 2 a$ đều là bình phương của một số nguyên thì $a$ và $b$ đều chia hết cho 3.

Bài 9. Cho các số tự nhiên $a, b, c$ thỏa: $a + 2 b, b + 2 c, c + 2 a$ đều là bình phương của một số tự nhiên.
a)Chỉ ra một bộ số thỏa đề bài.
b) Giả sử trong 3 số $a + 2 b, b + 2 c, c + 2 a$ có một số chia hết cho 3. Chứng minh rằng: $P = (a - b) (b - c) (c - a)$ chia hết cho 27.

Bài 10. Chứng minh rằng nếu $\overset{―}{a b c}$ là một số nguyên tố thì $b^{2} - 4 a c$ không phải là một số chính phương.

Bài 11. Tìm tất cả các số tự nhiên $n \geq 2$ sao cho tồn tại $n$ số nguyên liên tiếp mà tổng của chúng là một số chính phương.

Bài 12. Tìm $d$ sao cho với mọi $a, b \in 2, 5, d$ thì $a b - 1$ là một số chính phương.

Bài 13. Chứng minh rằng với mọi $d$ thì tập $2, 5, 13, d$ luôn tồn tại hai số $a, b \in 2, 5, 13, d$ sao cho $a b - 1$ không phải là số chính phương.

Bài 14. Chứng minh rằng nếu tích của hai số nguyên tố cùng nhau là một số chính phương thì mỗi số cũng là số chính phương.

Bài 15. Cho các số nguyên dương $a, b$ thỏa $2 a^{2} + a = 3 b^{2} + b$ .

a)Tìm $a, b$ biết $a$ và $b$ là hai số nguyên tố cùng nhau.
b) Chứng minh $a - b$ và $2 a + 2 b + 1$ là các số chính phương.

Bài 16. Cho các số nguyên $a, b, c$ thỏa $a + b + c$ chia hết cho 6 và $a^{2} + b^{2} + c^{2}$ chia hết cho 36. Đặt $A = a^{3} + b^{3} + c^{3}$

a) Chứng minh rằng A chia hết cho 8.
b) A có chia hết cho 27 không? Tại sao?

Bài 17. Cho $a, b, c$ là ba số nguyên dương thỏa $\frac{1}{a} - \frac{1}{b} = \frac{1}{c}$ . Gọi $d$ là ước chung lớn nhất của ba số đó . Chứng minh rằng $d (b - a)$ là số chính phương.

Bài 18. Tìm tất cả các số nguyên dương $n$ sao cho $T = 2^{n} + 3^{n} + 4^{n}$ là số chính phương.

Bài 19. Tìm tất cả các cặp số nguyên $a, b$ sao cho $3^{a} + 7^{b}$ là một số chính phương.

Bài 20. (Chuyên Thái Bình 2021) Giả sử $n$ là số tự nhiên thỏa mãn điều kiện $n (n + 1) + 7$ không chia hết cho 7. Chứng minh rằng $4 n^{3} - 5 n - 1$ không là số chính phương.

Bài 21 (Thanh Hóa – Chuyên Tin 2021) Cho số tự nhiên $n ⩾ 2$ và số nguyên tố $p$ thỏa mãn $p - 1$ chia hết cho $n$ và $n^{3} - 1$ chia hết cho $p$ . Chứng minh rằng $n + p$ là một số chính phương.

Bài 22 (Chuyên Lê Khiết) Cho các số nguyên tố $p, q$ thỏa mãn $p + q^{2}$ là số chính phương. Chứng minh rằng
a) $p = 2 q + 1$ .
b) $p^{2} + q^{2021}$ không phải là số chính phương.

Bài 23 (Kiên Giang 2021) Cho $m, p, r$ là các số nguyên tố thỏa mãn $m p + 1 = r$ . Chứng minh rằng $m^{2} + r$ hoặc $p^{2} + r$ là số chính phương.

Bài 24. (Chuyên Tiền Giang) Cho $m, n$ là các số nguyên dương sao cho $m^{2} + n^{2} + m$ chia hết cho $m n$ . Chứng minh rằng $m$ là số chính phương.

Bài 25.(Chuyên Phổ thông Năng khiếu – ĐHQG thành phố Hồ Chí Minh 2021-2022)

a) Tìm tất cả số tự nhiên $n$ sao cho $(2 n + 1)^{3} + 1$ chia hết cho $2^{2021}$ .
b) Cho số tự nhiên $n$ và số nguyên tố $p$ sao cho $a = \frac{2 n + 2}{p}$ và $b = \frac{4 n^{2} + 2 n + 1}{p}$ là các số nguyên. Chứng minh rằng $a$ và $b$ không đồng thời là các số chính phương.

Phương pháp ánh xạ trong các bài toán tổ hợp

Leave a reply

Thầy Nguyễn Tăng Vũ

1/ Lý thuyết:

Cho $A$ và $B$ là hai tập hợp hữu hạn.

Nếu có một đơn ánh $f : X ⟶ Y$ thì $| X | \leq | Y | .$
Nếu có một toàn ánh $f : X ⟶ Y$ thì $| X | \geq | Y | .$
Nếu có một song ánh $f : X ⟶ Y$ thì $| X | = | Y | .$

2/ Bài tập:

Bài 1.

Cho $X = 1, 2, . ., n$ . Một tập con $S = s_{1}, s_{2}, \dots, s_{k}$ của X ( $s_{1} < s_{2} < \dots < s_{k}$ ) được gọi là \textit{m- tách được} $(m \in N)$ nếu $s_{i} - s_{i - 1} \geq m; i = 1, 2, \dots, k$ . Có bao nhiêu tập con m- tách được gồm $k$ phần tử của X, trong đó $0 \leq k \leq n - (m - 1) (k - 1)$ .

Lời giải

Gọi A là tập tất cả các tập con m- tách được gồm $k$ phần tử của X và B là tập tất cả các tập con gồm k phần tử của tập $Y = {1, 2, \dots, n - (k - 1) (m - 1)}$ .

Ta xây dựng song ánh từ A đến B như sau: Với $S = {s_{1}, s_{2}, \dots, s_{k}} \in A$ ( $s_{1} < s_{2} < \dots < s_{k}$ ) lấy tương ứng $f (S) = {s_{1}, s_{2} - (m - 1), s_{3} - 2 (m - 1), \dots, s_{k} - (k - 1) (m - 1)}$ . Dễ chứng minh đây là một song ánh. Từ đó có $C_{n - (k - 1) (m - 1)}^{k}$ tập thoả yêu cầu đề bài.

Bài 2.

Cho $X = 1, 2, \dots, n$ , với mỗi tập con khác rỗng $A_{i} = a_{1}, a_{2}, \dots, a_{i}$ (không mất tổng quát giả sử $a_{1} > a_{2} > \dots > a_{i}$ ) ta định nghĩa tổng hỗn tạp của $A_{i}$ là số $m (A_{i}) = a_{1} - a_{2} + a_{3} - \dots \pm a_{i}$ . Tính $\sum_{A_{i} \subset X} m (A_{i})$ .

Lời giải

Gọi B là tập tất cả các tập con không chứa phần tử n của X và C là tập tất cả các tập con có chứa phần tử n của X.

Ta xây dựng song ánh từ B đến C như sau: Với $S = {s_{1}, s_{2}, \dots, s_{k}} \in B$ ( $s_{1} < s_{2} < \dots < s_{k} < n$ ) lấy tương ứng $f (S) = {s_{1}, s_{2}, \dots, s_{k}, n},$ nhận thấy $f (S) \in C$ . Dễ chứng minh đây là một song ánh.

Ta có: $| B | = | C | = 2^{n - 1}; B \cup C = \emptyset; B \cap C = X$

Và $m (S) + m (f (S)) = n$

Do đó: $\sum_{A_{i} \subset X} m (A_{i}) = \sum_{B_{i} \subset B} m (B_{i}) + \sum_{C_{i} \subset C} m (C_{i}) = n \cdot 2^{n - 1}$

Bài 3.

Cho $X = 1, 2, \dots, n$ . Một tập con A của X được gọi là tập béo nếu mỗi phần tử của A đều không nhỏ hơn số phần tử của nó. Tập rỗng cũng là một tập béo. Đặt $a_{n}$ là số các tập béo của X mà trong mỗi tập không chứa hai số liên tiếp, $b_{n}$ là số các tập con của X mà hai phần tử bất kỳ hơn kém nhau ít nhất 3 đơn vị. Chứng minh $a_{n} = b_{n} .$

Lời giải

Gọi A là họ các tập béo thỏa yêu cầu đề bài, B là họ các các tập con của X có tính chất hai phần tử bất kỳ hơn kém nhau 3 đơn vị. Ta thiết lập một ánh xạ $f$ đi từ A đến B như sau: giả sử $x = {a_{1}, a_{2}, \dots, a_{k}} \in A$ , ta có thể giả sử $k \leq a_{1} < a_{2} < a_{3} < \dots < a_{k} \leq n$ . Đặt $b_{1} = a_{1} - k + 1, b_{2} = a_{2} - k + 2, \dots, b_{k} = a_{k}$ . Khi đó $a_{i + 1} \geq a_{i} + 2, i = 1, 2, \dots, k - 1.$

Suy ra $a_{i + 1} - a_{i} \geq 2$ do đó $b_{i + 1} - b_{i} \geq 3$ và $b_{1} \geq 1, b_{k} \leq n .$ Định nghĩa $f (x) = y = {b_{1}, b_{2}, \dots, b_{k}}$ , suy ra $y \in B$ . Vậy $f$ là một ánh xạ, hơn nữa dễ thấy $f$ là một song ánh do đó ta có điều cần chứng minh.

Bài 4.

Cho số nguyên dương $n$ và $d$ là một ước dương của $n$ . Gọi S là tập tất cả những bộ $(x_{1}, x_{2}, \dots, x_{n})$ nguyên dương thỏa $0 \leq x_{1} \leq x_{2} \leq \dots \leq x_{n} \leq n$ và $d | x_{1} + x_{2} + \dots + x_{n}$ . Chứng minh rằng có đúng một nửa các phần tử của S có tính chất $x_{n} = n$ .

Lời giải

$(x_{1}, x_{2}, \dots, x_{n - 1}, x_{n}) \in S$ mà $x_{n} \neq n$ ta cho tương ứng với bộ $(x_{1} + 1, x_{2} + 2, \dots, x_{n - 1} + 1, x_{n} + 1)$ , với $(x_{1}, x_{2}, \dots, x_{n - 1}, n) \in S$ ta cho tương ứng với bộ $(0, x_{1}, \dots, x_{n - 1}) .$ \

Dễ chứng minh $f$ là một song ánh, $f$ hoán vị S và $f (S) = S .$ Vì tổng tất cả các phần tử của các bộ trong S và $f (S)$ là như nhau trong khi tương ứng thứ nhất tăng tăng tổng này lên $n$ đơn vị, tương ứng thứ hai giảm tổng này đi $n$ đơn vị nên số lần xuất hiện của hai tương ứng này là như nhau. Từ đó suy ra điều cần chứng minh

Bài 5.

Gọi $a_{n}$ là số các xâu nhị phân độ dài $n$ không chứa ba bit 0, 1, 0 liên tiếp. Gọi $b_{n}$ là số các xâu nhị phân độ dài $n$ chứa bốn bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng minh rằng $b_{n + 1} = 2 a_{n}$ với mọi số nguyên dương $n$ .

Lời giải

Gọi $A_{n}, B_{n}$ lần lượt là tập các xâu nhị phân độ dài $n$ thỏa điều kiện thứ nhất và thứ hai. Với mỗi xâu nhị phân $(x_{1}, x_{2}, \dots, x_{n})$ ta cho tương ứng với một xâu nhị phân $(y_{0}, y_{1}, \dots, y_{n})$ xác định bởi $y_{0} = 0$ và $y_{i} = x_{1} + x_{2} + \dots + x_{i} m o d 2, i = 1, 2, \dots, n . (*)$

Khi đó $x_{i} = y_{i} + y_{i - 1} m o d 2, i = 1, 2, \dots, n .$

Dễ thấy (*) là một song ánh giữa tập tất cả các xâu nhị phân độ dài $n$ và tập tất cả các xâu nhị phân độ dài $n + 1$ trong đó có bit đầu tiên là 0. Hơn nữa xâu nhị phân $(x_{1}, x_{2}, \dots, x_{n})$ có 3 bit 0,1,0 liên tiếp theo thứ tự này khi và chỉ khi xâu nhị phân tương ứng $(y_{0}, y_{1}, \dots, y_{n})$ có 4 bit liên tiếp theo thứ tự là 0,0,1,1 hoặc 1,1,0,0. Nói cách khác một xâu nhị phân thuộc $A_{n}$ sẽ tương ứng với một xâu nhị phân thuộc $B_{n + 1}$ và bắt đầu bằng bit 0. Vì số xâu nhị phân thuộc vào $B_{n + 1}$ bắt đầu bằng bit 0 đúng bằng một nửa số xâu nhị phân thuộc vào $B_{n + 1}$ do đó ta có $b_{n + 1} = 2 a_{n}$ (điều phải chứng minh).

Định lý Ceva và Menelaus – Phần 3

Leave a reply

Phần 2

Ví dụ 10. (USAMO 2012) Gọi $P$ là một điểm thuộc miền trong tam giác $A B C$ và $d$ là một đường thẳng qua $P$ . Đường thẳng đối xứng của $P A$ qua $d$ cắt $B C$ tại $A^{'}$ ; các điểm $B^{'}, C^{'}$ được xác định tương tự. Chứng minh rằng $A^{'}, B^{'}, C^{'}$ thẳng hàng.

Lời giải

Ta có $\frac{A^{'} B}{A^{'} C} = \frac{S_{A^{'} P C}}{S_{A^{'} P C}} = \frac{P B \cdot \sin A^{'} P B}{P C \cdot \sin A^{'} P C}$ . (1)
Tương tự ta cũng có $\frac{B^{'} C}{B^{'} A} = \frac{P C \cdot \sin B^{'} P C}{P A \cdot \sin B^{'} P A}$ và $\frac{C^{'} A}{C^{'} B} = \frac{P A \cdot \sin C^{'} P A}{P B \cdot \sin C^{'} P B}$ . (2)
Theo tính chất đối xứng ta có $\sin A^{'} P B = \sin B^{'} P A, \sin A^{'} P C = \sin C^{'} P A, \sin B^{'} P C = \sin C^{'} P B$ . (3)
Từ (1), (2), (3) ta có $\frac{A^{'} B}{A^{'} C} \cdot \frac{B^{'} C}{B^{'} A} \cdot \frac{C^{'} A}{C^{'} B} = 1$
Do đó $A^{'}, B^{'}, C^{'}$ thẳng hàng.

Ví dụ 11. Cho tam giác $A B C$ . Ba đường tròn $w_{a}, w_{b}, w_{c}$ lần lượt đi qua các cặp đỉnh $B, C$ ; $C, A$ ; và $A, B$ . Gọi $D, E, F$ lần giao điểm thứ hai của ba đường tròn này. Đường thẳng qua $D$ vuông góc với $A D$ cắt $B C$ tại $X$ ; các điểm $Y, Z$ được xác định tương tự. Chứng minh rằng $X, Y, Z$ thẳng hàng.

Lời giải

Ta có $\frac{X B}{X C} = \frac{D B \sin X D B}{D C \sin X D C}$ ;
$\frac{D B}{D C} = \frac{R_{c} \sin D A B}{R_{b} \sin D A C}$ và $\frac{\sin A D B}{\sin X D C} = \frac{\cos A D B}{\cos A D C}$ ;
Tương tự cho các phân thức $\frac{Y C}{Y A}, \frac{Z A}{Z B}$ .
Mặt khác ta có $A D, B E, C Z$ đồng quy tại tâm đẳng phương nên $\frac{\sin D A B}{\sin D A C} \cdot \frac{\sin E B C}{\sin E B A} \cdot \frac{\sin F C A}{\sin F C B} = 1$ .
Từ đó ta có $\frac{X B}{X C} \cdot \frac{Y C}{Y A} \cdot \frac{Z A}{Z B} = 1$ .
Vậy $X, Y, Z$ thẳng hàng.

Ví dụ 12. (IMO shortlist 2013) Cho tam giác $A B C$ nhọn. Gọi $O$ là tâm ngoại tiếp và $H$ là trực tâm tam giác $A B C$ . Chứng minh rằng tồn tại các điểm $D, E, F$ thuộc các cạnh $B C, A C, A B$ thỏa: $O D + D H = O E + E H = O F + F H$ và $A D, B E, C F$ đồng quy.

Lời giải

Gọi $H_{1}$ là điểm đối xứng của $H$ qua $B C$ , thì $H_{1} \in (O)$ .
Gọi $D$ là giao điểm của $O H_{1}$ và $B C$ , khi đó $O D + D H = O D + D H_{1} = O H_{1} = R$ .
Các điểm $E, F$ được xác định tương tự ta có $O D + D H = E O + E H = O F + F H$ .
Ta cần chứng minh $A D, B E, C F$ đồng quy bằng định lý Ceva dạng sin.
Ta có $\frac{D B}{D C} = \frac{S_{B H_{1} D}}{S_{C H_{1} D}} = \frac{B H_{1} . \sin B H_{1} D}{C H_{1} \sin C H_{1} D} = \frac{B H}{C H} \frac{\sin B}{\sin C}$
Các đẳng thức kia tương tự, nhân lại ta có điều cần chứng minh.

Ví dụ 13. Cho tam giác $A B C$ khác tam giác cân nội tiếp đường tròn $w$ , các đường trung tuyến từ $A, B, C$ cắt $w$ tại $A^{'}, B^{'}, C^{'}$ . Gọi $A_{1}$ là giao điểm của tiếp tuyến tại $A^{'}$ với $B C$ ; các điểm $B_{1}, C_{1}$ được xác định tương tự. Chứng minh rằng $A_{1}, B_{1}, C_{1}$ thẳng hàng.

Lời giải

Ta có $A_{1} B \cdot A_{1} C = A_{1} A^{' 2} \Rightarrow \frac{A_{1} B}{A_{1} C} = \frac{A_{1} B^{2}}{A_{1} A^{' 2}} = \frac{\sin^{2} A_{1} A^{'} B}{\sin^{2} A_{1} B A^{'}} = \frac{\sin^{2} A^{'} A B}{\sin^{2} A^{'} A C}$ .
Chứng minh tương tự cho các đẳng thức kia và nhân lại, áp dụng ceva sin cho 3 đường $A A^{'}, B B^{'}, C C^{'}$ đồng quy.

Bài tập rèn luyện

Bài 1. Cho tứ giác $A B C D$ , gọi $I$ là giao điểm của $A C$ và $B D$ , $K$ là giao điểm của $A B$ và $C D$ . Đường thẳng $I K$ cắt các cạnh $B C$ và $A D$ tại $P, Q$ .
Chứng minh rằng: $\frac{\overset{―}{I P}}{\overset{―}{I Q}} = - \frac{\overset{―}{K P}}{\overset{―}{K Q}}$

Bài 2. Cho tứ giác $A B C D$ ngoại tiếp đường tròn $w$ , $w$ tiếp xúc với các cạnh $A B, B C, C D, D A$ lần lượt tại $M, N, P, Q$ . Chứng minh $M Q, B D, P N$ song song hoặc đồng quy.

Bài 3. Cho tam giác $A B C$ , đường phân giác ngoài góc $A$ cắt đường thẳng vuông góc với $B C$ kẻ từ $B$ và $C$ lần lượt tại $D$ và $E$ . Chứng minh rằng $B E, C D$ và $A O$ đồng quy, với $O$ là tâm đường tròn ngoại tiếp tam giác $A B C$ .

Bài 4. Gọi $I$ là tâm đường tròn nội tiếp của tam giác $A B C$ . Gọi $A^{'}, B^{'}, C^{'}$ lần lượt là điểm đối xứng của $I$ qua $B C, A C, A B$ . Chứng minh rằng $A A^{'}, B B^{'}, C C^{'}$ đồng quy.

Bài 5. Cho tam giác $A B C$ . Về phía ngoài tam giác dựng các hình vuông $B C D E, A C F G, A B H K$ với tâm lần lượt là $O_{1}, O_{2}, O_{3}$ . Chứng minh $A O_{1}, B O_{2}, C O_{3}$ đồng quy.

Bài 6. Cho tam giác $A B C$ không cân tại $A$ . $M$ là một điểm nằm trong tam giác thỏa $∠ A M B - ∠ A C B = ∠ A M C - ∠ A B C$ . Chứng minh rằng đường thẳng nối tâm đường tròn nội tiếp tam giác $A M B$ và $A M C$ đi qua một điểm cố định.

Bài 7. Cho tam giác $A B C$ và điểm $M$ nằm trong tam giác. $A M, B M, C M$ cắt $B C, A C, A B$ lần lượt tại $A^{'}, B^{'}, C^{'}$ . Gọi $P$ là giao điểm của $B B^{'}$ và $A^{'} C^{'}$ ; $Q$ là giao điểm của $C C^{'}$ và $A^{'} B^{'}$ . Chứng minh rằng: $∠ M A P = ∠ M A Q \Leftrightarrow ∠ M A B = ∠ M A C$

Bài 8. Cho tam giác $A B C$ . Gọi $O$ là tâm đường tròn ngoại tiếp tam giác $A B C$ ; $O_{1}, O_{2}, O_{3}$ lần lượt là tâm ngoại tiếp các tam giác $B C O, A C O$ và $A B O$ . Chứng minh rằng $A O_{1}, B O_{2}, C O_{3}$ đồng quy tại một điểm.(Điểm Kosnita)

Bài 9. Cho tam giác $A B C$ có $M$ là trung điểm cạnh $A B$ . $C E$ là phân giác góc $∠ A C B$ . $D$ thuộc tia đối của tia $C A$ sao cho $C D = C B$ . Gọi $K$ là giao điểm của $D M$ và $C E$ . Chứng minh rằng $∠ K B C = ∠ B A C$ .

Bài 10. Cho tam giác $A B C$ nhọn nội tiếp đường tròn $(O)$ và có trực tâm $H$ . Gọi $A_{o}, B_{o}, C_{o}$ là trung điểm của $B C, A C, A B$ . $A_{1}$ là giao điểm của $A A_{o}$ và $(O)$ , $A_{2}$ là giao điểm của $H$ qua $A_{o}$ ; đường thẳng $A_{1} A_{2}$ cắt $B C$ tại điểm $S_{a}$ ; các điểm $S_{b}, S_{c}$ được xác định tương tự. Chứng minh $S_{a}, S_{b}, S_{c}$ thẳng hàng.

Bài 11. Cho tam giác $A B C$ . Các điểm $A_{1}, B_{1}, C_{1}$ lần lượt thuộc các cạnh $B C, A C, A B$ sao cho các đường thẳng $A A_{1}, B B_{1}, C C_{1}$ đồng quy.

a) Gọi $A_{2}$ là điểm đối xứng của $A_{1}$ qua trung điểm cạnh $B C$ ; các điểm $B_{2}, C_{2}$ được xác định tương tự. Chứng minh rằng $A A_{2}, B B_{2}, C C_{2}$ cũng đồng quy.
b) Đường tròn ngoại tiếp tam giác $A_{1} B_{1} C_{1}$ cắt $B C, A C, A B$ tại $A_{3}, B_{3}, C_{3}$ . Chứng minh $A A_{3}, B B_{3}, C C_{3}$ đồng quy.

Bài 12. Cho tam giác $A B C$ . Các điểm $A_{1}, B_{1}, C_{1}$ lần lượt thuộc các cạnh $B C, A C$ và $A B$ . Gọi $G_{a}, G_{b}, G_{c}$ lần lượt là trọng tâm các tam giác $A B_{1} C_{1}, B C_{1} A_{1}, C A_{1} B_{1}$ . Chứng minh rằng $A G_{a}, B G_{b}, C G_{c}$ đồng quy khi và chỉ khi $A A_{1}, B B_{1}, C C_{1}$ đồng quy.

Bài 13.(IMO SL 1995) Đường tròn nội tiếp tam giác $A B C$ tiếp xúc với các cạnh $B C, A C, A B$ tại $D, E, F$ . $X$ là điểm bên trong tam giác $A B C$ sao cho đường tròn nội tiếp tam giác $X B C$ tiếp xúc với $B C$ tại $D$ , tiếp xúc với $C X, B X$ tại $Y, Z$ . Chứng minh rằng $E, F, Z, Y$ cùng thuộc một đường tròn.

Bài 14. Cho $P$ là điểm thuộc miền trong của tam giác $A B C$ . Gọi $D, E, F$ là hình chiếu của $P$ trên $B C, A C, A B$ . Gọi $X$ là điểm trên $E F$ sao cho $P X ⊥ P A$ ; các điểm $Y, Z$ được xác định tương tự. Chứng minh rằng các điểm $X, Y, Z$ thẳng hàng.

Bài 15. (IMO SL 2006) Cho tam giác $A B C$ có $∠ A C B < ∠ B A C < 90^{o}$ .Lấy $D$ là điểm thuộc cạnh $A C$ sao cho $B D = B A$ . Đường tròn nội tiếp tam giác $A B C$ tiếp xúc với $A B$ tại $K$ và $A C$ tại $L$ . Gọi $J$ là tâm đường tròn nội tiếp tam giác $B C D$ . Chứng minh rằng đường thẳng $K L$ chia đôi đoạn $A J$ .

Bài 18. Cho tam giác $A B C$ nội tiếp đường tròn tâm $O$ . Gọi $A_{1}$ là điểm đối xứng của $A$ qua $O$ , gọi $A_{2}$ là điểm đối xứng của $O$ qua $B C$ ; các điểm $B_{1}, B_{2}, C_{1}, C_{2}$ được xác định tương tự. Chứng minh rằng đường tròn ngoại các tam giác $O A_{1} A_{2} O B_{1} B_{2}$ và $O C_{1} C_{2}$ cùng đi qua 2 điểm.

Bài 19. Cho tam giác $A B C$ , đường tròn tâm $I$ nội tiếp tam giác và tiếp xúc với các cạnh $B C, A C, A B$ tại $D, E, F$ . $X$ là điểm nằm trong tam giác $D E F$ , gọi $A_{1}, A_{2}$ là giao điểm của $D X$ với $E F$ và $(I)$ ; các điểm $B_{1}, B_{2}$ ; $C_{1}, C_{2}$ được xác định tương tự.

a) Chứng minh $A A_{2}, B B_{2}, C C_{2}$ đồng quy tại $Y$ ; $A A_{1}, B B_{1}, C C_{1}$ đồng quy tạu $Z$ .
b) Chứng minh $X, Y, Z$ thẳng hàng.

Bài 20. Cho một đường tròn với hai dây $A B$ và $C D$ không song song. Đường vuông góc với $A B$ kẻ từ $A$ cắt đường vuông góc với $C D$ kẻ từ $C$ và từ $D$ lần lượt tại $M, P$ . Đường vuông góc với $A B$ kẻ từ $B$ cắt đường vuông góc với $C D$ kẻ từ $C$ và $D$ lần lượt tại $Q$ và $N$ . Chứng minh rằng các đường thẳng $A D, B C, M N$ đồng quy và các đường thẳng $A C, B D, P Q$ cũng đồng quy.

Bài 21. (IMO shortlis 2011) Cho $A B C$ là một tam giác với đường tròn nội tiếp tâm $I$ và đường tròn ngoại tiếp $(C)$ . $D$ và $E$ là giao điểm thứ hai của $(C)$ với các tia $A I$ và $B I$ tương ứng. $D E$ cắt $A C$ tại điểm $F$ , và cắt $B C$ tại điểm $G$ . $P$ là giao điểm của đường thẳng đi qua $F$ song song với $A D$ và đường thẳng qua $G$ song song với $B E$ . Giả sử rằng $K$ là giao điểm của các tiếp tuyến của $(C)$ tại $A$ và $B$ . Chứng minh rằng ba đường thẳng $A E, B D$ và $K P$ là song song hoặc đồng quy.

Bài 22. (China TST 2014) Cho tam giác $A B C$ nội tiếp đường tròn $(O)$ ; $H_{a}$ là chân đường cao hạ từ $A$ của tam giác $A B C$ . $A O$ cắt đường tròn ngoại tiếp tam giác $B O C$ tại $A^{'}$ . Gọi $D, E$ là hình chiếu của $A^{'}$ trên $A B$ và $A C$ ; và $O_{a}$ là tâm đường tròn ngoại tiếp tam giác $D E H_{a}$ ; Ta định nghĩa các điểm $H_{b}, O_{b}, H_{c}, O_{c}$ tương tự. Chứng minh rằng $H_{a} O_{a}, H_{b} O_{b}$ và $H_{c} O_{c}$ đồng quy.

Toán Việt

Chia sẻ và học hỏi

Thuật toán tham lam (Greedy Algorithms)

Trắc nghiệm phép đếm

Đáp án thi chọn Đội Tuyển Trường PTNK năm học 2013-2014

Đáp án thi chọn Đội Tuyển PTNK năm học 2012-2013

Đề thi chọn đội tuyển PTNK năm học 2010-2011

Giới thiệu sách: Đề thi học sinh giỏi các nước.

Phương pháp chứng minh phản chứng (P2)

Bài tập số chính phương – Lớp 9

Phương pháp ánh xạ trong các bài toán tổ hợp

Định lý Ceva và Menelaus – Phần 3