tritanngo99

Bài 7: (Định lý Mantel) Cho $G$ là một đồ thị (đơn, vô hướng) có $n$ đỉnh. Nếu $G$ không có tam giác thì $G$ không có nhiều hơn $[\frac{n^2}{4}]$ cạnh. Đẳng thức xảy ra khi và chỉ khi $G=K_{{\frac{n}{2}},{\frac{n}{2}}}$ nếu $n$ chẵn và $K_{{\frac{n-1}{2}},{\frac{n-1}{2}}}$ với $n$ lẻ. Trong đó $K_{n}$ là đồ thị đầy đủ với $n$ đỉnh.

Bài 8: (Bổ đề bắt tay) Cho đồ thị $G=(V,E)$. Khi đó $2|E|=\sum\limits_{v\in V}deg(v)$. Trong đó $|V|,|E|$ lần lượt là số đỉnh và số cạnh của $G$

Để giúp các bạn làm quen với các bài toán liên quan đến lý thuyết đồ thị sau này, mình xin giới thiệu với các bạn một số khái niệm cơ bản về lý thuyết đồ thị (Tham khảo từ : mathscope.org)

1.1. Định nghĩa 1:

Một đơn đồ thị $G=(V,E)$ gồm một tập khác rỗng $V$ mà các phần tử của nó gọi là các đỉnh và một tập $E$ mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt.

1.2. Định nghĩa 2:

Một đa đồ thị $G=(V,E)$ gồm một tập khác rỗng $V$ mà các phần tử của nó gọi là các đỉnh và một họ $E$ mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt. Hai cạnh được gọi là cạnh bội hay song song nếu chúng cùng tương ứng với một cặp đỉnh.

1.3. Định nghĩa 3:

Một đồ thị có hướng $G=(V,E)$ gồm một tập khác rỗng $V$ mà các phần tử của nó gọi là các đỉnh và một tập $E$ mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc $V$.

1.4. Định nghĩa 4:

Một đa đồ thị có hướng $G=(V,E)$ gồm một tập khác rỗng $V$ mà các phần tử của nói gọi là các đỉnh và một họ $E$ mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc $V$.

1.5. Định nghĩa 5:

Hai đỉnh $u$ và $v$ trong đồ thị (vô hướng ) $G=(V,E)$ được gọi là liền kề nếu $(u,v)\in E$. Nếu $e=(u,v)$ thì $e$ gọi là cạnh liên thuộc với các đỉnh $u$ và $v$. Cạnh $e$ cũng được gọi là cạnh nối các đỉnh $u$ và $v$.

1.6. Định nghĩa 6:

Bậc của đỉnh $v$ trong đồ thị $G=(V,E)$, ký hiệu $deg(v)$, là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó.

Đỉnh $v$ được gọi là đỉnh treo nếu $deg(v)=1$ và được gọi là đỉnh cô lập nếu $deg(v)=0$.

1.7. Định nghĩa 7:

Cho $A,B$ là $2$ đỉnh của một đồ thị $G$. Một đường đi từ $A$ đến $B$ là một dãy các cạnh $(A_i,A_{i+1})(i=\overline{0,k-1})$ với $A_0=A,A_k=B$. Số các cạnh (ở đây là $k$) tạo nên đường đi gọi là độ dài của đường đi.

Một đồ thị gọi là liên thông nếu giữa hai đỉnh bất kỳ luôn có đường đi.

1.8. Định nghĩa 8: (Định nghĩa về tính liên thông).

Đường đi độ dài $n$ từ đỉnh $u$ đên đỉnh $v$, với $n$ là một số nguyên dương, trong đồ thị (giả đồ thị vô hướng hoặc đa đồ thị có hướng) $G=(V,E)$ là một dãy các cạnh (hoặc cung) $e_1,e_2,..,e_n$ của đồ thị sao cho $e_1=(x_0,x_1),e_2=(x_1,x_2),...,e_n=(x_{n-1},x_n)$, với $x_0=u,x_n=v$. Khi đồ thị không có cạnh (hoặc cung) bội, ta ký hiệu đường đi này bằng dãy các đỉnh $x_0,x_1,...,x_n$. Đường đi được gọi là chu trình nếu nó bắt đầu và kết thúc tại cùng một đỉnh.

Đường đi hoặc chu trình gọi là đơn nếu nó không chứa cùng một cạnh (hoặc cung ) quá một lần.

Một đường đi hoặc chu trình không đi qua đỉnh nào quá một lần (trừ đỉnh đầu và đỉnh cuối của chu trình trùng nhau) được gọi là đường đi hoặc chu trình sơ cấp. Rõ ràng một đường đi ( hoặc chu trình) sơ cấp là đường đi (hoặc chu trình) đơn.

1.9. Định nghĩa 9:

Một đồ thị (vô hướng) được gọi là liên thông nếu nó có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị.

Một đồ thị không liên thông là hợp của hai hay nhiều đồ thị liên thông con, mỗi cặp đồ thị con này không có đỉnh chung. Các đồ thị con liên thông rời nhau như vậy được gọi là các thành phần liên thông của đồ thị đang xét. Như vậy, một đồ thị liên thông khi và chỉ khi nó chỉ có một thành phần liên thông.

1.10. Định nghĩa 10 : (Chu trình Hamilton)

Định nghĩa: Chu trình (hoặc đường đi) sơ cấp chứa tất cả các đỉnh của đồ thị (vô hướng hoặc có hướng) $G$ được gọi là chu trình (hoặc đường đi) Halminton. Một đồ thị có chứa một chu trình ( hoặc đường đi) Hamilton được gọi là đồ thị Hamilton ( hoặc nữa Halminton)

Lời giải bài 5: Để giải quyết bài toán này, chúng ta sử dụng song song hai cách tô màu cho bảng $4\text{ X }N$ này. Cụ thể như sau:

 + Cách tô thứ nhất: Ta sẽ tô màu như trong cờ vua, trắng đen xen kẻ nhau, như hình vẽ dưới đây:

+ Cách tô thứ hai: Ta sẽ tô dòng thứ 1 ,dòng thứ 4 màu xanh và hai dòng 2 , 3 màu cam, như hình vẽ dưới đây: 

Giả sử tồn tại chu trình mà quân mã đi từ ô ban đầu , qua tất cả các ô còn lại, mỗi ô đúng một lần và quay lại ô ban đầu, không mất tính tổng quát, giả sử ô xuất phát của quân mã là ô ở trên cùng bên trái của bảng

- Khi đó ta có hai nhận xét sau:

+ Đối với cách tô thứ nhất: Chu trình của quân mã sẽ có dạng: Trắng - Đen - Trắng - Đen .... (Trắng , Đen xen kẻ nhau )

+ Đối với cách tô thứ hai: Chu trình của quân mã sẽ có dạng: Xanh - Cam - Xanh - Cam ... (Xanh, Cam xen kẻ nhau, vì tổng số ô xanh bằng tổng số ô Cam và hai ô Xanh thì không được đứng liền kề nhau trong chu trình).

- Kết hợp hai nhận xét này, ta thấy quân mã chỉ đi vào những ô: "Trắng/Xanh" , "Đen/Cam" và không đi vào ô "Trắng/Cam", "Đen/Xanh"  . Điều này có nghĩa là quân mã không đi hết tất cả các ô trong bảng $4\text{ X }N$ (Mâu thuẩn).

Vậy không tồn tại chu trình mà quân mã đi từ ô ban đầu, qua tất cả các ô còn lại, mỗi ô đúng một lần và quay lại ô ban đầu.

P/s: Lời giải này tương tự lời giải của bạn Spirit1234

Lời giải bài 6: Lấy $A$ là một trong số $25$ điểm đã cho. Xét hình tròn $\Omega_1(A;1)$ tâm $A$ bán kính $1$. Chỉ có hai khả năng sau có thể xảy ra:

1. Nếu tất cả các điểm đã cho nằm trong $\Omega_1$, thì kết luận của bài toán hiển nhiên đúng.

2. Tồn tại điểm $B\ne A$ ($B$ thuộc trong số $25$ điểm đã cho ), sao cho $B\notin \Omega_1$. Vì $B\notin \Omega_1$, nên $AB>1$.

Xét hình tròn $\Omega_1(B;1)$ tâm $B$, bán kính $1$. Lấy $C$ là điểm bất kỳ trong số $25$ điểm đã cho sao cho $C\ne A,C\ne B$. Theo giả thiết (và dựa vào $AB>1$), nên $min\left\{CA,CB\right\}<1$. Vì thế $C\in \Omega_1$, hoặc $C\in \Omega_2$.

Điều khẳng định này chứng tỏ rằng các hình tròn $\Omega_1$ và $\Omega_2$ chứa tất cả $25$ điểm đã cho. Vì thế theo nguyên lý Dirichlet, ít nhất một trong hai hình tròn nói trên chứa không ít hơn $13$ điểm đã cho.

Chú ý: 

Bài toán tổng quát: Cho $2n+1$ điểm trên mặt phẳng $(n\ge 3)$. Biết rằng trong ba điểm bất kỳ trong số đó luôn luôn tồn tại hai điểm cách nhau nhỏ hơn $1$. Khi đó tồn tại hình tròn bán kính $1$ chứa không ít hơn $n+1$ điểm đã cho

Bài 5: Có thể hay không một quân mã đi qua tất cả các ô của bàn cờ $4\text{ X }N$, mỗi ô đúng một lần và quay lại ô xuất phát ban đầu ?

Bài 6: Trên mặt phẳng cho 25 điểm. Biết rằng trong $3$ điểm bất kỳ trong số đó luôn tồn tại hai điểm cách nhau nhỏ hơn 1. Chứng minh rằng tồn tại hình tròn bán kính $1$ chứa không ít hơn $13$ điểm đã cho

Lời giải bài 3:

Ta có: $x_1+x_2+...+x_n=k(*)$

Gọi số nghiệm nguyên không âm của phương trình trên là $S(n,k)$. Dễ dàng thấy rằng $S(1,k)=1$. Để tính $S(n,k)$, ta chú ý rằng $(*)$ tương đương với $x_1+x_2+...+x_{n-1}=k-x_n(**)$.

Suy ra với $x_n$ cố định thì số nghiệm của $(**)$ là $S(n-1,k-x_n)$. Từ đó ta có được công thức $S(n,k)=S(n-1,k)+S(n-1,k-1)+...+S(n-1,0)(1)$.

Đây có thể coi là công thức truy hồi tính $S(n,k)$. Tuy nhiên, công thức này chưa thật tiện lợi. Viết công thức trên cho $(n,k-1)$ ta được:

$S(n,k-1)=S(n-1,k-1)+S(n-1,k-2)+...+S(n-1,0)(2)$

 Từ đây, trừ các đẳng thức $(1)$ và $(2)$ vế theo vế, ta được: $S(n,k)-S(n,k-1)=S(n-1,k)$. Hay $S(n,k)=S(n,k-1)+S(n-1,k)$. Từ đây bằng quy nạp, ta chứng minh được $S(n,k)=C_{n+k-1}^{n}$.

* Chú ý: Trong quá trình chứng mình bằng quy nạp, ta cần áp dụng công thức quen thuộc: $C_{n}^{k}=C_{n-1}^{k}+C_{n-1}^{k-1}$.

Lời giải bài 4: Xét $3$ tập :

+ $A_1=\left\{1,2,3\right\}\cup \left\{3m:m\ge 4\right\}$

+ $A_2=\left\{4,5,6\right\}\cup \left\{3m-1:m\ge 4\right\}$

+ $A_1=\left\{7,8,9\right\}\cup \left\{3m-2:m\ge 4\right\}$

Gọi $l$ là tổng hai phần tử phân biệt bất kì của tập $A_i$, khi đó đối với tập $A_1$ ta có $l\ge 13$, đối với tập $A_2$ ta có $l\ge 15$, đối với tập $A_3$ ta có: $l\ge 15$.

Do đó $k=3$ thỏa mãn yêu cầu bài toán.

