Jump to content
Sign in to follow this  
donjar

Himpunan $A+A$ dengan $A \subset \{0, \dotsc, 2n - 1\}$

Recommended Posts

Diberikan $n$ bilangan bulat positif. Diberikan bilangan-bilangan bulat $0 = a_0 < a_1 < \dotsb < a_n = 2n - 1$. Cari kardinalitas minimum himpunan $\{ a_i + a_j \, | \, 0 \le i \le j \le n \}$.

 

Sumber:

China TST Quiz 1 Day 2 no. 3

Share this post


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

Cauchy Davenport? 

 

Hmmm kayaknya bisa ya? Pakai generalisasinya yang di $\mathbb{Z}_n$ wkwk

Share this post


Link to post
Share on other sites

Tak tau sih.. kan bilangan prima.. tapi klo kita ambil prima $p$ yang terkecil sedemikian sehingga $p> 4n-2$ .. ntar dapetnya $|A+A| \geq 2n-1 $, ga cukup bagus sih, krn syarat distinct nya ga kepake...  

Spoiler

kuli2 sepertinya jawabnya 3n :p

 

Share this post


Link to post
Share on other sites
On 3/27/2016 at 4:49 PM, Adri said:

Cauchy Davenport? 

 

On 3/27/2016 at 8:56 PM, donjar said:

 

Hmmm kayaknya bisa ya? Pakai generalisasinya yang di Zn wkwk

 

Duh kalian ngomongin apasih? nggak ngerti kk... Yang saya tau cuma Cauchy temennya Schwarz

Share this post


Link to post
Share on other sites
Spoiler

Misalkan $G=\{a_i| 0\le i\le n\}$ dan $H=\{a_i + a_j | 0\le i\le j\le n\}$, ingin dicari nilai minimum dari $|H|$.

 

Akan dibuktikan bahwa nilai minimum dari $|H|$ adalah $3n$.\vspace{3mm}

 

Lemma 1:

 

Untuk setiap $0\le t\le 2n-1$, setidaknya satu dari $t$ atau $t+2n-1$ merupakan anggota dari $H$.

 

Bukti:

 

Misalkan $t$ bukan anggota dari $H$, akan ditunjukkan kalau maksimal $\lfloor \frac{t+1}{2}\rfloor$ dari bilangan di interval $(0,t)$ yang merupakan anggota dari $G$.

 

Perhatikan kalau diantara $k$ dan $t-k$ hanya maksimal $1$ yang merupakan anggota $G$ (untuk $0\le k \le t$), karena jika keduanya anggota $G$ maka $t$ adalah anggota $H$. Perhatikan kalau ada $t+1$ bilangan yang ada di $[0,t]$.

 

Jika $t$ genap, misalkan sama dengan $2m$, maka bisa dipasangin $k$ dengan $2m-k$ untuk semua $0\le k<m$, lalu jelas $m$ bukan anggota $G$, karena $m\in G\Rightarrow 2m=t\in H$, ada $m$ pasangan dan dari setiap pasangan cuma maksimal satu yang merupakan anggota $G$, maka banyaknya bilangan di interval $[0,t]$ di $G$ maksimal $m$, yakni $\lfloor \frac{t+1}{2}\rfloor$.

 

Jika $t$ ganjil, misalkan sama dengan $2m+1$, maka bisa dipasangin $k$ dengan $2m+1-k$ untuk semua $0\le k\le m$, ada $m+1$ pasangan, dan diantara pasangan maksimal 1 yang anggota $G$, maka banyak bilangan di interval $[0,t]$ yang ada di $G$ maksimal $m+1$, yakni $\lfloor\frac{t+1}{2}\rfloor$.

 

Terbukti maksimal $\lfloor \frac{t+1}{2}\rfloor$dari bilangan di interval $[0,t]$ yang merupakan anggota dari $G$. \vspace{3mm}

 

Misalkan $t+2n-1$ bukan anggota $H$, akan dibuktikan banyaknya bilangan di interval $[t,2n-1]$ yang ada di $G$ maksimal $\lfloor\frac{2n-t}{2}\rfloor$.

 

Perhatikan kalau diantara $k$ dan $2n-1+t-k$ hanya maksimal $1$ yang merupakan anggota $G$ (untuk $t\le k \le 2n-1$), karena jika keduanya anggota $G$ maka $t+2n-1$ adalah anggota $H$. Perhatikan kalau ada $2n-t$ bilangan yang ada di $[t,2n-1]$.

 

