Jump to content
Sign in to follow this  
donjar

Wakil dari himpunan

Recommended Posts

Misalkan $S={1, 2, \ldots, 2014}$. Untuk setiap himpunan tak kosong $T \subseteq S$, pilih salah satu anggotanya menjadi wakil. Cari banyaknya cara memilih wakil ke semua himpunan tak kosong dari $S$ sehingga bila ada himpunan tak kosong $A, B, C, D \subseteq S$ dan $D$ adalah disjoint union dari $A, B, C$, maka wakil dari $D$ merupakan wakil dari setidaknya satu dari $A, B, C$.


 


Asian Pacific Mathematics Olympiad 2014, no. 2


 


p.s. "D disjoint union A, B, dan C" artinya $A \cup B \cup C = D$ dan $A \cap B = \emptyset, B \cap C = \emptyset, C \cap A = \emptyset$.


Edited by donjar
koreksi dari Overflow

Share this post


Link to post
Share on other sites


akan dibuktiin yang lebih general, yaitu jika $S=1,2,..,n$, banyaknya cara memilih wakil itu $n!$.


akan dibuktikan dengan induksi.


jelas kalau $S=1$ benar.


kalau untuk $S=1$,$S=1,2$,...,$S=1,2,3,...,k$ benar, observasi $S=1,2,...,k+1$.


kita definisikan $W(m)$ sebagai wakil dari subset $m$.


jika $W(S)=h$ dimana $1\le n \le k+1$,


maka jelas setiap untuk setiap set $q$ dimana $h\in q \subseteq S$, $W(q)=h$.


otherwise, bisa dipilih set $A,B$ sehingga $A\cup B= S\setminus q$,$A\cap B= \emptyset$, lalu dipilih $A,B,q$ dan syarat tidak terpenuhi.


Jelas banyaknya cara memilih $W(S)$ adalah $k+1$.


sekarang kita sudah tidak perlu mempedulikan semua set $q$ dimana $h\in q \subseteq S$, $W(q)=h$, cara memilih wakil mereka sudah dihitung.


berarti kita tersisa dengan mengobservasi wakil dari semua set tak kosong $m$ dimana $m\subseteq S\setminus h$, perhatikan kalau ini identikal dengan mencari banyaknya wakil dari semua set $m$ dimana $m\subseteq Y$ dimana $Y=1,2,...,k$, berarti banyaknya cara memilih adalah $k!$.


berarti, banyaknya cara memilih wakil dari semua set tak kosong yang anggota $S$ dimana $S=1,2,...,k+1$ itu adalah $k!(k+1)=(k+1)!$ induksi selesai.


maka banyaknya cara memilih wakil ke semua himpunan tak kosong dimana $S=1,2,...,2014$ adalah $2014!$



CMIIW


edit: hmm ternyata salah:p saya coba lagi ya


Edited by sayakalah

Share this post


Link to post
Share on other sites

jika $W(S)=h$ dimana $1\le n \le k+1$,

maka jelas setiap untuk setiap set $q$ dimana $h\in q \subseteq S$, $W(q)=h$.

otherwise, bisa dipilih set $A,B$ sehingga $A\cup B= S\setminus q$,$A\cap B= \emptyset$, lalu dipilih $A,B,q$ dan syarat tidak terpenuhi.

Bagaimana kalau $S\setminusq = {28}$ ? Salah satu dari $A$ dan $B$ yang ingin Anda ambil harus merupakan himpunan kosong yang tidak diperbolehkan...

Edit : kak @donjar, kak @sayakalah, sepertinya ada kurang di soalnya, baru sadar .__. Itu harusnya "himpunan tak kosong A,B,C"

Edited by Overflow
  • Upvote 1

Share this post


Link to post
Share on other sites

akan dibuktiin yang lebih general, yaitu jika $S=1,2,..,n$, banyaknya cara memilih wakil itu $n!$.

akan dibuktikan dengan induksi.

jelas kalau $S=1$ benar.

kalau untuk $S=1$,$S=1,2$,...,$S=1,2,3,...,k$ benar, observasi $S=1,2,...,k+1$.

kita definisikan $W(m)$ sebagai wakil dari subset $m$.

jika $W(S)=h$ dimana $1\le n \le k+1$,

maka jelas setiap untuk setiap set $q$ dimana $h\in q \subseteq S$, $W(q)=h$.

otherwise, bisa dipilih set $A,B$ sehingga $A\cup B= S\setminus q$,$A\cap B= \emptyset$, lalu dipilih $A,B,q$ dan syarat tidak terpenuhi.

Jelas banyaknya cara memilih $W(S)$ adalah $k+1$.

sekarang kita sudah tidak perlu mempedulikan semua set $q$ dimana $h\in q \subseteq S$, $W(q)=h$, cara memilih wakil mereka sudah dihitung.

berarti kita tersisa dengan mengobservasi wakil dari semua set tak kosong $m$ dimana $m\subseteq S\setminus h$, perhatikan kalau ini identikal dengan mencari banyaknya wakil dari semua set $m$ dimana $m\subseteq Y$ dimana $Y=1,2,...,k$, berarti banyaknya cara memilih adalah $k!$.

berarti, banyaknya cara memilih wakil dari semua set tak kosong yang anggota $S$ dimana $S=1,2,...,k+1$ itu adalah $k!(k+1)=(k+1)!$ induksi selesai.

maka banyaknya cara memilih wakil ke semua himpunan tak kosong dimana $S=1,2,...,2014$ adalah $2014!$

CMIIW

 

anda terjebak :) jawabannya salah hahaha

untuk $n=4$, apakah benar ada 24 cara?

Edited by donjar

Share this post


Link to post
Share on other sites

