Olimpiad Matematik Kebangsaan 2009

Keputusan Olimpiad Matematik Kebangsaan 2009 (OMK 2009) sudah siap diproses. Insya Allah keputusan tersebut akan diterbitkan di laman web PERSAMA (http://www.persama.org.my/) pada akhir minggu ini atau awal minggu hadapan. Tahniah kepada para peserta dan sekolah yang menang.

logopersama

Para peserta terbaik dari OMK akan disenaraipendek dan dijemput untuk menghadiri kem latihan International Mathematical Olympiad 2010 (IMO 2010), bertempat di UiTM Shah Alam, Selangor. IMO merupakan pertandingan matematik paling berprestij di dunia, membabitkan pelajar-pelajar terpilih dari lebih 100 buah negara. Pertandingan IMO diadakan secara tahunan di bandar-bandar terpilih. IMO 2010 akan diadakan di Astana, Kazakhstan pada 2-15 Julai 2010. Para pelajar yang disenaraipendek ke kem tersebut akan melalui beberapa sesi ujian tapisan daripada bulan Januari hingga April untuk memilih enam peserta terbaik yang akan mewakili negara ke IMO 2010. Insya Allah, jika tiada halangan, saya akan mengetuai kontinjen IMO 2010 kelak.

Lawati laman web rasmi IMO di http://www.imo-official.org/ dan laman web rasmi IMO 2010 (belum siap sepenuhnya) di http://www.imo2010org.kz/ .

Ini adalah contoh soalan IMO sebenar:

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. The number of members of a clique is called its size.

In this competition, the largest size of a clique is even. Prove that the competitors can be arranged in two rooms A and B such that the largest size of a clique contained in room A is the same as the largest size of a clique contained in room B.

Soalan ini diambil daripada IMO 2007 yang berlangsung di Hanoi, Vietnam.

ADDENDUM: Official Solution to IMO 2007

20 Responses to Olimpiad Matematik Kebangsaan 2009

  1. samah says:

    dammit bal… sejam aku dok conteng2 atas kertas cuba solve.

    argh aku nak tido.

  2. samah says:

    ok jap jap… tak puas hati… hahaha tapi aku nak try trivial case and one extreme case saje.

    katala largest clique is M and everybody knows everyone.

    since M is even, bole la bahagi 2, so jadi M/2 an M/2.

    so dah setel. actually the better proof is if M is even, M can always be reduced to two lesser but equally-sized cliques (ni maybe kene guna clue ‘each two are friends’ tapi aku tak tahu haha).

    how about if there are cliques N where M/2 < N < M?

    kalau N is even, by above it is always reduceable. what if N is odd, or better yet N = M-1. assume wujud jugak second largest click M-1, and also the largest click M. M duk dalam bilik A, M-1 duk dalam bilik B.

    so what we can do, kita boleh amik sorang dari M and letak dalam bilik B.

    so now size(A) = M-1, and size of B mesti M-1 and not M (even though dah tambah sorang), sbb kalau dia jadi M, then M was never the largest clique to begin with.

    arghhh.

    damn u bal. tido2.

  3. suhaimiramly says:

    Very promising. Semua yg ko kata so far alright (of course, we are not discussing the general case yet). In particular you discussed the case where there exist two disjoint cliques of size M and M-1.

    “assume wujud jugak second largest click M-1, and also the largest click M. M duk dalam bilik A, M-1 duk dalam bilik B. so what we can do, kita boleh amik sorang dari M and letak dalam bilik B.

    so now size(A) = M-1, and size of B mesti M-1 and not M (even though dah tambah sorang), sbb kalau dia jadi M, then M was never the largest clique to begin with.”

    Ada one subtle point here. Largest clique is not unique. Kata lah kita ada 2 largest clique of size M, and these two largest cliques share M-1 members. Maknanya both largest cliques tu cuma differ by one person (call them X and Y).

    If we use your process above, then we might still have size(A)=M in the end, walaupun dah buang sorang dari clique tu, sbb mungkin yg kena buang tu ialah X.

    Kekeke soalan ni memang cibai punya case-by-case analysis. tapi a good problem for computer science people. banyak IMO contestant kantoi soalan ni pasal tak biasa thinking in terms of algorithms. student msia semua dapat 0.

  4. suhaimiramly says:

    By the way, aku ada omit satu ayat dlm soalan tu. Dalam soalan sebenar dia bagitau “Friendship is always mutual”. So the phrase “each two of them are friends” is nothing significant (it’s just the definition of a clique).

    Best way, cuba pikir in terms of graph theory. competitors = vertices, and friendships = edges. Then clique = complete graph (each pair of vertices is joined by an edge).

  5. samah says:

    hahaha itula memang dah pk pasal graph pun.. ok ok jap nak buat balik.

    mula2, kita identify all possible cliques (all non-related complete graphs).

    then, kita identify the size of the largest clique, say M.

    now we partition as such:

    largest clique M goes into room A.

    others go into room B.

    sekarang ada beberapa possible cases.

    case 1:

    in room B exists the largest clique of size M jugak. So setel.

    case 2:

    in room B exists the largest clique of size between 0 to M – 1.

    kalau camni, kita kene tgk balik kat room A. since M is a clique and a complete graph, aku boleh tarik one competitor out of room A and put in room B.

    this can be proved since size is M, so kita step backward je la. to create M, all we need is to add one connected competitor to a clique of size M-1. So M is always reduceable to M-1.

    what will happen is size(A) = M-1, and size of (B) still ranges from 0 to M-1.

    keep on reducing until we hit size(A) = size(B).

    tapi ada satu edge case. this is when M is the only clique, all are friends with everyone, and it is the largest, and it is odd.

    kalau kita split M equally, there is a possibility that it is M/2 + 1 in room A, and M/2 in room B.

    if we take one out from room A and letak kat room B, we will only switch (A = M/2, B = M/2 + 1) pulak.

    tapi since dia dah kata M is even, so we’re safe.. phew….

    itu je la yang aku leh pk. probably ada lagi edge cases aku tak consider, or maybe dah cuma tak kemas. hahaha…

  6. suhaimiramly says:

    OK good. Let us iron out the details.

    Put one of the largest cliques in A, and the rest in B.

    Now, size(A)=M, and 0<=size(B)size(B).

    Any time we move one person from A to B, we decrease size(A) by exactly 1, and we increase size(B) either by 0 or 1.

    Therefore, eventually we must have the situation where size(A)<=size(B)<=size(A)+1. (*)

    If size(A) = size(B), we are done.

    The only case left is when size(B) = size(A) + 1. (**)

    ========================
    PS:

    Kalau ikut skema pemarkahan IMO 2007,
    – put a largest clique in A and the rest in B = 1 point;
    – getting to (*) = 1 point;
    – the remaining case (**) = 5 points. This is actually the difficult part.

    Look at the statistics for Problem 3:
    http://www.imo-official.org/year_statistics.aspx?year=2007

    Dua students je dapat markah penuh…437 students dapat 0. This is actually the hardest problem ever to appear in IMO.

  7. suhaimiramly says:

    Kekeke jgn terpengaruh dgn result IMO tu…tu budak2 skolah menengah je, lagipun diorang ada limited time to solve 3 problems, so ramai tak attempt pon soalan ni.

    Kalau larat pikir lagi…you can do it!

  8. suhaimiramly says:

    kacau plak html tags ni.

    “Now, size(A)=M, and 0<=size(B)size(B)."

    sepatutnya

    "Now, size(A)=M, and 0<=size(B)<=M-1 [we're done if size(B)=M]. Clearly size(B)<size(A)."

  9. samah says:

    ok, katala size(B) is now size(A) + 1.

    meaning the last state before that was

    case 1:
    size(A+1) > size(A) (bila ubah +1 pada B, – 1 dari A)

    atau

    case 2:
    size(A+1) = size(A+1) (bila ubah +0 pada B, -1 dari A)

    kalau case 2: we’re done sbb dah sama in the first place.

    sekarang case(1)

    size(A+1) > size (A)

    since bila kita move 1 from A to B, and it becomes size(A) < size (A+1), that particular vertex connects both cliques.

    so originally, when we started out on the algorithm, the largest clique was 1 + 2A vertices = odd number

    since the largest clique is supposed to be even, this case would never arise.

  10. suhaimiramly says:

    Hehehee…alright so far, tapi kena hair-splitting lagi:

    Currently, size(B)=size(A)+1.
    Say size(B)=k+1, and size(A)=k.

    Assume Case 1 holds (the nontrivial case). This means that in the last step, we had moved a vertex X from A to B, changing size(A) by -1 and size(B) by +1.

    Let the original largest clique be M (the one we put in A at the beginning).

    When we send X to B in the last move, the largest clique in B is not necessarily formed only by vertices from M. In other words, (B intersect M) is <= k+1, not necessarily = k+1.

    So we cannot conclude that M = size(A) + size(B) = k+(k+1) = 2k+1.

    Hope this is clear.

  11. suhaimiramly says:

    kekekeeke untuk menguji mental toughness dengan lebih ganas lagi, aku dah letak addendum: official solution.

  12. samah says:

    hahaha this is why aku fail theoretical / algorithms dulu… haw haw haw.

    hmm… tak paham asal (B intersect M) is <= k+1 and not necessarily k + 1.

    ok patah balik yang first case tu.. M largest clique in A, the rest of the other cliques dalam B.

    if we take one vertex out of M, that vertex cannot contribute to any other clique in B initially.

    now assume there actually exists a clique N dalam B, in which when we moved the very first vertex from M, N jadi N + 1.

    so maksudnya M and N are connected. therefore M cannot be the largest clique. (should be the larger clique of M combined with N).

  13. suhaimiramly says:

    ok jap, aku rasa ada fundamental misunderstanding di sini:

    “ok patah balik yang first case tu.. M largest clique in A, the rest of the other cliques dalam B.

    if we take one vertex out of M, that vertex cannot contribute to any other clique in B initially.”

    This is incorrect. A single vertex from M can increase the size of a clique in B. This is because the cliques are not disjoint.

    Although M is the largest clique, its members might form smaller cliques with other vertices outside M.

    “now assume there actually exists a clique N dalam B, in which when we moved the very first vertex from M, N jadi N + 1.

    so maksudnya M and N are connected. therefore M cannot be the largest clique. (should be the larger clique of M combined with N).”

    This is also incorrect. M and N connected does not mean that (M union N) is a clique. They might share only one member.

    Therefore, the largest clique in B, need not be formed only by the members of M. Sebab tu lah (B intersect M) <= k+1, where k+1 is the size of largest clique in B.

  14. samah says:

    oh ok ok paham.. aku ingat as long as A kenal B, B kenal C, then its size is 3, even though A tak kenal C.

    hahahaha… anyway thanks for the question… rasa cam exercise otak sikit after so longgggggggggggggggggggggg. (eleh cam la kat universiti dulu bole solve pun hahahahaha)

  15. Simon says:

    Is there any age limit for the IMO camp 2010? Or the selection just based on the result of OMK?

  16. suhaimiramly says:

    Age limit: We invite students Form 4 or younger (in 2009 school year) to attend the IMO 2010 camp.

    Selection is based on OMK, but sometimes might include few students who did not take OMK but performed exceptionally well in well-known competitions, such as winning a Medal in the Australian Mathematics Competition or getting a perfect score in the American Mathematics Competition (AMC8, AMC10, AMC12).

  17. Simon says:

    Thanks for the information..
    Too bad..I’m form 5 this year..
    Anyway, wish M’sia IMO team all the best next year(get a gold medal^^)

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

%d bloggers like this: