Giả sử chọn $k = 2016$, và có $2^{2016}+1$ dòng, trong số các dòng này chứa tất cả các chuỗi nhị phân độ dài $k$ và có đúng 2 chuỗi giống nhau, xét hai chuỗi giống nhau ở cột thứ $2017$, một chuỗi chứa 0 một chuỗi để trống, ở cột thứ $2018$ thì chuỗi để trống ở cột $2017$ chứa 0 còn chuỗi còn lại thì để trống. Khi đó thì không thể xóa đi dòng nào được đâu bạn ạ.

 

Bảng này không phải bảng đầy đủ nhé bạn, lấy dãy nhị phân giống 2016 cột đầu của hai hàng này và đằng sau cho hai số 1,1 là thấy rõ.

Bài 2:

Câu b đã là gợi ý cho câu a. Một bảng gồm $2^k$ xâu nhị phân độ dài là $k$ và phần còn lại chừa trống thỏa mãn điều kiện là bảng tối giản.

câu b ta sẽ chứng minh nếu $m>2^k$ thì ta sẽ xóa được một dòng sao cho bảng vẫn còn là tối giản. Điều này có nghĩa là chứng minh rằng tất cả chuỗi nhị phân sinh ra từ dòng bị xóa sẽ thu được bằng cách thêm vào $0,1$ ở các dòng khác. Ta chỉ quan tâm tới cách sinh ra các chuỗi nhị phân với $k$ cột chứ $0,1$. Bây giờ xét tập A gồm $2^k$ chuỗi nhị phân có độ dài $k$. Mỗi một bước ta chọn một dòng của bảng (chỉ $k$ cột chứa 0,1), và xóa đi tất cả những chuỗi nhị phân trong A có thể sinh ra được bằng cách thêm $0,1$ vào các ô còn trống của dòng này. Với một dòng mà ta không xóa được trong A bất kì một chuỗi nào thì có nghĩa tất cả các chuỗi nhị phân sinh ra từ dòng đó có thể được sinh ra bởi các dòng khác, tức là xóa đi dòng đó bảng vẫn tối giản. A chỉ có $2^k$ phần tử mà ta có $m>2^k$ dòng thì dĩ nhiên sẽ chọn được một dòng chẳng xóa đi phần tử nào trong tập A được.

 

Thực ra lúc mình thi thì mình nhớ rằng ý b) không có điều kiện "tất cả các cột còn lại đều trống". Thực ra điều kiện chỉ cần có đúng $k$ cột có chứa hai số $0,1$ là đủ rồi. Lời giải của bạn vẫn đúng về ý tưởng nhưng có một xíu cải tiến như sau. Vẫn xét hàng mà chúng ta có thể xóa được trong lập luận của bạn, nếu nó không có phần tử nào ở các cột còn lại thì có thể xóa nó đi. Nhưng nếu nó có, và giả sử là số $0$ chẳng hạn ở một cột nào đó ngoài $k$ cột này thì ta vẫn có thể chứng minh mọi dãy nhị phân sinh ra từ hàng này thì có thể sinh ra từ một hàng khác bởi nếu không ta có thể lập luận và tạo thêm một cột nữa có chứa cả hai số $0,1$ và ta có điều vô lý.

Tại vương quốc Wakanda có $2018^2$ thành phố nằm trên $2018^2$ ô vuông của một bảng vuông $2018\times 2018$, mỗi ô có đúng một thành phố. Hai thành phố được coi là lân cận nếu chúng nằm trên hai ô vuông có chung cạnh. Một ngày nào đó vô tình một bệnh dịch khủng khiếp đã phát tán ở quốc gia Wakanda và có sức lây lan khủng khiếp. Sau một ngày, từ một thành phố bị nhiễm bệnh thì nó sẽ lây lan sang các thành phố lân cận. May thay, chính phủ và bộ y tế đã tìm ra loại thuốc khống chế dịch bệnh này và phân phát cho một số thành phố ở Wakanda, và cứ sau một ngày sẽ phân phát thuốc cho các thành phố lân cận, (các thành phố có thuốc chữa đương nhiên sẽ được coi là không nhiễm bệnh), Với sự phát triển công nghệ sinh học vượt bậc, các phương thuốc này tỏ ra rất hiệu quả và người ta nhận thấy rằng:

i) Nếu một thành phố mà các thành phố lân cận với nó đều không bị nhiễm bệnh hay có thuốc chữa thì nó sẽ không thay đổi trạng thái.

ii) Nếu một thành phố chưa bị nhiễm bệnh (các thành phố có thuốc chữa cũng là chưa nhiễm bệnh ) thì nó bị nhiễm bệnh khi và chỉ khi ở các thành phố lân cận của nó, số thành phố bị nhiễm bệnh lớn hơn số thành phố có thuốc chữa.

iii) Một thành phố bị nhiễm bệnh sẽ được chữa nếu nó có ít nhất $2$ thành phố lân cận có thuốc chữa.

a) Giả sử tại một thời điểm nào đó có đúng $3$ thành phố bị nhiễm bệnh. Hỏi quốc vương Wakanda phải đảm bảo tại thời điểm đó có ít nhất bao nhiêu thành phố có thuốc chữa để đến cuối cùng thì toàn vương quốc sẽ được chữa?

b) Xác định số $m$ nhỏ nhất để nếu tại bất kì một thời điểm nào có $m$ thành phố có thuốc chữa thì chắc chắn toàn vương quốc sẽ được chữa. 

