سوال ۲۶
قرار است ۱۰۰ نفر معلم از بین ۴ دانش‌آموز به‌نام‌های $C$، $B$، $A$ و $D$ یکی را به روش «حذفی»انتخاب کنند. این کار با معرفی دو نفر از ۴ دانش‌آموز شروع می‌شود. معلمان رأی می‌دهند و فردی که رأی کم‌تری آورد حذف می‌شود. سپس بین فرد برنده و یکی از دو نفر دیگر رأی‌گیری می‌شود و در بار آخر بین برنده‌ی بار دوم و تنها نفر باقی‌مانده رأی‌گیری می‌شود تا برنده‌ی نهایی معین شود. مدیر مدرسه در هر مرحله دو دانش‌آموزی که به رأی گذاشته می‌شوند را انتخاب می‌کند. او قبلاً در یک نظرخواهی از معلمان می‌داند که آن‌ها به‌صورت زیر رأی خواهند داد:
۱۷نفر: $C > A > D > B$
۳۲نفر:$A > B > D > C$
۳۴نفر:$D > B > C > A$
۱۷نفر:$B > A > C > D$
(به عنوان مثال ۳۴ نفر $D$ را به $B$، $B$ را به $C$ و $C$ را به $A$ ترجیح می‌دهند.)
مثلاً اگر $A$ و $B$ به‌رأی گذاشته شوند، $B$ با اختلاف دو رأی برنده می‌شود. با این فرض که هیچ معلمی رأی خود را عوض نمی‌کند، مدیر مدرسه ممکن است بتواند به‌ترتیبی دانش‌آموزان را در هرمرحله به‌رأی بگذارد که دانش‌آموز مورد نظرش انتخاب شود. مدیر می‌تواند کاری کند که آخرین مرحله‌ی رأی‌گیری بین دانش‌آموزان زیر باشد:
- $A$ و $B$
- $C$ و $D$
- $B$ و $C$
- $A$ و $C$
- همه‌ی حالت‌های ممکن
پاسخ
گزینه (؟) درست است.
$I$. برای آن که $A$ و $B$ به مرحله‌ی نهایی برسند الگوریتم زیر اجرا می‌شود:
- $C$ و $D$ باهم قیاس می‌شوند که $D$ برنده می‌شود.
- $A$ و $D$ باهم قیاس می‌شود که $A$ برنده شده و به همراه $B$ به فینال می‌رسد.
$II$. برای آن که $C$ و $D$ به مرحله‌ی نهایی برسند الگوریتم زیر اجرا می‌شود:
- $A$ و $B$ باهم قیاس می‌شوند که $B$ برنده می‌شود.
- $B$ و $D$ باهم قیاس می‌شوند که $D$ برنده شده و به همراه $C$ به فینال می‌رسد.
$III$. برای آن که $B$ و $C$ به مرحله‌ی نهایی برسند الگوریتم زیر اجرا می‌شود:
- $A$ و $D$ باهم قیاس می‌شوند که $A$ برنده می‌شود.
- $A$ و $C$ باهم قیاس می‌شوند که $C$ برنده شده و به همراه $B$ به فینال می‌رسد.
$IV$. برای آن که $A$ و $C$ به مرحله‌ی نهایی برسند الگوریتم زیر اجرا می‌شود:
- $B$ و $D$ باهم قیاس می‌شوند که $D$ برنده می‌شود.
- $A$ و $D$ باهم قیاس می‌شوند که $A$ برنده شده و به همراه $C$ به فینال می‌رسد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
