Sign in to follow this  
Followers 0
Rimba Erlangga

OSP SMA 2017 - Bagian Uraian No. 1

2 posts in this topic

Untuk setiap persegi satuan pada papan berukuran $5 \times 9$ dituliskan angka $1$ atau $0$. Kemudian dihitung jumlah semua bilangan pada setiap kolom dan juga pada setiap barisnya sehingga diperoleh $14$ bilangan. Misalkan $H$ adalah himpunan yang berisi bilangan-bilangan tersebut. Tentukan maksimum dari banyak anggota $H$!

0

Share this post


Link to post
Share on other sites

Oh ini soal bagus, tapi menurutku lebih susah dibandingkan nomor 2.

 

Hint 1:

Spoiler

range angka yang mungkin muncul di H?

 

Hint 2:

Spoiler

mungkinkah 0 dan 9 keduanya muncul di H?

 

Solusi lengkap:
 

Spoiler

 

Kita tunjukkan bahwa $|H| \le 9$.

Misalkan $c_i$ merupakan jumlah bilangan pada kolom ke-$i$ dan $r_j$ merupakan jumlah bilangan pada baris ke $j$, $i=1,\dots,9$ dan $j=1,\dots,5$. Perhatikan bahwa $0 \le c_i \le 5$ dan $0 \le r_j \le 9$. Jadi, $H \subseteq \{0,\dots,9\}$.

Asumsikan $H=\{0,\dots,9\}$. Karena $c_i \le 5$, maka untuk setiap $k \in \{6,7,8,9\}$, ada $j$ sehingga $r_j=k$. Namun, karena ada $j$ sehingga $r_j=9$, maka $c_i \ge 1$ untuk setiap $i=1,\dots,9$. Jadi, karena $0 \in H$, haruslah ada $j$ sehingga $r_j=0$. Namun, karena ada baris yang tidak mengandung $1$, berlaku $c_i \le 4$ untuk setiap $i=1,\dots,9$. Jadi, $5 \notin H$, kontradiksi.

Jadi, $|H| \le 9$. Berikut adalah konfigurasi di mana $|H|=9$, yaitu $H=\{1,2,\dots,9\}$.

 

000100000

001111110

011111110

111111110

111111111

 

 

0

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  
Followers 0