Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


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ó 106 trả lời

#1 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 29-06-2013 - 09:20

Đượ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 :luoi: )


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


#2 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 29-06-2013 - 09:27

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


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


#3 whatever2507

whatever2507

    Binh nhất

  • Thành viên
  • 34 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên KHTN
  • Sở thích:Combinatorics :D

Đã gửi 29-06-2013 - 10:15

Topic này có nên thêm cả phần đồ thị vào không nhỉ? :))

Giải bài 1. Số giao điểm: Xét một tứ giác bất kỳ lập thành từ $4$ đỉnh của đa giác, do đa giác lồi nên giao điểm 2 đường chéo của tứ giác này nằm trong đa giác và cũng là giao điểm 2 đường chéo của đa giác.

Ngược lại với $1$ giao điểm của $2$ đường chéo bất kỳ trong đa giác thì $2$ cặp đầu mút của $2$ đường chéo này lập thành $1$ tứ giác có $4$ đỉnh là $4$ đỉnh phân biệt của đa giác. Tóm lại ta lập được song ánh giữa số giao điểm và số tứ giác tạo bởi $4$ đỉnh phân biệt của đa giác.

$\Rightarrow$ Số giao điểm là $C^4_n$.

Số miền: Ta xuất phát từ đầu với $1$ miền (chính là $n$-giác) và lần lượt nối các đường chéo. Mỗi đường chéo chia đa giác thêm $1$ phần, và mỗi khi nó giao với đường chéo khác nó lại chia đa gíc thêm $1$ phần nữa.

Dễ tính được số đường chéo là: $C^2_n-n$.

$\Rightarrow$ Số miền là: $1+C^2_n-n+C^4_n$.

 

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$



#4 Stranger411

Stranger411

    Hạ sĩ

  • Thành viên
  • 85 Bài viết
  • Giới tính:Nam
  • Đến từ:Somewhere ...

Đã gửi 29-06-2013 - 11:02

Bài 2: (PP ánh xạ, chứng minh đặc tính tổ hợp) Gọi an là số các xâu nhị phân độ dài n không chứa chuỗi con 010, bn 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 bn+1 = 2an với mọi n nguyên dương. 

Giải bài 2:
Xét một xâu nhị phân bất kì  $\left \{ x_1, x_2,...,x_n \right \}$.
Ta xây dựng một xâu nhị phân $\left \{ y_1, y_2,...,y_{n+1} \right \}$ sao cho $y_1 =0$ và $y_k = x_1 + x_2 +...+ x_k(mod2)$
Rõ ràng, xâu $\left \{ x_1, x_2,...,x_n \right \}$ có dạng $a_n$ khi và chỉ khi $\left \{ y_1, y_2,...,y_{n+1} \right \}$ có dạng $b_n$. Nói cách khác đó là một song ánh biến các xâu có dạng $a_n$ thành các xâu có dạng $b_{n+1}$ bắt đầu bằng $0$.
Với mỗi xâu $\left \{ y_1, y_2,...,y_{n+1} \right \}$, ta thay các kí tự 1 bởi 0 và 0 bởi 1, ta được một xâu khác cũng có dạng $b_{n+1}$ nhưng bắt đầu bởi $1$.
Từ đó cho ta: $b_{n+1} = 2a_n$.
 

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$

Với bài này có lẽ ta phải chia bàn cờ ra 4 phần.
Cái đáp số hơi lằng nhằng, không biết có đúng không.


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

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


#5 whatever2507

whatever2507

    Binh nhất

  • Thành viên
  • 34 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên KHTN
  • Sở thích:Combinatorics :D

Đã gửi 29-06-2013 - 11:39

 

Với bài này có lẽ ta phải chia bàn cờ ra 4 phần.
Cái đáp số hơi lằng nhằng, không biết có đúng không.

Đá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?$


#6 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 29-06-2013 - 12:17

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 viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 29-06-2013 - 12:17


#7 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 29-06-2013 - 14:33

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



#8 nhatquangsin

nhatquangsin

    Thượng sĩ

  • Thành viên
  • 238 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Bình Định
  • Sở thích:mathematics

Đã gửi 29-06-2013 - 21:05

Giải bài 5

Gọi $S(n)$ là tích số thứ tự phòng của tất cả mọi người ngày thứ $n$

Như vậy ta có

$\frac{S(n+1)}{S(n)}=\frac{n(n+1)}{(n-1)(n+2)}=\frac{n^{2}+n}{n^{2}+n-2}< 1$

$\Rightarrow S(n+1)<S(n)$

Như vậy $S(n)$ là một đơn biến. Do $S(n)$ giảm và $S(n)>0$ nên việc chuyển phòng sẽ dừng sau một số ngày

 

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

