Jump to content
Sign in to follow this  
-_-

Simulasi OSN TOSKA 2016 Nomor 2 - Pasangan yang saling mengenal sebanyak tiga berpangkat

Recommended Posts

Sebuah kelompok dengan $n$ orang memenuhi syarat sebagai berikut: Jika diambil sebarang $n-2$ orang dari kelompok itu, banyak pasangan orang yang saling mengenal di subkelompok baru ini adalah sebanyak konstan, dan konstan tersebut berbentuk $3^k$, untuk sebuah $k$ nonnegatif. Tentukan semua $n$ yang mungkin.

Share this post


Link to post
Share on other sites

Pertama-tama kita nyatakan orang-orang tersebut sebagai verteks (titik) dari suatu graph dimana dua verteks terhubung jika dan hanya jika dua orang yang merepresentasikan verteks tersebut saling mengenal.

 

Untuk $n=4$,  graph  empat titik yang setiap dua titik dihubungkan dua garis memenuhi soal dengan $k=0$.

 

Untuk $n = 3$, apabila diambil dua verteks, maka hanya tersisa satu verteks jadi banyaknya garis adalah nol, tidak berbentuk $3^k$.

 

Untuk $n=1$ atau $n=2$, jelas tidak memenuhi.

 

Sekarang misalkan $n\geq 5$.

 

Kita akan membuktikan:

 

Sebuah graph $G$ dengan $n \geq 5$ verteks yang memenuhi syarat: Untuk setiap dua verteks $x$ dan $y$ dari graph $G$, apabila $x$ dan $y$ beserta semua garis-garis yang terhubung ke $x$ atau $y$ dihapus,   maka sisa $n-2$ verteks akan mempunyai banyak garis sebuah konstan $K>0$. 

Maka $G$ adalah graph lengkap $K_n$

 

(Graph Lengkap $K_n$ adalah sebuah graph yang mempunyai $n$ titik dan setiap dua titik berbeda pada graph tersebut selalu terhubung dengan tepat satu garis, jadi mempunyai tepat  ${n \choose 2} = \frac{n(n-1)}{2}$ garis.)

 

 

Bukti :

 

Misalkan $G$ bukan graph lengkap.

Misalkan $e$ menyatakan banyak garis awal di $G$ dan $d_v$ dan $d_w$ berturut-turut menyatakan banyak garis yang terhubung ke $v$ dan $w$, kita sebut $d_v$ ini sebagai degree dari verteks $v$, jadi $d_w$ adalah degree dari verteks $w$. 

 

Misalkan $v$ adalah verteks dengan degree minimal. Maka terdapat dua verteks $v$ dan $w$ yang tidak saling terhubung,  Apabila dua verteks ini kita buang, maka  garis yang tersisa  adalah $e-d_v - d_w$.

 

Apabila ada verteks lain yang tidak terhubung dengan $v$ misalkanlah $w_1$ maka jika mereka kita buang diperoleh garis yang tersisa adalah $e-d_v-d_{w_1}$. Dan karena syaratnya banyak edge tersisa ini konstant maka

 

\[K=e-d_v-d_w = e-d_v-d_{w_1} \Rightarrow d_w = d_{w_{1}}\] 

 

Ini berarti setiap verteks yang tidak terhubung dengan $v$ mempunyai degree yang sama, katakanlah degree nya $a$. Jadi $K=e-2a$.

 

Sekarang misalkan $u$ adalah verteks yang terhubung dengan $v$, apabila dua verteks ini kita buang, maka garis yang tersisa adalah $e-d_v-d_u+1$ (karena garis yang menghubungkan $v$ dan $u$ terhitung dua kali ). Dengan penalaran yang sama, semua verteks yang terhubung dengan $v$ akan mempunyai degree yang sama dengan $d_u$, katakanlah degree nya $b$.  

 

Perhatikan bahwa karena sisa garis ini konstant maka

 

\[K=e-d_v-d_w = e-d_v-d_{u}+1 \Rightarrow d_w=d_u-1 \Rightarrow  b=a+1\]

 

