Jump to content
Sign in to follow this  
Adri

Membuang anggota di subset

Recommended Posts

Misalkan $M$ adalah himpunan dengan $n$ anggota. Tentukan bilangan $k$ terbesar sedemikian sehingga, untuk tiap-tiap $k$-subhimpunan dari $M$ dapat dibuang satu anggota sedemikian  sehingga dari hasil pembuangan tersebut, setiap $(k-1)$-subhimpunan muncul minimal sekali.

Share this post


Link to post
Share on other sites
Spoiler

$k = \lceil \frac{n}{2} \rceil \cdots?$

Jika $k$ lebih besar dari itu, maka jumlah $k$-subhimpunan $M$ lebih sedikit dari pada $k-1$-subhimpunan $M$. Alhasil menurut PHP, soal tidak terpenuhi.

Untuk $k = \lceil \frac{n}{2} \rceil$, untuk setiap $z$ suatu $k-1$-subhimpunan dari $M$, misalkan $A_{z}$ himpunan dari semua $k$-subhimpunan $M$ yang memuat $z$ sebagai subsetnya.
Dapat dilihat bahwa $A_{z}$ selalu memuat $C^{n-(k-1)}_1=(n-k+1)$ elemen; dan setiap $k$-subhimpunan $M$ muncul tepat $C^k_1 = k$ kali pada $k$ buah $A_{z}$ yang berbeda.

Untuk setiap $z_1, z_2, \cdots, z_b$ sebanyak $b$ buah $k-1$-subhimpunan $M$ berbeda, pandang himpunan $C = \Cup{A_{z_i}}$. Setiap anggota $C$ dapat muncul pada maksimal $k$ buah $A_z$, padahal ada total $(n-k+1).b$ elemen $A_z$ yang "sedang digabungkan". Jadi $|A_{z_1} \cup A_{z_2} \cup \cdots \cup A_{z_b}| \ge \frac{(n-k+1).b}{k} \ge b$.
Kita punya Hall Theorem: dapat "dipilihkan" suatu $k$-subhimpunan yang berbeda untuk setiap $k-1$-subhimpunan. Singkat cerita, terbukti. CMIIW

 

  • Upvote 1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

×