(Toàn vương quốc được coi như được chữa khi không tồn tại một thành phố bị nhiễm bệnh)

( Lưu ý: Thành phố không bị nhiễm bệnh không có nghĩa rằng là có thuốc chữa. Nói đơn giản, một thành phố có ba trạng thái: bị nhiễm bệnh, có thuốc chữa, không bị bệnh cũng như không có thuốc chữa)

Kết quả bài này hình như không đúng lắm. 

Ta xét số $m$ sao cho $a_m$ $=$ $m^{2017}$. Ký hiệu $f(i_1,...,i_{2017})$ $=$ $a_{i_1}+2017a_{i_2}+...+2017^{2016}a_{i_{2017}}$

Do $a_m$ $=$ $m^{2017}$ nên $ \left \{ 0,1,...,m^{2017}-1 \right \} $ $\subset $ $\left \{ f(i_1,i_2,...,i_{2017}) | i_j < m \forall j = 1,2,...,2017 \right \}$ mà $\left | \left \{ f(i_1,i_2,...,i_{2017}) | i_j < m \forall j = 1,2,...,2017 \right \} \right | \leq m^{2017}$ $=$ $\left | \left \{ 0,1,...,m^{2017} -1 \right \} \right |$ nên $f(i_1,i_2,...,i_{2017})$ là đôi một phân biệt với mọi $i_j$ $<$ $m$. Từ đây đánh giá dễ thấy $a_{m-1-2017k-r}$ $=$ $a_{m-1} - k(2016A + 1) - r$ với $A$ $=$ $\frac{2017^{2017} - 1}{2016}$

Xét $n$ $=$ $0,1, ... , 2016$ ta suy ra $a_i$ $=$ $i$ $\forall i = 0,1, ... , 2016$

Do đó $a_{m-1} - k(2016A+1)$ $=$ $2016$ nên $a_{m-1}$ $=$ $2016 + k(2016A +1)$

Mà ta có $m^{2017} - 1$ $=$ $a_{m-1}A$ nên $m^{2017} - 1$ $=$ $2016A + k(2016A^2+A)$ do đó $m^{2017} - 2017^{2017}$ $\vdots $ $2017^{2017} A$.

Chỗ này nếu chọn $m = 2017 A$ thì sao?

xin lỗi bạn, mình quên điều kiện cần thiết nữa là duy nhất (đã sửa)

Một dãy số tự nhiên $a_0<a_1<a_2<...$ có tính chất sau: Với bất kỳ số tự nhiên $n$ nào thì tồn tại duy nhất $2017$ chỉ số $i_1,i_2,...,i_{2017}$ không nhất thiết phân biệt để 

$ n= a_{i_1}+2017 a_{i_2}+...+2017^{2016} a_{i_{2017}}$

Chứng minh rằng với số nguyên dương $m$ mà $a_m=m^{2017}$ thì tồn tại số tự nhiên $k$ để $m={2017}^k$.

Ta sẽ chứng minh bằng quy nạp mạnh theo $n$. Trước hết hãy cố định $\alpha$. Với $n=1$, xét 2 trường hợp:

Nếu $a_1>\alpha$ thì khi đó có đúng một giá trị $m_1$ thỏa $m_1>\alpha$ và do đó số giá trị này bé hơn $\frac{a_1}{\alpha}>1$.

Nếu $a_1\leq \alpha$ thì khi đó số giá trị $k$ thỏa $m_k>\alpha$ là $0<\frac{a_1}{\alpha}$.

Vậy giả thiết đúng với $n=1$, giả sử giả thiết đúng với mọi $1\leq k\leq n-1$. Ta sẽ chứng minh giả thiết đúng với $k=n$. Ta sẽ có hai trường hợp cho $m_n$ như sau:

TH1: $m_n\leq \alpha$ khi đó số giá trị $k$ ($1\leq k\leq n$) mà $m_k>\alpha$ bằng số giá trị $k$ ($1\leq k\leq n-1$) mà $m_k>\alpha$ và số giá trị này bé hơn $\frac{a_1+a_2+...+a_{n-1}}{\alpha}\leq \frac{a_1+a_2+...+a_n}{\alpha }$. (đúng)

TH2: $m_n>\alpha$ khi đó gọi $1\leq j\leq n$ là số thỏa $a_j+a_{j+1}+...+a_n>(n-j+1)\alpha$. Rõ ràng số các số $k$ ($1\leq k\leq n$) để $m_k>\alpha$ bằng tổng số các số $i$ ($1\leq i\leq j-1$) để $a_i>\alpha$ và tổng số các số $i$ ($j\leq i\leq n$) để $a_j>\alpha$. Theo giả thiết quy nạp thì tổng số các số này bé hơn

$\frac{a_1+a_2+..+a_{j-1}}{\alpha }+n-k+1< \frac{a_1+a_2+..+a_{j-1}}{\alpha }+\frac{a_j+a_{j+1}+...+a_n}{\alpha }=\frac{a_1+a_2+..+a_n}{\alpha }$ . (đúng)

 Vậy theo giả thiết quy nạp bài toán được chứng minh.

Với mỗi số nguyên dương $n$,trong lưới ô vuông, ta định nghĩa một $n-$mino là một tập hợp $n$ hình vuông $1\times 1$ liên thông với nhau ( có nghĩa là từ hình vuông này có thể đi đến các hình vuông khác chỉ qua các cạnh ). Hai $n-$mino là giống nhau khi và chỉ khi có một phép tịnh tiến biến mino này thành mino kia. Gọi $P_n$ là số tất cả các $n-$mino khác nhau. Chứng minh rằng $P_n\leq 6,75^n$.

