OSN 2009 Soal 4


Di suatu pulau terdapat 7 kota dan ada jaringan kereta api yang melalui kota-kota tersebut. Setiap segmen rel menghubungkan tepat 2 kota, dan diketahui bahwa setiap kota memiliki paling sedikit 3 segmen ke kota lain. Buktikan bahwa terdapat rute perjalanan kereta api yang mengunjungi 4 kota yang berbeda masing-masing sekali dan kembali ke kota asalnya. (Contoh: rute ).

Jawab:

Ambil satu kota, sebutlah A. A pasti terhubung dengan minimal 3 kota lain. Misalkan A terhubung dengan . Dan sebutlah tiga kota sisanya sebagai . Sebut kumpulan 3 kota pertama sebagai himpunan kota , dan 3 kota terakhir sebagai himpunan kota 

Jika ada  sehingga  dan  terhubung dengan rel, maka ada rute yang memenuhi, yaitu  , dan kita selesai.

Jika ada  sehingga  dan  terhubung dengan rel, maka rute yang memenuhi adalah , dan kita selesai. Asumsikan sebaliknya.

Jika ada satu tipe rel , sebutlah , maka  memiliki minimal satu jalur ke himpunan kota  memiliki minimal satu jalur ke himpunan kota , dan memiliki minimal 2 jalur ke himpunan kota . Maka total ada minimal 4 jalur ke himpunan kota . Tetapi,  hanya terdiri dari 3 kota. Menurut prinsip sangkar merpati, pasti ada satu kota yang dihubungkan dengan minimal 2 jalur ke himpunan kota , yaitu ke 2 kota berbeda pada himpunan kota . Maka kita selesai.

Jika ada satu tipe rel , maka  memiliki minimal 2 jalur ke himpunan kota  memiliki minimal 2 jalur ke himpunan kota , dan  memiliki minimal 2 jalur ke himpunan kota . Maka total ada minimal 6 jalur ke himpunan kota . Tetapi,  hanya terdiri dari  kota. Menurut prinsip sangkar merpati, pasti ada satu kota yang dihubungkan dengan minimal 2 jalur ke himpunan kota , yaitu ke 2 kota berbeda pada himpunan kota . Maka kita selesai.

Dari semua kasus, dipastikan ada jalur yang memenuhi, dan kita selesai. Terbukti.

About ardiantoarsadi

don't look for miracles it will come

Posted on Desember 21, 2009, in SOAL DAN SOLUSI and tagged , , . Bookmark the permalink. Tinggalkan komentar.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: