LNH

Làm phát đầu:

Bài 1:(Các đối tượng cơ bản trong tổ hợp, giải tích tổ hợp) Trong $n$ giác lồi kẻ tất cả các đường chéo. Biết rằng không có ba đường chéo nào đồng quy tại một điểm. Hỏi đa giác lồi được chia ra thành bao nhiêu phần? Các đường chéo cắt nhau tại bao nhiêu điểm?

Bài 2: (PP ánh xạ, chứng minh đặc tính tổ hợp) Gọi a_n là số các xâu nhị phân độ dài n không chứa chuỗi con $010$_, $b_n$là số các xâu nhị phân độ dài n không chứa chuỗi con $0011$ hoặc 1100. Chứng minh rằng $b_{n+1}=2a_n$ với mọi $n$ nguyên dương. 

Được sự góp ý của anh bachhammer và bạn nhatquangsin, mình xin mở topic về tổ hợp. Topic này được mở để các mem VMF có thể trao đổi thêm về các bài toán tổ hợp và rèn luyện việc giải toán tổ hợp ở phổ thông(phục vụ cho thi hsg, olympic...)

Chúng ta sẽ post các bài toán theo quy trình sau:

Bài x:(chuyên đề cần sử dụng để giải bài toán đó, loại bài toán,nguồn) [nội dung đề bài]

Khi giải một bài nào đó, ta sẽ trình bày như sau:

Giải bài x: [lời giải]

[những nhận định về bài toán, phương pháp giải] (nếu có)

Các bài toán được đưa ra theo các chuyên đề sau:

• Các đối tượng cơ bản trong tổ hợp (quy tắc nhân, cộng, hoán vị, tổ hợp, chỉnh hợp)
• Tập hợp
• PP ánh xạ
• PP truy hồi
• PP quỹ đạo
• PP đa thức
• PP hàm sinh
• Nguyên tắc Dirichlet
• Nguyên tắc cực hạn
• Các bài toán về tô màu
• PP quy nạp
• PP phản chứng
• Bất biến và đơn biến
• Hình học tổ hợp
• Lý thuyết đồ thị
• Khác(nêu rõ tên phương pháp)

Các dạng bài toán:

• Chứng minh đặc tính tổ hợp
• Giải tích tổ hợp(đếm)
• Đẳng thức tổ hợp
• Bất đẳng thức, cực trị tổ hợp

Quy định:

• Để tránh việc quá tải khi giải bài, khi trong topic có 10 bài chưa có lời giải, các bạn tham gia phải ngừng việc post bài để tập trung giải quyết các bài trước
• Các bài toán chưa giải quyết trong vòng 3 ngày thì người đưa lên phải đưa lời giải của bài đó (các bạn post bài phải biết rõ lời giải của bài này)
• Những bài toán và lời giải phải tuân thủ cách trình bày trên
• Về độ khó: Các bài toán phải có độ khó nhất định, phải suy nghĩ mới làm được
• Nếu có kiến thức nào mới thì có thể đưa lên diễn đàn để các bạn học hỏi lẫn nhau

Hi vọng topic trên sẽ ngày càng được phát triển! (nếu số lượng bài nhiều thì có thể cho ra lò 1 chuyên đề đặc sắc luôn cũng được  )

Bài 9:

Tìm 2 số nguyên dương thoả mãn PT: $x^{2011}+y^{2011}=2013^{2011}$

Giải bài 6:

\[\frac{{{a^3} + {b^3}}}{{{c^3} + {d^3}}} = \frac{1}{5}\]

\[ \Leftrightarrow 5({a^3} + {b^3}) = {c^3} + {d^3}\]

Lại có \[({a^3} - a) + ({b^3} - b) + ({c^3} - c) + ({d^3} - d) \vdots 6\]

\[ \Leftrightarrow 6({a^3} + {b^3}) - (a + b + c + d) \vdots 6\]

\[ \Leftrightarrow a + b + c + d \vdots 6\]

