Đến nội dung

Hình ảnh

Topic về tổ hợp, các bài toán về tổ hợp

- - - - -

  • Please log in to reply
Chủ đề này có 107 trả lời

#21
whatever2507

whatever2507

    Binh nhất

  • Thành viên
  • 34 Bài viết

Mình cũng hơi kém phần tổ hợp rời rạc này, nên cũng muốn được học tập trao đổi kinh nghiệm. Mình xin đưa ra một bài nho nhỏ:

Bài 8: (phương pháp tự do, không câu nệ cách giải) Trên một sân chơi có 10 em bé đứng. Biết rằng khoảng cách giữa các em bé đôi một khác nhau và mỗi em bé cầm trong tay một quả bóng (quả bóng là một trong bốn màu đỏ, vàng, lam, lục). Sau hiệu lệnh của chị phụ trách, mỗi em đưa quả bóng của mình cho bạn đứng gần nhất. Hỏi rằng có ít nhất bao nhiêu em bé còn có bóng trong tay?

4 màu để làm gì nhỉ?  :)).

Giải bài 8. Ta CM còn ít nhất 2 em bé có bóng. Gọi vị trí 10 em bé đứng lần lượt là $A_1 \rightarrow A_{10}$

Giả sử tồn tại cách đứng sao cho sau khi chuyển bóng thì còn đúng 1 em bé có bóng. Giả sử chỉ có em $A_1$ còn bóng.

Xét các góc $\angle A_jA_1A_i (\forall 2 \le i, j \le 10, i \neq j)$, theo nguyên lý Dirichlet tồn tại 1 góc nhỏ hơn $60^o$, WLOG giả sử là $\angle A_2A_1A_3 < 60^o$. Khi đó tồn tại một trong 2 góc $\angle A_1A_2A_3$ hoặc $\angle A_2A_3A_1$ lớn hơn $60^o$ và lớn hơn $\angle A_2A_1A_3$. Giả sử $\angle A_2A_1A_3< \angle A_1A_2A_3$, khi đó $A_2A_3<A_1A_3$ do vậy $A_3$ sẽ đưa bóng cho $A_2$ chứ không phải $A_1$ (mâu thuẫn).

Vậy có ít nhất 2 em còn cầm bóng.

Cấu hình sau đảm bảo có đúng 2 em cầm bóng là $A_1$ và $A_6$.

Hình gửi kèm

  • HInh.png

Bài viết đã được chỉnh sửa nội dung bởi whatever2507: 30-06-2013 - 18:37


#22
Ispectorgadget

Ispectorgadget

    Nothing

  • Quản lý Toán Phổ thông
  • 2946 Bài viết

Bài 12: (Bất biến) Trong một ngày chủ nhật mỗi học sinh trong bảy học sinh có ba lần đi đến hiệu sách. Biết rằng hai học sinh bất kì trong số đó có gặp nhau tại hiệu sách. Chứng minh rằng có mội thời điểm mà trong hiệu sách có mặt cùng lúc 3 học sinh. (trong 7 học sinh nói trên)


►|| The aim of life is self-development. To realize one's nature perfectly - that is what each of us is here for. ™ ♫


#23
The Collection

The Collection

    Hạ sĩ

  • Thành viên
  • 71 Bài viết

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. 

 

 



#24
whatever2507

whatever2507

    Binh nhất

  • Thành viên
  • 34 Bài viết

Bài 12: (Bất biến) Trong một ngày chủ nhật mỗi học sinh trong bảy học sinh có ba lần đi đến hiệu sách. Biết rằng hai học sinh bất kì trong số đó có gặp nhau tại hiệu sách. Chứng minh rằng có mội thời điểm mà trong hiệu sách có mặt cùng lúc 3 học sinh. (trong 7 học sinh nói trên)

