Chủ đề này có 173 trả lời

[tritanngo99]

Bài 115: Đa thức $P(x)$ bậc $n$ với hệ số thực có $n$ nghiệm thực phân biệt. Hỏi $P(x)$ có thể có nhiều nhất bao nhiêu hệ số bằng $0$?

Bài 116: Cho $k,n$ là các số nguyên dương. Chứng minh rằng : Số nghiệm nguyên không âm của phương trình $x_1+x_2+...+x_k=n$ là $C_{n+k-1}^{k-1}$.  

[tritanngo99]

Lời giải bài 115: Ta gọi $S(n)$ là số hệ số bằng $0$ nhiều nhất mà $1$ đa thức hệ số thực bậc $n$ với $n$ nghiệm thực phân biệt có thể có, $T(P)$, với $P$ là một đa thức là số hệ số bằng $0$ của $P$.

Ta có một số tính chất sau:

(i) $S(1)=1$( do $S(1)\le 1$ và xét đa thức $P(x)=x$ có $1$ hệ số bằng $0$)

(ii) $S(2)=1$( do mọi đa thức $P(x)=ax^2+bx+c(a\ne 0)$ không thể có $b=c=0$ và có $2$ nghiệm phân biệt).

(iii) Nếu đa thức $P(x)$ bậc $1$ có $T(P)=1$ thì $P(0)=0$.