Bài 5: Trước hết trong tập ${1,2,3,...,2017}$ ta chọn ra một số $m$ sao cho giá trị $\sqrt[m]{a_m}$ là lớn nhất.

Ý tưởng chính của em cho bài toán số 5 là chỉ ra một số $N$ đủ lớn để với mọi số $n>N$ thì tồn tại cách phân tích $a_n$ thành tích các thừa số $a_i$, $1\leq i\leq 2017$, tức là $a_n=a_{i_1}.a_{i_2}...a_{i_k}$, $1\leq i_j\leq 2017$ và $a_1=a_2=a_m$. Ta sẽ đi chứng minh nhận xét trên (coi là nhận xét $(*)$)

Trước hết ta nhận thấy rằng từ điều kiện bài toán thì với bất kì một số $n>2017$ nào thì cũng có thể phân tích thành:

$a_n=a_{i_1}.a_{i_2}...a_{i_k}$ với  $i_1+i_2+...+i_k=n$, $1\leq i_j\leq 2017$ với mọi $1\leq j\leq k$

Thật vậy trước hết tồn tại $j_1,j_2,j_3$ sao cho $a_n=a_{j_1}.a_{j_2}.a_{j_3}$ và nếu trong các số $j_1,j_2,j_3$ có một số lớn hơn $2017$ thì ta tiếp tục phân tích ra tiếp như vậy. Do đó điều nhận xét là đúng. Hơn nữa trong cách phân tích cuối cùng để ra được ba nhân tử $a_i,a_j,a_k$ thì phải có $i+j+k>2017$ và không mất tính tổng quát ta có thể giả sử $i_1+i_2+i_3>2017$. Quy về như vậy ta được điều kiện cần của các số $i_1,i_2,...,i_k$ là:

$i_1+i_2+...+i_k=n$, $1\leq i_j\leq 2017$ với mọi $j\in {1,2,...,k}$ và $i_1+i_2+i_3>2017$ (điều kiện $(1)$)

Bây giờ ta xét tập các số $ j_1,j_2,...,j_t$ thỏa điều kiện $(1)$. Khi đó ta có: $a_n\geq a_{j_1}.a_{j_2}.a_{n-j_1-j_2}\geq ...\geq a_{j_1}.a_{j_2}....a_{j_t}$. từ đó kết luận rằng:

$a_n=max\left \{ a_{i_1}.a_{i_2}...a_{i_k}\mid (i_1,i_2,..,i_k) \mathbf{thoa} (1))\right \} $

Bây giờ ta xét $n$ là số thỏa $n\geq N=2.2017^2m+3.2017$. Do $ n=i_1+i_2+...+i_k\leq 2017k$ nên $k\geq 2.2017m+3$. Do đó theo nguyên lý Dirichlet thì trong $k-3$ số $a_{i_4},a_{i_5},...,a_{i_k}$ có ít nhất $2m$ số bằng nhau. Xét hai trường hợp:

Trường hợp 1: Nếu $2m$ số đó bằng $a_m$ thì do $2m\geq 2$ nên nhận xét $(*)$ được chứng minh.

Trường hợp 2: Nếu $2m$ số đó không phải là $a_m$ mà là $a_q$ với $j\neq m$ thì khi đó ta sẽ thay $2m$ số đó bằng $2q$ số $a_m$ và khi đó ta lập được một dãy mới các số $a_{j_1},a_{j_2},....,a_{j_t}$ với tổng các chỉ số $j_1,j_2,...,j_t$ có tổng vẫn bằng $n$ và vẫn thỏa mãn $j_1+j_2+j_3=i_1+i_2+i_3>2017$ và $1\leq j_a\leq 2017$ với mọi $1\leq a\leq t$. Tức là dãy $a_{j_1}.a_{j_2}....a_{j_t}$ thỏa điều kiện $(1)$ và suy ra:

$a_n\geq a_{j_1}.a_{j_2}....a_{j_t}$

Suy ra

$a_{i_1}.a_{i_2}...a_{i_k}\geq a_{j_1}.a_{j_2}....a_{j_t}$

Giản ước đi ta có: $a_q^{2m}\geq a_m^{2q}$ hay suy ra $\sqrt[q]{a_q}\geq \sqrt[m]{a_m}$. Theo tính chất lớn nhất suy ra $\sqrt[q]{a_q}= \sqrt[m]{a_m}$ hay $a_q^{2m}= a_m^{2q}$. Từ đó suy ra $a_{i_1}.a_{i_2}...a_{i_k}= a_{j_1}.a_{j_2}....a_{j_t}= a_n$. Và trong dãy  $a_{j_1},a_{j_2},....,a_{j_t}$ có ít nhất $2q\geq 2$ phần tử bằng $a_m$ hay nhận xét $(*)$ đúng.

Như vậy nhận xét $(*)$ đúng. từ đó ta thấy rằng $a_n=a_m.a_m.a_{i_1}.a_{i_2}...a_{i_k}\geq a_m^2.a_{n-2m}\geq a_m.a_m.a_{i_1}.a_{i_2}...a_{i_k}=a_n$ với $i_1+i_2+...+i_k=n-2m$. Suy ra $a_n=a_m^2.a_{n-2m}$ với $n\geq N=2.2017^2m+3.2017>2m$.