Giải bài 12. Gọi $7$ bạn học sinh này là $X_1 \rightarrow X_7$, xét $3$ thời điểm $A_1, A_2, A_3$ mà học sinh $X_1$ đi đến hiệu sách. Do cả $6$ học sinh khác đều có gặp $X_1$ nên mỗi người trong số họ phải đến hiệu sách vào ít nhất $1$ trong $3$ thời điểm kể trên, theo nguyên lý Dirichlet thì tồn tại $2$ học sinh $X_i$ và $X_j (2 \le i,j \le 7, i \neq j)$ đến vào cùng $1$ thời điểm $A_i$. Do đó $3$ học sinh $X_i, X_j, X_1$ cùng có mặt tại hiệu sách cùng $1$ thời điểm nên ta có đpcm.

 

Có vẻ bài trên chỉ cần $5$ học sinh là đủ nhỉ? :)



#25
Stranger411

Stranger411

    Hạ sĩ

  • Thành viên
  • 85 Bài viết

Bài 11:(Lý thuyết đồ thị, APMO 1989) Chứng minh rằng một đồ thị n đỉnh, k cạnh thì sẽ có ít nhất $\frac{{k\left( {4k - {n^2}} \right)}}{{3n}}$ tam giác.

Câu này được chế biến lại làm đề chọn đội tuyển của KHTN năm nào đó thì phải, nhưng cũng chỉ là điều kiện cần.
Giải bài 11:
Gọi $D_i$ là bậc của đỉnh $i$ nào đó.
Nếu 2 đỉnh $i$ và $j$ liên thông thì tồn tại ít nhất $D_i + D_j - 2$ cạnh khác nổi đến $n-2$ đỉnh khác của đồ thị.
Nên có $D_i + D_j - n$ tam giác có đỉnh là $j$ và $j$. Vậy số tam giác có chứa cạnh $ij$ được tạo thành phải tối thiểu là:
$\sum_{i,j} {\frac{D_i + D_j -n}{3}}=\sum_{i,j} {\frac{D_i + D_j}{3} - \frac{nk}{3}} = \sum_{i} {\frac{D_i^2}{3} - \frac{nk}{3}}$

Vậy số tam giác tối thiểu được tạo thành là:

$\sum_{i}{\frac{D_i^2}{3}} -\frac{nk}{3} \geq \frac{1}{3n}\left ( \sum_{i}{D_i} \right )^2 - \frac{nk}{3} = \frac{4k^2}{3n} -\frac{nk}{3}$
Q.E.D.

 

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}?

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 a1 = 2, a2 = 6, ta tìm được

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

Với cách đặt trên ta có thể có công thức truy hồi khác là $b_n = 4^n - a_n$
từ đó suy ra $a_{n+1} = 2a_{n} + b_{n}= a_n + 4^n$
Nên $a_{n} = 4^{n-1} + 4^{n-2} +...+ a_{1} = \frac{4^n + 2}{3}$


Bài viết đã được chỉnh sửa nội dung bởi Stranger411: 30-06-2013 - 22:59

$P_{G}(\sigma_{1},\sigma_{2},\cdots,\sigma_{n})=\frac{1}{|G|}\sum_{\tau\in G}ind(\tau)$


#26
whatever2507

whatever2507

    Binh nhất

  • Thành viên
  • 34 Bài viết

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

Giải bài 9. Gọi các phần tử của $M$ là $a_1 \rightarrow a_{22222}$. Giả sử tồn tại $50$ tập con $M_i (1 \le i \le 50)$ thoả mãn $3$ yêu cầu trên. Ta đếm số cách chọn $2$ tập $M_i, M_j (i \neq j)$ kèm theo $1$ phần tử $a_k$ thuộc $M_i \cap M_j$. Gọi số cách chọn này là $S$.

Có $C^2_{50}$ cách chọn $2$ tập $M_i, M_j (i \neq j)$ và $22$ cách chọn phần tử $a_k$ thuộc $M_i \cap M_j$.

$\Rightarrow S=22.C^2_{50}=26950$.

 

Mặt khác, giả sử $a_i$ thuộc $r_i ( \forall 1 \le i \le 22222)$ tập $M_j$. Khi đó dễ CM được $$\sum_{i=1}^{22222}r_i= \sum_{i=1}^{50} |M_i|=50.1111=55550$$.

 