Jika $t$ genap, misalkan sama dengan $2m$, perhatikan kalau bisa dipasangin $2m+k$ dengan $2n-1-k$, untuk setiap $0\le k\le n-m-1$, dari setiap pasangan maksimal 1 yang anggota $G$, ada $n-m$ pasangan, maka banyak anggota interval $[t,2n-1]$ di $G$ adalah $n-m$ sama dengan $\lfloor\frac{2n-t}{2}\rfloor$.

 

jika $t$ ganjil, misalkan sama dengan $2m+1$, maka bisa dipasangin $2m+1+k$ dengan $2n-1-k$ untuk setiap $0\le k<n-m-1$, dan jelas $m+n$ bukan anggota dari $G$, karena $m+n\in G\Rightarrow 2(m+n)=2n-1+t\in H$. Ada $n-m-1$ pasangan, dan dari pasangan maksimal datu yang merupakan anggota dari $G$, maka banyak anggota $G$ yang berada di interval $[t,2n-1]$ maksimal $n-m-1$, sama dengan $\lfloor\frac{2n-t}{2}\rfloor$.

 

Terbukti maksimal $\lfloor\frac{2n-t}{2}\rfloor$ bilangan di interval $[t,2n-1]$ merupakan anggota dari $G$.

 

 

Berarti, jika $t$ dan $t+2n-1$ bukan anggota dari $H$, maksimal $\lfloor \frac{t+1}{2}\rfloor$dari bilangan di interval $[0,t]$ yang merupakan anggota dari $G$ dan maksimal $\lfloor\frac{2n-t}{2}\rfloor$ bilangan di interval $[t,2n-1]$ merupakan anggota dari $G$.

 

Maka, $2n+1<|G|\le \lfloor \frac{t+1}{2}\rfloor + \lfloor\frac{2n-t}{2}\rfloor\le \lfloor\frac{2n+1}{2}\rfloor<n+1$, kontradiksi.

 

Maka setidaknya satu dari $t$ atau $t+2n-1$ merupakan anggota dari $H$, lemma terbukti.

 

Perhatikan kalau $0,2n-1,4n-2$ merupakan anggota $H$, 3 anggota $H$ ya (kelompok 1)

 

Lalu, $a_i$ dan $a_i+2n-1$ merupakan anggota $H$ juga, ini $2n-2$ anggota $H$ ya (kelompok 2)

 

Lalu, untuk setiap $i$ di interval $[0,2n-1]$ yang bukan merupakan anggota dari $G$, menurut lemma 1 setidaknya satu dari $i$ atau $i+2n-1$ merupakan anggota $H$, ini minimal $n-1$ anggota $H$ ya. (kelompok 3)

 

obvious kelompok 1,2,3 saling ga potong, dan di dalam kelompok beda semua angkanya

 

Berarti $|H|$ minimal $3+2n-2+n-1=3n$. Terbukti $3n\le|H|$.

 

Perhatikan kalau dipilih $a_i=i$ untuk setiap $i\neq n$ dan $i\neq 0$, maka elemen $H$ adalah semua bilangan di $[0,3n-2]$ dan $4n-2$, maka $|H|=3n$

 

Maka kardinalitas minimum dari himpunan tersebut adalah $3n$.

 

  • Upvote 1

Share this post


Link to post
Share on other sites
1 hour ago, Prihandoko said:

 

 

Duh kalian ngomongin apasih? nggak ngerti kk... Yang saya tau cuma Cauchy temennya Schwarz

 

 

Cauchy - Davenport  ... tapi ga bisa dipake sih, cm mungkin ide nya sama (karena equality case untuk $3n$ terjadi ketika semua arithmetic progression, just like in case of Davenport ), dibuktikan bahwa $A+A$ residu hampir lengkap (or lengkap) males ngedetail yang ujung2nya :p .

 

edit: ooh udah ada solusi dari sayakalah:D

 

 

 

Edited by sayakalah

Share this post


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

 

 

Cauchy - Davenport  ... tapi ga bisa dipake sih, cm mungkin ide nya sama (karena equality case untuk $3n$ terjadi ketika semua arithmetic progression, just like in case of Davenport ), dibuktikan bahwa $A+A$ residu hampir lengkap (or lengkap) males ngedetail yang ujung2nya :p .

 

edit: ooh udah ada solusi dari sayakalah:D

 

 

 

Anda $0,1,...,n-2,2n-1$ juga kesamaan kalau gasalah

Share this post


Link to post
Share on other sites
2 hours ago, sayakalah said:

Anda ,1,...,n2,2n10,1,...,n−2,2n−1 juga kesamaan kalau gasalah

 

0 dan 2n-1 nya saya buang dulu sih, krn itu zero element di $Z_{2n-1}$  makanya saya jd males ngedetailin ujung2nya (si nol dan 2n-1 itu) :D

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  

×