Tức là như vậy ta đã chứng minh được rằng tồn tại số $m\leq 2017$ và tồn tại số $N$ đủ lớn sao cho với mọi $n>N$ thì $a_n=a_m^2.a_{n-2m}$. Khi đó ta tiếp tục chọn $n$ đủ lớn để $n-2m>N$. Khi đó $a_{n-2m}=a_m^2.a_{n-4m}$. Khi đó:

$a_n.a_{n-4m}=a_{n-2m}.a_m^2.a_{n-4m}=a_{n-2m}^2$

Và như vậy bài toán được chứng minh hoàn toàn.

Câu 4:

Ta sẽ chứng minh quy nạp theo $m$ cho điều này. Trước hết ta phát biểu bổ đề: $A\Delta B=A\Delta C$ thì $B=C$.

Giả sử $B\neq C$, khi đó không giảm tổng quát giả sử giả sử $a$ là phần tử thỏa $a\in B$ và $a\notin C$. Ta có hai trường hợp như sau:

   Case 1: Nếu $a\in A$ khi đó $a\notin (A\setminus B),a\notin (B\setminus A)\Rightarrow a\notin A\Delta B$. Nhưng lại có $a\in (A\setminus C)$ nên suy ra $a\in A\Delta C$ nên $A\Delta B\neq A\Delta C$, vô lý.

   Case 2: Nếu $a\notin A$ thì chứng minh tương tự suy ra $a\notin A\Delta C$ và $a\in A\Delta B$ nên suy ra $A\Delta B\neq A\Delta C$. Như vậy ta suy ra $B=C$.

Bây giờ ta sẽ quy nạp theo $m$. Với $m=1$ thì ta có một tập thuộc $T$ là tập rỗng. Với $m=2$ và hai tập $A,B$ thì ta có hai tập thuộc $T$ là tập rỗng và $A\Delta B$ thỏa. Như vậy giả thiết đúng với $m=1,2$.

Giả sử giả thiết đúng với $m=k$ thì ta chứng minh nó đúng với $m=k+1$. Xét $m+1$ tập $A_1,A_2,...,A_{m+1}$. Nếu với $m$ tập $A_1,A_2,...,A_m$ mà số lượng tập tạo thành không nhỏ hơn $m+1$ thì khi đó ta thêm vào một tập $A_{m+1}$ thì giả thiết vẫn đúng. Do đó ta chỉ xét cho trường hợp $|T|=m$.

Khi đó, nếu ta thêm vào một tập $A_{m+1}$ thì ta sẽ thêm vào tập $T$ các tập hợp $A_{m+1}\Delta A_1,...,A_{m+1}\Delta A_{m+1}$. Nếu các tập này trùng với $m$ tập đã có trong $T$ thì do $|T|=m$ nên theo nguyên lý Dirichlet tồn tại $i,j,1\leq i<j\leq m+1$ để $A_{m+1}\Delta A_i=A_{m+1}\Delta A_j$ và theo bổ đề ta có $A_i=A_j$, vô lý. Vậy trong $m+1$ tập đó chắc chắn có một tập khác với các tập trong $T$ và số phần tử của $T$ tăng lên ít nhất một đơn vị, tức là $|T|\geq m+1$.

Vậy giả thiết quy nạp là đúng và ta có điều phải chứng minh.

P.S: Cách giải bài số 2 của mình tương đối giống nhưng hơi khác so với cách của anh Lâm Hữu Phúc, mình sẽ đăng sau.

Đại học quốc gia TPHCM                                      Đề thi chọn đội dự tuyển môn toán lớp 10

Trường Phổ Thông Năng Khiếu                                        Năm học 2016-2017

                                                                                              Thời gian: 120 phút

Bài 1: Cho $x,y,z$ là các số dương thỏa $x+y+z=1$. Chứng minh rằng:

$\frac{x^4}{x^3+y^2+z^2}+\frac{y^4}{y^3+x^2+z^2}+\frac{z^4}{z^3+y^2+x^2}\geq \frac{1}{7}$

Bài 2: Tìm tất cả các hàm số $f:\mathbb{N}^*\rightarrow \mathbb{N}^*$ thỏa mãn đồng thời các điều kiện:

$i)$ $f(mn)=f(m)f(n)$ với mọi $m,n\in \mathbb{N}^*$

$ii)$ $f(m)+f(n)$ chia hết cho $m+n$ với mọi $m,n\in \mathbb{N}^*$

$iii)$ $f(2017)=2017^3$

Bài 3: Cho đường tròn $(O)$ và dây cung $AB$ cố định. $C$ là một điểm thay đổi trên cung lớn $AB$ sao cho tam giác $ABC$ nhọn. Gọi $I,I_a,I_b$ lần lượt là tâm đường tròn nội tiếp, đường tròn bàng tiếp góc $A$, đường tròn bàng tiếp góc $B$ của tam giác $ABC$.

a) Gọi điểm đối xứng của $i$ qua $O$ là $M$. Chứng minh tam giác $MI_aI_b$ cân.

b) Gọi $H,K$ lần lượt là hình chiếu của $I_b,I_a$ trên $OI$. Đường thẳng qua $H$ vuông góc với $BI_a$ và đường thẳng qua $K$ vuông góc với $AI_b$ cắt nhau tại $P$. Chứng minh rằng $P$ thuộc một đường cố định.

Bài 4: Cho $S$ là tập hợp khác rỗng và $A_1,A_2,...,A_m$ $(m\geq 2)$ là $m$ tập con của $S$. Gọi $T$ là tập gồm tất cả các tập $A_i\Delta A_j$ với $1\leq i,j \leq m$. Chứng minh rằng $\left | T \right |\geq m$.

