سوال ۱۵
عدد یک جای‌گشت عبارت است از تعداد جفت عددهای متوالی که هر دو عدد آن فرد باشند منهای تعداد جفت‌عددهای متوالی که هر دو عدد آن زوج باشند. برای مثال عدد جای‌گشت ۲۴۱۳۵۶ برابر ۱=۱-۲ است. بیشینه‌ی اعداد جای‌گشت‌های ۱ تا ۲۰ چیست؟
- ۰
- ۱
- ۹
- ۱۰
- ۱۹
پاسخ
گزینه (۲) درست است.
راه حل اول: در حالتی که اعداد از ۱ تا ۲۰ پشت سر هم نوشته شوند عدد جای‌گشت مورد نظر برابر $0-0$ یعنی ۰ به دست می‌آید. اگر در همان حال فقط جای دو عدد ۱ و ۲ را با هم عوض کنیم تا به جای‌گشت $1920...213456$ برسیم عدد مورد نظر برابر $1-0$ یعنی ۱ خواهد شد. از این‌جا به بعد به ازای هر دو عدد فردی که بخواهند در کنار هم قرار بگیرند لاجرم دو عدد زوج نیز پیش هم قرار خواهند گرفت و بنابراین عدد مورد نظر برابر $(x+1)-x$ یعنی ۱ خواهد شد.
راه حل دوم: دسته‌ای از اعداد فرد که در کنار هم هستند را $O$ و دسته‌ای از اعداد زوج که در کنار هم هستند را $E$ می‌نامیم. معلوم است که اگر در دسته‌ای $m$ عددد موجود باشد٬ $m-1$ جفت عدد با زوجیت یکسان در کنار هم قرار گرفته‌اند. جای‌گشت مورد نظر به یکی از چهار شکل زیر می‌باشد:
$I)E_1 O_1 E_2 O_2...E_n O_n$
$II)E_1 O_1 E_2 O_2...E_n O_n E_{n+1}$
$III)O_1 E_1 O_2 E_2...O_n E_n$
$IV)O_1 E_1 O_2 E_2...O_n E_n O_{n+1}$
فرض کنید $|E_i|$ و $|O_i|$ به ترتیب نشانگر تعداد اعداد موجود در هر یک از دسته‌های $E_i$ و $O_i$ باشد٬ آن‌گاه اولا معلوم است که $\sum |E_i|= \sum |O_i|=10$ و ثانیا تعداد جفت عددهای متوالی که هر دو عدد آن از نظر زوجیت یکسان باشد در هر یک از آن دو دسته به ترتیب برابر $|E_i|-1$ و $|O_i|-1$ خواهد شد٬ بنابراین در هر یک از چهار حالت اشاره شده عدد خواسته شده به شکل زیر به‌دست می‌آید:
$I)x_1=(|O_1|-1)+(|O_2|-1)+...+(|O_n|-1)-[(|E_1|-1)+(|E_2|-1)+...+(|E_n|-1)] \\ =\sum |O_i|-\sum |E_i|=0$
$II)x_2=(|O_1|-1)+(|O_2|-1)+...+(|O_n|-1)-[(|E_1|-1)+(|E_2|-1)+...+(|E_n|-1)] \\ =\sum |O_i|-\sum |E_i|-1=-1$
$III)x_3=x_1=0$
$IV)x_4=(|O_1|-1)+(|O_2|-1)+...+(|O_n|-1)-[(|E_1|-1)+(|E_2|-1)+...+(|E_n|-1)] \\ =\sum |O_i|-\sum |E_i|+1=1$
در اعداد به‌دست آمده عدد ۱ از همه بیش‌تر است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
