Art of Mathematics

25 Agustus 2008

Nilai terkecil anggota gabungan

Diarsipkan di bawah: Kombinatorik — Tag:, , , , , , , , — Johan @ 5.44

[China 2006] Misalkan X adalah sebuah himpunan 56 elemen. Untuk sebarang 15 subhimpunan X, di mana gabungan dari setiap 7 subhimpunan dari subhimpunan-subhimpunan ini memiliki setidaknya n elemen, maka terdapat 3 dari 15 subhimpunan ini yang irisannya tidak kosong. Tentukan nilai terkecil n.

Solusi
Nilai terkecil n adalah 41.

Pertama-tama, kita akan membuktikan bahwa n\le40 tidak mungkin. Anggaplah X=\{1,2,\cdots,56\}. Misalkan ada 15 subhimpunan sebagai berikut:

A_i=\{i,i+7,i+14,i+21,i+28,i+35,i+42,i+49\}\ (i=1,2,3,4,5,6,7)

B_j=\{j,j+8,j+16,j+24,j+32,j+40,j+48\}\ (j=1,2,3,4,5,6,7,8)

Mudah dilihat bahwa

|A_i|=8\ (i=1,2,\cdots,7),|A_i\cap A_j|=0\ (1\le i<j\le7)

|B_j|=7\ (j=1,2,\cdots,8),|B_i\cap B_j|=0\ (1\le i<j\le8)

|A_i\cap B_j|=1\ (1\le i\le7,1\le j\le8).

Untuk setiap 7 subhimpunan, misalnya A_{i_1},A_{i_2},\ldots,A_{i_s},B_{j_1},B_{j_2},\ldots,B_{j_t}\ (s+t=7), kita punya

|A_{i_1}\cap A_{i_2}\cap\ldots\cap A_{i_s}\cap B_{j_1}\cap B_{j_2}\cap\ldots\cap B_{j_t}|\\=|A_{i_1}|+|A_{i_2}|+\ldots+|A_{i_s}|+|B_{j_1}|+|B_{j_2}|+\ldots+|B_{j_t}|-st\\=8s+7t-st\\=8s+7(7-s)-s(7-s)\\=s^2-6s+49\\=(s-3)^2+40\ge40

Pada kasus ini, gabungan dari setiap 7 subhimpunan dari 15 subhimpunan itu memiliki setidaknya 40 elemen (dengan kata lain n=40). Tetapi, untuk setiap 3 subhimpunan dari 15 subhimpunan tadi, pasti setidaknya dua di antaranya adalah A_i atau setidaknya dua di antaranya adalah B_j. Ini menyebabkan irisan ketiganya kosong. Jadi n\le40 tidak memenuhi.

Sekarang, kita akan membuktikan bahwa n=41 memenuhi ketentuan. Kita akan melakukan pembuktikan dengan kontradiksi. Jadi, asumsikan ada 15 subhimpunan, gabungan dari setiap 7 di antaranya memiliki setidaknya 41 elemen, tetapi tidak ada 3 subhimpunan yang irisannya tidak kosong. Jadi tidak ada elemen yang berada di 3 subhimpunan. Kita bisa anggap setiap elemen berada di tepat 2 subhimpunan. Jika tidak, kita bisa menambah beberapa elemen ke beberapa subhimpunan dari 15 subhimpunan ini, dan ketentuan tetap berlaku.

Menurut Prinsip Rumah Burung, ada satu himpunan dari 15 subhimpunan ini (sebutlah ini A) sehingga |A|\ge\lceil\frac{2\times56}{15}\rceil=8. Misalkan 14 himpunan lainnya adalah A_1,A_2,\cdots,A_{14}.

Gabungan dari setiap 7 himpunan dari A_1,A_2,\cdots,A_{14} memiliki setidaknya 41 elemen. Jadi totalnya y\ge41_{14}C_7.

Kita gunakan cara lain untuk menghitung nilai y. Untuk setiap a\in X, jika a bukan elemen dari A (ada 56-|A| nilai a), maka a adalah anggota dari tepat dua himpunan dari A_1,A_2,\cdots,A_{14}. Jadi a dihitung _{14}C_7-_{12}C_7 kali. Jika a merupakan elemen dari A (ada |A| nilai a), maka a adalah anggota dari satu himpunan dari A_1,A_2,\cdots,A_{14}. Jadi a dihitung _{14}C_7-_{13}C_7 kali. Jadi

41_{14}C_7\le y=(56-|A|)(_{14}C_7-_{12}C_7)+|A|(_{14}C_7-_{13}C_7)\\=56(_{14}C_7-_{12}C_7)-|A|(_{13}C_7-_{12}C_{7})\\ \le56(_{14}C_7-_{12}C_7)-8(_{13}C_7-_{12}C_{7}).

Dapat dilihat dengan mudah bahwa 41_{14}C_7\le56(_{14}C_7-_{12}C_7)-8(_{13}C_7-_{12}C_{7}) itu tidak mungkin. Maka kita dapat kontradiksi.

Jawabannya adalah 41.

No Comments Yet »

Belum ada komentar.

RSS umpan untuk komentar-komentar dalam tulisan ini. URI Lacak Balik

Tinggalkan komentar

Blog pada WordPress.com.