سوال ۱- جدول n*n از اعداد ۱ تا n داده شده...

آمار پرسش:

پرسیده شده: 2015-02-17 10:19:49 -0500
مشاهده شده: 764 بار
بروز شده: 2020-11-17 05:19:04 -0500

پرسش‌های مشابه:

سوال ۲- برش نواحی یک جدول n در n

سوال ۳ - رنگ آمیزی دیوار خانه‌ی عمو نقّاش

سوال ۴ - روشی برای انتخاب سالن انتظار در هر روز و دیدن تلویزیون آن در شهر المپیادی‌ها

سوال 5- احداث جاده و مرکز پلیس در شهرهای کشور علی کوچولو

سوال 6- وزن کم ترین زبان n کلمه ای که هم پیشوند -آزاد باشد و هم پسوند-آزاد

سوال ۷- مجموعه‌ی سه‌ تایی‌ های پایدار

سوال ۸- دایره‌های دوبه‌دو نامتقاطع روابط

سوال 2- قورباغه‌ي پهلوان روی محور اعداد صحیح

سوال ۵- رنگ‌آمیزی پراکنده یک جدول با رنگ‌های سیاه و سفید

سوال ۶- سطل‌ها و توپ‌ها- نشان دهید در هر ۲۰ حرکت متوالی ناچاریم دست کم یک بار به سراغ سطلی با کم‌تر از ۱۰ توپ برویم.

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

یک جدول $n \times n$ از اعداد ٬۲٬۱ تا ... $n$ داده شده است. در هیچ سطر یا ستونی از این جدول عدد تکراری یافت نمی‌شود؛ به عبارت دیگر در هر سطر یا ستون تمام اعداد ٬۲٬۱ تا ... $n$ وجود دارند.

اگر $x$ یک عدد اعشاری باشد٬ $\lfloor x \rfloor$ بزرگ‌ترین عدد صحیحِ کوچک‌تر از $x$ است. با این تعریف٬ ثابت کنید که می‌توان $\lfloor \frac n2 \rfloor$ تا از خانه‌های این جدول را انتخاب نمود که هیچ زوج از خانه‌های انتخاب شده در یک سطر یا ستون قرار نداشته باشند و به ازای هر عدد $1 \le i \le n$ حداکثر دو تا از این خانه‌ها شامل عدد $i$ باشند.

2015-02-17 10:19:49 -0500

محمدی 2185 ● 55 ● 63 ● 94

پاک‌کردن ویرایش سوال

نظرات

هاااااااااااااااااااااااااااااا؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

2015-02-18 06:20:11 -0500 کلم بروکلی

سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com

2015-08-06 09:58:42 -0500 امیر شکری

میشه ثابت کرد که$\lfloor \frac n2 \rfloor$تا عدد میشه انتخاب کرد که 2 به 2 متفاوتند بعد ثابت میکنیم شرایط مساله را هم داره.

2016-03-31 02:17:28 -0500 ابکا

سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه

2016-10-26 08:44:41 -0500 امیر شکری

2 پاسخ

الگوریتم زیر را n/4 مرحله انجام میدیم به طوری که تو مرحله ی i ام اینگونه عمل میکنیم:

تاحالا 2i-2 تا عدد انتخاب کردیم که هیچ دوتایی توی یک سطر یا ستون نیستند.(از اعداد 1 تا i-1 هرکدوم دوتا).حالا باید 2 تا عدد i هم اضافه کنیم که شرط همچنان برقرار باشد.

باید ثابت کنیم در خانه های باقیمانده از جدول که میتوانیم عدد از آنها انتخاب کنیم به طوری که با قبلی ها هم سطر یا ستون نباشند حداقل 2 عدد i داریم.2i-2 ستون غیر قابل انتخاب داریم که در هرکدام از آنها یک عدد i قرار داردکه نمیتوان انتخابش کرد،همچنین 2i-2 سطر داریم که هرکدام یک عدد i دارند که نمیتوان انتخاب کرد پس در کل 4i-4 خانه که عدد i دارند غیرقابل انتخاب اند و بقیه را میتوان انتخاب کرد که به وضوح چون i<=n/4 پس حداقل دو خانه برای انتخاب وجود دارد و این دو خانه هم بایکدیگر هم سطر یا ستون نیستند چون هردو عدد i در جدول،در سطر و ستون متفاوتند.

در پایان به n/4 جفت عدد با خواص سوال میرسیم.

2016-04-20 11:38:11 -0500