Olimpiade Sains Provinsi (OSP) 2015 - Matematika SMA, Nomor 21
Misalkan X = {1, 2, 3, 4, 5}. Misalkan F = {A1, A2, A3, ..., Am}, dengan Ai X dan anggota Ai sebanyak 2, untuk i = 1, 2, ..., m. Tentukan m minimum sehingga untuk sebarang B
X, dengan B beranggota sebanyak 3, terdapat anggota F yang termuat di B. Buktikan jawab Anda.
1 jawaban
Taufiq Akbari Utomo10 tahun lalu
OSN MAT SMA '10
0
Set ,
,
,
,
,
. Dapat dicek via brute force bahwa untuk sebarang
dengan tiga anggota, terdapat anggota
yang termuat di
.
Untuk m=3, pasti ada anggota X yang terbawa tidak lebih dari satu kali ke ., tanpa mengurangi keumuman misal 1. Jika 1 tidak terbawa sama sekali, maka ada
dengan dua anggota sehingga
karena F hanya punya 3 anggota. Ambil
, maka tidak ada anggota F yang termuat di B. Jika 1 terbawa sekali, tanpa mengurangi keumuman misal
. Karena F hanya punya 3 anggota, ada
dengan dua anggota sehingga
. Ambil
, maka tidak ada anggota F yang termuat di B. Maka tidak mungkin m=3.
Jadi, m minimum adalah 4.
Masuk untuk menulis jawaban