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.

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.

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.

This entry was posted on Wednesday, October 28th, 2009 at 7:00 am and is filed under Math and Science, Updates. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

20 Responses to Olimpiad Matematik Kebangsaan 2009

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.

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.

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).

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…

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.

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.

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.

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.

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)

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).

Participate in the World's Largest Math Competition. Contest Day: 26 March 2015!

BEAVER INFORMATICS COMPETITION

To be held for the first time in Malaysia. Tentative: August 2015. Stay tuned!

Order My Books

Click on image for more details

My Amazon.com Wishlist

Books as gifts

SUHAIMI RAMLY

I am an entrepreneur and educator. I am based in Kuala Lumpur, Malaysia.

Many people know me as Bal. This is the nickname that I am stuck with since high school.

My day job is running two companies I founded in 2007: Aidan Corporation (an IT company) and ArdentEdu (an educational consulting company). Both companies are based in KL.

Since 2006, I have been training the Malaysian national team to the International Mathematical Olympiad (IMO). Also, I volunteer as an MIT Educational Counselor. I conduct interviews for MIT applicants from Malaysia.

I founded the Malaysian Informatics and Programming Society (MIPS) in 2011, to disseminate algorithmic thinking and programming education among high school students. MIPS run the Malaysian Computing Competition, which is open to all Malaysian school students, and the Malaysian Computing Olympiad, which is an invitation-only programming contest.

Since 2012, I am the Director of Kangaroo Math Competition (KMC) Malaysia. KMC is the largest math competition in the world, with more than 6 million participants annually.

To know more about me, click on the About page.

Welcome to my website. Don't forget to leave comments.

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

argh aku nak tido.

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.

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.

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).

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…

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.

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!

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)."

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.

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.

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

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).

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.

clique = complete graph

http://en.wikipedia.org/wiki/Complete_graph

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)

I see, that is connected component.

http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29

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

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).

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^^)

Thank you🙂