Category: Kombinatorika

Banyaknya zodiak yang kita kenal ada $12$. Jika kita pilih $12$ siswa, ada kemungkinan zodiak mereka berbeda semua, tetapi jika kita pilih $\boxed{12+1=13}$ siswa, dipastikan setidaknya ada $2$ siswa dengan zodiak yang sama.
(Jawaban D)

Tanggal lahir dimulai dari $1$ dan berakhir paling lama sampai tanggal $31$. Jika kita pilih $3 \times 31 = 93$ orang, ada kemungkinan masing-masing $3$ orang memiliki tanggal lahir yang sama, namun bila ditambah $1$ orang lagi, sudah dipastikan akan ada $4$ orang yang memiliki tanggal lahir yang sama.
Jadi, banyaknya orang yang dimaksud adalah $\boxed{94}$ orang.
(Jawaban C)

Banyaknya kemungkinan bulan ada $12$. Jika diratakan terdapat masing-masing $3$ siswa yang memiliki bulan lahir yang sama, maka akan ada $36$ siswa. Berdasarkan prinsip sarang merpati, tambahkan seorang siswa lagi sehingga dipastikan akan ada $4$ siswa yang mempunyai bulan lahir yang sama.
Jadi, banyaknya siswa paling sedikit adalah $\boxed{37}$ orang.
(Jawaban D)

Tanggal lahir dimulai dari $1$ dan berakhir paling lama sampai tanggal $31.$ Ada kemungkinan $31$ siswa memiliki tanggal lahir yang berbeda-beda. Karena ada $38$ siswa, $7$ siswa tersisa dianggap memiliki tanggal lahir yang berbeda-beda, sehingga paling sedikit ada $\boxed{2}$ siswa yang bulan lahirnya sama.
(Jawaban B)

Ada $3$ jenjang pada SMP, yaitu kelas $7$, kelas $8$, dan kelas $9$. Karena $\dfrac{111}{3} = 37$ (tanpa sisa), berarti dapat dianggap ada $37$ siswa kelas 7, $37$ siswa kelas 8, dan $37$ siswa kelas $9$. Artinya, paling sedikit ada $37$ siswa yang berada pada jenjang yang sama.
(Jawaban C) 

Bulan kelahiran dalam kalender ada $12$. Karena $\dfrac{119}{12} = 9$ dengan sisa $11,$ akan ada paling sedikit $\boxed{9+1 = 10}$ anak yang lahir pada bulan yang sama.
(Jawaban B)

Hari dalam kalender ada $7$. Karena $\dfrac{1.000}{7} = 142$ dengan sisa $6$, kita hanya perlu menganggap $6$ orang ini memiliki hari lahir yang berbeda-beda. Akibatnya, paling sedikit kita temukan ada $\boxed{142+1=143}$ orang dengan hari lahir yang sama.
(Jawaban C)

Huruf yang kita gunakan (English alphabet) ada $26.$ Karena $\dfrac{100}{26} = 3$ dengan sisa $22,$ kita hanya perlu menganggap $22$ orang ini memiliki nama dengan huruf depan yang berbeda-beda. Akibatnya, paling sedikit kita temukan ada $\boxed{3+1=4}$ orang yang memiliki nama dengan huruf depan yang sama.
(Jawaban B)

Contoh pasangan dua bilangan yang jumlahnya $28$ adalah $(8, 20),$ $(9, 19),$ $(10, 18),$ dan seterusnya, sampai $(13, 15).$ Andaikan kita dalam kondisi paling tidak beruntung. Ambil bilangan $1$ sampai $14.$ Dari $14$ bilangan tersebut, belum ada pasangan dua bilangan yang jumlahnya $28.$ Lebih lanjut, jika diambil satu bilangan lagi di antara pilihan bilangan $15$ sampai $20,$ pasti akan ada pasangan dua bilangan yang jumlahnya $28.$ Sebagai ilustrasi, jika bilangan $16$ diambil, didapat $(12, 16)$ sebagai pasangan dua bilangan yang jumlahnya $28.$ Dengan menggunakan prinsip sarang merpati, banyaknya bilangan yang perlu diambil supaya dipastikan terdapat pasangan dua bilangan yang memiliki jumlah $28$ adalah $\boxed{14+1=15}$
(Jawaban D)

