سوال ۱۵
عدد یک جای‌گشت عبارت است از تعداد جفت عددهای متوالی که هر دو عدد آن فرد باشند منهای تعداد جفت‌عددهای متوالی که هر دو عدد آن زوج باشند. برای مثال عدد جای‌گشت ۲۴۱۳۵۶ برابر ۱=۱-۲ است. بیشینه‌ی اعداد جای‌گشت‌های ۱ تا ۲۰ چیست؟
- ۰
- ۱
- ۹
- ۱۰
- ۱۹
پاسخ
گزینه (۲) درست است.
راه حل اول: در حالتی که اعداد از ۱ تا ۲۰ پشت سر هم نوشته شوند عدد جای‌گشت مورد نظر برابر 0−0 یعنی ۰ به دست می‌آید. اگر در همان حال فقط جای دو عدد ۱ و ۲ را با هم عوض کنیم تا به جای‌گشت 1920...213456 برسیم عدد مورد نظر برابر 1−0 یعنی ۱ خواهد شد. از این‌جا به بعد به ازای هر دو عدد فردی که بخواهند در کنار هم قرار بگیرند لاجرم دو عدد زوج نیز پیش هم قرار خواهند گرفت و بنابراین عدد مورد نظر برابر (x+1)−x یعنی ۱ خواهد شد.
راه حل دوم: دسته‌ای از اعداد فرد که در کنار هم هستند را O و دسته‌ای از اعداد زوج که در کنار هم هستند را E می‌نامیم. معلوم است که اگر در دسته‌ای m عددد موجود باشد٬ m−1 جفت عدد با زوجیت یکسان در کنار هم قرار گرفته‌اند. جای‌گشت مورد نظر به یکی از چهار شکل زیر می‌باشد:
I)E1O1E2O2...EnOn
II)E1O1E2O2...EnOnEn+1
III)O1E1O2E2...OnEn
IV)O1E1O2E2...OnEnOn+1
فرض کنید |Ei| و |Oi| به ترتیب نشانگر تعداد اعداد موجود در هر یک از دسته‌های Ei و Oi باشد٬ آن‌گاه اولا معلوم است که ∑|Ei|=∑|Oi|=10 و ثانیا تعداد جفت عددهای متوالی که هر دو عدد آن از نظر زوجیت یکسان باشد در هر یک از آن دو دسته به ترتیب برابر |Ei|−1 و |Oi|−1 خواهد شد٬ بنابراین در هر یک از چهار حالت اشاره شده عدد خواسته شده به شکل زیر به‌دست می‌آید:
I)x1=(|O1|−1)+(|O2|−1)+...+(|On|−1)−[(|E1|−1)+(|E2|−1)+...+(|En|−1)]=∑|Oi|−∑|Ei|=0
II)x2=(|O1|−1)+(|O2|−1)+...+(|On|−1)−[(|E1|−1)+(|E2|−1)+...+(|En|−1)]=∑|Oi|−∑|Ei|−1=−1
III)x3=x1=0
IV)x4=(|O1|−1)+(|O2|−1)+...+(|On|−1)−[(|E1|−1)+(|E2|−1)+...+(|En|−1)]=∑|Oi|−∑|Ei|+1=1
در اعداد به‌دست آمده عدد ۱ از همه بیش‌تر است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
