Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۸:سوال یک

خانه‌های دورنگی

یک جدول n×n از اعداد ٬۲٬۱ تا … n داده شده است. در هیچ سطر یا ستونی از این جدول عدد تکراری یافت نمی‌شود؛ به عبارت دیگر در هر سطر یا ستون تمام اعداد ٬۲٬۱ تا … n وجود دارند.

اگر x یک عدد اعشاری باشد٬ x بزرگ‌ترین عدد صحیحِ کوچک‌تر از x است. با این تعریف٬ ثابت کنید که می‌توان n2 تا از خانه‌های این جدول را انتخاب نمود که هیچ زوج از خانه‌های انتخاب شده در یک سطر یا ستون قرار نداشته باشند و به ازای هر عدد 1in حداکثر دو تا از این خانه‌ها شامل عدد i باشند.


ابزار صفحه