Xét $k\ge 4$, giả sử tồn tại $k$ tập $A_1,A_2,...,A_k$ thỏa bài toán. Khi đó, các tập $A_1,A_2,A_3,A_4\cap ...\cap A_k$ cũng thỏa yêu cầu bài toán nên ta chỉ cần xét $k=4$. Đặt $B_i=A_i\cap X,X=\left\{1,2,3,...,23\right\}$ với $i=1,2,3,4$

Vì mỗi số $15,16,...,24$ là tổng của hai số thuộc tập $B_i$. Do đó mỗi tập $B_i$ có ít nhất $5$ phần tử .

Mà $|B_1|+|B_2|+|B_3|+|B_4|=23$, nên tồn tại tại chỉ số $j$ sao cho $|B_j|=5$.

Đặt $B_j=\left\{x_1,x_2,x_3,x_4,x_5\right\}$. Vì tổng của hai số bất kì khác nhau và thuộc tập $\left\{15,16,...,24\right\}$ nên ta có $4(x_1+x_2+x_3+x_4+x_5)=15+16+...+24=195$. Vì $195$ không chia hết cho $4$ nên điều này vô lý. Vậy $k=3$ là giá trị cần tìm.

Bài 3: (Bài toán chia kẹo Euler) Cho $k,n$ là các số nguyên dương. Tìm số nghiệm nguyên không âm của phương trình $x_1+x_2+...+x_n=k$

Bài 4: Tìm số nguyên dương $k$ lớn nhất sao cho có thể phân hoạch tập các số tự nhiên thành $k$ tập $A_1,A_2,...,A_k$ sao cho với mọi số tự nhiên $n\ge 15$ và mọi $i\in \left\{1,2,...,k\right\}$ luôn tồn tại hai phần tử phân biệt của tập $A_i$ có tổng bằng $n$.

Xin lỗi các bạn vì đã đăng bài trễ !

Dưới đây là lời giải bài 1 và bài 2.

Lời giải bài 1:

- Do thể tích của các cốc nước là như nhau, nên không mất tính tổng quát , ta có thể giả sử thể tích là $1$ (đơn vị thể tích)

a) Câu trả lời là "Có". Ta đổ tuần tự như sau:

- Đổ hết nước từ chiếc cốc thứ ba sang chiếc cốc thứ hai, khi đó chiếc cốc thứ hai có lượng nước là : $\frac{1}{3}+\frac{1}{4}=\frac{7}{12}$

- Sau đó, đổ nước từ chiếc cốc thứ hai sang chiếc cốc thứ nhất cho đến khi đầy thì lượng nước còn lại trong chiếc cốc thứ hai sẽ là $\frac{7}{12}-\frac{1}{2}=\frac{1}{12}$ 

b) Câu trả lời là $0$. 

- Giả sử ở các cốc $A,B$ có số lượng nước tương ứng là $a,b$. Nếu ta đổ nước từ cốc $A$ sang cốc $B$ thì sẽ xảy ra những trường hợp sau:

+ Nếu $a+b<1$ thì lúc này lượng nước cốc $A$ là $0$ và lượng nước cốc $B$ là $a+b$.

+ Nếu $a+b>=1$ thì lúc này lượng nước cốc $A$ là $a+b-1$ và cốc $B$ lúc này sẽ tràn.

Tóm lại : Lượng nước ở cốc $A$ hoặc $B$ sẽ có dạng $(a+b)\text{ mod } 1 $.

Do đó, để sau một số lần đổ nước , tồn tại một cốc có lượng nước là $\frac{1}{6}$, chúng ta cần tìm tổ hợp những chiếc cốc sao cho tổng của chúng có dạng $\frac{1}{6}\text{ mod }1$.

Bằng cách quy đồng mẫu số các lượng nước ban đầu của từng chiếc cốc, ta có mẫu số chúng là $360$. Và tử số của chúng lần lượt là $180,120,90,72,45,40$ và 36 và nhiệm vụ của chúng ta là tìm những tổ hợp các tử số này để tạo thành các số $60$ hoặc $420$, vì $\frac{60}{360}\equiv \frac{420}{360}\equiv \frac{1}{6}\text{mod 1}$.  Rõ ràng, chúng ta không thể tìm được tổ hợp nào thỏa mãn được điều này, do đó câu là lời là "Không" thể.