Pasangan bilangan yang memiliki jumlah $30$ adalah $(10, 20)$, $(11, 19)$, $(12, 18)$, $(13, 17)$, $(14, 16)$. Bilangan $21$ dan seterusnya sampai $70$ tidak memiliki pasangan untuk membentuk jumlah $30$ sehingga kita ambil terlebih dahulu (sebanyak $70-21+1 = \color{blue}{50}$ bilangan). Selanjutnya, kita ambil bilangan $10$ sampai $15$ (ada $\color{red}{6}$ bilangan, dan tetap belum ditemukan pasangan berjumlah $30.)$ Jika kita ambil satu bilangan lagi, apapun bilangan itu, kita peroleh dua bilangan berjumlah $30$.
Jadi, bilangan yang perlu dipilih sebanyak $\boxed{\color{blue}{50}+\color{red}{6}+1=57}.$
(Jawaban E)

Dengan memperhatikan kondisi terburuk, kita mengambil $n$ bilangan dari $2n$ bilangan sehingga kita tidak peroleh dua bilangan yang selisihnya $70.$
Untuk kasus ini, nilai $n = 70.$
Dari bilangan $1$ sampai $123$, dipilih bilangan $1, 2, \cdots, 70$ (sebanyak $70$ bilangan). Jika kita ambil satu bilangan apapun lagi, sudah dipastikan terdapat pasangan bilangan yang berselisih $70$. Jadi, paling sedikit banyaknya bilangan yang harus dipilih adalah $\boxed{70+1=71}.$
(Jawaban C)

Dengan menganggap kita dalam kondisi yang paling tidak beruntung, kita mendapatkan tepat $9$ kartu untuk masing-masing nomor dari $1$ sampai $20.$ Khusus untuk kartu bernomor $1$ sampai $8$, kita ambil semua kartu yang ada sesuai banyaknya di kotak, sedangkan kartu nomor $9, 10, 11, \cdots, 20$ (ada 12 nomor) masing-masing diambil sebanyak $9$ kartu. Jadi, kita peroleh kartu sebanyak
$\begin{aligned} & 1+2+3+\cdots+8+\underbrace{9+9+\cdots+9}_{\text{ada}~12} \\ & = (1+8) \times 4 + 12 \times 9 \\ & = 36 + 108 = 144. \end{aligned}$
Sampai sini, kita masih belum mendapatkan $10$ kartu bernomor sama, tetapi dengan mengambil satu kartu lagi di dalam kotak, kita dipastikan mendapatkannya.
Jadi, paling sedikit kita harus mengambil $\boxed{144+1=145}$ kartu.
(Jawaban C)

Menurut PSM, kita harus menempatkan posisi kita dalam keadaan terburuk dalam pengambilan sumpit. Saat kita ambil acak $52$ sumpit, kita mendapatkan $52$ sumpit putih. Artinya, kita sudah mendapatkan $1$ pasang sumpit bukan cokelat. Kemudian, kita ambil lagi $1$ sumpit dan anggap kita peroleh $1$ sumpit cokelat. Terakhir, ambil $6$ sumpit lagi dan anggap kita peroleh $6$ sumpit kuning.
Catatan: Kasus boleh dibalik. Anggap mendapat $1$ sumpit kuning, kemudian mendapat $6$ sumpit cokelat.
Jadi, kita sudah peroleh 3 pasang sumpit yang bukan putih.
Jadi, paling sedikit perlu diambil $\boxed{52+1+6 = 59}$ sumpit.
(Jawaban C)

Pertama, kita cari dahulu banyaknya kemungkinan jawaban berbeda yang dapat dijawab oleh siswa.

1. Ada $3$ soal dengan $2$ pilihan jawaban sehingga banyaknya kemungkinan jawaban berbeda untuk bagian pertama adalah $2^3 = 8.$
2. Ada $5$ soal dengan $5$ pilihan jawaban sehingga banyaknya kemungkinan jawaban berbeda untuk bagian kedua adalah $5^5 = 3.125.$