Vậy $a+b+c+d$ là hợp số

Giải bài 7:

\[\frac{{{a^5} + {b^5}}}{{{c^5} + {d^5}}} = 4\]

\[ \Leftrightarrow {a^5} + {b^5} =4({c^5} + {d^5})\]

Lại có \[({a^5} - a) + ({b^5} - b) + ({c^5} - c) + ({d^5} - d) \vdots 5\]

\[ \Leftrightarrow 5({c^5} + {d^5}) - (a + b + c + d) \vdots 5\]

\[ \Leftrightarrow a + b + c + d \vdots 5\]

Vậy $a+b+c+d$ là hợp số (vì $a+b+c+d>5$)

Giải bài 5a:

Đặt \[9 + {2^n} = {a^2}\] ($a>0$)

\[ \Leftrightarrow {2^n} = \left( {a - 3} \right)\left( {a + 3} \right)\]

Đặt \[a - 3 = {2^x}\] và \[a + 3 = {2^y}\] với $y>x\ge 0$ và $x+y=n$, ta có:

\[{2^y} - {2^x} = 6\]

\[ \Leftrightarrow {2^x}({2^{y - x}} - 1) = 6\]

\[ \Leftrightarrow x = 1;y = 2\]

\[ \Leftrightarrow n = 3\]

Giải bài 4:\[{x^2} + 2xy + 5{y^2} = 5\]

\[ \Leftrightarrow {\left( {x + y} \right)^2} + {(2y)^2} = {( \pm 1)^2} + {( \pm 2)^2}\]

Giải ra ta được $(x,y)=(0,1);(0,-1);(2,-1);(-2;1)$

Bài 3: Tồn tại hay ko số x nguyên thỏa mãn $x^{2401}+x^2+1\vdots 2013$

Vì $x^{2401}+x^2+1\vdots 2013$ nên $x^{2401}+x^2+1\vdots 11$

Ta có:

\[{x^{2401}} + {x^2} + 1 = x\left( {{x^{2400}} - 1} \right) + {x^2} + x + 1\]

Vì \[x\left( {{x^{2400}} - 1} \right) = x\left[ {{{\left( {{x^{10}}} \right)}^{24}} - {1^{24}}} \right] \vdots x\left( {{x^{10}} - 1} \right)\] và theo định lý Fermat nhỏ \[x\left( {{x^{10}} - 1} \right) \vdots 11\] nên \[x\left( {{x^{2400}} - 1} \right) \vdots 11\]

\[ \Rightarrow {x^2} + x + 1 \vdots 11\]

Chạy x trên hệ thặng dư đầy đủ modulo 11 ta có \[{x^2} + x + 1\] không chia hết cho 11

Vậy không tồn tại x thoả mãn đk.

Vote 1 phiếu cho toán thủ khonggiadinh(bài hình của bạn làm mình rất phục)

In every cell of a table with  rows and ten columns, a digit is written. It is known that for every row  and any two columns, you can always find a row that has different digits from  only when it intersects with two columns. Prove that .

*Đính chính:Russia MO 2011

----------------------------------------------------------------------------------

Dịch và giải giúp mình với

Giả sử không có đường tròn nào thoả mãn yêu cầu.

Xét 2 điểm A,B mà các điểm còn lại nằm trên nửa mặt phẳng bờ AB

Tồn tại C sao cho góc ACB nhỏ nhất

Có 1 điểm nằm ngoài đường tròn (ACB)

Giả sử điểm này là D

Suy ra góc ADB nhỏ hơn góc ACB, vô lí

Suy ra đpcm

Mã hoá dấu cộng là +1 và dấu trừ là -1, thực hiện phép nhân.

Vì số số -1 lẻ nên kết quả phép nhân là -1

Vậy dấu cuối cùng còn lại là dấu trừ

Chém bài 6 cái đã:

Nhận xét: không có thí sinh nào làm được 0 bài

a) Ta có mọi thí sinh đều làm nhiều nhất 2 bài. Xét 2 TH:

TH1: Tất cả thí sinh đều làm được 2 bài. Suy ra đpcm

TH2: Tồn tại thí sinh $a_1$ làm được 1 bài:

Xét $a_1$ với $a_i$ bất kì (i khác 1) thì 2 thí sinh sẽ làm chung 1 bài nên suy ra đpcm

Vấn đề được giải quyết xong 

b) Giả sử không tồn tại bài nào có ít nhất 40 thí sinh làm ra.

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

TH1: Tồn tại 1 thí sinh giải 1 bài. Ta chứng minh giống câu a nên loại TH này

TH2: Các thí sinh đều làm được 2 bài trở lên

Gọi tập hợp các thí sinh làm được bài $i$ là $B_i$

Không mất tính tổng quát, giả sử $B_{1}=max$

Ta có $s(B_1)<40$

Suy ra số thí sinh không làm được bài 1 lớn hơn 20

Mà mỗi thí sinh đều làm ít nhất 2 bài

Suy ra các thí sinh này đều làm được bài 2 và 3

Gọi số thí sinh này là $x$

Ta có: $x>20>s(B_1)/2$

Xét tập $B_1$:

Các thí sinh làm được câu 1 phải làm được ít nhất câu 2 hay câu 3

Giả sử số thí sinh làm được câu 2 nhiều hơn số thí sinh làm câu 3

Ta có số thí sinh này là $y>=s(B_1)/2$

Suy ra $s(B_2)=x+y>s(B_1)$ (vô lý vì $B_1$ là max)

Suy ra giả thiết phản chứng sai

Suy ra đpcm 

------------------------------------------------------------------------------------------

Tình hình các bạn như thế nào? , còn mình làm...hết

Bài 5:(bài toán Ramsey)

a)Chứng minh rằng trong 6 người bất kỳ luôn có 3 người đôi một quen nhau hoặc 3 người đôi một không quen nhau. Chứng minh điều này nói chung không đúng với 5 người.

b) Chứng minh rằng trong 9 người bất kỳ luôn tìm được 3 người đôi một quen nhau hoặc 4 người đôi một không quen nhau. Chứng minh điều này nói chung không đúng với 8 người.

Mong ai có bài nào hay, lạ, hiếm thì post lên nhá! 

Mong nhận được sự đóng góp nhiệt tình! 

 

Bài 3: 

Trong một lớp học có 36 bàn học cá nhân, được xếp thành 4 hàng và 9 cột (các hàng được đánh số từ 1 đến 4, các cột được đánh số từ 1 đến 9 ). Sĩ số học sinh của lớp là 35. Sau một học kỳ, cô giáo chủ nhiệm xếp lại chỗ ngồi cho các bạn học sinh trong lớp. Đối với mỗi học sinh của lớp, giả sử trước khi chuyển chỗ, bạn ngồi ở bàn thuộc hàng thứ m, cột n và sau khi chuyển chỗ, bạn ngồi ở bàn thuộc hàng $a_m$  cột thứ $a_n$, ta gắn cho bạn đó số nguyên $(a_{m} + a_n ) - (m+n)$. Chứng minh tổng của 35 số nguyên gắn với 35 bạn học sinh không vượt quá 11. 

P/s: Bài này chắc quen rồi! 

 

NOTES: 

Tổng hợp tất cả các dạng bài nha! 

Ghi tên bài và Ghi lời giải bài bao nhiêu nha! 

Đề thi chuyên ĐHSP Hà nội năm ngoái

Xét 6 đỉnh của lục giác là $a_1;a_2;a_3;a_4;a_5;a_6$ có độ dài là $k;k+2;k+4;k+6;k+8;k+10$

Ta có: $\left( {{a}_{1}}+{{a}_{3}}+{{a}_{5}} \right)-({{a}_{2}}+{{a}_{4}}+{{a}_{6}})=-3$ không đổi

Vậy sau k bước các số trên các đỉnh không thể bằng nhau