Bài 7 (bất đẳng thức tổ hợp)

Gọi $X=\left \{ 1,2,...,2003 \right \}$. Lấy số tự nhiên $n\geq 1$ và $n\leq 2003$ sao cho nếu lấy tập hợp con gồm $n$ phần tử của $X$, thì ta có thể tìm được một phần tử là lũy thừa của $2$ hoặc $2$ phần tử có tổng là lũy thừa của $2$. Chứng minh rằng: $n\geq 999$


Bài viết đã được chỉnh sửa nội dung bởi nhatquangsin: 29-06-2013 - 21:14
LaTex + Trích dẫn


#9 Ispectorgadget

Ispectorgadget

    Nothing

  • Quản trị
  • 2938 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:Nơi tình yêu bắt đầu
  • Sở thích:Làm "ai đó" vui

Đã gửi 29-06-2013 - 21:18

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.


►|| The aim of life is self-development. To realize one's nature perfectly - that is what each of us is here for. ™ ♫ Giao diện website du lịch miễn phí Những bí ẩn chưa biết

#10 whatever2507

whatever2507

    Binh nhất

  • Thành viên
  • 34 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên KHTN
  • Sở thích:Combinatorics :D

Đã gửi 29-06-2013 - 23:49

Giải bài 5

Gọi $S(n)$ là tích số thứ tự phòng của tất cả mọi người ngày thứ $n$

Như vậy ta có

$\frac{S(n+1)}{S(n)}=\frac{n(n+1)}{(n-1)(n+2)}=\frac{n^{2}+n}{n^{2}+n-2}< 1$

$\Rightarrow S(n+1)<S(n)$

Như vậy $S(n)$ là một đơn biến. Do $S(n)$ giảm và $S(n)>0$ nên việc chuyển phòng sẽ dừng sau một số ngày

 

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

Lời giải này chưa chặt chẽ vì có thể mẫu bằng $0$ hoặc âm thì chưa thể đánh giá được.

 

 

 

Bài 7 (bất đẳng thức tổ hợp)

Gọi $X=\left \{ 1,2,...,2003 \right \}$. Lấy số tự nhiên $n\geq 1$ và $n\leq 2003$ sao cho nếu lấy tập hợp con gồm $n$ phần tử của $X$, thì ta có thể tìm được một phần tử là lũy thừa của $2$ hoặc $2$ phần tử có tổng là lũy thừa của $2$. Chứng minh rằng: $n\geq 999$

Giải bài 7. Xét tập $A=\left \{ 5, 6, 7, 12, 13, 14, 15, 21, 22, 23, 24, 28, 29, 30, 31, 37, 38, 39, 44\right \}$ và $B=\left \{n|n \in \mathbb{N}, 1025 \le n \le 2003\right \}$.

Xét tập $C=A \cup B$. Dễ thấy $|C|=998$.

Các phần tử trong $B$ nằm giữa $2^{10}$ và $2^{11}$ nên không thể là luỹ thừa của $2$ và  $\forall x \neq y; x, y \in B$ thì $2^{11} < x+y < 2^{12}$ nên tổng $x+y$ cũng không thể là luỹ thừa của $2$.

Với $x \in A$ và $y \in B$ thì $1030 \le x+y \le 2047$ nên tổng $x+y$ cũng không là luỹ thừa của $2$.

Dễ kiểm tra các phần tử của $A$ không là luỹ thừa của $2$ và tổng của $2$ số bất kỳ trong số chúng cũng vậy.

$\Rightarrow \forall n \le 998$ ta chỉ cần lấy một tập con $n$ phần tử của $C$ thì tập này sẽ không có phần tử nào và cũng không có tổng của $2$ phần tử nào là luỹ thừa của $2$.

$\Rightarrow n \geq 999$.

 

 

 



#11 nhatquangsin

nhatquangsin

    Thượng sĩ

  • Thành viên
  • 238 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Bình Định
  • Sở thích:mathematics

Đã gửi 30-06-2013 - 06:26

 

Lời giải này chưa chặt chẽ vì có thể mẫu bằng $0$ hoặc âm thì chưa thể đánh giá được.

 

Nhưng $S(n)>0$  mà bạn, với lại $S(n)$ đúng hơn là số nguyên dương, làm sao mà âm được


  • LNH yêu thích

#12 bachhammer

bachhammer

    Thiếu úy

  • Thành viên
  • 659 Bài viết
  • Giới tính:Nam
  • Đến từ:ĐHKHTN TPHCM
  • Sở thích:Bay...trên trời (SKY!!!)

Đã gửi 30-06-2013 - 09:40

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?


:ukliam2: TOPIC SỐ HỌC - Bachhammer :ukliam2: 

Topic số học, các bài toán về số học

:namtay  :namtay  :namtay  :lol:  :lol:  :lol:  :lol:  :excl:  :excl:  :excl:  :lol:  :lol:  :lol: :icon6:  :namtay  :namtay  :namtay  


#13 Ispectorgadget

Ispectorgadget

    Nothing

  • Quản trị
  • 2938 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:Nơi tình yêu bắt đầu
  • Sở thích:Làm "ai đó" vui

Đã gửi 30-06-2013 - 10:20

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

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

 

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$


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

►|| The aim of life is self-development. To realize one's nature perfectly - that is what each of us is here for. ™ ♫ Giao diện website du lịch miễn phí Những bí ẩn chưa biết

#14 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 30-06-2013 - 12:31

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 viết đã được chỉnh sửa nội dung bởi Ispectorgadget: 30-06-2013 - 18:02
Latex fixed


#15 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 30-06-2013 - 15:26

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 viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 30-06-2013 - 15:27


#16 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 30-06-2013 - 17:08

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

 

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


#17 nhatquangsin

nhatquangsin

    Thượng sĩ

  • Thành viên
  • 238 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Bình Định
  • Sở thích:mathematics

Đã gửi 30-06-2013 - 17:40



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.

Gọi $S_n$ là số cách chọn ra một số người từ $2n$ người xếp thành 2 hàng dọc và Tn là số cách chọn ra một số người từ $2n-1$ người xếp thành 2 hàng dọc, trong đó khuyết một chỗ ở đầu của một hàng. Ta có S1 = 2, T1 = 1.

Xét 2n người xếp thành 2 hàng dọc. Ta xét các cách chọn thoả mãn điều kiện đầu bài. Xảy ra các khả năng sau :

1)     Người ở vị trí số 1 được chọn :  Khi đó người ở vị trí số 2 và số 3 không được chọn à Có $T_{n-1}+1$

cách chọn (+1 là do bổ sung cách chọn " không chọn gì cả"  )

2)     Người ở vị trí số 2 được chọn : Tương tự, có $T_{n-1}+1$ cách chọn.

3)     Cả hai người ở vị trí số 1 và số 2 đều không được chọn: Có $S_{n-1}$ cách chọn.

Vậy ta có  $S_n=S_{n-1}+2T_{n-1}+2$  (1).

Xét $2n-1$ người xếp thành 2 hàng dọc. Ta xét các cách chọn thoả mãn điều kiện đầu bài. Xảy ra các khả năng sau :

1)     Người ở vị trí số 1 được chọn : Khi đó người ở vị trí số 2 không được chọn à có $T_{n-1}+1$ cách chọn

2)     Người ở vị trí số 1 không được chọn : có $S_{n-1}$cách chọn.

Vậy  ta có $T_n=S_{n-1}+T_{n-1}+1$ (2)

 

Từ (1) ta suy ra $2T_{n-1} = S_n – S_{n-1} – 2, 2T_n = S_{n+1} – S_n – 2$. Thay vào (2), ta được

               $S_{n+1} – S_n – 2 = 2S_{n-1}+ S_n – S_{n-1} – 2 + 2$

              $S_{n+1} = 2S_n + S_{n-1} +2$

Từ đây dễ dàng tìm được

               \[{S_n} = \frac{{{{(1 + \sqrt 2 )}^{n + 1}} + {{(1 - \sqrt 2 )}^{n + 1}} - 2}}{2}\]

===

 

MOD: Bạn học gõ Latex lại đi nhé ! Đừng dùng kí hiệu chỉ số. Nên gõ là

công thức_{gõ chỉ số}

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


#18 nhatquangsin

nhatquangsin

    Thượng sĩ

  • Thành viên
  • 238 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên Lê Quý Đôn-Bình Định
  • Sở thích:mathematics

Đã gửi 30-06-2013 - 17:47

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.


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


#19 whatever2507

whatever2507

    Binh nhất

  • Thành viên
  • 34 Bài viết
  • Giới tính:Nam
  • Đến từ:THPT chuyên KHTN
  • Sở thích:Combinatorics :D

Đã gửi 30-06-2013 - 17:54

Nhưng $S(n)>0$  mà bạn, với lại $S(n)$ đúng hơn là số nguyên dương, làm sao mà âm được

VD nhé, nếu có ngày mà ở phòng $1$ và $2$ có người thì họ sẽ chuyển sang phòng $0$ và $3$, thì $S(n)$ lúc này bằng $0$ thì sao thực hiện phép chia xuống mẫu được :).

 

 

 

 

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

 

 

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 3 và 4 vẫn chưa có lời giải nhé mọi người :)



#20 LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 30-06-2013 - 18:06



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

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


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





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

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