KTO Matematika

(Re) Simulasi OSP KTO Matematika Maret 2016 - Bagian A

Recommended Posts

Spoiler

 

Spoiler

 

Ini menurut ane :3

 

1. 52

2. 504

3. (Ini soal kombin yang cukup gampang... namun saya lemah kombin, jadi jangan tanya kenapa kosong !!)

4. 183

5. 120

6. 18

7. 108

8. 7 (soal terakhir yang terjawab :D aku kira kombin, ternyata bukan... hehe )

9. 15

10. 250

11. -14

12. (Kombin lagi... jangan ketawa !!)

13. -1

14. 12

15. (Apakah ini satu-satunya soal teori bilangan yang sulit dipahami .-. )

16. (Oh kombin... kenapa kau membunuhku secara perlahan !!)

17.

18. (Yang pasti jawaban 17~18 yang aku input itu SALAH... -_- )

19. karena hanya 2^32 dan 5 yang dapat membagi C(20^16, 2k-1), Banyak faktor : 66

20. 17

 

*CMIIW

 

Untuk melihat caranya, silakan cek FB saya : https://www.facebook.com/terza.reyhan (promosi...)

 

Atau silahkan hubungi kami di nomor berikut ini :

(021) 8407xxx :P

 

 

Share this post


Link to post
Share on other sites
14 hours ago, Muh. Fadlan said:

Bukannya no 12 itu 575+1296=1871575+1296=1871 emang gimana caranya dapat 395+1296

banyak kemungkinan a+b > c+d sama banyak kan dengan a+b < c+d ??

 

Jadi tinggal cari banyak kemungkinan a+b = c+d, baru ruang sampel dikurangin setelah itu bagi 2 ..

 

Setelah dihitung kembali jawabannya 1871 yang benar

 

Edited by Calvin Liusnando

Share this post


Link to post
Share on other sites
11 hours ago, Terza Reyhan said:
  Hide contents

 

  Reveal hidden contents

 

Ini menurut ane :3

 

1. 52

2. 504

3. (Ini soal kombin yang cukup gampang... namun saya lemah kombin, jadi jangan tanya kenapa kosong !!)

4. 183

5. 120

6. 18

7. 108

8. 7 (soal terakhir yang terjawab :D aku kira kombin, ternyata bukan... hehe )

9. 15

10. 250

11. -14

12. (Kombin lagi... jangan ketawa !!)

13. -1

14. 12

15. (Apakah ini satu-satunya soal teori bilangan yang sulit dipahami .-. )

16. (Oh kombin... kenapa kau membunuhku secara perlahan !!)

17.

18. (Yang pasti jawaban 17~18 yang aku input itu SALAH... -_- )

19. karena hanya 2^32 dan 5 yang dapat membagi C(20^16, 2k-1), Banyak faktor : 66

20. 17

 

*CMIIW

 

Untuk melihat caranya, silakan cek FB saya : https://www.facebook.com/terza.reyhan (promosi...)

 

Atau silahkan hubungi kami di nomor berikut ini :

(021) 8407xxx :P

 

 

yang 19 saa dapat yang faktor limanya habis jadi banyak faktornya 33

19 hours ago, Jonathan CN said:

Pertama, dapatkan bahwa AD garis tinggi, setelah itu kesebangunan, jadi saya dptnya 250

sama

Share this post


Link to post
Share on other sites
12 minutes ago, Rahmat Esar Salsabil said:

yang dapat nomor 4 tolong apa jawabannya,jawabanku 768 saya tidak dapat menjamin jawabannya kalalu konbinatorik

Kalau saya seperti ini, cara menyusun 4 pasangan itu pada 8 kursi saja adalah 3! (Permutasi siklis). Dan selanjutnya diantara 4 pasangan itu, di sisipkan 2 kursi kosong, caranya 5C2. Terakhir entah pasangan itu duduknya bisa ditukar atau tidak. Mungkin saya salahnya karena pasangannya tidak ditukar tempat duduknya.

Share this post


Link to post
Share on other sites
Just now, Jonathan CN said:

