المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۰

در یک جشن‌واره ‎$m$‎ فیلم سینمایی به نمایش در می‌آید و ‎$n$‎ نفر به داوری فیلم‌ها می‌پردازند. هر داور به هر فیلم نمره‌ی قبول یا رد می‌دهد. می‌دانیم به دلیل نزدیک بودن معیارهای داوران برای قضاوت در مورد فیلم‌ها، هر دو داور حداکثر در مورد ‎$d$‎ فیلم با یک‌دیگر اختلاف عقیده دارند. در این جشن‌واره روش انتخاب فیلم‌های برگزیده به این ترتیب است که در مورد هر یک از ‎$m$‎ فیلم یک گروه ‎$\frac{n}{2}$‎ نفری از داوران به تصادف انتخاب می‌شوند (‎$n$‎ حتماً عددی زوج است) و نمره‌ی آن‌ها در مورد فیلم مورد نظر بررسی می‌شود. فیلم در صورتی برگزیده می‌شود که بیش از نیمی از آن‌ها به فیلم نمره قبول داده باشند.

ثابت کنید فاصله‌ی مجموعه‌ی فیلم‌های مورد قبول هر داور با مجموعه‌ی برگزیده نمی‌تواند بیش‌تر از ‎$4d$‎ باشد. فاصله‌ی دو مجموعه برابر است با تعداد عناصری که‎ دقیقا‎ً‎ در یکی از دو مجموعه عضویت دارند.


ابزار صفحه