Có $22222$ cách chọn phần tử $a_i$ bất kỳ, và có $C^2_{r_i}$ cách chọn 2 tập $M_j, M_k$ sao cho $a_i \in M_j \cap M_k$ (coi $C^2_1=0$).

$\Rightarrow S=\sum_{i=1}^{22222} C^2_{r_i}$

$=\sum_{i=1}^{22222} \frac{r_i(r_i-1)}{2}$

$=\frac{1}{2}(\sum_{i=1}^{22222}r_i^2 - \sum_{i=1}^{22222}r_i)$

$\geq \frac{1}{2} (\frac{(\sum_{i=1}^{22222} r_i)^2}{22222}-\sum_{i=1}^{22222} r_i)$ (BĐT C-S)

$=\frac{55550^2-22222.55550}{2.22222}>26950=S$ (mâu thuẫn).

Vậy không tồn tại $50$ tập con của $M$ thoả mãn đề bài.


Bài viết đã được chỉnh sửa nội dung bởi whatever2507: 30-06-2013 - 23:19


#27
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

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


Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 01-07-2013 - 10:56


#28
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

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.



#29
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

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 viết đã được chỉnh sửa nội dung bởi Ispectorgadget: 01-07-2013 - 17:08


#30
nhatquangsin

nhatquangsin

    Thượng sĩ

  • Thành viên
  • 238 Bài viết

Bài 4 (Tô màu - Nguồn: Đề thi HSG lớp 10 THPT chuyên KHTN). Cho một bảng ô vuông kích thước $m \times n$. Người ta muốn tô màu các ô vuông con của bảng, mỗi ô vuông con chỉ được tô bởi 1 trong 2 màu Xanh hoặc Đỏ theo quy tắc sau:

i) Tất cả các ô vuông con ở cạnh của bảng đều được tô màu Đỏ.
ii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà $4$ ô vuông con được tô cùng màu.
iii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà hai ô ở mỗi đường chéo đều được tô cùng màu.
Hỏi người ta có thể thực hiện cách tô màu như trên trong các trường hợp với bảng ô vuông kích thước:
$a) 2012 \times 2013?$
$b) 2012 \times 2014?$

 

 

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


Bài viết đã được chỉnh sửa nội dung bởi nhatquangsin: 01-07-2013 - 15:38


#31
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

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)

attachicon.gifSnap100.png

attachicon.gifSnap101.png

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

attachicon.gifSnap102.png

Được tao ra từ cách ghép 2 ô $2\times 2$ dạng 1 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à !?



#32
whatever2507

whatever2507

    Binh nhất

  • Thành viên
  • 34 Bài viết

 

Bài 3 (Toán trò chơi-Nguồn: Tournament of the Towns). Trên bảng ô vuông $20$x$20$ mỗi ô có $1$ quân cờ. $A$ chọn một số thực $d$ và $B$ phải đưa mỗi quân cờ đi tới ô cách ô ban đầu nó đứng một khoảng cách ít nhất là $d$ (khoảng cách giữa $2$ ô được tính theo khoảng cách tâm của $2$ ô đó) và mỗi ô chỉ có thể có $1$ quân cờ. Hỏi với điều kiện gì của $d$ thì $B$ có thể thao tác thoả mãn điều kiện trên?

Hỏi tương tự với bảng $21$x$21$

Bài này chỉ dùng duy nhất $1$ nhận xét, tiếc là chưa ai giải.

Giải bài 3. $*$ TH bảng $20 \times 20$:

Xét toạ độ các ô (được tính ở tâm ô) là $(i, j) \forall 1 \le i, j \le 20$. Xét ô $(10, 10)$, giả sử sau bước chuyển quân cờ ở ô này chuyển đến ô $(a,b) (1 \le a,b \le 20, a, b$ không đồng thời bằng $10)$, khi đó khoảng cách giữa $2$ ô là: $\sqrt{(a-10)^2+(b-10)^2} \ge d$.