Misalkan $W$ adalah himpunan semua verteks yang tidak terhubung dengan $v$ dan $U$ adalah himpunan semua verteks yang terhubung dengan $V$.  Ini berarti semua verteks dari $G$ hanya punya tepat satu dari tiga status berikut yakni:  dia adalah $v$ itu sendiri, anggota $W$ atau anggota $V$. 

 

Jika $|W|=1$, ini berarti hanya ada satu verteks yang tidak terhubung dengan $v$ katakanlah $x$, dan semua verteks lain terhubung dengan $v$, sehingga $d_v=n-2$. Karena $d_v$ minimal maka semua verteks yang lain mempunyai degree $\geq n-2$. Dengan kata lain $w\in W$ juga memenuhi $d_w \geq n-2$, tapi $w$ dan $v$ tidak terhubung, jadi $d_w=n-2$, sehingga $d_w=a=n-2$. Ini berarti semua verteks lain yang terhubung dengan $v$ mempunyai degree $b=a+1 = n-1$. Ini berarti jika $v$ dan $w$ dibuang maka sisa garis adalah $e-2(n-2)$, sedangkan jika $u_1, u_2 \in U$ dibuang (karena mereka terhubung) sisa garis adalah $e-2(n-1)+1$, kontradiksi

 

Jika $|U|=1$, ini berarti hanya ada satu verteks yang terhubung dengan $v$ katakanlah $x$, dan semua verteks lain tidak terhubung dengan $v$, ambil dua verteks yang tidak terhubung dengan $v$, katakanlah $s$ dan $t$ maka $d_s=d_t = b=a+1$,  jika mereka tidak terhubung, maka apabila $s$ dan $t$ dibuang akan diperoleh sisa garis $K=e-2(a+1)$, tapi kita juga tahu bahwa $K=e-2a$ kontradiksi. Sekarang jika $s$ dan $t$ terhubung, maka apabila mereka dibuang diperoleh $K=e-2a-1$ yang juga tidak sama dengan $K=e-2a$, kontradiksi.

 

Jadi $|W| \geq 2$ dan $|V| \geq 2$. 

 

Ambil dua verteks di $x,y \in W$ dan $s, t \in V$, diperoleh kasus:

 

i) Jika $x$ dan $y$ terhubung, dan $s$ dan $t$ juga terhubung, diperoleh $K=e-2a+1$ dan $K=e-2a-1$, kontradiksi. 

ii) Jika $x$ dan $y$ terhubung, dan $s$ dan $t$ tidak terhubung, diperoleh $K=e-2a+1$ dan $K=e-2a-2$, kontradiksi.

iii) Jika $x$ dan $y$ tidak terhubung, dan $s$ dan $t$ terhubung, diperoleh $K=e-2a$ dan $K=e-2a-1$, kontradiksi.

iv) Jika $x$ dan $y$ tidak terhubung, dan $s$ dan $t$ tidak terhubung, diperoleh $K=e-2a$ dan $K=e-2a-2$, kontradiksi.

 

Karena semua kemungkinan menghasilkan kontradiksi, maka haruslah $G$ graph lengkap. Terbukti.

 

Ini berarti untuk $n \geq 5$, graph yang diperoleh harus graph lengkap, dan ketika dua verteks dihilangkan maka sisa garis adalah

 

\[K=\frac{n(n-1)}{2} - (2n-2) + 1 = \frac{(n-3)(n-2)}{2} = 3^k\]

 

Karena $n-3$ dan $n-2$ relatif prima kemungkinan hanya $n-3=1$, $n-3=2$, $n-2=1$, $n-2=2$ , yang memenuhi $n \geq 5$  hanya $n=5$.  Ini berarti $k=1$.

 

Dapat dilihat bahwa graph $K_5$ memang memenuhi syarat soal, karena apabila dua verteks dibuang akan tersisa $3$ garis. 
 

Jadi jawabannya adalah $n=4$ dan $n=5$. 

Edited by Adri

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  

×