(iv) Giả sử $P(x)=\sum\limits_{i=0}^{n}a_ix^i$ thì $P'(x)=\sum\limits_{i=1}^{n}ia_ix^{i-1}$. Nên nếu $T(P)=k$ thì $T(P')=k$ hoặc bằng $k-1$ và $T(P')=k-1\iff P(0)=0$.

Ta tìm $S(n)$ thông qua quy nạp theo $n$.

Qua $(i),(ii),(iii)$ ta kiểm chứng được giả thiết quy nạp:

$\left\{\begin{array}{I} S(2k)=k\\ S(2k-1)=k-1\forall k=\overline{1;N}\\ \text{ Nếu } deg(P)=2k-1 \text{ và } T(P)=k \text{ thì } P(0)=0\end{array}\right.$

Ta sẽ chứng minh: $\left\{\begin{array}{I} S(2N+1)=N+1(*)\\ S(2N+2)=N+1(**)\\ \text{ Nếu } deg(P)=2N+1 \text{ và } T(P)=N+1 \text{ thì } P(0)=0(***)\end{array}\right.$

Thật vậy, bắt đầu với $(*)$ và $(***)$. Xét đa thức $P$ thỏa $deg(P)=2N+1;P$ có $2N+1$ nghiệm thực phân biệt. Ta có $P'$ là $1$ đa thức bậc $2N$ có $2N$ nghiệm thực phân biệt (Giữa $2$ nghiệm của $P$ luôn có $1$ nghiệm của $P'$ theo định lý Rolle). Nên ta có: $T(P)\le T(P')+1\le S(2N)+1=N+1$. Để dấu $=$ xảy ra thì theo $(iv): P(0)=0$.

 

Ta kiểm chứng được sự tồn tại của dấu bằng qua đẳng thức: $P(x)=x(x^2-1)(x^2-2)...(x^2-N)$. Vậy $S(2N+1)=N+1$.

Ta tiếp tục với $(**)$. Xét đa thức $P$ thỏa $deg(P)=2N+2$; $P$ có $2N+2$ nghiệm thực phân biệt. Ta có $P'$ là $1$ đa thức bậc $2N+1$ có $2N+1$ nghiệm thực phân biệt.

Ta có: $T(P)\le T(P')+1\le S(2N)+1=N+2$. Giả sử tồn tại đa thức $P$ như vậy có $T(P)=N+2$. Suy ra:

$\left\{\begin{array}{I} P(0)=0\\ T(P')=N+1\text{ nên } P'(0)=0\end{array}\right.$. Suy ra $P$ có nghiệm kép là $0$ (loại).

Vậy suy ra: $T(P)\le N+1$. Ta kiểm chứng được sự tồn tại của dấu bằng qua đa thức:

$P(x)=(x^2-1)(x^2-2)...(x^2-N)(x^2-N-1)$. Vậy $S(2N+2)=N+1$. 

 

Vậy ta suy ra: $S(2n+1)=n+1$ và $S(2n+2)=n+1$ với mọi $n\in \mathbb{N}$.

Hay số hệ số bằng $0$ nhiều nhất mà một đa thức hệ số thực bậc $n$ với $n$ nghiệm phân biệt có thể có là $[\frac{n+1}{2}]$.

Lời giải bài 116: Ta cho tương ứng mỗi nghiệm nguyên không âm của phương trình $x_1+x_2+...+x_n=n(1)$ với một xâu nhị phân độ dài $n+k-1$ trong đó có $n$ bít $1$ và $k-1$ bít $0$, cụ thể xâu gồm $x_1$ bít $1$, sau đó là $1$ bít $0$, tiếp theo là $x_2$ bít $1$, sau đó là $1$ bít $0$, cứ như thế, cuối cùng là $x_k$ bít $1$. Dễ dàng chứng minh được đây là một song ánh từ tập $A$ các nghiệm nguyên không âm của $(1)$ vào tập hợp $B$ các xâu nhị phân độ dài $n+k-1$ với $n$ bít $1$ và $k-1$ bít $0$. Từ đó theo nguyên lý song ánh ta có: $|A|=|B|=C_{n+k-1}^{k-1}$. Ta có điều phải chứng minh.

Ps: Đây chính là bài toán chia kẹo Ơ-le.

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 02-11-2018 - 19:18

[tritanngo99]

Bài 117: Cho tập $S=\left\{1,2,3,...,2009\right\}$. $A$ là tập con có $n$ phần tử của $S$. Tìm $n$ nhỏ nhất sao cho với mọi cách chọn tập $A$ thì trong $A$ luôn có hai phần tử $a,b$ mà $\frac{a}{b}=3$.

Bài 118: Chứng minh rằng phương trình sau không có nghiệm nguyên khác $0: x^3+3y^3+9z^3=0$.

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 03-11-2018 - 05:44

[tritanngo99]

Lời giải bài 117: Với mỗi số nguyên dương $x$, ta kí hiệu $v(x)$ là số nguyên không âm lớn nhất thỏa mãn $3^{v(x)}|x$( nói cách khác, nếu đặt $v(x)=k$) thì $x$ chia hết cho $3^k$ và không chia hết cho $3^{k+1}$. Bây giờ, ta chia tập $S$ thành các tập con $S_i$ thỏa mãn: $S_i=\left\{x\in S|v(x)=i\right\}$.

Ta chứng minh rằng số phần tử được chọn là nhiều nhất nếu ta chọn các tập $S_0,S_2,S_4,...$. Thật vậy, với mỗi số nguyên dương $k$ không chia hết cho $3$, xét tập $T_k=\left\{k,3k,3^2k,...\right\}$. Rõ ràng các tập $T_k$ phủ kín $S$.

Xét một giá trị $k$ bất kì. Khi đó, trong tập $A$ được chọn sẽ không tồn tại hai phần tử liên tiếp cùng nằm trong $T_k$. Như thế, nếu đặt $s$ là số nguyên không âm lớn nhất sao cho $3^s.k<2009$ thì ta chỉ có thể được chọn nhiều nhất $[\frac{s+1}{2}]$ phần tử thuộc $T_k$, và giá trị đó đạt được nếu ta chọn các số $k,3^2k,3^4k,...$.

Do mệnh đề trên đúng với số $k$ nguyên dương bất kì, nên gộp lại, số phần tử được chọn sao cho không có phần tử nào nhiều gấp ba lần phần tử kia nằm trong các tập $S_0,S_2,...$. Tính toán trực tiếp, ta có:

$|S_0|=1340,|S_1|=446,|S_2|=149,|S_3|=50,|S_4|=16,|S_5|=6,|S_6|=2,|S_i|=0\forall i\ge 7$.

Và do đó, nếu ta chon $1507$ phần tử nằm trong các tập $S_0,S_2,S_4,S_6$ thì bất kì hai phần tử $a,b$ phân biệt nào thuộc $S$ cũng đều thỏa mãn $a\ne 3b$. Vậy tập hợp $A$ cần có ít nhất $1508$ phần tử, hay giá trị nhỏ nhất của $n$ là $1508$.

Lời giải bài 118: Giả sử phương trình đã cho có nghiệm nguyên khác $0$. Không mất tính tổng quát, ta có thể chọn được nghiệm nguyên $(x_0,y_0,z_0)$ sao cho $x_0\ne 0$ và $|x_0|$ có giá trị nhỏ nhất.

Ta có: $x_0^3+3y_0^3+9z_0^3=0$ suy ra $x_0^3$ chia hết cho $3$, vậy $x_0$ cũng chia hết cho $3$. Đặt $x_0=3x_1(x_1\in \mathbb{Z})$.

Ta được $3^3x_1^3+3y_0^3+9z_0^3=0\iff 3^2x_1^3+y_0^3+3z_0^3=0$ suy ra $y_0^3\vdots 3\implies y_0\vdots 3$. Đặt $y_0=3y_1(y_1\in\mathbb{Z})$.

Ta được: $9x_1^3+3^3y_1^3+3z_0^3=0\iff 3x_1^3+9y_1^3+z_0^3=0\implies z_0^3\vdots 3\implies z_0\vdots 3$. Đặt $z_0=3z_1(z_1\in\mathbb{Z})$.

Ta được: $x_1^3+3y_1^3+9z_1^3=0$, vậy $(x_1,y_1,z_1)$ cũng là nghiệm nguyên của phương trình đã cho. Nhưng $|x_1|=\frac{|x_0|}{3}<|x_0|$. Mâu thuẩn với cách chọn $x_0$. Vậy phương trình không có nghiệm nguyên khác $0$.

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 05-11-2018 - 18:59

[tritanngo99]

Bài 119: Xét số Fermat $F_n=2^{2^n}+1(n\ge 2)$. Chứng minh rằng nếu $p$ là ước nguyên tố của $F_n$ thì $p\equiv 1(\text{ mod } 2^{n+1})$.

Bài 120: Với mỗi số nguyên dương $n$, ta đặt $x_n=C_{2n}^n$.

Chứng minh rằng tồn tại hai tập hợp vô hạn $A,B$ sao cho $A\cap B=\emptyset$ và $\frac{\prod\limits_{i\in A}x_i}{\prod\limits_{i\in B}x_i}=2012$. 

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 05-11-2018 - 18:59

[tritanngo99]

Lời giải bài 119: Đặt $k=ord_{p}2$. Ta có: $p|F_n$ nên $2^{2^{n}}\equiv -1(\text{ mod }p)$, suy ra rằng: $2^{2^{n+1}}\equiv 1(\text{ mod }p)$.

Theo tính chất của cấp thì $k|2^{n+1}$, tuy nhiên $k$ không phải là ước của $2^n$, vì nếu không thì $-1\equiv 2^{2^n}\equiv 1(\text{ mod }p)$, suy ra $2|p$, vô lý do $F_n$ là số lẻ với $n\ge 2$.

Vậy $k=2^{n+1}$. Nhưng vì $k=ord_{p}2$ nên $k|(p-1)$ tức là $p\equiv 1(\text{ mod }2^{n+1})$.

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

Lời giải bài 120: Ta thấy rằng: $\frac{x_n}{x_{n-1}}=\frac{C_{2n}^n}{C_{2n-2}^{n-1}}=\frac{(2n)!}{n!n!}:\frac{(2n-2)!}{(n-1)!(n-1)!}=\frac{2n(2n-1)}{n^2}=\frac{2(2n-1)}{n}$.

Do đó với $a,b\in \mathbb{Z^+}$ thì: $\frac{x_a}{x_{a-1}}.\frac{x_b}{x_{b-1}}=4.(\frac{2a-1}{a}).(\frac{2b-1}{b})$.

Ta sẽ chọn $k\in \mathbb{Z^+}$ sao cho $(\frac{2a-1}{a})(\frac{2b-1}{b})=\frac{8k-1}{2k}\implies b=\frac{2k(2a-1)}{a-4k}$.

Chọn $a=4k+2$ hoặc $a=6k$ thì đều có giá trị $b$ nguyên và tương ứng là $b=k(8k+3)$ hoặc $b=12k-1$.

Từ đó ta có: $\frac{x_{4k+2}}{x_{4k+1}}.\frac{x_{8k^2+3k}}{x_{8k^2+3k+1}}=\frac{2(8k-1)}{k}=\frac{x_{6k}}{x_{6k-1}}.\frac{x_{12k-1}}{x_{12k-2}}$.

Với $k\ge 100$, ta chọn:

$A_1=\left\{4k+1,6k,12k-1,8k^2+3k-1\right\},B_1=\left\{4k+2,6k-1,12k-2,8k^2+3k\right\},k\ge 100$.

$A=A_0\cup A_1,B=B_0\cup B_1$.

Đến đây, ta thấy rằng tỉ số giữa tích của các giá trị $x_i$ có chỉ số tương ứng lần lượt thuộc $A_1,B_1$ sẽ là $1$ và chỉ cần chọn $A_0,B_0$ thích hợp.

Ta xét $A_0=\left\{1,5,252\right\},B_0=251$, dễ thấy: $\frac{C_1^1C_{10}^{5}C_{504}^{252}}{C_{502}^{251}}=\frac{2.252.4.(2.252-1)}{2.252}=2012$.

Ta thấy rằng hai tập $A,B$ đều là các tập vô hạn, rời nhau và có: $\frac{\prod\limits_{i\in A}x_i}{\prod\limits_{i\in B}x_i}=2012$ nên chúng thỏa mãn đề bài và ta có điều phải chứng minh.

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 06-11-2018 - 20:00

[tritanngo99]

Bài 121: Tìm số tập con của tập $X=\left\{1,2,...,n\right\}(n\ge 2)$ sao cho trong mỗi tập con chứa ít nhất hai phần tử là hai số nguyên liên tiếp.

Bài 122: Trong hình vuông diện tích bằng $6$, đặt ba đa giác diện tích bằng $3$. Chứng minh rằng luôn tìm được hai đa giác mà diện tích phần chung của chúng không nhỏ hơn $1$.

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 07-11-2018 - 05:14

[tritanngo99]

Lời giải bài 121: Gọi $S_n$ là tập hợp các tập con không rỗng của tập $X$ mà trong mỗi tập con không có hai phần tử nào là hai số nguyên liên tiếp. Chia các phần tử của $S_n$ thành hai nhóm: 

- Nhóm không chứa phần tử $n$: Số các tập con kiểu này là $|S_{n-1}|$.

- Nhóm có chứa phần tử $n$ (và vì thế không thể chứa phần tử $n-1$): Tập con kiểu này chỉ có thể là $n$ hoặc $A\cup \left\{n\right\}$ trong đó $A$ là tập con của $S_{n-2}$. Số các tập con kiểu này là $|S_{n-2}|+1$.

Do đó: $|S_n|=|S_{n-1}|+|S_{n-2}|+1$.

Xét cụ thể các trường hợp $n=2,n=3$, ta có: $|S_2|=3,|S_3|=4$.

Từ đó ta có: $|S_n|=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n+2}-(\frac{1-\sqrt{5}}{2})^{n+2}]-1$.

Mặt khác, số tập con không rỗng của $X$ là $2^n-1$.

Vậy số tập con thỏa mãn điều kiện bài toán là: $2^n-\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n+2}-(\frac{1-\sqrt{5}}{2})^{n+2}]$

Lời giải bài 122: Gọi ba đa giác $M_1,M_2$ và $M_3$. Kí hiệu $|A|$ là diện tích của hình phẳng $A$.

Khi đó dễ thấy: $|M_1\cup M_2\cup M_3|=|M_1|+|M_2|+|M_3|-(|M_1\cap M_2|+|M_2\cap M_3|+|M_3\cap M_1|)+|M_1\cap M_2\cap M_3|(1)$.

Theo giả thiết ta có $|M_1|=|M_2|=|M_3|=3(2)$.

Để ý rằng $M_1\cup M_2\cup M_3$ nằm trong hình vuông có diện tích bằng $6$, nên từ $(1),(2)$ suy ra bất đẳng thức sau:

$6\ge 9-(|M_1\cap M_2|+|M_2\cap M_3|+|M_3\cap M_1|)+|M_1\cap M_2\cap M_3|(3)$

Hay $|M_1\cap M_2|+|M_2\cap M_3|+|M_3\cap M_1|\ge 3+|M_1\cap M_2\cap M_3|$.

Do $|M_1\cap M_2\cap M_3|\ge 0$ nên từ $(3)$ ta có:

$|M_1\cap M_2|+|M_2\cap M_3|+|M_3\cap M_1|\ge 3(4)$.

Từ $(4)$ và theo nguyên lý Dirichlet suy ra tồn tại ít nhất một trong $3$ số: $|M_1\cap M_2|,|M_2\cap M_3|,|M_3\cap M_1|$ lớn hơn hoặc bằng $1$.

Giả sử: $|M_1\cap M_2|\ge 1$.

Điều đó có nghĩa là hai đa giác $M_1$ và $M_2$ có diện tích phần chung không nhỏ hơn $1$. Bài toán được chứng minh.

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 09-11-2018 - 17:22

[tritanngo99]

Bài 123: Trong một cuộc thi đấu bóng bàn. An và Bình quy ước với nhau: người thắng cuộc là người đầu tiên thắng $3$ ván hoặc thắng $2$ ván liên tiếp và không có trận hòa. Hãy xác định số khả năng có thể.

Bài 124: Cho dãy số $(U_n)$ xác định bởi: $\left\{\begin{array}{I}u_1=\frac{1}{2}\\ u_{n+1}=\frac{3}{2}u_n^2-\frac{1}{2}u_n^3,\forall n\ge 1\end{array}\right.$

Chứng minh rằng dãy số trên có giới hạn hữu hạn và tìm giới hạn đó.

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 25-11-2018 - 07:10

[tritanngo99]

Lời giải bài 123: Dùng $A$ để ký hiệu An thắng, $B$ để ký hiệu Bình thắng. Dùng cây mô tả toàn bộ hiện trạng có khả năng xảy ra.

Xây dựng cây: Xuất phát từ điểm $S$.

+ Ván đầu tiên có hai khả năng: An thằng hoặc Bình thắng, nên lấy hai điểm sao cho hai điểm này với $S$ không thẳng hàng. Một trong hai điểm này ghi $A$, còn điểm còn lại ghi $B$. Nối $S$ với $A$ bằng một đoạn thẳng hoặc một đoạn cong để biểu thị $A$ thắng. Tương tự, để biểu thị $B$ thắng nối $S$ với $B$ bằng một đoạn thẳng hoặc một đoạn cong.

+ Ván thứ $2$ lại có hai khả năng: An thắng hoặc Bình thắng, nên xuất phát từ $A$ cũng lấy hai điểm mới ghi các ký hiệu tương ứng $A,B$ và từ $A$ kẻ hai đoạn thẳng hoặc hai đoạn cong tới hai điểm mới thêm. Đối với $B$ cũng chọn thêm hai đỉnh mới ghi $A$ và $B$, rồi từ $B$ kẻ hai đoạn thẳng hoặc hai đoạn cong đi tới hai điểm mới thêm.

Tiếp theo thực hiện kéo dài các đường một cách tương tự nhưng do quy ước của An và Bình những đường mà trên đó xuất hiện $2$ đỉnh liên tiếp ghi cùng một ký hiệu hoặc có $3$ đỉnh được ghi cùng một ký hiệu thì không được kéo dài.

Vì An và Bình đấu với nhau $5$ ván thì hoặc có người thắng $2$ ván liên tiếp hoặc có người thắng $3$ ván. Do đó những đường xuất phát từ $S$ có không quá $5$ cạnh.

Cây có $10$ đỉnh ngọn nên có $10$ khả năng xảy ra.

Lời giải bài 124:

+Xét hàm số: $f(x)=\frac{3}{2}x^2-\frac{1}{2}x^3$ với $x\in [0;1]$, ta có: $f'(x)=3x-\frac{3}{2}x^2\ge 0\forall x\in [0;1]$.

$\implies f(x)$ tăng trên $[0;1]$ và $0\le f(x)\le 1\forall x\in [0;1]$.

+Chứng minh: $u_n\in [0;1]\forall n\ge 1$.

Thật vậy: $u_1=\frac{1}{2}\in [0;1]$.

Giả sử: $u_k\in [0;1],\forall k>1$ thì:

$\left\{\begin{array}{I} u_{k+1}=\frac{3}{2}u_k^2-\frac{1}{2}u_k^3\\ 0\le u_k\le 1\end{array}\right.\implies 0\le u_{k+1}\le 1\implies u_{k+1}\in [0;1]$.

Vậy $u_n\in [0;1],\forall n\ge 1$.

Do $f$ là hàm tăng nên $f(u_n)-f(u_{n-1})$ cùng dấu với $u_{n}-u_{n-1}$.

Suy ra: $u_{n+1}-u_n$ cùng dấu với $u_n-u_{n-1}$. Lập luận tiếp tục ta đi đến $u_{n+1}-u_n$ cùng dấu với $u_2-u_1$.

+ Vì $u_2-u_1=\frac{5}{16}-\frac{1}{2}=\frac{-3}{16}<0\implies u_{n+1}-u_n<0\implies u_{n+1}<u_n\forall n\ge 1$.

Suy ra $(u_n)$ là dãy giảm.

+ Lại do: $u_1=\frac{1}{2}$ nên suy ra được $u_n\in [0;\frac{1}{2}]$.

+ Do $(U_n)$ giảm và bị chặn nên theo Tiêu chuẩn Weierstrass nó có giới hạn. Giả sử $\lim\limits_{n\to+\infty}=a$ thì $0\le a\le \frac{1}{2}$.

+Chuyển qua giới hạn hệ thứ khi $n\to +\infty$, ta có:

$\frac{3}{2}a^2-\frac{1}{2}a^3\iff a=0,a=1,a=2$.

+ Do $0\le a\le \frac{1}{2}$. Vậy dãy số $(u_n)$ có giới hạn hữu hạn khi $n\to +\infty$ và $\lim\limits_{n\to +\infty}u_n=0$

 

 

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 25-11-2018 - 07:36

[tritanngo99]

Bài 126: Cho $p$ là một số nguyên tố, $n,k$ là các số nguyên không âm có biểu diễn trong cơ sở $p$ như sau:

$n=n_0+n_1p+...+n_tp^{t},k=k_0+k_1p+...+k_tp^t$.

Chứng minh rằng: $C_{n}^{k}\equiv C_{n_0}^{k_0}C_{n_1}^{k_1}...C_{n_t}^{k_t}(\text{ mod p})$.

Bài 127: Cho dãy số $\left\{a_n\right\}$ xác định bởi:

$\left\{\begin{array}{I} a_0=1999\\ a_{n+1}=\frac{a_n^2}{1+a_n},\forall n\ge 0\end{array}\right.$. Tìm phần nguyên của $a_n$ với $0\le n\le 999$. 

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 25-11-2018 - 07:51

[tritanngo99]

Lời giải bài 127: Ta có: $(a+b)^{p^{r}}\equiv a^{p^{r}}+b^{p^{r}}(\text{ mod }p)$ với mọi $r\ge 0$.

Do đó: 

$(1+x)^n=(1+x)^{n_0+n_1p+...+n_tp^{t}}$.

$\equiv (1+x)^{n_0}(1+x)^{n_1p}...(1+x)^{n_tp^{t}}$.

$\equiv (1+x)^{n_0}(1+x^{p})^{n_1}...(1+x^{p^{t}})^{n_t}$.

$\equiv (\sum\limits_{i_0=0}^{n_0}C_{n_0}^{i_0}x^{i_0})(\sum\limits_{i_1=0}^{n_1}C_{n_1}^{i_1}x^{i_1p})...(\sum\limits_{i_t=0}^{n_t}C_{n_t}^{i_t}x^{i_t.p^{t}}) \text{ mod }p$.

Vì $k$ có biểu diễn duy nhất trong cơ sở $p,k=k_0+k_1p+...+k_tp^{t}$ nên hệ số của $x^{k}$ trong biểu thức cuối cùng là: $C_{n_0}^{k_0}C_{n_1}^{k_1}...C_{n_t}^{k_t}$.

Từ đó ta có: $C_{n}^{k}\equiv C_{n_0}^{k_0}C_{n_1}^{k_1}...C_{n_t}^{k_t}\text{ mod }p$.

Điều phải chứng minh.

Lời giải bài 128: Rõ ràng: $a_n>0,\forall n\ge 0$ nên: 

$a_n-a_{n+1}=a_n-\frac{a_n^2}{1+a_n}=\frac{a_n}{1+a_n}>0,\forall n\ge 0$.

$\implies \left\{a_n\right\}$ là dãy giảm. (1)

$\implies a_{n+1}=\frac{a_n^2}{1+a_n}=a_n-\frac{a_n}{1+a_n}>a_n-1,\forall n\ge 0$.

$\implies a_{n+1}>a_0-(n+1),\forall n\ge 0$.

$\implies a_{n-1}>a_0-(n-1),\forall n\ge 2$.

$\implies a_{n-1}>2000-n,\forall n\ge 2$   (2).

Mặt khác ta lại có: $a_n=a_0t(a_1-a_0)+(a_2-a_1)+...+(a_n-a_{n-1})$.

$=1999-(\frac{a_0}{1+a_0}+\frac{a_1}{1+a_1}+...+\frac{a_{n-1}}{1+a_{n-1}})$.

$=1999-n+(\frac{1}{1+a_0}+\frac{1}{1+a_1}+...+\frac{1}{1+a_{n-1}})$   (3).

Từ $(1)(2)$ ta có: 

$0<\frac{1}{1+a_0}+\frac{1}{1+a_1}+...+\frac{1}{1+a_{n-1}}<\frac{n}{1+a_{n-1}}$.

$<\frac{n}{2001-n}<\frac{n}{1998-n}\le 1$( với $2\le n\le 1999$) (4).

Từ $(3),(4)$ ta có:

$1999-n<a_n<1999-n\pm 1$( với $2\le n<999$)

$\implies [a_n]=1999-n$. 

Kiểm tra trực tiếp:

+$a_0=1999\implies [a_0]=1999$.

+$a_1=\frac{a_0^2}{1+a_0}=a_0-\frac{a_0}{1+a_0}=1999-\frac{1999}{2000}$.

$\implies a_1=1998+\frac{1}{2000}$.

$\implies [a_1]=1998$.

Vậy $[a_n]=1999-n$( với $0\le n\le 1999$).

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 09-12-2018 - 19:44

[tritanngo99]

Bài 129: Có $17$ nhà toán học viết thư cho nhau, viết về $3$ đề tài khác nhau, mỗi người phải viết thư cho các người còn lại, biết từng cặp nhà toán học viết thư trao đổi cùng một đề tài. Chứng minh rằng có ít nhất $3$ nhà toán học viết thư cho nhau trao đổi về cùng $1$ đề tài.

Bài 130: Cho $\alpha \in (0;\frac{\pi}{2})$. Tìm $\lim\limits_{n\to +\infty}(cos^2\alpha. \sqrt[n]{cos\alpha}+sin^2\alpha\sqrt[n]{sin\alpha})^n$

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 09-12-2018 - 19:44

[tritanngo99]

Lời giải bài 129: Chọn $17$ điểm trên mặt phẳng và đặt tên là $OA_1,OA_2,...,OA_{16}.$ Và cứ $2$ điểm bất kì ta dùng màu đỏ nối hai điểm đó chỉ sự trao đổi đề tài thứ nhất, màu xanh là đề tài thứ $2$ và màu vàng chỉ đề tài thứ $3$.

Bổ đề: Trong phòng có $6$ người. Chứng minh rằng luôn tồn tại $3$ người đôi một quen nhau hoặc $3$ người đôi một không quen nhau.

Chứng minh bổ đề:

Xét $6$ điểm trên mặt phẳng. Chọn $1$ điểm bất kì, ta dùng đoạn nối liền giữa các điểm thể hiện sự quen nhau và các điểm nối nét đứt với nhau chỉ sự không quen nhau.

Bây giờ ta xét $6$ điểm $O,A,B,C,D,E$ lấy $O$ làm gốc.

Trong $5$ điểm còn lại, ta thấy $2$ người bất kỳ là quen nhau, hoặc là không quen nhau.

Theo nguyên lý Dirichlet thì tồn tại ít nhất $3$ đường thẳng nét liền từ $O$ đến $5$ điểm $A,B,C,D,E$ hoặc $3$ đường nối nét đứt.

Bây giờ ta chỉ cần xét sự quen nhau. Thật vậy, nếu trong $3$ điểm $A,B,C$ mà nối lại với nhau thì ta được $1$ tam giác có đỉnh là $O$, suy ra thỏa mãn bài toán. Nếu không nối lại thì $3$ điểm $A,B,C$ sẽ chỉ nối nhau bằng bét đứt cũng là điều phải chứng minh. Vậy luôn tìm được $3$ người đôi một quen nhau hoặc không quen nhau.

Giả sử các cạnh được tô nhiều nhất là màu đỏ, theo nguyên lý Dirichlet trong $16$ cạnh thì có ít nhất $6$ cạnh được tô màu đỏ. Giả sử đó là các cạnh $OA_1,OA_2,...,OA_6$. Trong $6$ điểm $A_1,A_2,...,A_6$ nếu có $2$ điểm được nối với nhau màu đỏ thì tạo thành $1$ tam giác màu đỏ có đỉnh là $O$ tức là đã có $3$ người trao đổi cùng một đề tài. 

Bây giờ xét $6$ điểm này không có $2$ điểm nào được nối với nhau màu đỏ thì phải nối với nhau màu xanh hoặc vàng.

Lúc này theo bài bổ đề trên thì luôn tồn tại trong $6$ điểm đó $3$ điểm cùng được nối bởi màu xanh hoặc màu vàng. Vậy bài toán được chứng minh.

Lời giải bài 130: Đặt $x_n=cos^2\alpha\sqrt[n]{cos\alpha}+sin^2\alpha\sqrt[n]{sin\alpha},n\in \mathbb{N}$.

$\implies x_n\rightarrow 1\text{ khi }n]\rightarrow +\infty$.

$\implies \frac{ln(x_n)}{x_n-1}\to 1(n\to +\infty)$.

(Để ý: $\left\{\begin{array}{I} 0<x_n<1,\forall n\in \mathbb{N}\\ \frac{ln(1+x)}{x}\to 1,\text{ khi } x\to 0 \end{array}\right.$)

$\implies \frac{nln(x_n)}{n(x_n-1)}\to 1,\text{ khi }n\to +\infty$.

Mà $n(x_n-1)=cos^2\alpha\frac{\sqrt[n]{cos\alpha}-1}{\frac{1}{n}}+sin^2\alpha\frac{\sqrt[n]{sin\alpha}-1}{\frac{1}{n}}$.

$\to cos^2\alpha ln(cos\alpha)+sin^2\alpha ln(sin\alpha)$

(Vì $\lim\limits_{n\to +\infty}n(\sqrt[n]{x}-1)=ln x(x>0)$).

$\implies (x_n)^n\to (cos\alpha)^{cos^2\alpha}(sin\alpha)^{sin^2\alpha}$.

 

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 09-12-2018 - 19:44

[tritanngo99]

Bài 131: Trong một nhóm gồm $2n+1$ người, với mỗi $n$ người thì tồn tại $1$ người trong $2n+1$ người này quen $n$ người đó. Chứng minh rằng:

a) Có $n+1$ người đôi một quen nhau.

b) Tồn tại $1$ người quen hết tất cả các người.

Bài 132: Với mỗi số nguyên dương $n$, ta kí hiệu $\tau(n)$ là số phần tử của tập hợp tất cả các ước nguyên dương của $n$. Một số nguyên dương $n$ được gọi là "số tốt" nếu $\tau(m)<\tau(n)$ với mọi $m<n$.

Chứng minh rằng với mỗi số nguyên dương $k$ cho trước, luôn tồn tại hữu hạn số tốt không chia hết cho $k$.

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 09-12-2018 - 19:44

[tritanngo99]

Lời giải bài 131:

a) Ta sẽ quy nạp: Rõ ràng có $2$ người quen nhau, giả sử có $k$ người đôi một quen nhau($k\le n$) thì tồn tại $1$ người quen $k$ người này, theo giả thiết suy ra có $k+1$ người đôi một quen nhau. Do đó tồn tại $n+1$ người đôi một quen nhau.

b) Xét $n$ người còn lại trong câu $a)$ thì tồn tại $1$ người trong $n+1$ người này quen $n$ người đó suy ra người này quen tất cả các người còn lại.