Kalau saya seperti ini, cara menyusun 4 pasangan itu pada 8 kursi saja adalah 3! (Permutasi siklis). Dan selanjutnya diantara 4 pasangan itu, di sisipkan 2 kursi kosong, caranya 5C2. Terakhir entah pasangan itu duduknya bisa ditukar atau tidak. Mungkin saya salahnya karena pasangannya tidak ditukar tempat duduknya.

kalo saya mulai dari penentuan susunan 4 laki2 ,jadi banyak susunannya (4-1)!=6 terus setiap laki2 ada pasangannya jadi letak wanita masing2 ada 2 tempat banyak susunan wanita itu 2^4=16 terus susunan 2 kursi yang kosong ada 4 tempat yang dapat disisipkan antar pasangan jadi banyak susunan ada 4.4/2=8 jadi banyak susunan 6.16.8=768

Share this post


Link to post
Share on other sites

Ada yang request no 15, no 16, dan no 19

 

Beikut cara membuktikan untuk soal no  15:

 

Spoiler

15. Jawab: 23.  Ini karena $23 = \lfloor 23/4 \rfloor + \lfloor 23/3 \rfloor + \lfloor 23/2 \rfloor$, jadi kita setidaknya mempunyai satu solusi positif, dan karena yang ditanya adalah solusi yang terbesar maka kita cukup mengerjakan kasus dimana $x>0$ (mencari jika ada yang lebih besar lagi).  Perhatikan juga bahwa karena bagian sebelah kanan dari persamaan pada soal adalah bilangan bulat, maka nilai $x$ yang memenuhi persamaan diatas harus bilangan bulat. 

Definisikan 

\[f(r)=r - \left \lfloor\frac{r}{2} \right\rfloor - \left\lfloor\frac{r}{3} \right\rfloor - \left\lfloor\frac{r}{4}\right\rfloor \]

Lemma  Jika $r$ adalah bilangan bulat non-negatif maka berlaku $f(r) \leq 1$. 

 

Bukti: Dengan ketaksamaan $\alpha-1 < \lfloor \alpha \rfloor$, kita peroleh 

 

\[\frac{r}{2} - 1 < \left \lfloor\frac{r}{2} \right\rfloor  \quad \frac{r}{3} - 1 < \left \lfloor\frac{r}{3} \right\rfloor  \quad \frac{r}{4} - 1 < \left\lfloor\frac{r}{4} \right\rfloor\] 

Sehingga apabila ketiga ketaksaman diatas dijumlahkan dan dikurang $r$ dan pindah ruas maka akan diperoleh $f(r) < 3 - \frac{r}{12}$. Jika $r \geq 12$, maka diperoleh $f(r)<2$, sehingga karena $f(r)$ bilangan bulat maka $f(r)\leq 1$. Jika $0\leq r \leq 11$, perhatikan bahwa 

\begin{align*}f(r+4) &= r+4 - \left \lfloor\frac{r}{2} \right\rfloor-2 - \left\lfloor\frac{r+1}{3} \right\rfloor-1 - \left\lfloor\frac{r}{4}\right\rfloor -1 \\ &= r - \left \lfloor\frac{r}{2} \right\rfloor - \left\lfloor\frac{r+1}{3} \right\rfloor - \left\lfloor\frac{r}{4}\right\rfloor\end{align*}

dan nilai $\left\lfloor\frac{r+1}{3} \right\rfloor$ bisa sama dengan $\left\lfloor\frac{r}{3} \right\rfloor$ atau $\left\lfloor\frac{r}{3} \right\rfloor + 1$, Jadi $f(r+4)$ bisa sama dengan $f(r)$ atau $f(r)-1$, dengan kata lain bisa lebih kecil atau tetap $f(r)$. Karena $f(1)=f(2)=f(3)=1$ dan $f(0)=0$, maka $f(4), f(5), \cdots, f(11)$ nilainya hanya bisa lebih kecil lagi atau tetap. Jadi $f(r) \leq 1$ juga untuk $0 \leq r \leq 11$.

 

