Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


the unknown

Đăng ký: 10-03-2016
Offline Đăng nhập: 27-02-2020 - 21:06
****-

#704950 VN TST 2018

Gửi bởi the unknown trong 05-04-2018 - 15:56

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õ.




#704837 VN TST 2018

Gửi bởi the unknown trong 03-04-2018 - 23:18

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ý.




#703604 Dịch bệnh tại vương quốc Wakanda

Gửi bởi the unknown trong 15-03-2018 - 22:29

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)




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

Gửi bởi the unknown trong 11-09-2017 - 20:18

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$.




#692855 CM với mỗi $\alpha>0$,số giá trị của $k$ luôn bé...

Gửi bởi the unknown trong 11-09-2017 - 18:39

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.




#675655 ĐỀ VIỆT NAM TST 2017

Gửi bởi the unknown trong 29-03-2017 - 20:57

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.

 




#668370 Đề thi chọn đội dự tuyển lớp 10 PTNK - ĐHQGTPHCM

Gửi bởi the unknown trong 15-01-2017 - 10:22

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.




#668294 Đề thi chọn đội dự tuyển lớp 10 PTNK - ĐHQGTPHCM

Gửi bởi the unknown trong 14-01-2017 - 18:56

Đạ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----------------------------------------------------------




#667342 Đề Thi VMO năm 2017

Gửi bởi the unknown trong 06-01-2017 - 20:30

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.




#663163 Chứng minh rằng: $\left | S_1 \right |-\left | S_2 \...

Gửi bởi the unknown trong 27-11-2016 - 10:24

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.




#663025 $\sum_{k=0}^{n}\begin{pmatrix} n...

Gửi bởi the unknown trong 25-11-2016 - 19:40

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  :P




#649054 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...

Gửi bởi the unknown trong 11-08-2016 - 18:50

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.




#649011 CMR có một thị trấn không thể bị "ủi" (IMO Shortlist 2015 C1)

Gửi bởi the unknown trong 11-08-2016 - 14:26

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$




#648558 Topic: [LTDH] Mỗi ngày hai bất đẳng thức.

Gửi bởi the unknown trong 08-08-2016 - 12:34

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.




#648428 Topic: [LTDH] Mỗi ngày hai bất đẳng thức.

Gửi bởi the unknown trong 07-08-2016 - 16:36

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  :D

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.