المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:تئوری مقدماتی:سوال ۲

سوال ۲

درختی ‎$n$‎ راسی داریم ‎$(n>3)$‎. می‌خواهیم روی هر یال‌ این درخت یکی از اعداد ‎$-1,0,1$‎ را قرار دهیم طوری که به ازای هر یال مجموع یال‌های مجاورش عددی مثبت باشد و همچنین مجموع اعداد یال‌ها کمینه شود. ثابت کنید این مجموع حداکثر ‎$\lfloor \frac{2(n-1)}{3} \rfloor$‎ است. ‎


ابزار صفحه