LNH

Post tiếp 2 bài nữa làm ... điểm tâm  :

Bài 15:(APMO 1998) Cho F là tập tất cả các bộ (A₁, . . . ,A_n) sao cho mỗi A_i là một tập con của {1, 2, . . . , 1998}. Ký hiệu |A| là số các phần tử của tập hợp A. Hãy tính

$\sum\limits_{({A_1},{A_2},...,{A_n}) \in F} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|} $

Bài 16:(Bulgaria 1996) HÌnh chữ nhật $m \times n ( m,n \in N, m,n>1)$ được chia thành $mn$ hình vuông đơn vị. Có bao nhiêu cách xoá 2 hình vuông sao cho phần còn lại có thể lát kín bởi các domino?

Giải bài 23: Giả sử \[{x_1} \le {x_2} \le ... \le {x_n}\]
Theo giả thiết ta có  \[{x_{n-2}} + {x_{n-1}} \le {x_{n - 1}} + {x_n}\]

\[ \Leftrightarrow x_n^p \le x_1^p\]
\[ \Leftrightarrow {x_n} \le {x_1}\]
\[ \Rightarrow {x_1} = {x_n}\] hay \[ \Rightarrow {x_1} = {x_2} = ... = {x_n}\]
Thay vào HPT ta được \[ \Rightarrow {x_1} = {x_2} = ... = {x_n} = \sqrt[{p - 1}]{2}\] hoặc \[ \Rightarrow {x_1} = {x_2} = ... = {x_n} =0\]
 

Giải bài 4

Xét một bảng $2\times 2$ của bảng. Vì tất cả ô trong bảng đó không thể chỉ có một màu và đường chéo không thể có một màu nên bảng chỉ có thể có dạng(hình 1, gọi là dạng 1 cho dễ làm bài) hoặc (hình 2, gọi là dạng 2)  (em vẽ đại cái hình nên hơi bị xấu)

Snap100.png

Snap101.png

xét một bảng $2\times 4$ (như hình 3)(xấu tệ nhỉ)

Snap102.png

Được tao ra từ cách ghép 2 ô $2\times 2$ dạng 1 và dạng 2

Từ đó ta thấy ô $2\times 2$ được tạo ra từ dòng 1,2 và cột 2,3 không thỏa yêu cầu đề.

Vì vậy bảng chỉ có thể được tạo ra từ toàn bộ ô dạng 1 (hoặc dạng 2)

Vì các ô ở góc của bảng lớn phải có màu đỏ nên rõ ràng dòng đầu tiên của bảng (hoặc cột đầu tiên của bảng) phải có màu đỏ. Như vậy màu đỏ sẽ được to cho các dòng(hoặc cột) có thứ tự lẻ. Vì vậy mà dòng(hoặc cột) cuối cùng của bảng phải là dòng lẻ(hoặc cột lẻ)

Như vậy số dòng(hoặc cột) của bảng phải là số lẻ. Từ đó ta thấy trường hợp a:$2012\times 2013$ thỏa mãn và trường hợp b:$2012\times 2014$ là không thỏa mãn

Giải sai rồi Quang ơi, ở đây tô màu 4 cạnh chứ có phải 4 góc đâu. Với lại phải có hai đường chéo có ô vuông cùng màu mới không thoả mãn, một đường chéo vẫn được mà !?

Bài 7: (Đề đề nghị 30/4 -2012) Trong một kì thi hoa hậu, mỗi thành viên của ban giám khảo được quyền đề xuất $10$ người đẹp vào vòng chung kết. Một nhóm người đẹp được gọi là nhóm ưng ý đối với giám khảo A nếu trong nhóm đó có ít nhất một người đẹp mà A đề xuất. Biết rằng với 6 giám khảo bất kỳ luôn tồn tại một nhóm gồm 2 người đẹp là nhóm ưng ý đối với mỗi giám khảo trong 6 giám khảo đó. Chứng minh rằng tồn tại một nhóm gồm 10 người đẹp là nhóm ưng ý đối với mỗi thành viên của ban giám khảo.

Anh Ispectorgadget giải bài này luôn đi ạ (bài này ra lâu rồi mà vẫn chưa có người giải)

Ngoài bài 7 ra, còn bài 3, 4, 14 chưa có lời giải

=====

Anh cũng bí bài này :3 tiếc là nó không có giải....

Bài 22: Với mỗi số nguyên dương n, gọi $S(n)$ là tổng các chữ số của n.

a)      Chứng minh rằng các số $n = 999$ và $n = 2999$ không thể biểu diễn được dưới dạng $a + b$ với $S(a) = S(b)$.

b)      Chứng minh rằng mọi số $999<n<2999$ đều biểu diễn được dưới dạng $a + b$ với $S(a) = S(b)$.

Bài 14:(Cực trị tổ hợp, China TST 2012) Trong một hình vuông được tạo bởi \[2012 \times 2012\] ô vuông có chứa những con bọ, trong một ô vuông có nhiều nhất 1 con bọ. Vào một thời điểm nào đó, những con bọ này bay lên rồi lại đậu xuống lại vào các ô vuông, mỗi ô vuông cũng có nhiều nhất một con bọ. Đối với mỗi con bọ, có thể xem đoạn thẳng có hướng nối tâm của ô vuông lúc đầu và tâm của lúc sau mà nó đậu lên tạo thành một vector. Với một số lượng bọ ban đầu, xét tất cả những trường hợp  có thể xảy ra với các vị trí đầu tiên và cuối cùng của những con bọ, hãy tìm độ dài lớn nhất của tổng các vector.

Bài 13: Cho $n$ điểm xanh và $n$ điểm đỏ trên mặt phẳng, trong đó không có $3$ điểm nào thẳng hàng. Chứng minh rằng ta có thể nối $2n$ điểm này bằng $n$ đoạn thẳng có đầu mút khác màu sao cho chúng đôi một không giao nhau. 

 

 

Giải bài 13:

Ta giải bài này theo nguyên lý cực hạn (lần sau nhớ post bài kèm theo nguồn và phương pháp nhé bạn)

Giả sử không tồn tại cách nối thoả mãn đk trên

Tồn tại cách nối sao cho tổng độ dài các cạnh được nối nhỏ nhất

Trong cách nối trên:

Theo giả thiết tồn tại 2 cạnh $AB$ và $CD$ cắt nhau tại $O$ ($A,C$ màu đỏ, $B,D$ màu xanh)

Theo bất đẳng thức tam giác, ta có:

$OA+OD>AD$

$OB+OC>BC$

Suy ra $AD+BC<AB+CD$

Vậy khi ta thay cạnh AB và CD bằng cạnh AD và BC thì sẽ có một cách nối nhỏ hơn, vô lí (vì cách nối trên là nhỏ nhất)

Suy ra đpcm

Đây là PP đa thức và số phức. Sao anh không giải bằng PP truy hồi luôn ạ?

Sau đây là cách giải PP truy hồi:

Gọi $a_n$ là số các số có $n$ chữ số lập từ ${3, 4, 5, 6}$ và chia hết cho 3, còn $b_n$ là số các số có $n$ chữ số lập từ ${3, 4, 5, 6}$ và không chia hết cho 3. Khi đó ta có

$a_n = 2a_{n-1} + b_{n-1}(1)$

$b_n = 2a_{n-1} + 3b_{n-1}(2)$

Từ (1) suy ra $b_{n-1} = a_n – 2a_{n-1}$, thay n à n+1 thì được $b_n = a_{n+1} – 2a_n$. Thay vào (2), ta được

$a_{n+1} – 2a_n = 2a_{n-1} + 3(a_n – 2a_{n-1})$

$a_{n+1} – 5a_n + 4a_{n-1} = 0$.

Giải phương trình sai phân này, với chú ý rằng a₁ = 2, a₂ = 6, ta tìm được