hmm baiklah pantesan rasanya trivial sekali hahah. kalau boleh tahu salah dimananya ya?


Share this post


Link to post
Share on other sites

ini perbaikannya,tolong dicek kakak saya masih tidak yakin



misalkan $f(n)$ adalah banyaknya cara memilih subset" tersebut jika $S=1,2,...,n$.


bisa di cek kalau $f(4)=108\times 4!$  (gay sekali)


akan dibuktikan kalau $f(n)=nf(n-1)$ untuk $n\ge 5$


 


 


kita konsider kasus $n\ge 5$


kita definisikan $W(m)$ sebagai wakil dari subset $m$.


jika $W(S)=h$ dimana $1\le h \le n$,


 


akan dibuktikan untuk setiap set $q$ dimana $h\in q \subset S$, $W(q)=h$.


 


perhatikan kalau $0<|q|\le n-2$, statementnya pasti benar karena bisa dipilih $A,B$ himpunan tak kosong sehingga $A\cup B= S\setminus q$,$A\cap B= \emptyset$ karena $2\le |S\setminus q|$


 


sekarang consider set $q$ dimana $|q|=n-1$.


pilih 4 set berbeda $A,B,C,D\in S$, $|A|=|B|=|C|=|D|=1$, $A=\{a\},B=\{b\},C=\{c\},D=\{d\}$(memilih ini mungkin karena $n-1\ge 4$).


 $A\cup B\cup \{q\setminus \{A\cup B\}\}=C\cup D\cup \{q\setminus \{C\cup D\}\}=q$, 


maka $W(q)=(W(A)\cup W(B) \cup W(q\setminus A\cup B)\cap((W( C )\cup W(D) \cup W(q\setminus C\cup D)=(a\cup b\cup h)\cap(c\cup d\cup h)=h$.Terbukti.

 


sekarang kita sudah tidak perlu mempedulikan semua set $q$ dimana $h\in q \subseteq S$, $W(q)=h$, cara memilih wakil mereka sudah dihitung.


berarti kita tersisa dengan mengobservasi wakil dari semua set tak kosong $m$ dimana $m\subseteq S\setminus h$, perhatikan kalau ini identikal dengan mencari banyaknya wakil dari semua set $m$ dimana $m\subseteq Y$ dimana $Y=1,2,...,n-1$, berarti terbukti kalau $f(n)=nf(n-1)$ untuk $n\ge 5$.


berarti $f(2014)=2014f(2013)=2014\times 2013f(2012)=....=2014\times 2013 \times 2012\times ... \times 6\times 5 f(4)=108\times2014!$


 



statement terakhir donjar sangat membantu hahah terima kasih


btw sial sekali ya soal seperti ini, kalau saya jawab pakai jawaban pertama saya paling max 3 point-____-


Edited by sayakalah

Share this post


Link to post
Share on other sites

ini perbaikannya,tolong dicek kakak saya masih tidak yakin

misalkan $f(n)$ adalah banyaknya cara memilih subset" tersebut jika $S=1,2,...,n$.

bisa di cek kalau $f(4)=108\times 4!$  (gay sekali)

akan dibuktikan kalau $f(n)=nf(n-1)$ untuk $n\ge 5$

 

 

kita konsider kasus $n\ge 5$

kita definisikan $W(m)$ sebagai wakil dari subset $m$.

jika $W(S)=h$ dimana $1\le h \le n$,

 

akan dibuktikan untuk setiap set $q$ dimana $h\in q \subset S$, $W(q)=h$.

 

perhatikan kalau $0<|q|\le n-2$, statementnya pasti benar karena bisa dipilih $A,B$ himpunan tak kosong sehingga $A\cup B= S\setminus q$,$A\cap B= \emptyset$ karena $2\le |S\setminus q|$

 

sekarang consider set $q$ dimana $|q|=n-1$.

pilih 4 set berbeda $A,B,C,D\in S$, $|A|=|B|=|C|=|D|=1$, $A=\{a\},B=\{b\},C=\{c\},D=\{d\}$(memilih ini mungkin karena $n-1\ge 4$).

 $A\cup B\cup \{q\setminus \{A\cup B\}\}=C\cup D\cup \{q\setminus \{C\cup D\}\}=q$, 

maka $W(q)=(W(A)\cup W(B) \cup W(q\setminus A\cup B)\cap((W( C )\cup W(D) \cup W(q\setminus C\cup D)=(a\cup b\cup h)\cap(c\cup d\cup h)=h$.Terbukti.

 

sekarang kita sudah tidak perlu mempedulikan semua set $q$ dimana $h\in q \subseteq S$, $W(q)=h$, cara memilih wakil mereka sudah dihitung.

berarti kita tersisa dengan mengobservasi wakil dari semua set tak kosong $m$ dimana $m\subseteq S\setminus h$, perhatikan kalau ini identikal dengan mencari banyaknya wakil dari semua set $m$ dimana $m\subseteq Y$ dimana $Y=1,2,...,n-1$, berarti terbukti kalau $f(n)=nf(n-1)$ untuk $n\ge 5$.

berarti $f(2014)=2014f(2013)=2014\times 2013f(2012)=....=2014\times 2013 \times 2012\times ... \times 6\times 5 f(4)=108\times2014!$

 

statement terakhir donjar sangat membantu hahah terima kasih

btw sial sekali ya soal seperti ini, kalau saya jawab pakai jawaban pertama saya paling max 3 point-____-

 

nah yang ini baru bener. banyak yang menjawab seperti solusi pertama anda tadi :P

 

cara gw jg mirip ama cara lu yang ini, tapi untungnya gw coba dari kasus kecil jadi ketahuan hahaha

Edited by donjar

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  

×