فهرست مندرجات
سوالات ۱۹ تا ۲۱
روال جام حذفی بدین صورت است که $2^n$ تیم در $n$ مرحله با هم مسابقه می‌دهند به نحوی که در هر مرحله هر تیم با یک تیم دیگر مسابقه می‌دهد (مثلا در مرحله‌ی اول $2^{n-1}$ مسابقه انجام می‌شود) و تیم‌هایی که شکست بخورند حذف می‌شوند. تیم‌های پیروز شده (نیمه‌ی دیگر تیم‌ها) به مرحله‌ی بعد می‌روند و دوباره به همین ترتیب مسابقه می‌دهند تا جایی که فقط یک تیم باقی بماند که تیم قهرمان نامیده می‌شود.
هر تیم عددی بین ۰ تا ${2^n}-1$ دارد که قدرت آن تیم را نیز نشان می‌دهد (قدرت هیچ دو تیمی با هم برابر نیست). در مسابقه‌ی بین دو تیم، تیمی پیروز خواهد شد که قدرت بیشتری داشته باشد مگر در شرایطی که هر سوال مشخص می‌کند.
سوال ۱۹
این مسابقات با شرکت 64 تیم برگزار می‌شود ($n=6$). در یک مسابقه اگر قدرت دو تیم را در مبنای دو بنویسیم و همه‌ی رقم‌های آنها به جز یکی برابر باشند هر دو تیم ممکن است پیروز شوند، در غیر این صورت تیم قوی‌تر پیروز می‌شود. برای مثال اگر $2$ و $10$ با هم مسابقه بدهند، هر دو تیم می‌توانند پیروز شوند. اما اگر $16$ و $7$ با هم مسابقه بدهند، حتما $16$ پیروز خواهد شد. ضعیف‌ترین تیمی که ممکن است قهرمان شود چه تیمی است؟
- ۱
- ۹
- ۱۵
- ۰
- ۳۱
پاسخ
گزینه (۴) درست است.
تمامی تیم‌ها را به ترتیب از کوچک به بزرگ قرار دهید و مسابقات را با این چینش انجام دهید. در این صورت هر تیم با شماره‌ی زوج با تیم حریفش تنها در رقم یکان متفاوت است. پس تیم‌های زوج می‌توانند برنده باشند. بدین ترتیب به حالتی می‌رسیم که تمام اعداد زوج صعود کرده‌اند. همین روند را برای 32 بعدی انجام دهید (رقم یکان همه صفر است و می‌توان همه‌ی اعداد را بر 2 تقسیم کرد تا به اعداد 1 تا 31 برسیم. به ازای این اعداد هم همین روال را انجام دهید. با تکرار این کار در مراحل بعدی می‌توان به حالتی رسید که تیم با قدرت صفر برنده‌ی مسابقات شود.
سوال ۲۰
در یک جام حذفی $32$ تیم حضور دارند ($n=5$) و چهار تیم $31$، $23$، $14$ و $5$ آمادگی کافی ندارند و ممکن است در یک مسابقه به طور اتفاقی شکست بخورند. با این شرایط ضعیف‌ترین تیمی که ممکن است قهرمان شود چه تیمی است؟
- ۱۵
- ۱
- ۱۶
- ۴
- ۰
پاسخ
گزینه (۲) درست است.
می‌دانیم تیم قهرمان باید ۵ بازی را ببرد و در شرایط سوال، ۴ تیم گفته شده است که ممکن است در شرایطی از تیمی ضعیف‌تر شکست بخورند. پس تیم ۰ نمیتواند قهرمان شود.
حال می‌خواهیم ساختاری ارائه دهیم که طی آن تیم ۱ قهرمان شود. تیم ۱ به ترتیب با تیم‌های ۰ و ۵ و ۱۴ و ۲۳ و ۳۱ بازی کند و در ۴ مسابقه‌ی آخر تیم حریف به طور اتفاقی شکست می‌خورند.
تیم ۵ با تیم‌های ۲ و ۱ و تیم ۱۴ با تیم‌های ۶ و ۴ و ۱ و تیم ۲۳ با تیم‌های ۱۳ و ۱۲ و ۱۰ و ۱ و تیم ۳۱ با تیم‌های ۳۰ و ۲۹ و ۲۷ و ۲۲ و ۱ بازی خواهند کرد و طی این ساختار تیم ۱ قهرمان می‌شود.
سوال ۲۱
در یک جام حذفی $16$ تیم حضور دارند ($n=4$) و هر تیم ممکن است به طور اتفاقی در یک مسابقه پیروز شود. ضعیف‌ترین تیمی که ممکن است قهرمان شود چه تیمی است؟
- ۲
- ۷
- ۶
- ۴
- ۵
پاسخ
گزینه (۴) درست است.
ابتدا اثبات می‌کنیم تیم ۳ نمیتواند قهرمان شود. چون هر تیم برای قهرمانی باید ۴ بازی را ببرد و اگر فرض کنیم تیم ۳ قهرمان شده است باید حتما با هر سه تیم ضعیف‌تر از خودش بازی کند زیرا یک بازی را فقط می‌تواند از تیم قوی‌تری پیروز شود، پس در یکی از بازی‌های فینال یا نیمه نهایی باید تیم ۳ از تیمی ضعیف‌تر از خود پیروز شود.
یعنی آن تیم حداقل باید ۲ بازی را پیروز شده باشد تا به آن مرحله رسیده باشد که با توجه به اینکه هر ۳ تیم ضعیف‌تر از ۳ از خود ۳ شکست خواهند خورد پس هیچ کدام از این تیم‌ها نمیتواند ۲ پیروزی داشته باشد (یک بازی را می‌توانند از تیم قوی‌تر ببرند و تیم ضعیف‌تری نیز وجود ندارد که از آن ببرند) تا به نیمه نهایی برسند پس تیم ۳ نمیتواند قهرمان شود.
حال ساختاری حریصانه برای قهرمانی تیم ۴ ارائه می‌دهیم:
تیم ۴ با تیم‌های ۱ و ۲ و ۳ و ۱۵ بازی می‌کند و تیم ۱۵ با تیم‌های ۱۴ و ۱۳ و ۱۲ و ۴ بازی می‌کند. تیم ۳ با تیم‌های ۰ و ۷ و ۴ بازی می‌کند و تیم ۲ با تیم‌های ۶ و ۴ بازی می‌کند و همچنین تیم ۱ با تیم ۴ بازی می‌کند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
