Tahap 2 IMO Tes 3

Soal. Tiap-tiap dari n >1 orang membawa sebuah bingkisan ke suatu acara. Setiap dua orang bertukar bingkisan tepat satu kali dengan urutan pertukaran tidak ditentukan. Tunjukkan bahwa setiap bingkisan dapat kembali ke pemilik awalnya:

(a) jika 4|n.

(b) jika 4|n-1.

(c) hanya jika 4|n atau 4|n-1.

Solusi.

(a) Misalkan ada 4 orang (a,b,c,d) perhatikan skema pertukaran

a-b

c-d

a-c

b-d

a-d

b-c

Pada skema ini, setiap orang bertukar tepat satu kali dan bingkisan setiap orang kembali ke pemilik awalnya. Jika 4|n, misalkan n  orang dibagi menjadi n/4 kelompok, masing-masing berisi 4 orang. Perhatikan bahwa setiap kelompok bisa saling tukar. Sekarang, cukup ditunjukkan cara pertukaran untuk antar kelompok. Misalka ada dua kelompok {a,b,c,d} dan {e,f,g,h}. Kita perlu mengatur pertukaran di mana pertukaran selalu antar orang dari kelompok yang berbeda sebanyak tepat satu kali, dan akhirnya setiap hadiah kembali ke pemilik awalnya. Dengan meniru skema untuk 4 orang, kita bisa membuat skemanya sebagai berikut:

a-f

e-b

c-h

d-g

a-g

c-e

b-h

d-f

a-h

d-e

b-g

c-f

a-e

b-f

c-g

d-h.

(b) Ambil  satu orang, sebut X dari n orang, maka n-1 orang lainnya dapat saling bertukar bingkisan seperti skema antar-grup pada soal (a). Sekarang, setiap kali sebuah kelompok ingin bertukar bingkisan di dalam kelompoknya, si X ikut dalam pertukaran bingkisan di kelompok tersebut.

Misalkan kelompoknya adalah {a,b,c,d,x}. Pandang skema pertukaran:

a-x

a-b

b-x

c-x

c-d

d-x

a-c

b-d

a-d

b-c.

(c) Pandang permutasi dari 1,2,\dots,n. Sebut suatu permutasi genap jika ia merupakan komposisi sebanyak genap transposisi/swap dan ganjil jika ia merupakan sebanyak ganjil transposisi/swap. Dapat ditunjukkan bahwa setiap permutasi genap atau ganjil, dan tidak bisa bersifat kedua-keduanya (dibuktikan kepada pembaca). Dari soal, kita menginginkan dengan melakukan {n \choose 2} transposisi (1,2),(1,3),\dots,(n-1,n), diperoleh permutasi identitas kembali (1)(2) \dots (n). Namun, permutasi identitas merupakan permutasi genap. Dengan demikiaan, haruslah {n \choose 2} genap. Ini hanya mungkin jika n \equiv 0,1 \pmod{4}.

Refleksi

Awalnya soal ini tidak ingin dipecah menjadi beberapa bagian seperti di atas. Namun, sepertinya akan terlihat sangat intimidatif (setidaknya untuk saya sendiri). Apalagi kalau disuruh mencari n yang demikian. Semakin hancurlah nilainya.

Soal ini lumayan dapat dikerjakan oleh anak-anak Pelatnas Tahap 2 IMO secara parsial. Yang bisa mengerjakan “hampir sempurna” hanya 2 orang. Kebanyakan hanya mendapatkan nilai parsial 3 atau 4. Cukup membedakan lah ya di antara para peserta. Bukan pilihan soal yang buruk.

 

Advertisements
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s