( Với ký hiệu $A\Delta B=(A\setminus B)\cup (B\setminus A)$ và $|T|$ là số phần tử của $T$).

-----------------------------------------------------------HẾT----------------------------------------------------------

Bài 6b: Lời giải của em cho bài 6b) 

Ta sẽ chứng minh cho trường hợp tổng quát $p$ là số nguyên tố và $p\equiv 1(mod 4)$. Khi đó do $2017$ là số nguyên tố và chia $4$ dư $1$ thì bài toán được chứng minh.

Trước hết ta có nhận xét sau:

$(-1)^k\binom{p}{k}=(-1)^k\frac{p}{k}\binom{p-1}{k-1}\equiv 2(-1)^{2k-1}\frac{p}{2k}\equiv 2\binom{p}{2k}$ $(mod$ $p^2)$

với mọi $k=1,2,...,\frac{p-1}{2}$.

Do đó ta có

$\sum _{k=1}^{\frac{p-1}{4}}(-1)^k\binom{p}{k}\equiv 2\sum_{k=1}^{\frac{p-1}{4}}\binom{p}{2k}= \sum _{k=1}^{\frac{p-1}{2}}\binom{p}{k}+\sum _{k=1}^{\frac{p-1}{2}}(-1)^k\binom{p}{k} (mod p^2)$

Và ta lại áp dụng nhận xét trên một lần nữa:

$\sum _{k=1}^{\frac{p-1}{2}}(-1)^k\binom{p}{k}\equiv 2\sum _{k=1}^{\frac{p-1}{2}}\binom{p}{2k}= \sum _{k=1}^{p-1}\binom{p}{k}+\sum _{k=1}^{p-1}(-1)^k\binom{p}{k} (mod p^2)$

Ta có các kết quả quen thuộc sau:

$\sum _{k=1}^{p-1}\binom{p}{k}=2^p-2$

$\sum _{k=1}^{p-1}(-1)^k\binom{p}{k}=0$

$\sum _{k=1}^{\frac{p-1}{2}}\binom{p}{k}=\frac{1}{2}\sum _{k=1}^{p-1}\binom{p}{k}=2^{p-1}-1$

Kết hợp tất cả các điều trên lại và ta có:

$\sum _{k=1}^{\frac{p-1}{4}}(-1)^k\binom{p}{k}\equiv 3(2^{p-1}-1)(mod p^2)$

Và bài toán được chứng minh.

Mình chứng minh tính chất " Nếu $I$ là họ tập con của $S$ sao cho không có tập nào là tập con của tập khác thì $\left | I \right |\leq \binom{n}{\frac{n}{2}}$" theo một cách khác.

Ta sẽ đếm số các chuỗi tập con $B_1,B_2,..,B_n$ của $S$ thỏa $B_1\subset B_2\subset ...\subset B_n$ và $\left | B_i \right |=i $ $\forall i=1,2,...,n$. Dễ thấy rằng từ tập $B_n$, có $n$ cách chọn ra môt phần tử và nếu loại phần tử đó đi thì ta được tập $B_{n-1}$ và tương tự cũng có $n-1$ cách chọn ra tập $B_{n-2}$ và cứ thế. Suy ra rằng số chuỗi các tập con này đúng bằng $n!$ ( do trong cách chọn không có chuỗi nào trùng nhau).

Cố định một tập $A$ có $k$ phần tử, bằng cách tương tự như trên ta thấy rằng số chuỗi các tập con thỏa $B_1\subset B_2\subset ,,,\subset B_{k-1}\subset A\subset B_{k+1}\subset ...\subset B_n$ và $\left | B_i \right |=i$ $\forall i=1,2,...,n$ là $(n-k)!k!$.

Ta thấy rằng với hai tập con khác nhau $A,B$ thuộc $I$ thì do $A,B$ không có tập nào là tập con của tập khác nên chuỗi các tập con lập được từ $A$ và $B$ là phân biệt. Như vậy nếu giả sử rằng $I$ có $k$ tập con là $A_1,A_2,...,A_k$ thì khi đó số chuỗi có thể tạo thành như trên là $\sum _{i=0}^k(n-i)!i!$.

Vậy ta có: 

$\sum _{i=0}^k(n-i)!i!\leq n!\Leftrightarrow \sum _{k=0}^n\frac{1}{\binom{n}{i}}\leq 1$

Để ý rằng ta có $\binom{n}{i}\leq \binom{n}{\frac{n}{2}}\forall i=1,2,...,n$. nên ta có $\frac{k}{\binom{n}{\frac{n}{2}}}\leq 1\Leftrightarrow k\leq \binom{n}{\frac{n}{2}}$.

Vậy ta có điều phải chứng minh.

Ta sẽ đếm hệ số của $x^n$ của $(1+2x)^n(1+x)^n$ bằng hai cách.

Cách 1: Ta có $(1+2x)^n(1+x)^n=\sum _{k=0}^{n}2^kx^k\binom{n}{k}\sum _{j=0}^{n}\binom{n}{j}x^j=\sum _{k=0}^n\sum _{j=0}^n2^k\binom{n}{k}\binom{n}{j}x^{k+j}$.

Từ đó suy ra hệ số của $x^n$ là $\sum _{j+k=n}2^k\binom{n}{k}\binom{n}{j}=\sum _{k=0}^n2^k\binom{n}{k}\binom{n}{n-k}=\sum _{k=0}^n2^k\binom{n}{k}^2$.