Lời giải bài 132: Gọi $G$ là tập hợp tất cả các số tốt nêu trong đề bài, dễ thấy $G$ khác rỗng.

Trước hết, ta sẽ chứng minh hai bổ đề sau:

Bổ đề 1: Giả sử $p_1<p_2<...<p_3<...$ là các số nguyên tố được sắp xếp theo thứ tự tăng dần. Nếu xét $\alpha, \gamma$ là các số nguyên dương với $a\in G$ thỏa mãn điều kiện $p_{\gamma}^{\alpha}|a$ thì $n=(\prod\limits_{i=1}^{\gamma}p_i)^{\alpha}|a$.

Chứng minh.

Kí hiệu $v_p(a)$ là số mũ lớn nhất của $p$ trong khai triển $a$ thành thừa số nguyên tố.

Giả sử rằng kết luận trên sai thì tồn tại $1\le i\le r$ mà $v_{p_i}(a)=\beta<\alpha$, khi đó ta có: $b=\frac{a}{p_i^{\beta}.p_{\gamma}^{\alpha}}.p_i^{\alpha}.p_{\gamma}^{\beta}<a$ và $\tau(b)=\tau(a)$, mâu thuẩn do $a\in G$.

Bổ đề được chứng minh.

Bổ đề 2: Với mỗi số nguyên tố $p_t$, tồn tại một số nguyên dương $M$ mà với mỗi $a\in G$, nếu $a>M$ thì $p_t|a$.

Chứng minh:

Xét số nguyên dương $\alpha$ thỏa mãn $2^{\alpha}>p_t$ và đặt $M=(p_1p_2...p_{t-1})^{3\alpha}$.

Với mỗi $a\in G$, giả sử $a>M$ và $(a,p_t)=1$.

Theo bổ đề $1$ thì tất cả các ước của $a$ đều thuộc tập hợp $\left\{p_1,p_2,...,p_{t-1}\right\}$, suy ra tồn tại một giá trị $1\le i\le t-1$ mà $v_{p_t}(a)=\beta>3\alpha$.

Tuy nhiên, ta lại có: $p_i^{\alpha}\ge 2^{\alpha}>p^t$ nên $b=\frac{a}{p_i^{\alpha}}p_t<a$.

Do $2(\beta-\alpha+1)>\beta+1$ nên ta có: $\tau(b)>\tau(a)$, mâu thuẩn.

Bổ đề được chứng minh.

Bổ đề 3: Với mỗi số nguyên tố $p_t$ và $\alpha$ là số nguyên dương, tồn tại một số nguyên dương $M$ mà với mỗi $a\in G$, nếu $a>M$ thì $p_t^{\alpha}|a$.

Chứng minh:

Xét một số nguyên tố thỏa mãn $p_{\gamma}>p_t^{\alpha}$, theo bổ đề $2$ thì tồn tại số nguyên dương $M$ mà với mỗi $a\in G$, nếu $a>M$ thì $v_{p_{\gamma}}(a)=\gamma>1$.

Nếu $v_{p_{t}}(a)=\beta<\alpha$ thì $b=\frac{a}{p_{\gamma}}p_t^{\alpha}<a$, nhưng do $\frac{\gamma}{\gamma+1}.\frac{\alpha+\beta+1}{\beta+1}\ge \frac{2\gamma}{\gamma+1}\ge 1$ hay $\tau(b)\ge \tau(a)$, lại mâu thuẩn.

Bổ đề được chứng minh.

Trở lại bài toán.

Giả sử ước nguyên tố lớn nhất của $k$ là $p_t$, xét một số nguyên dương $\alpha$ thỏa mãn $2^{\alpha}>k$.

Suy ra với mỗi số nguyên tố $p$ mà $p|k$ và $v_p(k)<a$ thì $k|n=(\prod\limits_{i=1}^{t}p_i)^{\alpha}$.

Theo bổ đề $3$, tồn tại một số nguyên dương $M$ mà với mỗi $a\in G,a>M$ thì $n|a$ hay nói cách khác là $k|a$.

Vậy tập hợp các số tốt không chia hết cho $k$ là hữu hạn. Ta có điều phải chứng minh.

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 09-12-2018 - 19:45

[tritanngo99]

Bài 133: Cho $x,y$ là hai số nguyên và cho $n$ là số nguyên dương. Cho số nguyên tố $p$ bất kỳ sao cho $p|x-y$ và $p$ không phải là ước của $x$ và $y$ và GCD(p,n)=1. Chứng minh rằng: $v_{p}(x^{n}-y^{n})=v_{p}(x-y)$.

