ساختن جایگشتی که میانگین هیچ دو عددی بین آن دو نباشد
رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ
رساندن حداقل یک مهره در جدول $2 ×n$ و $2^n$ مهره
دریک تورنمنت بدون تساوی تیمی هست که از بقیه‌ی تیم ها یا شخصا برده یا با یک واسطه!
بازی با سکه ها: 2001 سکه را به پشت برگردانید
حرکت دادن خانه‌ی خالی در جدول پر شده از دومینو ها
حذف چوب کبریت ها از یک جدول n در n
$n$ لامپ و $m$ کلید داریم. هر کلید به تعدادی لامپ متصل است و می‌دانیم هر لامپ حداقل به یک کلید متصل است. در ابتدا تمام کلیدها در وضعیت ۰ قرار دارند و تمام لامپها خاموش اند. با تغییر وضعیت هر کلید تمام لامپ‌های متصل به آن تغییر وضعیت می‌دهند. ثابت کنید میتوان به گونه‌های کلیدها را تغییر وضعیت داد که حداقل $\lceil n/2 \rceil$ لامپها روشن شوند.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 06:47:04 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 10:29:48 -0500 امیر شکریاز اصل میانگین هم میشه استفاده کرد که در گراف 2 بخشی یک طرف حالات زدن کلید ها که با توجه به اینکه تعداد کلید ها برابر n هست میشه $2^n$و طرف دیگه لامپها که تعدادشون m ست
اگر بخوایم یالهارو پیدا کنیم نمیتونیم درجات حالات کلید زدن رو بشمریم اما میتونیم بشمریم که هر لامپ با چند حالت کلید زدن میتونه روشن بشه خوب یک لامپ (مثلا L)که به یک سری کلید وصله رو در نظر میگریم فرض کنیم L به k کلید وصله
با توجه به اینکه تمام لامپها خاموشن باید فرد بار کلیدهای تصل به لامپهارو بزنیم تا روشن بشن یعنی میخوایم از کلید هایی که به لامپ L متصلند زیرمجموعه های فرد عضوی انتخاب کنیم که تعداد حالاتی که میتونیم کلید رو بزنیم و لامپ روشن بشه $2^{ k-1} $
هست و بقیه کلید ها هم تعدادشون n-k تا میشه که حالت کلید اینکه روشون بزنیم $2^{n-k}$هست اگه این حالات رو در هم ضرب کنیم که میشه $ 2^{n-1} $یعنی تعداد حالت های انتخاب کلید ها به طوریکه لامپ موردنظر ما روشن بشه$ 2^{n-1}$هست پس تعداد یالهای گراف میشود $2^{n-1}$ ضربدر m.
حالا طبق اصل میانگین سقف 2 به توان n-1 ضربدر m روی 2 به توان n ، که برابر $[m/2]$ است حداقل نصف لامپها رو میتوان روشن کرد
با استقرا روی $m$ (تعداد کلیدها) حل میکنیم:
یکی از کلیدها و تمام لامپ‌های متصل به آن را حذف شده درنظر بگیرید. فرض کنید تعداد لامپ‌هایی که حذف میشود $k$ عدد باشد. طبق فرض استقرا با باقی کلیدها میتوان حداقل $\lceil \frac{m-k}{2} \rceil$ لامپ از لامپ‌های دیگر را روشن کرد. حال لامپ‌های حذف شده را در نظر بگیرید، با تغییر در وضعیت کلیدها ممکن است بعضی از آن‌ها روشن شده باشند. برای این لامپها دو حالت زیر ممکن است: