Đến nội dung

Hình ảnh

Topic về các bài toán: Tập hợp - Logic tập hợp

- - - - - enjoy

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

#1
Trần Đức Anh @@

Trần Đức Anh @@

    Thượng sĩ

  • Thành viên
  • 286 Bài viết
Có gì thắc mắc mọi người có thể thắc mắc ngay trong topic này, đề bài nhớ ghi rõ nguồn nếu biết, mong mọi người ủng hộ. Bây giờ ta vào vấn đề chính nào:
Problem 1: Có bao nhiêu cặp tập con không giao nhau của một tập hợp $X$ gồm $n$ phần tử.
Chữ ký spam! Không cần xoá!

#2
minhtuyb

minhtuyb

    Giả ngu chuyên nghiệp

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

Có gì thắc mắc mọi người có thể thắc mắc ngay trong topic này, đề bài nhớ ghi rõ nguồn nếu biết, mong mọi người ủng hộ. Bây giờ ta vào vấn đề chính nào:
Problem 1: Có bao nhiêu cặp tập con không giao nhau của một tập hợp $X$ gồm $n$ phần tử.

-Xét $A,B$ là hai tập con thỏa mãn đề bài.
-Với mỗi phần tử trong tập hợp $X$, có 3 khả năng xảy ra:
+) $x\in A;x\not\in B$
+) $x\in B;x\not\in A$
+) $x\not\in A;x\not\in B$
Vì tập $X$ có $n$ phần tử $\Rightarrow $ có $3^n$ trạng thái $\Rightarrow$ có tổng cộng $3^n$ cặp tập con thỏa mãn đề bài.
-------------------------------------------------------------
Đây là topic thảo luận, không cần xoá đâu em!

Bài viết đã được chỉnh sửa nội dung bởi Trần Đức Anh @@: 14-11-2012 - 22:20

Phấn đấu vì tương lai con em chúng ta!

#3
Trần Đức Anh @@

Trần Đức Anh @@

    Thượng sĩ

  • Thành viên
  • 286 Bài viết
Đáp số là $\frac{3^n+1}{2}$, em coi kiểm tra lại lời giải !
Chữ ký spam! Không cần xoá!

#4
Trần Đức Anh @@

Trần Đức Anh @@

    Thượng sĩ

  • Thành viên
  • 286 Bài viết
Chúng ta tiếp tục với bài toán sau:
Problem 2: Cho tập hợp $X$ gồm $n$ phần tử. Với mỗi cặp tập con $A_{1}$, $A_{2}$ của $X$ ta tính được số phần tử của $A_{1}\cap{A_{2}}$. Chứng minh rằng tất cả các số nhận được bằng $n4^{n-1}$
Chữ ký spam! Không cần xoá!

#5
minhtuyb

minhtuyb

    Giả ngu chuyên nghiệp

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

-Xét $A,B$ là hai tập con thỏa mãn đề bài.
-Với mỗi phần tử trong tập hợp $X$, có 3 khả năng xảy ra:
+) $x\in A;x\not\in B$
+) $x\in B;x\not\in A$
+) $x\not\in A;x\not\in B$
Vì tập $X$ có $n$ phần tử $\Rightarrow $ có $3^n$ trạng thái $\Rightarrow$ có tổng cộng $3^n$ cặp tập con thỏa mãn đề bài.
-------------------------------------------------------------
Đây là topic thảo luận, không cần xoá đâu em!

Em quên đếm số tập bị lặp :P:
----
Bổ sung: Trong $3^n$ cặp tập con đó có một cặp $(\varnothing
;\varnothing)$ và các cặp còn lại, mỗi cặp được đếm 2 lần nên số tập con thỏa mãn là: $\dfrac{3^n-1}{2}+1=\dfrac{3^n+1}{2}$

Bài viết đã được chỉnh sửa nội dung bởi minhtuyb: 14-11-2012 - 23:03

Phấn đấu vì tương lai con em chúng ta!

#6
soros_fighter

soros_fighter

    Hạ sĩ

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

Chúng ta tiếp tục với bài toán sau:
Problem 2: Cho tập hợp $X$ gồm $n$ phần tử. Với mỗi cặp tập con $A_{1}$, $A_{2}$ của $X$ ta tính được số phần tử của $A_{1}\cap{A_{2}}$. Chứng minh rằng tất cả các số nhận được bằng $n4^{n-1}$

Có tất cả $4^n$ cặp tập con $(A,B)$ của X
Ta chia các tập con này thành các bộ $4$: $(A \cap B,\bar{A} \cap B,A \cap \bar{B},\bar{A}\cap \bar{B})$, có $4^{n-1}$ bộ như vậy
Khi đó mỗi phần tử $a\in X$ chỉ thuộc 1 trong trong 4 cặp thuộc 1 bộ mà có n phần tử
$\Rightarrow \sum A\cap B= n.4^{n-1}$

Bài viết đã được chỉnh sửa nội dung bởi soros_fighter: 14-11-2012 - 22:51


#7
minhtuyb

minhtuyb

    Giả ngu chuyên nghiệp

  • Thành viên
  • 470 Bài viết
Problem 3: Có bao nhiêu cách chọn ba tập con $A,B,C$ của $\left\{ 1,2,...,n\right\}$ thỏa $A\subseteq C;B\subseteq C;A\cap B\neq\varnothing$
Phấn đấu vì tương lai con em chúng ta!

#8
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết
Bài 3:
Phương pháp giống bài này:
http://diendantoanho...ia-cac-dội-bơi/
Đáp số: $5^n$.
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#9
Trần Đức Anh @@

Trần Đức Anh @@

    Thượng sĩ

  • Thành viên
  • 286 Bài viết
Problem 4: Let $A$ and $B$ two sets such that $A\cap B=\emptyset$ and $A\cup B=\mathbb{N}$ (such sets are known as partitions). Let $a,b\in \mathbb{N}$ such that $aA=bB$, where $aA=\{ax\mid x\in A\}$. Find the set $U$ of all such ordered pairs $(a,b)$.
Chữ ký spam! Không cần xoá!




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

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