Do $1 \le a,b \le 20$ nên $|a-10| \le 10, |b-10| \le 10 \Rightarrow d \le 10\sqrt{2}$.

Cách chuyển quân: Các quân ở các ô $(i, j)$ đến ô $(i', j')$ với $\begin{cases} i'=i+10 & \text{ if } i \le 10\\ i'=i-10 & \text{ if } i > 10 \end{cases}$.

 

$*$ TH bảng $21 \times 21$: Lập luận tương tự với ô $(11,11)$, cách xây dựng mọi người tự tìm nhé :).



#33
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

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

Bài 15:(APMO 1998) Cho F là tập tất cả các bộ (A1, . . . ,An) sao cho mỗi Ai 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?


Bài viết đã được chỉnh sửa nội dung bởi Ispectorgadget: 02-07-2013 - 10:00


#34
Stranger411

Stranger411

    Hạ sĩ

  • Thành viên
  • 85 Bài viết

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

Bài 15:(APMO 1998) Cho F là tập tất cả các bộ (A1, . . . ,An) sao cho mỗi Ai 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?

Tại sao các bạn cứ thích post những bài không có lời giải ở trong sách ra thế nhỉ :))
Mình nhớ không nhầm thì mấy bài này trong chuyên đề của thầy Huỳnh Tấn Châu để học sinh tự giải. Sau đây là cách của mình, bạn có cách khác thì post lên cho mọi người tham khảo.
Giải bài 15:

Bài này đếm bằng truy hồi.
Tập $(1, 2, . . . , 1998)$ có tất cả $2^{1998}$ tập con $A_i$ nên tổng cần tính có tất cả $2^{1998n}$ bộ $n$ số.
Bước 1: Với các tập con $(A_1, A_2 ... , A_n)$ của $(1, 2, . . . , 1997)$, ta có thể thêm hoặc không thêm vào mỗi tập $A_i$ phần tử $1998$ để tạo thành tập con của tập $(1, 2, . . . , 1998)$. Vậy từ bộ $(A_1, A_2 ... , A_n)$ ta có $2^n$ bộ gồm các tập con của $\left \{1, 2, . . . , 1998 \right \}$.

Bước 2: Bây h chỉ còn xét các tập con $(A_1, A_2 ... , A_n)$ của các bộ còn lại. Làm tương tự như trên thì ta có được $(2^n -1).2^{n(m-1)}$.
Tình tổng lại, ta có:

$\sum\limits_{({A_1},{A_2},...,{A_n}) \in (1,...,1998)} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|} = (2^n.\sum\limits_{({A_1},{A_2},...,{A_n}) \in (1,...,1998)} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|}) + (2^n -1) 2^{n(m-1)}$
Từ đó, ta có: $\sum\limits_{({A_1},{A_2},...,{A_n}) \in F} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|} = 1998(2^{1998n} - 2^{1997n})$.

 

Mở rộng bài 15: Tính:
$P= \sum_{(A_{1},A_{2},...,A_{k})\in F_{k}}\sum_{b\in (A_{1}\cup A_{2}\cup ...\cup A_{k})}b$
$S= \sum_{(A_{1},A_{2},...,A_{k})\in F_{k}}\sum_{i=1}^{k}\sum_{b\in A_{i}}b$
 

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.

Đề này của trường chuyên Nguyễn Tất Thành - Komtum và họ không đưa đáp án nên trong sách không có lời giải.
Mình nghĩ bạn Ispectorgadget cũng không có đáp án cho bài này. (Trừ khi bạn ấy học trường chuyên NTT)

Bài này chắc không thể giải bằng đồ thị vì phải xét tới 2 đối tượng là hoa hậu và giám khảo.
Thôi thì phát biểu lại dưới dạng tập hợp để mọi người cùng nghiên cứu:
Cho $X=\{1;2;...;n\}$. Và $A_1 ,A_2, ..., A_m$ là các tập con của $X$.
Biết 6 phần tử bất kì của $X$ luôn thuộc $|A_i\cup A_j|$ nào đó.
Chứng minh tồn tại $i_1;i_2;..;i_{10}$ phân biệt mà $|\bigcup\limits_{j=1}^{10}A_{i_j}|=X$.


