Hiện đã có đề TST January, xin mạn phép đăng để hoàn thiện topic.

Bài 1: Cho số nguyên dương $n$ và $S\subseteq\{0,1\}^n$ là một tập các xâu nhị phân độ dài $n$. Cho một số lượng lẻ các xâu (không nhất thiết phân biệt) $x_1,\, x_2,\, \dots ,\, x_{2k+1}\in S$, ta gọi "đa số" của chúng là xâu $y\in\{0,1\}^n$ sao cho bit thứ $i$ của $y$ là bit xuất hiện nhiều lần nhất trong số các bit thứ $i$ của $x_1,\, x_2,\, \dots ,\, x_{2k+1}$ (ví dụ, khi $n=4$, "đa số" của 0000, 0000, 1101, 1100, 0101 là 0100.)

Giả sử với số nguyên dương $k$ nào đó $S$ có tính chất $P_k$ sao cho đa số của bất kỳ $2k+1$ xâu trong $S$ (có thể có trùng lặp) cũng thuộc $S$. Chứng minh rằng $S$ cũng có tính chất $P_k$ với mọi $k$. 

Bài 2: Cho $ABCD$ là một tứ giác lồi, sao cho nó có hai đường chéo vuông góc nhau tại $H$, và không có hai cạnh kề nhau nào bằng nhau. Gọi $M,\ N$ lần lượt là các trung điểm các đoạn $BC, \, CD$. Các tia $MH$ và $NH$ cắt các đoạn $AD,\, AB$ lần lượt tại $S$ và $T$. Chứng minh rằng tồn tại điểm $E$ nằm bên ngoài $ABCD$ sao cho:

$\quad \bullet$ tia $EH$ chia đôi các góc $BES$, $TED$ và

$\quad \bullet$ $\angle BEN = \angle MED$.

Bài 3: Alice và Bob cùng chơi một trò chơi. Đầu tiên Alice bí mật chọn một tập hữu hạn $S$ các điểm nguyên trên mặt phẳng Đề-các. Sau đó, với mọi đường thẳng $\ell$ trên mặt phẳng mà song song với trục tung hay trục hoành hay có hệ số góc bẳng $\pm 1$, Alice nói cho Bob biết số điểm thuộc $S$ mà $\ell$ đi qua. Bob dành chiến thắng nếu anh ta có thể xác định được $S$. 

Chứng minh rằng nếu Alice chọn một tập $S$ có dạng

$$S = \{(x, y) \in \mathbb{Z}^2 \mid m \le x^2 + y^2 \le n\}$$

với số nguyên dương $m, n$ nào đó, Bob có thể thắng trò chơi này (Bob không hề biết rằng $S$ có dạng trên.)

Mình có ý tưởng cho câu b bài 5, đã đăng lên bên AOPS. Xin đăng lại ở đây; bạn đọc kiểm tra dùm.

Trước hết ta nhận thấy rằng nếu $d=2n-1$ thì tồn tại một bộ số như vậy:

$$n,n-1,n-2,\dots ,3,2,1,2,3,\dots ,n-2,n-1,n$$

Để hoàn tất chứng minh, ta chỉ ra rằng với mỗi $d$ nguyên dương, số $n$ nhỏ nhất sao cho $|S_n(d)|>0$ thì không nhỏ hơn $\frac{d+1}{2}$, bằng quy nạp.

Trường hợp $d=1$ hiển nhiên đúng.

Giả sử $k+1$ là số nguyên dương nhỏ nhất mà mệnh đề trên sai. Khi đó tồn tại một bộ $k+1$-số sao cho $n< \frac{k+2}{2}$. Khi đó phải tồn tại hai chỉ số $i,j$ sao cho $x_i=x_j$ và $|i-j|$ nhỏ nhất có thể. Khi đó mọi số nguyên nằm giữa $x_i,x_j$ chỉ xuất hiện đúng một lần, suy ra phải có một số $m$ nào đó xuất hiện ba lần. Ta thấy rằng bộ $k+1$-số bị cắt thành bốn đoạn (có thể rỗng) bởi $m$:

