Jump to content
Sign in to follow this  
Adri

International Zhautykov Olympiad 2016, Hari Pertama: No 3

Recommended Posts

Di Graphland terdapat 60 kota; setiap dua kota terhubung oleh jalan satu-arah. Buktikan bahwa kita dapat mewarnai empat buah kota berwarna merah dan empat buah kota lain berwarna hijau, sedemikian sehingga setiap jalan yang menghubungkan kota merah ke kota hijau adalah jalan yang terarah dari kota merah ke kota hijau.

 

 

:rock::rock:

Share this post


Link to post
Share on other sites

kurang lebih

Spoiler

lihat degree $v_1,v_2,..,v_60$

menurut karamata $\sum_{i=1}^{60}\dbinom{v_i}{4}\ge 30(\dbinom{30}{4}+\dbinom{29}{4})>3\dbinom{60}{4}$. Maka ada.

 

  • Upvote 1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

×