Processing math: 14%

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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


ابزار صفحه