Dengan demikian, ada $8 \cdot 3.125 = 25.000$ jawaban berbeda yang mungkin. Jika ada $25.000$ siswa, maka masih ada kemungkinan bahwa tidak ada dua siswa yang jawabannya sama persis. Menurut prinsip sarang merpati, perlu ditambah satu siswa lagi agar dipastikan terdapat dua siswa yang jawabannya sama persis. Jadi, banyaknya siswa minimal adalah $\boxed{25.001~\text{orang}}.$
(Jawaban E)

Susun dua kelompok yang terdiri dari 5 anak perempuan dan 1 anak laki-laki untuk ditempatkan pada posisi duduknya di meja melingkar tersebut. Buat kelompok sehingga semua anak tercakup secara keseluruhan sehingga nantinya akan ada 8 kelompok yang terdiri dari 5 anak perempuan dan 8 anak kelompok yang terdiri 5 anak laki-laki (jumlahnya tepat 48 anak). Posisi duduk mereka akan seperti gambar.
Posisi duduk mereka memang dibuat selang-seling per kelompok agar tidak ada 6 anak perempuan yang duduk berdekatan. Dengan menggunakan prinsip sarang merpati, tambahkan $1$ anak perempuan lagi sehingga akan ditemukan secara pasti $6$ anak perempuan yang duduk berdekatan. Jadi, banyak minimum anak perempuan adalah $8 \cdot 5 + 1 = 41$ anak, sisanya adalah anak laki-laki.
(Jawaban C)

Andaikan kita dalam kondisi paling tidak beruntung. Pertama, ambil terlebih dahulu bilangan-bilangan yang bukan faktor positif dari $100.$ Karena faktor dari $100$ adalah $1, 2, 4, 5,$ $10, 20,$ $25, 50,$ dan $100$ (ada $9$), ambil bilangan selain ini, yaitu sebanyak $100-9 = 91$ bilangan. Berikutnya, ambil bilangan $10$ karena $10$ tidak memiliki pasangan agar hasil kalinya $100.$ Sampai sejauh ini, sudah $92$ bilangan yang telah diambil. Terakhir, ambil bilangan $1, 2, 4,$ dan $5$ sehingga total bilangan yang terambil sekarang menjadi $92+4=96.$ Jika satu bilangan apa pun diambil lagi, dapat dijamin bahwa kita akan menemukan pasangan bilangan yang hasil kalinya $100.$ Oleh karena itu, paling sedikit bilangan yang perlu diambil supaya dipastikan terdapat pasangan dua bilangan yang hasil kalinya $100$ adalah $\boxed{96+1=97}.$
(Jawaban E)

Jawaban a)
Dalam keadaan terburuk, kita mengambil $6$ bola putih dan $5$ bola hitam, lalu diikuti dengan pengambilan sebuah bola merah. Jadi, minimal bola yang harus diambil adalah $\boxed{6+5+1=12}.$
Jawaban b)
Dalam keadaan terburuk, kita mengambil $8$ bola merah dan $5$ bola hitam, lalu diikuti dengan pengambilan sebuah bola putih. Jadi, minimal bola yang harus diambil adalah $\boxed{8+5+1=14}.$
Jawaban c)
Dalam keadaan terburuk, kita mengambil $8$ bola merah dan $6$ bola putih, lalu diikuti dengan pengambilan $2$ bola hitam. Jadi, minimal bola yang harus diambil adalah $\boxed{8+6+2=16}.$
Jawaban d)
Dalam keadaan terburuk, kita mengambil $6$ bola putih, disusul dengan pengambilan $8$ bola merah, dan terakhir $2$ bola hitam. Jadi, minimal bola yang harus diambil adalah $\boxed{6+8+2=16}.$
Jawaban e)
Dalam keadaan terburuk, kita dianggap mengambil bola sebanyak mungkin terlebih dahulu, yaitu $8$ bola merah, lalu $6$ bola putih, dan terakhir cukup $1$ bola hitam. Jadi, minimal bola yang harus diambil adalah $\boxed{8+6+1=15}.$