Sekarang kembali pada soal, misalkan terdapat sebuah solusi $x \geq 24$, maka berdasarkan Teorema Sisa diperoleh terdapat bilangan asli $q$ dan bilangan bulat tak-negatif $r$ sedemikian sehingga $x = 24q + r$ dimana $r=0,1,\cdots, 23$. Substitusikan $x$ pada persamaan diperoleh

 

Untuk $n=2$: 

\[24q+r = \left\lfloor\frac{24q+r}{2} \right\rfloor = 12q+\left\lfloor\frac{r}{2} \right\rfloor \Leftrightarrow  12q+r = \left\lfloor\frac{r}{2} \right\rfloor \leq \frac{r}{2} < r\]

kontradiksi, karena $q>0$.

 

Untuk $n=3$:

\[24q+r= 12q+ \left\lfloor\frac{r}{2} \right\rfloor  + 8q+ \left\lfloor\frac{r}{3} \right\rfloor  \Rightarrow 4q + r = \left\lfloor\frac{r}{2} \right\rfloor + \left\lfloor\frac{r}{3} \right\rfloor < r   \]

kontradiksi lagi.

 

Untuk $n=4$:

\[24q+r= 12q+ \left\lfloor\frac{r}{2} \right\rfloor  + 8q+ \left\lfloor\frac{r}{3} \right\rfloor + 6q+ \left\lfloor\frac{r}{4} \right\rfloor  \Rightarrow  2q = f(r)\]

 

Sehingga dengan menggunakan Lemma  diperoleh $2q=f(r) \leq 1$,t idak mungkin karena berakibat $q \leq \frac{1}{2}$, sedangkan $q$ bilangan asli.

 

 

Sedangkan untuk $n \geq 5$ kita peroleh

 

\[24q+r = 2q+ \left\lfloor\frac{r}{2} \right\rfloor  + 8q+ \left\lfloor\frac{r}{3} \right\rfloor + 6q+ \left\lfloor\frac{r}{4} \right\rfloor + \sum_{k=5}^n \left\lfloor \frac{x}{k} \right\rfloor\]

 

yang setara dengan 

 

\[2q+\sum_{k=5}^n \left\lfloor \frac{x}{k} \right\rfloor = f(r) \]

 

Namun berdasarkan Lemma $f(r)\leq 1$, sehingga diperoleh $2q\leq 2q+\sum_{k=5}^n \left\lfloor \frac{x}{k} \right\rfloor = f(r) \leq 1$, yakni $2q \leq 1$, kontradiksi dengan $q$ bilangan asli.

 

Jadi tidak ada solusi untuk $n \geq 24$.

 

Share this post


Link to post
Share on other sites

Untuk no 16 :

 

 

Spoiler

Jawab: 4374

 

Kita akan generalisasi soalnya, misalkan terdapat $n \geq 3$ kotak.  Sebut bilangan $n$ digit yang bisa kita bentuk dengan cara pada soal sebagai bilangan $n$-kolo

 

Dan misalkan $a_n$ menyatakan banyaknya bilangan $n$-kolo  yang bisa terbentuk. Perhatikan bahwa $a_3= 6$, karena tiga bilangan $1,2,3$ bisa diletakkan ulang dengan $3!=6$ cara.  

 

Kita akan membuktikan rumus rekursi $a_{n+1} = 3 a_n$ untuk $n\geq 3$. 

 

Ambil sebarang bilangan $n$-kolo sebutlah $\overline{d_1 d_2 \cdots  d_{n-2} xy }$ maka bilangan $n$ digit $\overline{d_1 d_2 \cdots  d_{n-2} yx }$ juga bilangan $n$-kolo, ini karena ketika mereka diperoleh dari peletakan ulang tiga bilangan $\{d_{n-2}, x, y\}$, kita sebut dua bilangan $n$-kolo diatas bersaudara.  Contoh $1243$ dan $1234$ adalah bilangan $4$-kolo yang bersaudara, sedangkan $2134$ dan $1243$ bukan saudara (karena berbeda digit awal). Jelas bahwa, setiap bilangan $n$-kolo hanya mempunyai tepat satu saudara.

 

Dengan demikian kita bisa memasangkan bilangan-bilangan $n$-kolo ini menjadi pasangan-pasangan bilangan bersaudara, dan karena banyaknya bilangan $n$-kolo adalah $a_n$ maka banyaknya pasangan-pasangan tersebut adalah $\frac{a_n}{2}$.  

 

Ambil salah satu bilangan kolo $n$ digit $D=\overline{d_1 d_2 \cdots  d_{n-2} xy }$ apabila diperkenalkan digit yang baru  yang pasti merupakan $z=n+1$, maka ada $6=3!$ buah bilangan kolo $n+1$-digit  yang  bisa diperoleh dari $D$, yakni: $\overline{d_1 d_2 \cdots  d_{n-2} xyz }$, $\overline{d_1 d_2 \cdots  d_{n-2} zxy }$, $\overline{d_1 d_2 \cdots  d_{n-2} zyx }$, $\overline{d_1 d_2 \cdots  d_{n-2} yxz }$, $\overline{d_1 d_2 \cdots  d_{n-2} xzy }$, dan $\overline{d_1 d_2 \cdots  d_{n-2} yzx }$. Dan saudara dari $D$ juga akan menghasilkan $6$ buah bilangan yang sama.

 

Ini berarti setiap satu pasangan saudara menghasilkan $6$ buah bilangan  $n+1$-kolo berbeda, dan karena digit $n+1$ pada bilangan $n+1$-kolo hanya bisa berada pada tiga tempat terakhir maka setiap bilangan $n+1$-kolo dapat dikontruksi dengan cara ini.  Sehingga banyak bilangan $n+1$-kolo adalah $6 \times \frac{a_n}{2} = 3 a_{n}$.

 

jadi $a_9 = 3a_8 = 9 a_7 = 27 a_6 = 81 a_5 = 243 a_4 = 729 a_3 = 729 \times 6 = 4374$.

 

 

Share this post


Link to post
Share on other sites

Untuk no 19 : 

 

Spoiler

Jawab:  33

 

Saya pakai Lucas Theorem 

 

 

Kita akan buktikan bahwa 

 

\[FPB \left( {2n \choose 1} , {2n \choose 3}, \cdots, {2n \choose 2n-1}  \right) = 2^{v_2(2n)}\]

 

dimana $v_2(x)$ menyatakan pangkat tertinggi $2$ yang membagi $x$, contoh $v_2(12) = 2$, karena $2^2 | 12$ tapi $2^3 \nmid 12$.  

 

Pertama-tama, kita akan buktikan bahwa tidak ada bilangan prima ganjil $p$ sedemikian sehingga $p \lvert {2n \choose 2j+1}$ untuk setiap $j=0,1, \cdots, n-1$. 

 

Tulis $2n$ dalam basis $p$, yakni $2n=  d_m p^m + d_{m-1} p^{m-1} + \cdots + d_1 p + d_0$, dimana $d_i \in \{0,1, \cdots, p-1\}$.  Dan juga tulis $2j+1$ dalam basis $p$ misalkan $2j+1=  e_m p^m + e_{m-1} p^{m-1} + \cdots + e_1 p + e_0$, dimana $e_i \in \{0,1, \cdots, p-1\}$, disini $e_m$, $e_{m-1}$, dan seterusnya bisa nol jika banyak digit $2j+1$ tidak sama dengan banyak digit $2n$. Berdasarka Teorema Lucas

 

\[{2n \choose 2j+1} \equiv \prod_{i=1}^m {d_i \choose e_i} \pmod p\]

 

kita akan membuktikan bahwa akan selalu ada $2j+1$ yang membuat hasil kali diatas tidak nol (tidak kelipatan $p$), ini berarti akan selalu ada bilangan ganjil $2j+1$ sedemikian sehingga ${2n \choose 2j+1} \not \equiv 0 \pmod p$. Untuk membuktikan hal ini, perhatikan bahwa

 

  • Jika $d_i \geq e_i$ maka ${d_i \choose e_i} = \frac{d_i (d_i-1) \cdots (d_i - e_i+1)}{e_i!}$ dan karena $0 \leq d_i, e_i \leq p-1$, faktor prima $p$ tidak mungkin muncul pada koefisien binomial ${d_i \choose e_i}$., ini berarti ${d_i \choose e_i} \not \equiv \pmod p$.