\[{a_n} = \frac{{{4^n} + 2}}{3}.\]

Một số tự nhiên chia hết cho $3$ khi và chỉ khi tổng các chữ số của nó chia hết cho 3.

Do vậy số các chữ số có $n$ chữ số lập từ $\{3;4;5;6\}$ chia hết cho $3$ ta gọi là $u_n$ bằng tổng hệ số của $x^{3k}$ trong khai triển đa thức $$F(x)=(x^3+x^4+x^5+x^6)^n.$$

 

Xét phương trình $x^2 + x + 1 = 0$ có 2 nghiệm phức là $\varepsilon _t = \cos \frac{{2t\pi }}{3} + i\sin \frac{{2t\pi }}{3},t = 1;2 \Rightarrow \varepsilon _i^3 = 1$

Theo định lý RUF

Spoiler

Định lí: Xét đa thức $f(x)=a_n x^n+a_{n-1} x^{n-1}+...+a_1 x+a_0$
Và số $M=cos \frac{2 \pi}{m}+i sin \frac{2 \pi}{m}$ là căn bậc $m$ của đơn vị.

Khi đó để ý rằng tổng $1+M^k+M^{2k}+...+M^{(m-1)k}$ sẽ bằng $0$ nếu $k$ không chia hết cho $m$,và bằng $m$ nếu $k$ chia hết cho $m$.

 

 

Ta có:

 

$$F(1)+F(\varepsilon)+F(\varepsilon)=3a_n$$

Ta có $F(1)=4^n;F(\varepsilon)=F(\varepsilon^2)=1$ nên ta có $u_n=\frac{4^n+2}{3}. \square$

Đây là PP đa thức và số phức. Sao anh không giải bằng PP truy hồi luôn ạ?

====

=)) Trình không đủ, cái pp truy hồi h đang luyện...

Bài 10:(truy hồi, GGTH 4) Có 2n người xếp thành 2 hàng dọc. Hỏi có bao nhiêu cách chọn ra một số người (ít nhất 1) từ 2n người này, sao cho không có hai người nào đứng kề nhau được chọn. Hai người đứng kề nhau là hai người có số thứ tự liên tiếp trong một hàng dọc hoặc có cùng số thứ tự ở hai hàng.

Bài 9: (tập hợp,Germany 1970) Cho tập $M$ có $22222$ phần tử .Hỏi $M$ có hay không 50 tập con thoả mãn :

 1/Mỗi phần tử của $M$ là phần tử của ít nhất 1 trong các tập con.

 2/Mỗi tập con đều có $1111$ phần tử.

 3/Với 2 tập $M_i;M_j (i\neq j)$ có ${M_i} \cap {M_j}$ 22 phần tử.

Bài 15:Chứng minh rằng nếu p nguyên tố thì (p – 2)!  – 1 chia hết cho p nhưng nếu p > 5 thì (p –2)! – 1 không phải là một lũy thừa của p

Bài 6: (truy hồi/đa thức,giải tích tổ hợp,PTNK 2009) Cho số nguyên dương n. Có bao nhiêu số chia hết cho 3, có n chữ số và các chữ số đều thuộc {3, 4, 5, 6}?

Bài 5:(Đơn biến) Trong 1 dãy nhà vô hạn ,được đánh số :$1,2,3,…$ mỗi phòng có thể có người hoặc không có người ,nhưng số người là hữu hạn .Mỗi buổi sáng 2 người ở 2 phòng liên tiếp $k,k+1$ nào đó sẽ thực hiện việc chuyển phòng như sau :

i)Người ở phòng $k$ chuyển sang phòng $k-1$ $(k>1)$

ii)Người ở phòng $k+1$ chuyển sang phòng $k+2$

CMR:Việc chuyển phòng chỉ ra hữu hạn lần.

Bài 12:Tìm tất cả các số nguyên $n$ sao cho $C_n^k$ là số lẻ với mọi $k=0,..,n $