Cách 2: Ta có: $(1+2x)^n(1+x)^n=((1+x)^2+x(1+x))^n=\sum _{k=0}^n\binom{n}{k}(1+x)^{2k}x^{n-k}(1+x)^{n-k}=\sum _{k=0}^n\binom{n}{k}x^{n-k}(1+x)^{n+k}$.

Hệ số của $x^k$ trong $(1+x)^{n+k}$ là $\binom{n+k}{k}$. Suy ra hệ số của $x^n$ trong $(1+2x)^n(1+x)^n$ là $\sum _{k=0}^n\binom{n}{k}\binom{n+k}{k}$.

Vậy ta có điều phải chứng minh.

P.s: Lâu lắm rồi mới quay lại diễn đàn 

Cho p là một số nguyên tố bất kì khác 2 và khác 5. Chứng minh rằng trong dãy các số tự nhiên 9;99;999;9999;... có vô số số chia hết cho p

Theo giả thiết thì $(p,10)=1$ nên theo định lí Fermat nhỏ thì: $10^{p-1}\equiv 1 (mod$ $p)$.

Do đó chỉ cần chọn $k$ là một bội của $p-1$ thì $p\mid 10^k-1$. Dễ thấy có vô hạn số $k$ như vậy.

Lời giải:

Trước hết ta gọi $C_1,C_2,...,C_n$ lần lượt là các thị trấn theo thứ tự từ trái sang phải. Dễ dàng suy ra từ giả thiết rằng nếu một thị trấn $C_i$ có thể ủi được thị trấn $C_j$ thì thị trấn $C_i$ sẽ ủi được tất cả mọi thị trấn nằm ở giữa hai thị trấn này.

Ta sẽ chứng minh bài toán bằng quy nạp mạnh theo $n$. Dễ thấy trường hợp $n=1$ là hiển nhiên.

Bây giờ ta giả sử bài toán đúng với mọi $k<n$. Trước hết ta thấy có hai chiếc máy ủi "vô dụng" đó là chiếc bên trái của $C_1$ và chiếc bên phải của $C_n$, do đó ta bỏ qua hai chiếc máy này. Bây giờ nếu chiếc máy bên trái của $C_n$ ( hoặc chiếc bên phải của $C_1$) có thể ủi được tất cả các thị trấn thì bài toán được chứng minh, vì khi đó không một chiếc máy ủi nào có thể ủi lại chiếc máy ủi này và thị trấn $C_n$ không bao giờ bị ủi.

Giả sử nếu điều này là không thể. Bây giờ trong $2n-2$ chiếc máy ủi còn lại thì phải có một chiếc lớn nhất ( do kích thước các chiếc xe khác nhau). Ta có thể giả sử là chiếc bên phải của thị trấn $C_k$ với $k<n$. Khi đó chiếc xe này sẽ ủi hết tất cả các chiếc xe khác ở bên phải của nó và do đó nó sẽ ủi tất cả các thị trấn $C_{k+1},...,C_n$. Do đó nếu ta loại bỏ các thị trấn này đi thì các thị trấn còn lại sẽ không thay đổi trạng thái ủi và bị ủi của mình. Hơn nữa theo giả thiết quy nạp do $k<n$ nên trong $k$ thị trấn này có $1$ thị trấn không bao giờ bị ủi. Vậy giả thiết quy nạp đúng và bài toán được chứng minh. $\square$

Có thể mở rộng bài toán: Tìm hằng số $k$ lớn nhất để bất đẳng thức sau đúng:

                           $a^2+b^2+c^2+kabc\geqslant 3+k$

Có thể chọn $a=b=\frac{3}{2}$, $c=0$ thì ta được $k\leq \frac{3}{2}$. Ta sẽ chứng minh $k=\frac{3}{2}$ là hằng số tốt nhất cần tìm. Tức là ta chứng minh $2(a^2+b^2+c^2)+3abc\geq 9$.

Đặt $q=ab+bc+ca,r=abc,p=a+b+c=3$, bất đẳng thức tương đương $9+3r-4q\geq 0$.

Xét hai trường hợp:

$\text{TH 1:}$ $q\leq \frac{9}{4}$. Ta có: $9+3r-4q\geq 9-4q\geq 0$. (đúng)

$\text{TH 2:}$ $q\geq \frac{9}{4}$. Áp dụng bất đẳng thức Schur ta có:

$9+3r-4q\geq 9+3\frac{p(4q-p^2)}{9}-4q=9+(4q-9)-4q=0$.

Vậy với cả hai trường hợp bất đẳng thức đúng. Vậy bài toán được chứng minh.

Bài 2: Cho $x,y,z$ là các số thực dương thỏa mãn: $x(x+y+z)=3yz$. Chứng minh rằng: $(x+y)^3+(x+z)^3+3(x+y)(y+z)(z+x)\le 5(y+z)^3$

Ủng hộ bài đầu tiên 

Giả thiết bài toán có thể viết lại thành: $(x+y)(x+z)=4yz$.

Áp dụng bất đẳng thức Bunyakovsky, ta có:

$(x+y)(x+z)\geq (x+\sqrt{yz})^2\Rightarrow 4yz\geq (x+\sqrt{yz})^2\Rightarrow x\leq \sqrt{yz}$

Vậy ta có:

$(x+y)^3+(x+z)^3\leq (y+\sqrt{yz})^3+(z+\sqrt{yz})^3$

