سوال ۲۶

قرار است ‎۱۰۰‎ نفر معلم از بین ‎۴‎ دانش‌آموز به‌نام‌های ‎$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$ به فینال می‌رسد.