Bài viết đã được chỉnh sửa nội dung bởi Stranger411: 02-07-2013 - 12:29

$P_{G}(\sigma_{1},\sigma_{2},\cdots,\sigma_{n})=\frac{1}{|G|}\sum_{\tau\in G}ind(\tau)$


#35
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

 

Tại sao các bạn cứ thích post những bài không có lời giải ở trong sách ra thế nhỉ :))
Mình nhớ không nhầm thì mấy bài này trong chuyên đề của thầy Huỳnh Tấn Châu để học sinh tự giải. Sau đây là cách của mình, bạn có cách khác thì post lên cho mọi người tham khảo.
Giải bài 15:

Bài này đếm bằng truy hồi.
Tập $(1, 2, . . . , 1998)$ có tất cả $2^{1998}$ tập con $A_i$ nên tổng cần tính có tất cả $2^{1998n}$ bộ $n$ số.
Bước 1: Với các tập con $(A_1, A_2 ... , A_n)$ của $(1, 2, . . . , 1997)$, ta có thể thêm hoặc không thêm vào mỗi tập $A_i$ phần tử $1998$ để tạo thành tập con của tập $(1, 2, . . . , 1998)$. Vậy từ bộ $(A_1, A_2 ... , A_n)$ ta có $2^n$ bộ gồm các tập con của $\left \{1, 2, . . . , 1998 \right \}$.

Bước 2: Bây h chỉ còn xét các tập con $(A_1, A_2 ... , A_n)$ của các bộ còn lại. Làm tương tự như trên thì ta có được $(2^n -1).2^{n(m-1)}$.
Tình tổng lại, ta có:

$\sum\limits_{({A_1},{A_2},...,{A_n}) \in (1,...,1998)} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|} = (2^n.\sum\limits_{({A_1},{A_2},...,{A_n}) \in (1,...,1998)} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|}) + (2^n -1) 2^{n(m-1)}$
Từ đó, ta có: $\sum\limits_{({A_1},{A_2},...,{A_n}) \in F} {|{A_1} \cup {A_2} \cup ... \cup {A_n}|} = 1998(2^{1998n} - 2^{1997n})$.

 

Mở rộng bài 15: Tính:
$P= \sum_{(A_{1},A_{2},...,A_{k})\in F_{k}}\sum_{b\in (A_{1}\cup A_{2}\cup ...\cup A_{k})}b$
$S= \sum_{(A_{1},A_{2},...,A_{k})\in F_{k}}\sum_{i=1}^{k}\sum_{b\in A_{i}}b$

 

Vẫn còn nhiều tài liệu có lời giải bài này mà bạn, đừng nghĩ xấu mình thế chứ  :icon6:

Còn một cách giải khác của bài 15 bằng phương pháp đếm theo phần tử (hơi lạ), mong các bạn cố gắng tìm thêm


Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 02-07-2013 - 13:19


#36
whatever2507

whatever2507

    Binh nhất

  • Thành viên
  • 34 Bài viết

 

Đáp số của cả $2$ TH đều là $d \le 10\sqrt{2}$, dùng chung $1$ lập luận và chỉ hơi khác nhau cách đưa quân cờ thỏa mãn :).

 

Bài 4 (Tô màu - Nguồn: Đề thi HSG lớp 10 THPT chuyên KHTN). Cho một bảng ô vuông kích thước $m \times n$. Người ta muốn tô màu các ô vuông con của bảng, mỗi ô vuông con chỉ được tô bởi 1 trong 2 màu Xanh hoặc Đỏ theo quy tắc sau:

