Wednesday, March 14, 2012

Pembahasan Olimpiade Matematika #4

4. Diberikan himpunan A=\{1,2,3,\ldots,2008\}. a) Tentukan banyaknya subhimpunan dari A sehingga hasil kali anggotanya habis dibagi 7. b) Jika N(i) adalah banyaknya subhimpunan sehingga jumlah anggotanya bersisa i jika dibagi 7, buktikan bahwa N(0)-N(1)+N(2)-N(3)+N(4)-N(5)+N(6)-N(7)=0.
Solusi:
a) Kita cari banyaknya subhimpunan sehingga hasil kalinya tidak habis dibagi 7. Perhatikan bahwa 7,14,21,28,35,…,2002 tidak boleh ada dalam subhimpunan tersebut tetapi yang lain boleh. Maka ini sama dengan mencari subhimpunan dari \{1,2,3,4,5,6,8,\ldots,2008\}, di mana tidak ada kelipatan 7. Banyak anggota himpunan ini adalah 1722. Jadi banyaknya subhimpunan adalah 2^{1722}, sehingga banyaknya subhimpunan yang hasil kalinya habis dibagi 7 adalah 2^{2008}-2^{1722}.
b) Cukup dibuktikan bahwa N(i)-N(7-i)=0 untuk i=1,2,3. Suatu subhimpunan \{a_1,a_2,\ldots,a_m\} kita bijeksikan dengan subhimpunan \{(2009-a_1),(2009-a_2),\ldots,(2009-a_m)\}. Maka jumlah anggota subhimpunan pertama i\pmod{7} jika dan hanya jika yang kedua 7-i\pmod7. Maka jelas bahwa N(i)=N(7-i).


Related Article to Pembahasan Olimpiade Matematika #4:



Enter your email address below to receive updates each time we publish new content :
  
Privacy guaranteed. We'll never share your info.
free counters

0 komentar:

Terimakasih telah menyempatkan waktu untuk membaca artikel Pembahasan Olimpiade Matematika #4.
Semoga Informasi ini dapat bermanfaat dan menambah wawasan. Silahkan meninggalkan komentar artikel Pembahasan Olimpiade Matematika #4
Salam Hormat.
Arwiesmart Blog's

Blogumulus by Roy Tanck and Amanda Fazani




Artikel Ter_Gress