Jawaban a)
Dalam keadaan terburuk, kita mengambil $6$ pasang kaus kaki warna kuning, $4$ pasang warna merah, dan $3$ pasang warna hitam. Kemudian, barulah diambil $1$ pasang kaus kaki warna ungu.
Jadi, paling sedikit kaus kaki yang perlu diambil agar diperoleh sepasang kaus kaki warna ungu adalah $\boxed{2(6)+2(4)+2(3)+2(1) = 28}.$
Jawaban b)
Dalam keadaan terburuk, kita mengambil $6$ pasang kaus kaki warna kuning, $4$ pasang warna merah, dan $5$ pasang warna ungu. Kemudian, barulah diambil $1$ pasang kaus kaki warna hitam.
Jadi, paling sedikit kaus kaki yang perlu diambil agar diperoleh sepasang kaus kaki warna hitam adalah $\boxed{2(6)+2(4)+2(5)+2(1) = 32}.$
Jawaban c)
Dalam keadaan terburuk, kita mengambil $6$ pasang kaus kaki warna kuning, $5$ pasang warna ungu, dan $3$ pasang warna hitam. Kemudian, barulah diambil $3$ pasang kaus kaki warna merah.
Jadi, paling sedikit kaus kaki yang perlu diambil agar diperoleh $3$ pasang kaus kaki warna merah adalah $\boxed{2(6)+2(5)+2(3)+2(3) = 34}.$
Jawaban d)
Dalam keadaan terburuk, kita dianggap mengambil pasang kaus kaki yang paling banyak terlebih dahulu, yaitu $6$ pasang kaus kaki warna kuning, lalu $5$ pasang kaus kaki warna ungu, diikuti oleh $4$ pasang kaus kaki warna merah, dan terakhir cukup $1$ kaus kaki warna hitam (bukan sepasang).
Jadi, paling sedikit kaus kaki yang perlu diambil agar didapat $4$ kaus kaki dengan warna berbeda adalah $\boxed{2(6)+2(5)+2(4)+1 = 31}.$

Pasangan $2$ bilangan yang memiliki selisih $50$ adalah $(1, 51)$, $(2, 52)$, $(3, 53)$, $\cdots$, $(49, 99)$, dan $(50, 100$). Kita menemukan ada $50$ pasangan. Jika kita mengambil tepat $50$ bilangan, ada kemungkinan kita mendapatkan bilangan $1, 2, 3, \cdots, 49, 50$ sehingga tidak ada pasangan bilangan yang berselisih $50$. Berdasarkan PSM, ambil $50+1 =51$ bilangan dan dipastikan terdapat $2$ bilangan yang selisihnya $50.$ $\blacksquare$

Dengan memperhatikan kondisi terburuk, kita mengambil $n$ bilangan dari $2n$ bilangan sehingga kita tidak peroleh dua bilangan yang selisihnya $11.$
Untuk kasus ini, nilai $n = 9.$

1. Dari bilangan $1$ sampai $22$, diambil bilangan $1, 2, \cdots, 11.$
2. Dari bilangan $23$ sampai $44$, diambil bilangan $23, 24, \cdots, 33.$
3. Dari bilangan $45$ sampai $66$, diambil bilangan $45, 46, \cdots, 55.$
4. Dari bilangan $67$ sampai $88$, diambil bilangan $67, 68, \cdots, 77.$
5. Dari bilangan $89$ sampai $100$, diambil bilangan $89, 90, \cdots, 99.$

Banyaknya bilangan yang kita ambil seluruhnya adalah $11+11+11+11+11=55,$ dan tidak ditemukan adanya $2$ bilangan yang berselisih $11.$  

Dengan memperhatikan kondisi terburuk, kita mengambil $n$ bilangan dari $2n$ bilangan sehingga kita tidak peroleh dua bilangan yang selisihnya $9.$
Untuk kasus ini, nilai $n = 9.$

1. Dari bilangan $1$ sampai $18$, diambil bilangan $1, 2, \cdots, 9.$
2. Dari bilangan $19$ sampai $36$, diambil bilangan $19, 20, \cdots, 27.$
3. Dari bilangan $37$ sampai $54$, diambil bilangan $37, 39, \cdots, 45.$
4. Dari bilangan $55$ sampai $72$, diambil bilangan $55, 56, \cdots, 63.$
5. Dari bilangan $73$ sampai $90$, diambil bilangan $73, 74, \cdots, 81.$

Dari bilangan $91$ sampai $100$, diambil semua bilangan yang ada, kecuali $100.$ Banyaknya bilangan yang kita ambil seluruhnya adalah $9+9+9+9+9+9 =54.$ Jika kita mengambil satu bilangan tersisa secara acak (berapapun nilainya), dipastikan akan ada dua bilangan yang berselisih $9$. Jadi, terbukti bahwa setidaknya terdapat $2$ bilangan yang selisihnya $9$ bila kita mengambil $55$ bilangan secara acak. $\blacksquare$

Untuk mendapatkan sepasang kaus kaki sewarna, berarti kita harus mengambil setidaknya $2$ kaus kaki, tetapi belum dapat dipastikan kita mendapatkannya.
Berdasarkan prinsip sarang merpati, untuk memastikan diperolehnya sepasang kaus kaki sewarna, kita hanya perlu mengambil paling sedikit $2 + 1 = 3$ kaus kaki.

Jika delapan bilangan bulat tersebut dibagi $12$, maka kemungkinan sisanya adalah $\{0,1,2,\cdots, 12\}$. Sekarang siapkan $7$ buah “kotak” dan beri label seperti berikut.
$$\{0\}, \{1,11\}, \{2,10\}, \{3,9\}, \{4,8\}, \{5,7\}, \{6\}$$Kemudian kita masukkan delapan bilangan bulat itu ke dalam “kotak” sesuai dengan sisa hasil baginya oleh $12$. Karena terdapat $7$ buah kotak dan $8$ bilangan, menurut prinsip sarang merpati, terdapat setidaknya satu kotak yang memuat dua bilangan. Jika kotak itu adalah kotak berlabel $\{0\}$ atau $\{6\}$, maka selisih dua bilangan tersebut adalah kelipatan $12$, contohnya bilangan $6$ dan $18$ yang masuk ke kotak berlabel $\{6\}$ (karena sisa hasil baginya oleh $12$ adalah $6$) memiliki selisih $12$. Di lain sisi, jika yang memuat dua bilangan itu kotak lainnya, maka hasil penjumlahan dua bilangan tersebut habis dibagi $12$, contohnya bilangan $2$ dan $22$ masuk ke dalam kotak berlabel $\{2,10\}$ memiliki jumlah $24$, yang merupakan kelipatan $12.$ $\blacksquare$ 

Ambil sembarang bilangan bulat positif $n.$ Akan ditunjukkan bahwa terdapat bilangan kelipatan $n$ yang digit-digitnya hanya tersusun dari angka $0$ dan $1.$
Misalkan kita memiliki $(n+1)$ bilangan bulat positif, yaitu $1, 11, 111, \cdots, \underbrace{111…111}_{\text{ada}~n+1}.$ Perhatikan bahwa ketika suatu bilangan bulat dibagi oleh $n,$ akan ada $n$ sisa hasil bagi yang mungkin, yaitu $0, 1, 2, 3, \cdots, n-1.$ Karena kita mempunyai $(n+1)$ bilangan, menurut PSM, ada setidaknya $2$ bilangan yang memiliki sisa hasil bagi yang sama ketika dibagi $n,$ katakanlah $A$ dan $B$ dengan $A > B.$ Bilangan $A-B$ merupakan kelipatan $n$ yang digit-digitnya hanya tersusun dari angka $0$ dan $1.$ $\blacksquare$

Ilustrasi: Misalkan kita ingin mengecek apakah bilangan kelipatan $6$ memiliki digit-digit yang hanya tersusun dari angka $0$ dan $1.$ Konstruksi $7$ bilangan, yaitu $1, 11, 111,$ $1.111, 11.111,$ $111.111,$ dan $1.111.111.$ Sisa hasil bagi tujuh bilangan ini ketika dibagi $6$ secara berturut-turut adalah $1, 5, 3, 1, 5, 3,$ dan $5.$ Kita cukup memilih dua bilangan yang memiliki sisa hasil bagi yang sama, misalkan $1$ dan $1.111.$ Perhatikan bahwa selisihnya, $1.111-1 = 1.110$ merupakan bilangan kelipatan $6$ yang hanya tersusun dari angka $0$ dan $1.$ 

Setiap bilangan bulat $n \ge 1$ dapat dinyatakan dalam bentuk $n = 2^a \cdot b$ dengan $b$ adalah faktor ganjil terbesar. Dari $2n$ bilangan yang ada pada himpunan, kita punya $n$ bilangan ganjil berbeda. Dengan menggunakan prinsip sarang merpati, jika kita memilih $(n+1)$ bilangan berbeda pada himpunan tersebut, paling sedikit dua di antara bilangan itu pasti memiliki faktor ganjil terbesar yang sama. Misalkan dua bilangan itu adalah $n_1 = 2^x \cdot b$ dan $n_2 = 2^y \cdot b$ sehingga jelas bahwa $n_1 \mid n_2$ jika $n_2 \ge n_1$ atau $n_2 \mid n_1$ jika $n_1 \ge n_2.$ $\blacksquare$

Ide yang kita gunakan adalah fakta bahwa setiap bilangan bulat positif dapat dituliskan sebagai perkalian perpangkatan $2$ dan suatu bilangan ganjil (ambil sebesar mungkin). Contoh: $30 = 2 \times 15$ dan $40 = 2^3 \times 5.$
Misalkan kita punya $n+1$ bilangan bulat positif, yaitu $a_1, a_2, \cdots, a_n, a_{n+1}.$ Nyatakan semua bilangan ini dalam bentuk $a_j = 2^{k_j} \cdot q_j$ untuk $j = 1, 2, \cdots, n+1$ dengan $k_j$ merupakan bilangan bulat nonnegatif dan $q_j$ merupakan bilangan ganjil. Bilangan bulat $q_1, q_2, \cdots, q_{n+1}$ merupakan bilangan ganjil positif yang nilainya kurang dari $2n.$ Namun, hanya ada $n$ bilangan ganjil positif berbeda yang nilainya kurang dari $2n.$ Menurut PSM, ada setidaknya dua bilangan ganjil dari $q_1, q_2, \cdots, q_{n+1}.$ Dengan kata lain, ada bilangan bulat berbeda $i$ dan $j$ sedemikian sehingga $q_i = q_j.$ Misalkan $q = q_i = q_j$ sehingga $a_i = 2^{k_i} \cdot q$ dan $a_j = 2^{k_j} \cdot q.$ Akibatnya, jika $k_i < k_j,$ maka $a_i$ membagi $a_j.$ Sebaliknya, jika $k_j < k_i,$ maka $a_j$ membagi $a_i.$
Jadi, terbukti bahwa di antara $n+1$ bilangan bulat positif yang nilainya tidak melebihi $2n$, selalu ada bilangan bulat yang membagi salah satu bilangan bulat yang lain. $\blacksquare$

Misalkan $a_1$ adalah banyaknya latih tanding yang telah dilakukan petinju sampai hari ke-$i$ dengan $i = 1,2,3,\cdots, 75$, sehingga diperoleh
$1 \leq a_1 < a_2 < a_3 < \cdots < a_{75} \leq 125$
dan dengan menambahkan $24$ di setiap ruas, diperoleh
$$25 \leq a_1 + 24 < a_2+24< \cdots < a_{75} + 24 \leq 149.$$Karena ada $149$ bilangan terhitung dari $1$ sampai $149,$ sedangkan $a_1,a_2,\cdots, a_{75}, a_1+24,$ $a_2+24, \cdots, a_{75}+24$ terdiri dari $75+75=150$ bilangan, menurut prinsip sarang merpati, setidaknya ada $2$ bilangan yang sama dari barisan tersebut, yakni ada $i$ dan $j$ sedemikian sehingga $a_i = a_j +24.$
Dengan kata lain, pada hari ke $j+1,j+2,\cdots, i$, si petinju tepat latih tanding sebanyak $24$ kali. $\blacksquare$