المپدیا

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

ابزار کاربر

ابزار سایت


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

ماتریس کم‌تنوع

یک ماتریس ‎$n \times n$‎ که با اعداد ‎$1‎, ‎2‎, ‎\dots‎, ‎n^2$‎ پر شده است داریم. رتبه‌ی یک درایه در این ماتریس برابر تعداد اعداد بزرگ‌تر از این درایه در کل سطر و ستونش می‌باشد. بنابراین رتبه‌ی هر درایه عددی بین ‎$0$‎ تا ‎$2n-2$‎ است. تعداد رتبه‌های مختلف که در این ماتریس مشاهده می‌شود برابر تنوع آن است. کم‌ترین تنوع در بین همه‌ی ماتریس‌های ‎$n \times n$‎ با درایه‌های متفاوت را ‎$T(n)$‎ بنامید. ثابت کنید ‎$T(ab) \leq T(a)T(b)$‎.


ابزار صفحه