i) Tất cả các ô vuông con ở cạnh của bảng đều được tô màu Đỏ.
ii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà $4$ ô vuông con được tô cùng màu.
iii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà hai ô ở mỗi đường chéo đều được tô cùng màu.
Hỏi người ta có thể thực hiện cách tô màu như trên trong các trường hợp với bảng ô vuông kích thước:
$a) 2012 \times 2013?$
$b) 2012 \times 2014?$

 

 Để giải hoàn chỉnh và chặt chẽ bài này ra thì khá dài, thế nên mình chỉ post ý tưởng của câu b ra mọi người thực hiện tính toán nhé :). (Còn câu a cách xây dựng thì hoàn toàn không khó  :P ).

 

Gợi ý câu 4b)  Giả sử tồn tại cách tô màu thoả mãn điều kiện. Xét các giao điểm của các đường thẳng vuông góc nhau bên trong bảng vuông là các điểm nguyên trên mặt phẳng toạ độ với toạ độ $(i,j) (1 \le i \le 2011, 1 \le j \le 2013)$. Gọi $x_{ịj}$ là số đoạn thẳng đơn vị (đoạn thẳng độ dài $1$) nằm trong hình vuông $4 \times 4$ có tâm là điểm $(i,j)$ mà ngăn cách giữa $2$ ô cùng màu, $y_{ịj}$ là số đoạn thẳng đơn vị nằm trong hình vuông $4 \times 4$ có tâm là điểm $(i,j)$ mà ngăn cách giữa $2$ ô khác màu, $X$ là số đoạn thẳng đơn vị nằm trong bảng vuông $2012 \times 2014$ ngăn cách giữa $2$ ô cùng màu, $Y$ là số đoạn thẳng đơn vị nằm trong bảng vuông $2012 \times 2014$ ngăn cách giữa $2$ ô khác màu. Ta tính $X-Y$ theo $2$ cách.

Để ý rằng $x_{ij}=y_{ij} \forall i,j$.

Đầu tiên ta tính $X-Y$ theo tổng $\sum_{i \equiv j (mod2)} (x_{ij}-y_{ij})$ sau đó theo tổng  $\sum_{i \not\equiv j (mod2)} (x_{ij}-y_{ij})$. Có vẻ ta thấy $2$ tổng này bằng nhau và bằng $0$ nhưng với mỗi cách đếm thì có một số cạnh chưa được tính (các cạnh này toàn nằm giữa các ô vuông đỏ trên biên nên dễ đếm thôi), và 2 cách đếm cho ta số cạnh chưa được tính khác nhau nên suy ra mâu thuẫn :).



#37
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

Bài 16:(song ánh) Một tập hữu hạn các số nguyên dương được gọi là “béo” nếu mỗi phần tử của nó lớn hơn hoặc bằng số phần tử của nó (Tập rỗng “béo”) . Gọi $a_n$ là số tập con “béo” của $X= \left\{1,2,3,4,…..,n\right\}$ mà không chứa 2 số nguyên liên tiếp nào, $b_n$ là số tập con của X mà 2 phần tử bất kì hơn kém nhau ít nhất 3 đơn vị.

Chứng minh rằng $a_n=b_n$


Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 02-07-2013 - 20:50


#38
nhatquangsin

nhatquangsin

    Thượng sĩ

  • Thành viên
  • 238 Bài viết

Bài 17 (cực trị-bất đẳng thức tổ hợp)

Cho tập hợp $X=\left \{ 1,2,...,50 \right \}$. Tìm số nguyên dương nhỏ nhất $k$ sao cho mọi tập con gồm $k$ phần tử của $X$ đều chứa hai phần tử phân biệt $a$ và $b$ sao cho $ab$ chia hết cho $a+b$


Bài viết đã được chỉnh sửa nội dung bởi nhatquangsin: 02-07-2013 - 20:26

  • LNH yêu thích

#39
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

Bài 17 (cực trị-bất đẳng thức tổ hợp)

Cho tập hợp $X=\left \{ 1,2,...,50 \right \}$. Tìm số nguyên dương nhỏ nhất $k$ sao cho mọi tập con gồm $k$ phần tử của $X$ đều chứa hai phần tử phân biệt $a$ và $b$ sao cho $ab$ chia hết cho $a+b$

