المپدیا

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

ابزار کاربر

ابزار سایت


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

استاد قلب‌ها!

فرض کنید $n$ و $d$ دو عدد طبیعی باشند. $\langle a_1, a_2, \ldots, a_n \rangle$ را دنباله‌ای از اعداد طبیعی در نظر بگیرید. گوییم $a_i$ و $a_j$ تشکیل یک زوج سلطانی مرتبه $d$ می‌دهند، اگر شروط زیر برقرار باشد:

  • $i < j$
  • $a_i > a_j$
  • $a_i \overset{d}{\equiv} a_j$

به دو قسمت زیر پاسخ دهید:

  1. در میان دنباله‌هایی که مجموع اعدادشان $s$ است، بیشینه‌ی تعداد زوج‌های سلطانی مرتبه $d$ چیست؟ پاسخ را بر حسب $s$ و $d$ بیابید. (۵۰ نمره)
  2. در میان دنباله‌های نزولی $n$ عنصره که عدد تکراری ندارند، کمینه‌ی تعداد زوج‌های سلطانی مرتبه $d$ چیست؟ پاسخ را بر حسب $n$ و $d$ بیابید. (۵۰ نمره)

ابزار صفحه