المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۶:سوال ۵

کیسه‌ها

$n$۲ مهره داریم که روی هر یک عددی نوشته شده است. می‌دانیم هر یک از اعداد ۱ تا $n$ روی دقیقاً دو مهره نوشته شده است. مهره‌ها در $n$ جعبه طوری گذاشته شده‌اند که در هر جعبه دو مهره (با اعداد نه لزوماً یک‌سان) قرار دارند و مهره‌های درون جعبه‌ها دیده می‌شوند. یک مهره از یکی از جعبه‌ها اخیراً گم شده است.

می‌خواهیم از هر جعبه تنها یک مهره برداریم به طوری که از همه‌ی اعداد ۱ تا $n$ مهره‌ای برداشته باشیم.

آیا این کار همواره ممکن است؟ در صورت مثبت بودن پاسخ٬ این موضوع را اثبات کرده و در صورت منفی بودن٬ یک مثال نقض بزنید.


ابزار صفحه