رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ
رساندن حداقل یک مهره در جدول $2 ×n$ و $2^n$ مهره
دریک تورنمنت بدون تساوی تیمی هست که از بقیه‌ی تیم ها یا شخصا برده یا با یک واسطه!
بازی با سکه ها: 2001 سکه را به پشت برگردانید
حرکت دادن خانه‌ی خالی در جدول پر شده از دومینو ها
حذف چوب کبریت ها از یک جدول n در n
جایگشتی از اعداد طبیعی $1$ تا $n$ را زیبا می‌گوییم اگر به ازای هیچ$1 \leq i,j\leq n$ میانگین $i$ و $j$ بین این دو قرار نگرفته باشد. ثابت کنید برای هر عدد طبیعی $n$، یک جایگشت زیبا از اعداد طبیعی یک تا $n$ وجود دارد.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 09:23:58 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-27 08:26:52 -0500 امیر شکریمسئله را به ازای توان‌های دو حل می‌کنیم. برای $n$هایی که توان دو نیستند میتوانیم جایگشت زیبای کوچکترین توان دو بزرگتر از $n$ را درنظر بگیریم و اعداد بزرگتر از $n$ را از آن برداریم. به وضوح، نتیجه کماکان یک جایگشت زیبا خواهد بود.
اثبات برای توان‌های ۲: از استقرا استفاده می‌کنیم. برای $n=2^1$ جایگشت $1,2$ زیباست. فرض می‌کنیم برای $n=2^k$ جایگشت زیبای $\pi$ که عبارت است از $\pi_1, \pi_2,...,\pi_n$ وجود داشته باشد. حال دنباله‌ی زیر را در نظر بگیرید: $$(2\pi_1-1), (2\pi_2-1),...,(2\pi_n-1),2\pi_1, 2\pi_2,..., 2\pi_n$$
این دنباله شامل اعداد طبیعی یک تا $2^{k+1}$ است. اعداد فرد در سمت چپ و اعداد زوج در سمت راست قرار دارند. ثابت می‌کنیم این دنباله یک جایگشت زیبا از این اعداد است. سه حالت زیر را داریم:
بنابراین برای $n=2^{k+1}$ نیز حداقل یک جایگشت زیبا وجود دارد.
راه حل مستقیم برای ساختن جایگشت:
فرض کنیم عدد $n$ در مبنای ۲، $k$ بیت دارد (یعنی $n<2^k$). $n$ دومینوی چوبی می‌آوریم. در قسمت بالای دومینوی $i$ اُم عدد $i$ و در پایین آن عدد $f(i)$ را می‌نویسیم. $f(x)$ برابرست با مقدارِ مبنای دهِ قرینه‌ی نمایش $k$ بیتیِ عدد $x$ در مبنای ۲. (مثال در پاراگراف بعدی) اکنون اگر دومینوها را بر حسب عدد پایینی‌شان از کوچک به بزرگ مرتب کنیم، عدد بالایی دومینوها جایگشت خواسته شده را نشان می‌دهند!
برای مثال اگر $n$ برابر با ۱۳ باشد، آن‌گاه $k$ برابر با ۴ است و $f(1)$ برابرست با قرینه‌ی $(0001)_2$ که می‌شود $(1000)_2$ یا همان ۸. به همین‌ترتیب برای همان $n=13$ خواهیم داشت $f(2)=4$، $f(3)=12$، $f(4)=2$ و $f(5)=10$ و ... $f(13)=11$.
اثبات:
فرض کنید دو عدد $i$ و $j$ وجود دارند به صورتی که میانگین آن‌دو یعنی $x=\frac{i+j}{2}$ با این رویه‌ی ما، بین آن دو قرار گرفته است. نمایش مبنای دوی $i$ و $j$ را زیر هم می‌نویسیم. فرض کنید سمت راست‌ترین بیتی که $i$ و $j$ در آن تفاوت دارند (یکی‌شان صفر و یکی‌شان یک است)، بیت $b$ است ($b$ نمی‌تواند سمت‌راست‌ترین بیت باشد. چرا؟).
اکنون بیت سمت راستیِ بیتِ $b$ را در نظر می‌گیریم. هر دو عدد $i$ و $j$ در این بیت مقدار برابر (مثلاً $v$) دارند ولی عدد $x$ در همین بیت باید مقدار عکس $v$ (یا به‌عبارتی $1-v$) را داشته باشد. (چرا؟ راهنمایی: $i+j = 2x$). واضح‌ست که اکنون وقتی برای ساختن $f()$ها همه‌ی بیت‌ها را برعکس کرده و سپس مرتب می‌کنیم، اگر $v$ یک باشد، آن‌گاه $x$ حتماً پیش از هر دوی $i$ و $j$ قرار می‌گیرد؛ و اگر $v$ صفر باشد $x$ حتماً بعد از هر دوی $i$و $j$ قرار می‌گیرد (چرا که در باارزش‌ترین بیت متفاوت‌شان که همان بیتِ کناریِ بیت $b$ است با آن دو تفاوت دارد). پس امکان ندارد که $x$ بین $i$ و $j$ بیافتد!