$=(\sqrt{y}+\sqrt{z})^3((\sqrt{y})^3+(\sqrt{z})^3)=(\sqrt{y}+\sqrt{z})^4(y-\sqrt{yz}+z)$

$=\frac{1}{4}(y+2\sqrt{yz}+z)^2(4y-4\sqrt{yz}+4z)\leq \frac{1}{4}(\frac{4y-4\sqrt{yz}+4z+2(y+2\sqrt{yz}+z)}{3})^3=2(y+z)^3$

Và ta cũng có: $3(x+y)(y+z)(z+x)=12yz(y+z)\leq 3(y+z)^3$. Do ta có bất đẳng thức quen thuộc $(y+z)^3\geq 4yz(y+z)\Leftrightarrow 3(y-z)^2(y+z)\geq 0$

Cộng hai bất đẳng thức trên và ta được $(x+z)^3+(x+y)^3+3(x+y)(y+z)(z+x)\leq 5(y+z)^3$.

Nên có đpcm.

Tìm tất cả các hàm số $f:\mathbb{N}^*\rightarrow \mathbb{N}^*$ thỏa mãn hệ thức:

$f(\frac{f(n)}{n})=n^2$

với mọi số nguyên dương $n$.

Ta viết lại đề như sau: Tìm số tự nhiên $N_0$ lớn nhất không thể biểu diễn được dưới dạng $6x+10y+15z$ trong đó $x,y,z$ là các số tự nhiên. Hay nói cách khác mọi số tự nhiên lớn hơn $N_0$ đều biểu diễn được dưới dạng $6x+15y+10z$ với $x,y,z$ là các số tự nhiên.

Để giải bài toán này, ta sử dụng bổ đề sau:

Định lí Sylvester: Cho $a,b$ là hai số nguyên dương nguyên tố cùng nhau. Khi đó $N_0=ab-a-b$ là số nguyên dương lớn nhất không biểu diễn được dưới dạng $ax+by$ với $x,y$ là các số tự nhiên.

Bằng định lí này ta sẽ chứng minh kết quả khác: Cho $a,b,c$ là ba số nguyên dương đôi một nguyên tố cùng nhau. Khi số $N_0=2abc-ab-bc-ca$ là số nguyên dương lớn nhất không thể biểu diễn được dưới dạng $abx+bcy+caz$ với $x,y,z$ là các số tự nhiên.

(1) Ta sẽ chứng minh $2abc-ab-bc-ca$ không biểu diễn được dưới dạng $abx+bcy+caz$. Thật vậy nếu tồn tại $x,y,z$ tự nhiên để:

$2abc-ab-bc-ca=abx+bcy+caz$

$\Leftrightarrow 2abc=ab(x+1)+bc(y+1)+ca(z+1)\Rightarrow b\mid ca(z+1)\Rightarrow b\mid z+1\Rightarrow z+1\geq b$

Tương tự ta được $x+1\geq c$ và $y+1\geq a$ và ta suy ra $ab(x+1)+bc(y+1)+ca(z+1)\geq 3abc>2abc$ vô lí.

(2) Ta sẽ chứng minh tồn tại $x,y,z$ để $m+2abc-ab-bc-ca+1=abx+bcy+caz$ với $m\geq 0$. Biến đổi đẳng thức tương đương với:

$b(ax+cy-ac+a+c-1)+acz=m+abc-ac-b+1\geq abc-ac-b+1$

Theo định lí Sylvester thì tồn tại $u,z$ tự nhiên để $bu+acz=m+abc-ac-b+1$. Hơn nữa do $u\geq 0$ nên cũng tồn tại $x,y$ tự nhiên để $ax+cy=u+ac-a-c+1$. Và từ đó dễ dàng suy ra tồn tại $x,y,z$ tự nhiên thỏa mãn. Vậy kết quả được chứng minh.

Với $a=2,b=3,c=5$ thì ta được $N_0=29$. Vậy $29$ là số lớn nhất thỏa mãn đề bài.

Giả sử $1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}=\frac{a_n}{b_n}$, trong đó $a_n,b_n$ là hai số nguyên tố cùng nhau. Chứng minh rằng tồn tại vô hạn số $n$ để $b_{n+1}<b_n$.

Giả sử ta có các số thực dương $x_1,x_2,...,x_k$ thỏa mãn điều kiện:

$x_1^2+x_2^2+...+x_k^2<\frac{x_1+x_2+...+x_k}{2}$

$x_1+x_2+...+x_k<\frac{x_1^3+x_2^3+...+x_k^3}{2}$

Tìm giá trị nhỏ nhất của $k$ và với giá trị $k$ đó, hãy chỉ ra một bộ số $(x_1,x_2,...,x_k)$ thỏa mãn điều kiện trên.

Bạn thử kiểm tra lại.  Chú ý số hạng $\dfrac{x^{2}+x\sqrt{x}+2}{x+x\sqrt{x}+4}.$

 

Phương trình này có ít nhất một nghiệm khác trong $\left(\frac{3}{2},2\right)$?

À vâng em có đã kiểm tra và hơi sai sót một tí. Thật sự ra thì cách giải của em không có vấn đề gì mà do anh NTA1907 ghi đề bị sai sót đó anh. Đề chính xác phải là:

$\dfrac{3+\sqrt{x}}{x^{2}+x\sqrt{x}+x+3}+\dfrac{x+\sqrt{x}+2}{x^{2}+x\sqrt{x}+4}+\dfrac{x\sqrt{x}+x+2}{x^{2}+\sqrt{x}+4}+\dfrac{x^{2}+x\sqrt{x}+2}{x+\sqrt{x}+4}+\dfrac{x^{2}+3}{x\sqrt{x}+x+\sqrt{x}+3}=\dfrac{10}{3}$