Bài 134: Chứng minh rằng: Trong đồ thị vô hướng, số các đỉnh bậc lẻ là một số chẵn.

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 09-12-2018 - 19:45

[tritanngo99]

Lời giải bài 133: Ta có: $p|x-y$ nên $x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1}\equiv nx^{n-1}\not\equiv 0(\text{ mod }p)$

Mà $x^{n}-y^{n}=(x-y)(x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1})$ 

$\implies v_p(x^n-y^n)=v_p(x-y)+v_p(x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1})$.

$\iff v_p(x^n-y^n)=v_p(x-y)+0=v_p(x-y)$.

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

Lời giải bài 134: Kí hiệu: $G=(V,E)$ là một đồ thị vô hướng.

Kí hiệu: $U$ là tập các đỉnh bậc chẵn trong $G$ và $W$ là tập các đỉnh bậc lẻ trong $G$.

Khi đó ta có: $\sum\limits_{v_i\in V}deg_{G}(v_i)=\sum\limits_{v_i\in U}deg_{G}(v_i)+\sum\limits_{v_i\in W}deg_{G}(v_i)$

$\implies 2e-\sum\limits_{v_i\in U}deg_{G}(v_i)=\sum\limits_{v_i\in W}deg_{G}(v_i)(1)$

Ta nhận thấy rằng vế trái của $(1)$ là một số chẵn. Vì vậy $\sum\limits_{v_i\in W}deg_{G}(v_i)$ là một số chẵn.

