Đến nội dung

Hình ảnh

Có bao nhiêu cách sắp xếp n cặp vợ chồng trên một bàn tròn sao cho mỗi người phụ nữ không ngồi kề chồng của mình.

- - - - -

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

#1
phathuy

phathuy

    Trung sĩ

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

Bài 1: Cho \[X=\left\{ 1,2,3,...,100 \right\}\] và \[S=\left\{ \left( a,b,c \right)|a,b,c\in X,a<b<c \right\}\]. Tìm \[\left| S \right|\].

Bài 2: Có bao nhiêu cách sắp xếp n cặp vợ chồng trên một bàn tròn sao cho mỗi người phụ nữ không ngồi kề chồng của mình.

Bài toán 3. Chứng minh số tập con thực sự và khác rỗng của một tập có n phần tử là ${{2}^{n}}-2$ 


Mục đích của cuộc sống là sống có mục đích :biggrin:


#2
Robben98

Robben98

    Lính mới

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

Bài toán 3. Chứng minh số tập con thực sự và khác rỗng của một tập có n phần tử là ${{2}^{n}}-1$ 

 

Cho tập $S$ có $n$ phần tử thì số tập con của $S$ là $2^{n}$ (kể cả tập rỗng)

Bài toán trên chứng minh bằng nguyên lý quy nạp

Chứng minh:

Bước 1: $n=1\Rightarrow$ tập $S$ có $2$ tập con là chính nó và tập rỗng.

Bước 2: Giả sử $n=k$ thì số tập con của $S$ là $2^{k}$

Bước 3:Ta cần chứng minh với $n=k+1$ thì số tập con của $S$ là $2^{k+1}$

Đặt $A=\begin{Bmatrix} a_{1};a_{2};...;a_{k} \end{Bmatrix}$ và $B=\begin{Bmatrix} a_{1};a_{2};...;a_{k};a_{k+1} \end{Bmatrix}$

Do $A\subset B$ nên số tập con của B là:

     * Các tập con của A có $2^{k}$ tập

     * Các tập con của A thêm phần tử $a_{k+1}$ ta có: $2^{k}$ tập

Dẫn đến số tập con của tập có $k+1$ phấn tử là $2^{k+1}$ tập

Do đó số tâp con của tập có $n$ phần tử là $2^{n}$ tập

Vậy số tập con của tập có $n$ phần tử và khác rỗng là $2^{n}-1$ tập

 

 



 



#3
hxthanh

hxthanh

    Tín đồ $\sum$

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

Bài 2: Có bao nhiêu cách sắp xếp n cặp vợ chồng trên một bàn tròn sao cho mỗi người phụ nữ không ngồi kề chồng của mình.

Đếm theo phương pháp bao gồm-loại trừ

Số cách xếp $2n$ người ($n$ cặp vợ chồng) lên một bàn tròn là $(2n-1)!$

Số cách xếp có ít nhất $k$ cặp vợ chồng ngồi gần nhau là $C_n^k\times 2^k \times (2n-1-k)! $

 

Vậy số cách xếp thỏa mãn là $S_n$

$$S_n=\sum_{k=0}^n (-1)^k 2^k C_n^k(2n-1-k)!$$

Tham khảo thêm về dãy số này ở đây: A129348



#4
phathuy

phathuy

    Trung sĩ

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

 

Cho tập $S$ có $n$ phần tử thì số tập con của $S$ là $2^{n}$ (kể cả tập rỗng)

Bài toán trên chứng minh bằng nguyên lý quy nạp

Chứng minh:

Bước 1: $n=1\Rightarrow$ tập $S$ có $2$ tập con là chính nó và tập rỗng.

Bước 2: Giả sử $n=k$ thì số tập con của $S$ là $2^{k}$

Bước 3:Ta cần chứng minh với $n=k+1$ thì số tập con của $S$ là $2^{k+1}$

Đặt $A=\begin{Bmatrix} a_{1};a_{2};...;a_{k} \end{Bmatrix}$ và $B=\begin{Bmatrix} a_{1};a_{2};...;a_{k};a_{k+1} \end{Bmatrix}$

Do $A\subset B$ nên số tập con của B là:

     * Các tập con của A có $2^{k}$ tập

     * Các tập con của A thêm phần tử $a_{k+1}$ ta có: $2^{k}$ tập

Dẫn đến số tập con của tập có $k+1$ phấn tử là $2^{k+1}$ tập

Do đó số tâp con của tập có $n$ phần tử là $2^{n}$ tập

Vậy số tập con của tập có $n$ phần tử và khác rỗng là $2^{n}-1$ tập

 

 



 

Vậy mà sách Bài tập Tài liệu chuyên toán Giải tích 11 trang 140 dòng thứ 7 lại ghi: "Số các tập con thực sự và khác rỗng của một tập có n-1 phần tử là $2^{n-1}-2$".


Mục đích của cuộc sống là sống có mục đích :biggrin:


#5
phathuy

phathuy

    Trung sĩ

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

Đếm theo phương pháp bao gồm-loại trừ

Số cách xếp $2n$ người ($n$ cặp vợ chồng) lên một bàn tròn là $(2n-1)!$

Số cách xếp có ít nhất $k$ cặp vợ chồng ngồi gần nhau là $C_n^k\times 2^k \times (2n-1-k)! $

 

Vậy số cách xếp thỏa mãn là $S_n$

$$S_n=\sum_{k=0}^n (-1)^k 2^k C_n^k(2n-1-k)!$$

Tham khảo thêm về dãy số này ở đây: A129348

A129348 Sao không đọc được nhỉ? Tiện đây xin hỏi hxthanh "phương pháp bao gồm - loại trừ" là phương pháp như thế nào vậy? Bạn có thể nêu một cách tổng quát phương pháp này rồi cho một vài bài đơn giản ví dụ được không?


Mục đích của cuộc sống là sống có mục đích :biggrin:


#6
PolarBear154

PolarBear154

    Sĩ quan

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

Vậy mà sách Bài tập Tài liệu chuyên toán Giải tích 11 trang 140 dòng thứ 7 lại ghi: "Số các tập con thực sự và khác rỗng của một tập có n-1 phần tử là $2^{n-1}-2$".

Có khi nào "các tập con thực sự" được nói đến ở đây không có chứa chính nó ạ? Nếu thế thì bỏ tập rỗng và chính tập đó đi sẽ có  $2^{n-1}-2 tập con ạ  :(


Trong bất cứ hoàn cảnh công việc nào, không cúi đầu trước cái ác, không lùi trước hiểm nạn. Nhìn thẳng và đi trên con đường mình đã chọn: con đường mà sự nhẫn nại bao dung là những bước đi tới, hành trang là những ước mơ vô cùng bé nhỏ- chỉ xin làm một cành dương tưới trên cuộc đời đầy rẫy khô khát và bất trắc... 


#7
tunglamlqddb

tunglamlqddb

    Trung sĩ

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

Đếm theo phương pháp bao gồm-loại trừ
Số cách xếp $2n$ người ($n$ cặp vợ chồng) lên một bàn tròn là $(2n-1)!$
Số cách xếp có ít nhất $k$ cặp vợ chồng ngồi gần nhau là $C_n^k\times 2^k \times (2n-1-k)! $
 
Vậy số cách xếp thỏa mãn là $S_n$
$$S_n=\sum_{k=0}^n (-1)^k 2^k C_n^k(2n-1-k)!$$
Tham khảo thêm về dãy số này ở đây: A129348

Thầy (anh) có thể giải thích kỹ hơn phần mà: số cách xếp ít nhất có k cặp ngồi gần nhau đc không?

#8
hxthanh

hxthanh

    Tín đồ $\sum$

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

Thầy (anh) có thể giải thích kỹ hơn phần mà: số cách xếp ít nhất có k cặp ngồi gần nhau đc không?

Coi bàn tròn có $n$ chiếc ghế đôi.
Chọn ra $k$ chiếc ghế đôi cho $k$ cặp vc có $C_n^k$ cách.
Có $2^k$ cách đặt $k$ cặp vc vào $k$ ghế đôi đó.
Bây giờ trên bàn tròn có $2n-k$ vị trí bao gồm $k$ vị trí ghế đôi đã dùng và $2n-2k$ vị trí của $n-k$ ghế đôi chưa dùng. Như vậy sẽ có $(2n-k-1)!$ cách sắp xếp.

#9
tientethegioi

tientethegioi

    Binh nhì

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

Bài 1. Cứ 1 bộ 3 số $(a,b,c)$ chỉ có duy nhất 1 cách xếp sao cho thỏa mãn $a<b<c$. Do đó sẽ  có $\binom{100}{3}$ tập con thỏa mãn đề ra.






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

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