Jump to content
Sign in to follow this  
Adri

Himpunan yang beririsan sama.

Recommended Posts

Untuk suatu bilangan asli $n, d$ dan $k$ dimana $1 \leq k< d \leq n$, misalkan $A_1 , A_2, \cdots, A_n$ adalah himpunan-himpunan yang memenuhi:

 

i)  $|A_i| = d$ untuk setiap $i=1, 2, \cdots, n$.

 

ii) $|A_i \cap A_j| = k $ untuk sebarang $i$ dan $j$, $i\neq j$.

 

iii) $|A_1 \cup A_2 \cup \cdots \cup A_n |= n$

 

Buktikan bahwa jika $n$ genap maka $(d-k)((n-1)k+d)$ bilangan kuadrat, dan jika $n$ ganjil maka $(n-1)k+d$ bilangan kuadrat. 

 

Edit : soal tadi salah, sekarang sudah benar.

Edited by Adri
Salah soal
  • Upvote 1

Share this post


Link to post
Share on other sites
7 hours ago, Adri said:
7 hours ago, Adri said:

Untuk suatu bilangan asli n,d dan k dimana 1k<dn , misalkan A1,A2,,An adalah himpunan-himpunan yang memenuhi:

 

i)  |Ai|=d untuk setiap i=1,2,,n .

 

ii) |AiAj|=k untuk sebarang i dan j , ij .

 

Buktikan bahwa jika n genap maka (dk)((n1)k+d) bilangan kuadrat, dan jika n ganjil maka (n1)k+d bilangan kuadrat. 

 

 

Untuk suatu bilangan asli n,d dan k dimana 1k<dn , misalkan A1,A2,,An adalah himpunan-himpunan yang memenuhi:

 

i)  |Ai|=d untuk setiap i=1,2,,n .

 

ii) |AiAj|=k untuk sebarang i dan j , ij .

 

Buktikan bahwa jika n genap maka (dk)((n1)k+d) bilangan kuadrat, dan jika n ganjil maka (n1)k+d bilangan kuadrat. 

 

 

Boleh tau sumber soalnya darimana???

Share this post


Link to post
Share on other sites
45 minutes ago, sukumbundut said:

Boleh tau sumber soalnya darimana???

 

Soal ini dari modif2 sendiri (generalisasi 'malas' sbnrnya) , cuma ide nya copycat dari  solusi orang lain pada soal :

 

Apakah ada konfigurasi 22 lingkaran dan 22 titik sedemikian sehingga setiap lingkaran memuat paling sedikit 7 titik dan setiap titik termuat di paling sedikit 7 lingkaran?

 

(Moldovan TST 2005)

 

Edited by Adri
  • Upvote 1

Share this post


Link to post
Share on other sites
2 minutes ago, Adri said:

 

Soal ini saya modif sendiri, cuma ide nya copycat dari soal (dan solusi) orang lain pada soal :

 

Apakah ada konfigurasi 22 lingkaran dan 22 titik sedemikian sehingga setiap lingkaran memuat paling sedikit 7 titik dan setiap titik termuat di paling sedikit 7 lingkaran?

 

(Moldovan TST 2005)

 

Thanks, kalo untuk ide soalnya. dari soal kompetisi apa? :)

Share this post


Link to post
Share on other sites
15 hours ago, sukumbundut said:

Thanks, kalo untuk ide soalnya. dari soal kompetisi apa? :)

 

Itu diatas saya udah kasi tau, soal dari Seleksi IMO Tim Moldovan tahun 2005. Soalnya yang 22 lingkaran itu. 

Share this post


Link to post
Share on other sites

Saya lupa kasi syarat iii) , padahal asumsi itu saya pakai dari awal :headbang:

 

Biar ga double post (saving face sebenarnya :rofl:) saya post solusi saja (buat memperbanyak trick) :

 

Spoiler

Lemma : 

Misalkan $A$ adalah matriks $n \times n$, yang semua entri di diagonal utama nya adalah $d$ dan semua entri yang lain adalah $k$. Maka berlaku $\text{A}= (d-k)^{n-1} ((n-1)k+d)$

 

Bukti : 

Sebenarnya bisa pakai expansi cofactor, cuma ribet ngetik matriks disini. Jadi buat yang udah belajar aljabar linear bisa begini:

 

 Vektor $(1, -1, 0, 0, \cdots, 0)$,  $(0, 1, -1, 0, \cdots, 0)$,  $(0, 0, 1, -1, \cdots, 0)$, ....,  $(0, 0, 0, 0, \cdots,1, -1)$, adalah $n-1$ buah vektor yang linearly independent dan merupakan eigenvector dari $A$ dengan eigen value $\lambda=d-k$. Ini berarti eigenspace $K(\lambda)$ mempunyai dimensi minimal $n-1$ (yaitu multiplisitas geometry). Sehingga multiplisitas aljabar dari $\lambda$ haruslah minimal $n-1$. Sedangkan $\lambda_2 = ((n-1)k+d)$ juga merupakan eigenvalue dari $A$ dengan eigenvektor $(1,1,\cdots, 1)$. Sehingga eigenvalue dari $A$ adalah :  $d-k$ (sebanyak $n-1$ kali) dan $((n-1)k+d)$ sebanyak sekali, jadi determinant $A$ adalah perkalian dari eigenvalue ini, yakni $(d-k)^{n-1} ((n-1)k+d)$

 

Misalkan anggota-anggota pada gabungan semua $A_i$ adalah $x_1, x_2 , \cdots, x_n$.

 

Sekarang misalkan $\textbf{a}_i$ adalah vektor yang komponen ke-$j$ nya sama dengan $1$ apabila $x_j$ merupakan anggota $A_i$. Ini berarti berdasarkan syarat i), vektor $\textbf{a}_i$ hanya memuat $d$ buah angka 1. 

 

Berdasarkan syarat ii) perkalian dot product $\textbf{a}_i \cdot \textbf{a}_j = k$  untuk setiap $i\neq j$.

 

Misalkan $B$ adalah matriks yang baris ke-$i$ nya adalah vektor $\textbf{a}_i$, maka berlaku $B B^T = A$ dimana $A$ adalah matriks pada lemma, namun ini berarti

 

\[ (d-k)^{n-1} ((n-1)k+d)= \text{det}(A)= \text{det}(B B^T)=  \text{det}(B)  \text{det}(B^T)=  \text{det}(B)^2\]

 

Sehingga $(d-k)^{n-1} ((n-1)k+d)$ haruslah bilangan kuadrat, dan kesimpulan mengikuti.

 

  • 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  

×