Do mỗi $deg_{G}(v_i)$ là một số lẻ. Nên số các đỉnh bậc lẻ là một số chẵn.

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

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 09-12-2018 - 19:45

[tritanngo99]

Bài 135: Chứng minh rằng:

a) $2$ là một căn nguyên thủy của $3^n$ với mọi $n\ge 1$.

b) $2$ là một căn nguyên thủy của $101$

Bài 136: Xét bàn cờ vô hạn ô. Mỗi quân cờ có thể nhảy ngang hoặc nhảy dọc theo quy tắc "solitairejump": Nếu ba ô $A,B,C$ liên tiếp trong cùng một hàng hoặc cùng một cột sao cho $B$ nằm giữa $A$ và $C$, các ô $A,B$ có quân cờ và ô $C$ không có quân cờ thì quân cờ ở $A$ có thể nhảy sang $C$. Sau khi làm như vậy thì loại bỏ quân cờ ở $B$ ra khỏi bàn cờ. Trò chơi kết thúc nếu trên bàn cờ chỉ còn lại đúng một quân cờ. Ban đầu ta đặt $n^2$ quân cờ trong một hình vuông $nxn(n\ge 1)$. Hỏi với $n$ thế nào thì trò chơi có thể kết thúc?

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 09-12-2018 - 19:45

[tritanngo99]

Lời giải bài 135:

a) Định lý: Nếu $p$ là một số nguyên tố lẻ và $g$ là một căn nguyên thủy modulo $p^2$ thì $g$ cũng là căn nguyên thủy modulo $p^n$ với $n\ge 3$. 

Ta có: $\phi(9)=6,2^1=2\not\equiv 1(\text{ mod }9),2^2=4\not\equiv 1(\text{ mod }9),2^3=8\not\equiv 1(\text{ mod }9),2^6=64\equiv 1(\text{ mod }9)$ nên $2$ là một căn nguyên thủy modulo $9$ nên $2$ là một căn nguyên thủy modulo $9$. Theo định lý trên suy ra $2$ là căn nguyên thủy của $3^n$ với mọi $n\ge 1$.

b) Ta có: $\phi(101)=100$. Mặt khác: $2^{10}=1024\equiv 14(\text{ mod }101),$

$2^{20}\equiv 14^2\equiv -6(\text{ mod }101),$

$2^{40}\equiv (-6)^2\equiv 36(\text{ mod }101),$

$2^{50}\equiv 14.36\equiv -6(\text{ mod }101),$

nên suy ra $2$ là một căn nguyên thủy modulo $101$. Điều phải chứng minh.

Lời giải bài 136: Giả sử sau $m$ bước ta nhận được dãy $x_n,x_{n-1},...,x_1$. Ta quy ước, cặp số $(x_i,x_j)$ gọi là một cặp số đẹp nếu $i<j$ và $x_i$ đứng trước $x_j$ trong dãy. Gọi $(k)$ là số cặp đẹp ở bước thứ $k$. Mỗi lần thực hiện thuật toán thì có thể xem như thực hiện một số chẵn lần việc đổi số hai số hạng liên tiếp. Mỗi lần đổi chỗ hai số hạng liên tiếp thì số cặp số đẹp tăng lên $1$ hoặc giảm đi $1$, do đó: $S(k+1)\equiv S(k)(\text{ mod }2),\forall k\ge 0$.

Mặt khác: $S(0)=\frac{n(n-1)}{2},S(m)=0\implies \frac{n(n-1)}{2}\equiv 0(\text{ mod }2)$.

Từ đó suy ra $n=4k$ hoặc $n=4k+1$.

Với $n=4k$ ta thực hiện việc đổi chỗ lần lượt cho các bộ:

$(x_1,x_2,x_{4k-1},x_{4k}),(x_3,x_4,x_{4k-3},x_{4k-2}),...,(x_{2k-1},x_{2k},x_{2k+1},x_{2k+2})$.

Với $n=4k+1$ ta thực hiện việc đổi chỗ lần lượt cho các bộ:

$(x_1,x_2,x_{4k},x_{4k+1}),...,(x_{2k-1},x_{2k},x_{2k+1},x_{2k+2})$( giữ nguyên $x_{2k+1}$).

Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 11-12-2018 - 18:06