Lời giải bài 2: Giả sử $X=\left\{x_1,x_2,...,x_n\right\}$ và $S_i=x_1+x_2+...+x_i$ trong đó $i=1,2,...,n$. Nếu có một $S_i$ nào đó chia hết cho $n$ thì ta có điều phải chứng minh.

Trong trường hợp ngược lại, ta gọi $r_i$ là số dư khi chia $S_i$ cho $n$ thì $r_i$ nhỏ nhất bằng $1$ và lớn nhất bằng $n-1$. Do đó bằng nguyên lý chuồng chim bồ câu (nguyên lý Dirichlet), chúng ta phải có $p,q$ nào đó thỏa mãn $p<q$ và $r_p=r_q$. Ta có: $S_q-S_p=x_{p+1}+x_{p+2}+...+x_q$.

Hiển nhiên $S_q-S_p$ chia hết cho $n$ (đpcm)

Hôm nay, nhân ngày đẹp trời, mình quyết định lập Topic: "Mỗi ngày hai bài toán tổ hợp" để mọi người cùng trao dồi và nâng cao những kiến thức về tổ hợp , làm hành trang sau này ta vào cấp ba, luyện thi vào đại học và những chặng đường tiếp theo trong tương lai ! 

Và dưới đây là nội quy của diễn đàn:

+ Mỗi ngày sẽ có hai bài toán tổ hợp đăng lên (rất nhiều thể loại) và lời giải sẽ được đăng vào ngày hôm sau.

+ Những bài viết của các bạn đăng lên chú ý phải rõ ràng, viết đúng công thức theo chuẩn Latex, và đặc biệt không được spam, quảng cáo làm sao nhãng Topic.

Nội quy chỉ có bấy nhiều hi vọng mọi người ủng hộ và giúp đỡ để topic ngày càng phát triển hơn

Ps: Mình biết tổ hợp là lĩnh vực khó, ít dạy trên lớp ở cấp THCS, nên nếu các bạn nào đọc thấy khó thì đừng nản nhé !

Bài 1: Có 7 chiếc cốc cùng dung tích đang đựng nước theo thứ tự chiếm $\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\frac{1}{8},\frac{1}{9},\frac{1}{10}$ cốc.

Cho phép trút tất cả nước từ một cốc sang một cốc khác nếu nước không tràn ra ngoài hoặc đổ nước từ cốc này sang cốc khác cho đến khi đầy thì dừng lại. Hỏi có thể hay không sau một số lần đổ nước, một chiếc cốc nào đó chứa nước chiếm 

a) $\frac{1}{12}$ cốc.

b) $\frac{1}{6}$ cốc.

Bài 2: Cho tập hợp X gồm n số nguyên bất kỳ. Chứng minh rằng X luôn có một tập con mà tổng của các số nguyên có trong tập hợp đó chia hết cho n.

Tìm các số nguyên tố p thỏa mãn $x,y \epsilon  \mathbb{Z}$ thỏa mãn: $p+1=2x^2$ và $p^2+1=2y^2$.

Lời giải:

Ta có nhận xét như sau: Nếu $(x_0;y_0;p_0)$ là một nghiệm của phương trình trên thì $(-x_0;y_0;p_0),(-x_0;-y_0;p_0);(x_0;-y_0;p_0)$ cũng là nghiệm của phương trình trên. Do đó không mất tính tổng quát: Giả sử $x>0;y>0$. (Bằng cách thay trực tiếp, ta thấy x,y không thể bằng 0)

Đặt $p+1=2x^2 \rightarrow \text{(1)}; p^2+1=2y^2 \rightarrow \text{(2)}$

Nhận xét: Thay $p=2$ vào (1) và (2). Ta dễ dàng thấy đươc không tồn tại $x,y\in \mathbb{Z}$. Từ đây ta suy ra $p$ lẻ.

Lấy $(2)-(1)$ vế tho vế ta được: $p(p-1)=2(y-x)(y+x) \rightarrow \text{(3)}$

Từ $(3)\implies y>x> 0$.

Do $p$ là số nguyên tố và $p$ lẻ nên từ đây ta suy ra được $p|(y-x)$ hoặc $p|(y+x)$ (Ghi chú: $a|b$ có nghĩa là $a$ là ước của $b$). 

  +Nếu $p|(y-x)\implies p\le y-x$. Từ $(3)$ ta suy ra được $p-1\ge 2(x+y)$. Điều này mâu thuẫn vì $p\le y-x<2(x+y)\le p-1$. 

Do đó $p|(x+y)$. Khi đó $p\le (x+y)\implies p-1\le 2(y-x)$.

Đặt $p\le x+y \rightarrow \text{(4)}; p-1\le 2(y-x) \rightarrow \text{(5)}$.

Lấy $2*(4)-(5)$ vế theo vế ta được: $p+1\le 4x$ hay $2x^2\le 4x$.

Do $x\ge 0\implies x=1$ hoặc $x=2$

$y^3-1=x^4+x^2$

Đây là 2013 Baltic Way, Problem 18. Bạn có thể tham khảo tại đây: https://artofproblem...h569087p3338997

dạ em nhầm nhưng cộng thế biến đổi có tới được không a nhỉ?

Được em !

a ơi check giúp cách e làm với

Chỗ dòng thứ 2, sau dòng ta có, em biến đổi nhầm chỗ $-3(1-x)(2+x+y)$. Chỗ đó phải là dấu $+$ chứ ?

a chưa lớn hơn hoặc bằng 0 thì sao $3ab\geq 3a(3-a)$ ?

Cảm ơn bạn, mình đã sửa thành hai trường hợp !

Cho $a\leq 1; a+b\geq 3$

CMR: $3a^2+b^2+3ab-\frac{27}{4}\geq 0$

TH1: Xét $0\le a\le 1$.

Ta có: $a+b\ge 3\implies b\ge 3-a\ge 3-1\ge 2>0\implies b^2\ge (3-a)^2$.

Khi đó ta có: $3a^2+b^2+3ab-\frac{27}{4}\ge 3a^2+(3-a)^2+3a(3-a)-\frac{27}{4}=a^2+3a+\frac{9}{4}=(a+\frac{3}{2})^2\ge 0$.

TH2: Xét $a<0$.

Đặt $t=-a(t>0)$. Khi đó ta có: $b-t\ge 3$. Và ta cần đi chứng minh $3t^2+b^2-3tb-\frac{27}{4}\ge 0$.

Thật vậy, đặt $k=b-t(k\ge 3)\implies b=k+t$

Khi đó ta có: $3t^2+b^2-3tb-\frac{27}{4}=3t^2+(k+t)^2-3t(k+t)-\frac{27}{4}=k^2-kt+t^2-\frac{27}{4}=(\frac{1}{4}k^2-kt+t^2)+(\frac{3}{4}k^2-\frac{27}{4})=(\frac{k}{2}-t)^2+\frac{3}{4}(k^2-9)>0$

Vậy từ hai trường hợp trên ta có điều phải chứng minh.

Theo bất đẳng thức Cauchy (cho 3 số) ta có 

$ab + bc + ca \geq 3\sqrt[3]{a^2b^2c^2}= 3$(1)

 

Trở lại bài toán

$\frac{1}{a+2}+\frac{1}{b+2}+\frac{1}{c+2}\leq1$

$<=> (a+2)(b+2)+(b+2)(c+2)+(a+2)(c+2)\leq(a+2)(b+2)(c+2)$

$<=> ab+bc+ac+4a+4b+4c+12 \leq abc+4a+4b+4c+2ab+2bc+2ca+8$

$<=> ab+bc+ca \leq 12-8-abc = 4-1 = 3$ (luôn đúng do (1))

Bạn giải đúng rồi, nhưng ở dòng cuối bạn ghi ngược dấu !. Phải là $ab+bc+ca\ge 3$ chứ ?