Tức là phải sửa số hạng $\frac{x^2+x\sqrt{x}+2}{x+x\sqrt{x}+4}$ thành $\frac{x^2+x\sqrt{x}+2}{x+\sqrt{x}+4}$.

Đây hình như là đề đề nghị Olympic 30/4.

Nhân tiện vì không có ai gửi bài nên em xin tiếp tục:

Bài 93: Giải phương trình: $\sqrt{2x+15}=32x^2+32x-20$.

Bài 91: Giải phương trình:

$\dfrac{3+\sqrt{x}}{x^{2}+x\sqrt{x}+x+3}+\dfrac{x+\sqrt{x}+2}{x^{2}+x\sqrt{x}+4}+\dfrac{x\sqrt{x}+x+2}{x^{2}+\sqrt{x}+4}+\dfrac{x^{2}+x\sqrt{x}+2}{x+x\sqrt{x}+4}+\dfrac{x^{2}+3}{x\sqrt{x}+x+\sqrt{x}+3}=\dfrac{10}{3}$

Bài này thì ý tưởng là dùng bất đẳng thức:

Điều kiện $x\geq 0$

Ta đặt $a=2,b=\sqrt{x}+1,c=x^2+1,d=x\sqrt{x}+1,e=x+1$. Khi đó phương trình tương đương: $\sum \frac{a+b}{c+d+e}\geq \frac{10}{3}$

Ta sẽ chứng minh: $\sum \frac{a+b}{c+d+e}\geq \frac{10}{3}$ với mọi $a,b,c,d,e$ dương.

Thật vậy ta có: $\sum \frac{a+b}{c+d+e}\geq \frac{10}{3}\Leftrightarrow (a+b+c+d+e)\sum \frac{1}{a+b+c}\geq \frac{25}{3}$.

Mà theo BĐT Cauchy Schwarz thì $\sum \frac{1}{a+b+c}\geq \frac{25}{3(a+b+c+d+e)}$ 

Tù đó ta suy ra điều phải chứng minh. Hơn nữa đẳng thức xảy ra khi và chỉ khi $a=b=c=d=e$ tức là $x=1$. Từ đó suy ra phương trình có nghiệm duy nhất $x=1$.

Mạn phép cho em nói một tí  : Em thấy topic có vẻ hơi lạc hướng của Marathon mà dần trở thành Topic thảo luận về phương trình và hệ phương trình rồi ạ.

Vì hướng tới thi olympic nên em xin đề xuất bài tiếp theo:

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

$\left\{\begin{matrix} x_1+x_2+x_3+x_4+x_5=1\\ (x_1+x_2)(x_1+x_2+x_3)(x_1+x_2+x_3+x_4)=256x_1x_2x_3x_4x_5\\ x_1,x_2,x_3,x_4,x_5> 0\\ \end{matrix}\right.$

Giả sử $a$ là nghiệm của phương trình:

$2013x^3+2014x^2+2015x+2016=0$

Và $b$ là nghiệm của phương trình:

$2014x^3+2015x^2+2016x+2017=0$

Chứng minh rằng $a<b$.

Gọi $N$ là số nghiệm nguyên của phương trình $x^2-y^2=z^3-t^3$, với điều kiện $0\leq x, y, z, t\leq 10^6$, và $M$ là số nghiệm nguyên của phương trình $x^2-y^2=z^3-t^3+1$, với điều kiện tương tự. Chứng minh $N> M$.

(IMO Shortlist 1979)

Hai phương trình trên tương đương: $x^2+t^3=y^2+z^3$ và $x^2+t^3=y^2+z^3+1$.

Ta kí hiệu $f(n)$ tương ứng là số nghiệm của phương trình $a^2+b^3=n$ với $n$ là số tự nhiên.

Ta xét với một số tự nhiên $n$ $(0\leq n\leq 10^{12}+10^{18})$ thì ta có phương trình: $x^2+t^2=y^2+z^3=n$ thì khi đó phương trình $x^2+t^3=n$ có $f(n)$ nghiệm và phương trình $y^2+z^3=n$ cũng có $f(n)$ nghiệm. Vậy khi đó số nghiệm $(x,y,z,t)$ của phương trình $x^2+t^3=y^2+z^3=n$ là $f(n)^2$. Và như thế, đặt $k=10^{12}+10^{18}$ thì ta sẽ tính được: 

$N=\sum _{n=0}^k f(n)^2$

Tương tự: Ta xét với một số tự nhiên $n$ $(0\leq n\leq 10^{12}+10^{18})$ thì ta có phương trình: $x^2+t^2=y^2+z^3+1=n$. Khi đó phương trình $x^2+t^3=n$ có $f(n)$ nghiệm còn phương trình $y^2+z^3+1=n$ có $f(n-1)$ nghiệm nên

$M=\sum _{n=0}^k f(n).f(n-1)$

Ta có:

$N-M=\sum _{n=0}^k f(n)^2-\sum _{n=0}^k f( n).f(n-1)=\frac{1}{2} \sum _{n=0}^k(f(n)-f(n-1))^2> 0$

Bởi vì đẳng thức không thể xảy ra do $f(0)\neq f(1)$. (do $f(0)=1, f(1)=2$)

Nên $N>M$ và ta kết thúc chứng minh.