Ta có các cặp số thoả mãn $ab$ chia hết $a+b$: $(3;6);(4;12);(5;20);(6;12);(6;30);(7;42);(8;2);(9;18);(10;15);(10;40);(12;24);(12;36);(14;35);(15;30);(16;48);(18;36);(20;30);(21;28);(21;42);(24;40);(24;48);(30;45);(36;45)$

Tổng hợp các số lại tập $A$, ta có:\[A = \left\{ {3;4;5;6;7;8;9;10;12;14;15;16;18;20;21;24;30;35;36;40;45;48} \right\}\]

\[ \Rightarrow k \ge \left| {X\backslash A} \right| + \left[ {\frac{{\left| A \right|}}{2}} \right] + 1 = 39\]

Vậy $min(k)=39$

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

Đây là kết quả sau 1h bấm máy tính của mình, các bạn có cách nào hay hơn thì đưa lên để mọi người cùng tham khảo



#40
Stranger411

Stranger411

    Hạ sĩ

  • Thành viên
  • 85 Bài viết

Bài 17 (cực trị-bất đẳng thức tổ hợp)

Cho tập hợp $X=\left \{ 1,2,...,50 \right \}$. Tìm số nguyên dương nhỏ nhất $k$ sao cho mọi tập con gồm $k$ phần tử của $X$ đều chứa hai phần tử phân biệt $a$ và $b$ sao cho $ab$ chia hết cho $a+b$

Ta có các cặp số thoả mãn $ab$ chia hết $a+b$: $(3;6);(4;12);(5;20);(6;12);(6;30);(7;42);(8;2);(9;18);(10;15);(10;40);(12;24);(12;36);(14;35);(15;30);(16;48);(18;36);(20;30);(21;28);(21;42);(24;40);(24;48);(30;45);(36;45)$

Tổng hợp các số lại tập $A$, ta có:\[A = \left\{ {3;4;5;6;7;8;9;10;12;14;15;16;18;20;21;24;30;35;36;40;45;48} \right\}\]

\[ \Rightarrow k \ge \left| {X\backslash A} \right| + \left[ {\frac{{\left| A \right|}}{2}} \right] + 1 = 39\]

Vậy $min(k)=39$

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

Đây là kết quả sau 1h bấm máy tính của mình, các bạn có cách nào hay hơn thì đưa lên để mọi người cùng tham khảo

Giải bài 17:
Chứng minh $k \ge 39$
Các cặp số thoả mãn $ab$ chia hết $a+b$: $(3;6);(4;12);(5;20);(6;12);(6;30);(7;42);(8;2);(9;18);(10;15);(10;40);(12;24);(12;36);(14;35);(15;30);(16;48);(18;36);(20;30);(21;28);(21;42);(24;40);(24;48);(30;45);(36;45)$

Xét tập $M=(6,12,15,18,20,21,24,35,40,42,45,48)$. Vì 23 cặp trên đều có phần tử thuộc $M$ nên tập $X\M$ không thỏa mãn bài toán. Mà $|X\M|=38 \rightarrow k \ge 39$

Chứng minh mọi tập có 39 phần tử đều thỏa mãn bài toán:
Xét tập $A$ bất kì gồm 39 phần tử của $X$.
Chọn 12 cặp số trong 23 cặp trên sao cho các phần tử không trùng nhau: $(3;6);(4;12);(5;20);(7;42);(8;2);(9;18);(10;15);(14;35);(18;36);(21;28);(24;40);(30;45)$

12 cặp trên chứa 24 phần tử của $X$. Nên $X$ chỉ còn lại 26 phần tử.
Vậy ít nhất 13 phần tử của $A$ của phải thuộc 12 cặp trên.
Theo nguyên lí drichlet thì $A$ chứa ít nhất 1 trong 12 cặp trên.
Từ đó tập $A$ thỏa mãn đề bài.


Bài viết đã được chỉnh sửa nội dung bởi Stranger411: 03-07-2013 - 10:01

$P_{G}(\sigma_{1},\sigma_{2},\cdots,\sigma_{n})=\frac{1}{|G|}\sum_{\tau\in G}ind(\tau)$





0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh