سوال ۱- جدول n*n از اعداد ۱ تا n داده شده...
سوال ۲- برش نواحی یک جدول n در n
سوال ۴ - روشی برای انتخاب سالن انتظار در هر روز و دیدن تلویزیون آن در شهر المپیادی‌ها
سوال 5- احداث جاده و مرکز پلیس در شهرهای کشور علی کوچولو
سوال 6- وزن کم ترین زبان n کلمه ای که هم پیشوند -آزاد باشد و هم پسوند-آزاد
سوال ۷- مجموعه‌ی سه تایی های پایدار
سوال ۸- دایره‌های دوبه‌دو نامتقاطع روابط
سوال 2- قورباغه‌ي پهلوان روی محور اعداد صحیح
سوال ۵- رنگ‌آمیزی پراکنده یک جدول با رنگ‌های سیاه و سفید
دیوار خانه‌ی عمو نقّاش به صورت یک جدول $n \times n$ می‌باشد. عمو نقّاش برای اینکه مصداق ضرب‌المثل «کوزه‌گر از کوزه‌شکسته آب می‌خورد» نشود٬ می‌خواهد دیوار خانه‌اش را رنگ‌آمیزی کند. برای این کار عمو هر بار قلم‌موی خودش را درون یک سطل رنگ متفاوت با رنگ‌های قبلی که تا به حال استفاده کرده٬ می‌کند و قلم‌موی رنگی را روی یک سطل یا یک ستون جدول به طور کامل می‌کشد.
عمو نقّاش می‌خواهد هر کسی به خانه‌شان می‌آید٬ هنرش را بفهمد. به همین خاطر او می‌خواهد طوری دیوار را رنگ‌آمیزی کند که تعداد رنگ‌هایی که روی دیوار دیده می‌شود٬ بیش‌ترین باشد.
شما به عمو نقّاش کمک کنید٬ به این معنی که اولاً٬ برای هر عدد $n$٬ یک روش رنگ‌آمیزی ارائه دهید که در آن با بیش‌ترین تعداد رنگ دیوار رنگ‌آمیزی شود و ثانیاً٬ ثابت کنید این مقدار بیشینه است.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 06:42:46 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 10:27:07 -0500 امیر شکریجواب 2n-1 می شود.
روش رنگ آمیزی:
سطر ها را با n رنگ مختلف رنگ می کنیم و سپس n-1 ستون را با n-1 رنگ دیگر رنگ می کنیم. اکنون در جدول 2n-1 رنگ مختلف وجود دارد. چون در ستون رنگ نشده رنگ تمامی سطر ها 1 بار آمده و رنگ هر ستون نیز سر جای خودش است.
اثبات بیشنه بودن:
مقدار جواب از 2n بیش تر نیست. چون دوبار رنگ کردن یک سطر یا یک ستون باعث می شود که رنگ اولیه ی آن سطر یا ستون را از بین برود. پس هر سطر و هر ستون حداکثر 1 رنگ جدید به جدول اضافه می کند که این یعنی حداکثر 2n رنگ مختلف.
اما جواب 2n هم نیست. چون اگر 2n باشد یعنی هر سطر و هر ستون دقیقاً یک رنگ جدید به جدول اضافه می کند. اکنون بدون کم شدن از کلیت مسئله فرض کنید که اولین حرکت رنگ کردن یک سطر است می دانیم که بعد از آن تمامی ستون ها یک بار رنگ می شوند و تمام خانه های رنگ شده توسط اولین سطر را از بین می برند.
نکته: توجه کنید دوبار رنگ کردن یک سطر یا یک ستون بی فایده است و تنها ترتیب عملیات را از بین می برد. و منظور ما از اولین سطر رنگ شده آن سطر یا ستونی است که دیگر رنگ آن تغییر نمی کند.