$$\{S_1\}m\{S_2\}m\{S_3\}m\{S_4\}$$

Câu 4a khá đơn giản. Ta chia mảnh đất thành $10$ hình chữ nhật kích thước $30\times 40$. Khi đó sẽ tồn tại một hình chữ nhật không tâm bồn hoa nào ở phần trong (không kể cạnh của nó). Khi đó phần trung tâm $25\times 35$ của hình chữ nhật này không cắt bồn hoa nào.

Uầy, bài toán rời rạc kia cũ quá rồi (nó là đề thi Liên xô cũ hay một nước đông âu nào đấy). Đã có người hỏi bài này gần một năm trước, xin trích lại câu trả lời:

*Edit: Sau khi đọc kỹ thì thấy hai lời giải hoàn toàn như nhau.

 

Giả sử ngược lại, không có hai điểm nào cùng màu cách nhau 1 đvđd.

Xét một điểm $O$ bất kỳ có màu vàng trên mặt phẳng. Vẽ đường tròn $(O,\, \sqrt{3})$. Lấy một điểm $P$ bất kỳ trên $(O)$. Dựng hình thoi $OAPB$ có cạnh bằng $1$ và có đường chéo là $OP$. Dễ thấy $OA=OB=AB=AC=BC=1$. Theo giả thiết, $A,B$ phải tô khác màu vàng và khác màu nhau. Do đó $P$ phải tô vàng. Từ đây suy ra tất cả các điểm trên $(O)$ phải tô vàng. Điều này trái với giả thiết vì dễ thấy tồn tại hai điểm trên $(O)$ có khoảng cách 1 đvđd.

P/s: Số $1$ có thể được thay bởi bất kỳ số thực dương nào.

Chà chà, anh không có kiến thức về số học đại số nên chịu. Đúng là ban đầu anh cũng có ý tưởng về số nguyên Gauss.

Ta có $xy=z^2+1$, Vì ước nguyên tố của $z^2+1$ chỉ có dạng đồng dư $1$ với $4$, nên $x,y$ cũng chỉ có các ước nguyên tố dạng $4k+1$. Khi đó, theo định lý Fermat-Euler về tổng hai bình phương, cộng với hằng đẳng thức Brahmagupta-Fibonacci nói rằng tích một đám có dạng $m^2+n^2$ cũng có dạng này, ta suy ra sự tồn tại của $a,b,c,d$. 

Nếu $p$ là số nguyên tố có dạng $3k+2$ thì không tồn tại số nguyên $x$ sao cho $x^{2}+3$ $\vdots$ $p.$

Để chứng minh mệnh đề trên, có một cách rất ngắn gọn của anh Trung như sau:

Đề bài thiếu điều kiện $p$ nguyên tố lẻ nhé.

Cách khác sơ cấp hơn:

Giả sử tồn tại số nguyên $x$ mà $p | x^2 + 3$, có thể giả sử $x$ lẻ vì nếu $x$ chẵn có thể thay $x$ bởi $p - x$.

Hay là $x = 2l + 1, l\in Z$.

$\Rightarrow p | 4(l^2 + l + 1)$.

$\Rightarrow p | l^2 + l + 1$. (1)

$\Rightarrow p | l^3 - 1$. (2).

Mặt khác theo định lý Fermat:

$p | l^{3k + 1} - 1$. (3).

Từ (2) và (3) suy ra $p | l - 1$, điều kiện này kết hợp với (1) suy ra $k | 3$ và điều này là mâu thuẫn.

Bài 4. Coi mỗi học sinh là một đỉnh, và nối hai đỉnh với nhau nếu và chì nếu hai học sinh tương ứng không là bạn của nhau. Như vậy, theo điều kiện của đề bài thì graph tạo thành sẽ không chứa một tam giác nào, đồng thời bậc của mỗi đỉnh tối thiểu là $\lfloor n/2 +1\rfloor -1=\lfloor n/2\rfloor$. Theo định lý 9 trong file này thì graph nói trên phải là một bipartite graph. Khi đó phần bù (complement) của nó phân hoạch được thành hai graph đầy đủ (đpcm).

2. (CMO 2000, Q6)

IMO 2007 Q3.

CMO 1996, Q2.

Đây là đề thi năm học 2014-15, đã được đăng tải trên diễn đàn.

Cho $a,b,c$ là các số nguyên dương thỏa mãn $\frac{1}{a}+\frac{2}{b}+\frac{4}{c}<1$. Tìm giá trị lớn nhất có thể của $\frac{1}{a}+\frac{2}{b}+\frac{4}{c}$ và giá trị nhỏ nhất có thể của $abc$.

Nguồn: https://artofproblem...sitive_integers

Hai người $A$ và $B$ chơi một trò chơi. $A$ có $20$ đồng xu, cân nặng khác nhau từng đôi một. $A$ biết thứ tự cân nặng của các đồng xu này nhưng $B$ thì không. Ở mỗi lượt chơi, $B$ được chọn ra $10$ đồng tùy ý từ $20$ đồng đó và hỏi $A$ thứ tự cân nặng của chúng (và $A$ phải thành thật trả lời). Hỏi rằng sau ít nhất bao nhiêu lượt chơi $B$ có thể tìm ra được thứ tự của $20$ đồng xu này?

Tổng quát lên thành bài toán như sau: Thay $10$ bởi số nguyên dương $n$ bất kỳ và $20$ bởi $2n$. Hãy tìm số lượt chơi ít nhất có thể.

Nguồn: https://artofproblem...arrange_coins_a

https://diendantoanh...n-mã-đi-tuần/

https://blogm4e.word...u-do-trang-tri/

Kết quả chính thức IMO 2017:

1. Hàn Quốc          170 điểm (6 V)

2. Trung Quốc       159 điểm (5 V, 1B)

3. Viêt Nam           155 điểm (4V, 1B, 1Đ)

Đây là thứ hạng cao nhất từ trước tới nay của Việt Nam (sau lần đứng thứ 3 năm 2007).

Thí sinh Hoàng Hữu Quốc Huy, THPT chuyên Lê Quí Đôn, Vũng Tàu đạt số điểm 35, cũng là điểm cao nhất trong kỳ thi năm nay (share #1 với 1 bạn Japan và Iran).

IMO 2017 cũng trở thành kỳ thi có top score thấp nhất trong lịch sử. Bài toán số 3 cũng trở thành bài toán khó nhất lịch sử kỳ thi này (với 608/615 thí sinh đạt điểm 0, chỉ có 2 thí sinh đạt điểm 7, mean score = 0.042).

Thống kê chi tiết xem tại: https://www.imo-offi...otal&order=desc

Theo nguồn tin nội bộ (Thầy Nguyễn Khắc Minh) thì đoàn Việt Nam đạt tổng điểm là 78 trong ngày thứ nhất. Đây là kết quả tốt nhất trong ngày 1.

Bài toán 3 có lẽ là bài toán khó nhất trong lịch sử IMO: Cho tới giờ chỉ có một thí sinh người Úc đạt điểm 7 và một thí sinh của Anh đạt 5 diểm. Hầu hết là 0. Các đoàn mạnh như Mỹ, Trung Quốc có 5/6 thí sinh đạt điểm 0 ở bài này. Có khả năng cao là năm nay sẽ không có điểm tuyệt đối.

Điểm từng phần hiện đã có tại: https://artofproblem...804_imo_results

 

 

Mục đích của việc chọn là để tìm xem hiệu lớn nhất có thể của a−ba−b sao cho a−ba−b luôn chia hết a+ba+b.

Mình nói là "chia hết", không phải "chia hết cho". Thay vì nói "a chia hết cho b" người ta có thể nói "b chia hết a".

 

 

(...) mình thắc mắc là trong trường hợp a=(k+1)xa=(k+1)x và b=(k−1)xb=(k−1)x với x∈Zx∈Z thì sẽ như thế nào ý?

Trường hợp đó thật sự không có ý nghĩa trong việc tìm lời giải. Cho nên mình không xét tới nó

 

Nếu chọn 3

3vẫn có khả năng xảy ra điều mình nói thì sao vẫn chọn thế bạn?

Cái điều đó có thể xảy ra, nhưng không phải lúc nào cũng xảy ra. Bạn xem xem, nếu chọn toàn bộ chia $3$ dư $1$ hay $2$ nó đâu có xảy ra, nhưng nếu mình chọn toàn bộ chia hết cho $3$ thì có: $9=6+3$ chia hết cho $6-3=3$. 

Còn về cái cuối: Giả sử thế này đi, nếu chọn chia hết cho $3$ cả đi, và bạn chọn được $n$ số. Tuy nhiên trong số đó có những số làm cho điều kiện đề bài không được thỏa mãn. Vậy nếu vẫn giữ quyết định ban đầu thì bạn phải loại bớt đi ít nhất $k$ số chẳng hạn. Khi đó $n-k$ số còn lại thỏa mãn. Bây giờ nếu bạn chọn trường hợp khác (không chia hết cho ba) thì bạn chỉ chọn được nhiều nhất là $m$ số, và $m<n-k$ đi. Như vậy rõ ràng là bạn đâu thể nói rằng do xuất hiện một số số không thỏa đề bài mà kết luận rằng cách đó không thích hợp, phải đi vào xem xét cụ thể. Thực ra điều mình giả sử hồi nãy sai hoàn toàn (vì $n=670$ và $m=671$ ), nhưng đấy là khi đã biết giá trị cụ thể của chúng rồi!

Và n+1 người ấy có chiều cao giảm dần hoặc tăng dần. Khi đó sẽ k có người nào đứng giữa 2 người có chiều cao liên tiếp

Đề bài là $2n$, và bạn chọn được $n+1$. Chẳng giải quyết được gì.

Mình k biết gì về định lý này nhưng nếu theo cách mình hiểu từ trên thì sao k áp dụng cho 1 tập con có n^2 +1 người. Khi đó chẳng phải có đpcm luôn sao?


P/S :mặc dù biết là mình hỏi như nhưng k thể nào giải đáp đh thắc mắc ấy

Bạn chọn được $n+1$ người, rồi sao nữa?

Vậy trong trường hợp $a \neq k + 1$ và $b \neq k - 1$ thì sao bạn?

 

Khúc tiếp theo, mình nghĩ việc chọn sao cho các số liên tiếp hơn kém nhau đúng $3$ đơn vị còn 1 lý do khác là nếu chọn con số lớn hơn (đặc biệt là số chẵn) thì có thể lúc này, $\frac{a}{b} = \frac{k + 1}{k - 1}$ đúng không nhỉ?

 

Còn khúc dưới ("xét các số chia hết cho 3") mình nghĩ là không cần thiết đúng không nhỉ? Vì khi đó có thể sẽ tồn tại 2 số sao cho tổng của chúng chia hết cho hiệu của chúng?

Xin lỗi bạn vì không trả lời mấy ngày qua.

Mình không cần quan tâm đến việc $a\ne k+1$ và $b\ne k-1$ làm gì. Mục đích của việc chọn là để tìm xem hiệu lớn nhất có thể của $a-b$ sao cho $a-b$ luôn chia hết $a+b$.

Chọn là $3$ chỉ đơn giản là vì $3$ là số nguyên nhỏ nhất mà lại lớn hơn $2$. Đúng là nếu chọn một số lớn hơn ba thì có khả năng như bạn nói (thực ra nếu chọn ba thì vẫn có đấy), nhưng đó không phải là lí do tại sao chọn $3$.

Phải xét chứ, vì biết đâu bạn loại đi những số đó đi rồi, số còn lại vẫn lớn hơn trong trường hợp dư $1$ hay $2$ thì sao?

Kỳ thi Olympic Toán Quốc Tế lần thứ 58

Brazil, 2017

Ngày thi thứ nhất (18/07/2017)

Bài 1. Với mỗi số nguyên bất kỳ $a_0>1$, xét dãy số $a_0, a_1, a_2, \dots$ xác định bởi:

$a_{n+1}=\sqrt{a_n}$ nếu $\sqrt{a_n}$ là số nguyên,

$a_{n+1}=a_n+3$ trong trường hợp ngược lại,

với mỗi số nguyên $n\geq 0$.

Hãy xác định tất cả các số $a_0$ sao cho tồn tại số $A$ mà $a_n=A$ với vô hạn số $n$.

Bài 2. Kí hiệu $\mathbb{R}$ là tập số thực. Hãy tìm tất cả các hàm số $f:\mathbb{R}\mapsto\mathbb{R}$ sao cho với mọi số thực $x$ và $y$,

$$f(f(x)f(y)) + f(x+y) = f(xy).$$

Bài 3. Một cô thợ săn và một con thỏ tàng hình chơi trò chơi sau trên mặt phẳng. Điểm xuất phát $A_0$ của con thỏ và điểm xuất phát $B_0$ của cô thợ săn trùng nhau. Sau $n-1$ lượt chơi, con thỏ ở điểm $A_{n-1}$ và cô thợ săn ở điểm $B_{n-1}$. Ở lượt chơi thứ $n$, có ba điều lần lượt xảy ra theo thứ tự dưới đây:

(i) Con thỏ di chuyển một cách không quan sát được tới điểm $A_n$ sao cho khoảng cách giữa $A_{n-1}$ và $A_n$ bằng đúng $1$.

(ii) Một thiết bị định vị thông báo cho cô thợ săn về một điểm $P_n$, đảm bảo khoảng cách giữa $P_n$ và $A_n$ không lớn hơn $1$.

(iii) Cô thợ săn di chuyển một cách quan sát được tới điểm $B_n$ sao cho khoảng cách giữa $B_{n-1}$ và $B_n$ bằng đúng $1$.

Hỏi điều sau đây sai hay đúng: cho dù con thỏ có di chuyển như thế nào và các điểm được thiết bị định vị thông báo có là những điểm nào, cô thợ săn luôn có thể chọn cho mình cách di chuyển sao cho sau $10^9$ lượt chơi, cô ta có thể khẳng định chắc chắn rằng khoảng cách giữa mình và con thỏ không vượt quá $100$?

Ngày thi thứ hai (19/07/2017)

Bài 4. Cho $R$ và $S$ là hai điểm phân biệt trên đường tròn $\Omega$ sao cho $RS$ không phải là đường kính. Cho $\ell$ là tiếp tuyến tại $R$ của $\Omega$. Lấy điểm $T$ sao cho $S$ là trung điểm của đoạn thẳng $RT$. Lấy điểm $J$ trên cung nhỏ $\overarc{RS}$ của $\Omega$ sao cho đường tròn ngoại tiếp $\Gamma$ của tam giác $JST$ cắt $\ell$ tại hai điểm phân biệt. Gọi $A $ là giao điểm gần $R$ nhất của $\Gamma$ và $\ell$. Đường thẳng $AJ$ cắt lại $\Omega$ tại $K$. Chứng minh rằng $KT$ tiếp xúc với $\Gamma$.

Bài 5. Cho số nguyên $N>2$. Có $N(N+1)$ cầu thủ bóng đá, trong đó không có hai người nào có cùng chiều cao, đứng thành một hàng ngang. Ngài Alex muốn đưa $N(N – 1)$ cầu thủ ra khỏi hàng sao cho ở hàng ngang mới nhận được, gồm $2N$ cầu thủ còn lại, $N$ điều kiện sau được đồng thời thỏa mãn:

(1) không có cầu thủ nào đứng giữa hai cầu thủ cao nhất,

(2) không có cầu thủ nào đứng giữa cầu thủ cao thứ ba và cầu thủ cao thứ tư,

$\dots$

($N$) không có cầu thủ nào đứng giữa hai cầu thủ thấp nhất.

Chứng minh rằng Ngài Alex luôn có thể làm được điều đó.

Bài 6. Cặp có thứ tự các số nguyên $(x, y)$ được gọi là điểm nguyên thủy nếu ước số chung lớn nhất của $x$ và $y$ bằng $1$. Cho tập $S$ gồm hữu hạn điểm nguyên thủy. Chứng minh rằng tồn tại số nguyên dương $n$ và các số nguyên $a_0,a_1,a_2,\dots ,a_{n-1},a_n$ sao cho với mỗi điểm $(x, y)$ thuộc $S$, ta có:$$a_0x^n+a_1x^{n-1}y+a_2x^{n-2}y^2+\cdots+a_{n-1}xy^{n-1}+a_ny^n=1.$$

--- Hết ---

Đề gốc: https://www.imo-offi...g/problems.aspx

Good question, mình sẽ chỉ ra tại sao người ta lại đi đến lời giải đó.

Xét hai số nguyên dương $a,b$ bất kỳ, giả sử $a+b$ chia hết cho $a-b$. Khi đó, $a+b=(a-b)k$ với số nguyên dương $k$ nào đó. Biến đổi ta thu được:

$$\frac{a}{b}=\frac{k+1}{k-1}.$$

Nếu chọn $a=k+1, b=k-1$ thì đẳng thức trên được thỏa mãn với $k$ bất kỳ, nghĩa là nếu ta muốn chọn $n$ số sao cho điều kiện đề bài được thỏa mãn thì phải chọn sao cho hiệu của hai số liên tiếp phải lớn hơn $2$ (điều kiện cần). Khi đó ta nghĩ ngay tới việc chọn sao cho các số liên tiếp hơn kém nhau đúng $3$ (để được nhiều nhất -  cái này chính là tư tưởng tham lam). Vậy các số này có cùng số dư khi chia cho $3$. Ta thử xét các số đều chia hết cho $3$. Cách này được nhiều nhất là $670$ số (lấy tất cả các số chia hết cho $3$). Lại xét cách thứ hai: Tất cả chia $3$ dư $1$. Cách này thì được nhiều nhất là $671$ số, rõ ngon hơn cách một. Hay nếu xét cách thứ ba, chính là cách trong lời giải, thì cũng được nhiều nhất là $671$ số. Vậy cách trong lời giải không phải là duy nhất. 

Sau khi đã "chọn" được rồi, ta phải chứng minh là cách chọn của ta thỏa mãn đề bài (điều kiện đủ). Và đơn giản nhất là xét số dư cho $3$ (như trong lời giải).

Thoạt đầu, mình cũng không hiểu tại sao người ta lại nghĩ ra cách chọn như vậy. Nhưng ta phải lật ngược lại vấn đề: Chọn thế nào thì không được (bằng cách xét thử điều kiện hai số đề tổng chia hết cho hiệu), sau đó tìm cách chọn để không vướng vào điều kiện đó. Và lưu ý, phải "tham lam", chọn được nhiều nhất có thể, đối với những dạng thế này.

$\boxed{\text{Bài 5}}$.

Đáp số: $\frac{n^2-3n+6}{6}$ nếu $3|n$ và $\frac{n^2-3n+2}{6}$ nếu $3\not |n$.

Do $a+b+c<3n$, nên có hai trường hợp có thể xảy ra:

$\bullet $ Trường hợp 1. $a+b+c=n$.

Trước hết, ta đếm số bộ $(a,b,c)$, có tính đến thứ tự *, sao cho $0\leq a,b, c \leq n$ và $a+b+c=n$ (1). Theo bài toán chia kẹo Euler, số bộ như vậy là:

$$\binom{n+2}{2}.$$

Bây giờ, ta đếm số bộ $(a,b,c)$ như trên, nhưng với thêm điều kiện: Ít nhất hai trong ba số $a,b,c$ là giống nhau (2). Khi đó, ta xét phương trình:

$$2x+y=n,$$

có đúng $\left\lfloor\frac{n}{2}\right\rfloor+1$ nghiệm $(x,y)$.

Trong trường hợp $3|n$, trong số $\left\lfloor\frac{n}{2}\right\rfloor+1$ nghiệm kể trên thì có duy nhất một nghiệm mà $x,y$ giống nhau, tương ứng với bộ $\left(\frac{n}{3},\frac{n}{3},\frac{n}{3}\right)$; các nghiệm còn lại tương ứng với ba bộ $(x,x,y)$, $(x,y,x)$, $(y,x,x)$. Như vậy nếu $3|n$, số bộ có tính chất (2) là:

$$3\left\lfloor\frac{n}{2}\right\rfloor +1.$$

Còn trong trường hợp $3\not | n$, thi mỗi nghiệm $(x,y)$ tương ứng với ba bộ $(a,b,c)$ có thứ tự. Khi đó số bộ có tính chất (2) là:

$$3\left(\left\lfloor\frac{n}{2}\right\rfloor +1\right).$$

Ngoài các bộ có tính chất (2), các bộ có tính chất (1) còn lại nếu không tính đến thứ tự sẽ thỏa mãn đề bài. Thật vậy, do $a,b,c$ phân biệt, nên điều kiện $0\leq a, b, c \leq n$ trở thành $0\leq a<b<c\leq n-1$. Suy ra số bộ như vậy là:

(i)

$\frac{1}{6}\left(\binom{n+2}{2}-3\left\lfloor\frac{n}{2}\right\rfloor -1\right)$ nếu $3|n$, và

(ii) 

$\frac{1}{6}\left(\binom{n+2}{2}-3\left(\left\lfloor\frac{n}{2}\right\rfloor +1\right)\right)$ nếu $3\not | n$

(chia $6$ nhằm loại bỏ các hoán vị). $\square$

$\bullet $ Trường hợp 2. $a+b+c=2n$.

Đặt $a=n-A,b=n-B,n-C$ thì $1\leq C<B<A\leq n-1$ và $A+B+C=n$. Để ý rằng mỗi bộ $(A,B,C)$ tương ứng với duy nhất một bộ $(a,b,c)$, nên ta có thể đếm số bộ $(A,B,C)$. Mặt khác, số bộ $(A,B,C)$ lại đúng bằng số bộ $(a,b,c)$ trong trường hợp 1 trừ đi số bộ có dạng $(0,x,y)$ hay nói cách khác, trừ đi số nghiệm nguyên dương, không tính đến thứ tự $(x,y)$ của phương trình:

$$x+y=n.$$

Dễ thấy phương trình trên có đúng $\left\lfloor\frac{n-1}{2}\right\rfloor$ nghiệm $(x,y)$ như vậy, từ đó suy ra số bộ $(A,B,C)$. $\square$

Vậy, tóm lại, số bộ $(a,b,c)$ thỏa mãn đề bài là:

(i) 

nếu $3|n$.

(ii) 

nếu $3\not | n$.

* Note: cặp có thứ tự $(a,b)$ thì khác với cặp $(b,a)$ nếu $a\ne b$. Tương tự như thế với các bộ có $n$ số.

Ta xét tập rỗng trước. Tập này có đúng một tập con là chính nó.

Tiếp theo xét một tập có đúng $1$ phần tử. Tập này có đúng $2$ tập con là tập rỗng và chính nó.

Xét tập có hai phần tử $\{a,b\}$. Tập này có đúng $4$ tập con là $\varnothing, \{a\}, \{b\}, \{a,b\}$.

Dự đoán rằng tập có $n$ phần tử thì có đúng $2^n$ tập con. Chứng minh: Giả sử khẳng định của ta là đúng với trường hợp $n=k$ nguyên dương nào đó. Ta sẽ chứng minh điều đó đúng với $n=k+1$. Thật vậy, xét tập $S$ có $k+1$ phần tử. Gọi $x$ là một phần tử bất kỳ của $S$. Rõ ràng các tập con của $S$ đều có thể xếp vào đúng một trong hai lớp:

- Lớp thứ nhất gồm các tập con của $S\setminus \{x\}$, tức là không chứa $x$. Rõ ràng lớp này có $2^k$ phần tử theo giả thuyết quy nạp.

- Lớp thứ hai gồm các tập con của $S$ mà chứa $x$. Các tập này lại có dạng $T\cup \{x\}$ với $T$ là tập con của $S$ thuộc lớp thứ nhất. Vậy lớp này cũng sẽ có đúng $2^k$ phần tử.

Vậy tóm lại là $S$ có đúng $2^k+2^k=2^{k+1}$ tập con, chứng tỏ khẳng định của ta là đúng với mọi $n$ nguyên dương. $\square$