Ini berarti diantara suku-suku pada perkalian diatas, yang bisa menghasilkan $0$ hanya terjadi ketika $d_i < e_i$. 

 

Kita kontruksi bilangan $k=2j+1$ dengan menggunakan digit dari $2n$ sebagai berikut: 

 

Pertama-tama, kita mulai dengan representasi basis $p$ dari $2n$. Misalkan $d_j$ adalah digit paling kanan yang tak nol,  kita ganti digit tersebut menjadi $e_j=d_j-1$. Hanya ada dua kasus yang perlu kita perhatikan, yakni apabila representasi basis $p$ dari $2n$ berbentuk $100\cdots 0$ atau $00\cdots 1$, pada kasus ini hanya ada tepat satu digit yang tak-nol yakni $d_n=1$ atau $d_0=1$ dan apabila digit tersebut dipilih maka $e_n=1-1=0$ atau $e_0=0$, sehingga bilangan yang diperoleh menjadi nol.  Tapi kasus ini tidak mungkin terjadi karena ini sama saja dengan $2n=p^k$ atau $2n=1$, sedangkan kita tahu bahwa $p$ prima ganjil.  

 

Dengan demikian proses diatas akan menghasilkan bilangan baru $k$  yang tak-nol dengan digit seperti $2n$ namun berbeda hanya $d_j$. Yakni $k=\overline{d_n \cdots (d_j-1) \cdots d_0}$. Perhatikan juga bahwa $k$ bilangan ganjil, karena $k$ hanya selisih $p^j$  dengan $2n$ yang merupakan bilangan genap (disini $j$ juga boleh nol)

 

 ini berarti dengan Teorema Lucas

 

\[{2n \choose k} \equiv {d_1 \choose d_1} \cdots {d_j \choose d_j-1} \cdots {d_0 \choose d_0} \equiv {d_j \choose d_j-1} \not \equiv 0 \pmod p\]

 

Jadi kita telah menemukan bilangan ganil $k$ sehingga $p$ tidak membagi ${2n \choose k}$.

 

Sehingga FPB yang kita cari harus berbentuk $2^q$. Kita akan buktikan $q=v_2(2n)$, pangkat dua terbesar yang bisa membagi ${2n \choose 1}$ adalah $v_{2}(2n)$, sehingga ini berarti $q \leq v_2(2n)$. Perhatikan bahwa ${2n \choose k} = \frac{2n}{k} {2n-1 \choose k}$, dan karena $k$ ganjil maka pada suku $\frac{2n}{k}$ tersebut  $k$ tidak membuang faktor $2$ pada $2n$. Jadi $v_2(2n) | {2n \choose k}$ untuk setap $k$ ganjil, sehingga $v_2(2n) \leq q$, diperoleh $q=v_2(2n)$. 

 

Kembali ke soal KTO, disini $2n=20^{16} = 2^{32} 5^{16}$, sehingga $v_2(2n) = 32$. Jadi bilangan $s$ yang memenuhi adalah $2^{32}$, yang mempunyai $32+1=33$ faktor positif.

 

 

 

Edited by Adri

Share this post


Link to post
Share on other sites
11 hours ago, Faishol said:

17. 6 pasangan .....?

  Reveal hidden contents

(a,b,c)=(1,2,4);(1,4,2);(2,1,4);(2,4,1);(4,1,2);(4,2,1)

 

aku 18 pasangan.. Kalau a,b, dan c sama jadi 12.. Terus (3,3,6) dan permutasinya dan (3,6,6) dan permutasinya

Share this post


Link to post
Share on other sites
8 hours ago, Muh. Fadlan said:

aku 18 pasangan.. Kalau a,b, dan c sama jadi 12.. Terus (3,3,6) dan permutasinya dan (3,6,6) dan permutasinya

Nemu 32 sekarang...... a,b,c sama dapet 6x.  terus (1,1,2);(1,1,4),(1,2,2),(1,4,4);(3,3,6);(3,6,6);(1,2,4) dan permutasinya.

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