المپدیا

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

ابزار کاربر

ابزار سایت


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

پیچ‌ها و مهره‌ها

$n$ پیچ و $n$ مهره که از نظر ظاهری شبیه به هم هستند٬ داده شده‌اند. می‌دانیم که هر پیچ تنها به یک مهره می‌خورد(با آن هم‌اندازه است) و هیچ دو پیچی هم‌اندازه نیستند.

عمل «آزمون» یعنی برداشتن یک پیچ و یک مهره و امتحان کردن آن‌ها. با این کار تشخیص می‌دهیم که پیچ از مهره بزرگ‌تر است٬ مهره از پیچ بزرگ‌تر است٬ یا این که هر دو هم‌اندازه هستند.

می‌خواهیم با انجام تعدادی عمل «آزمون»٬ کوچک‌ترین پیچ و کوچک‌ترین مهره (که مسلماً به هم می‌خورند) را پیدا کنیم. توجه کنید که نمی‌توان دو مهره یا دو پیچ را مستقیماً با هم مقایسه کرد.

الف) نشان دهید که برای $n = 2$ مسئله را در بدترین حالت می‌توان با دو آزمون حل کرد.

ب) روشی ارائه دهید تا بتوان مسئله را در حالت کلی با $2n-2$ آزمون حل کرد.


ابزار صفحه