رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ
انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
یافتن تعداد گرافای خوب n راسی ، ( یه مساله ترکیبی : گراف و شمارش )
.ثابت کنید در حداکثر 2n-4 سفر میتوانیم این کار را بکنیم.
کلاس با 20 دانش اموز - 230 نامه رد و بدل کرده اند
ساختن جایگشتی که میانگین هیچ دو عددی بین آن دو نباشد
پیدا کردن گراف دوبخشی کامل یکرنگ
حداکثر تعداد یالهای گراف بدون مثلث
در یک کشور تعدادی شهر وجود دارد به طوری که هر دوتایی با جاده ای به هم وصل اند و هر جاده بین دوشهر است و هیچ دوشهری با بیش از 1 جاده به هم وصل نشده اند می خواهیم جاده ها را با اعداد 1 تا r شماره گداری کنیم به طوری که به ازای هر 3 شهر دوجاده از جاده های بین این 3 شهر دارای شماره برابر و از شماره سومی یزرگتر باشند و در ضمن از هر عدد هم حداقل 1 بار استفاده شود.بیشترین r را بیابید و تعداد حالات شماره گذاری با r را که r بیشینه است را بیابید.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 07:17:32 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-27 07:38:26 -0500 امیر شکریاز اونجایی که جواب خیلی طولانیه به جواب کوتاه بسنده میکنم(امیدوارم متوجه کل جواب بشید)
جواب : $r \le n-1$
اولا که سوال رو به گراف تبدیل میکنیم. بعدش استقرای ضعیف میزنیم و یک راس دلخواه $v$ رو حذف میکنیم. به حالت فرض میرسیم و یک بررسی کوتاه نتیجه میگیریم که حداکثر 1 عدد جدید میتونه اضافه بشه(وگرنه مثلثی داریم که همه اعدادش فرق میکنه)
برای تعداد حالات هم ادعا میکنیم جواب برابر $\prod_{i=2}^n{i \choose 2}$
دقت کنید اگه یال $xy$ عددش برابر 1 باشه، اونوقت به ازای هر راس $v$ هر جفت یالهای $vx$ و $vy$ عددشون برابره و بزرگتر از 1.
پس دو راس $x$ و $y$ رو ادغام کنیم به یک راس $u$، یال های چندگانه بین هر راس $v$ و راس جدید $u$، به یک رنگند، پس میشه یکیشون کرد. یعنی الان به گرافی با $n-1$ راس رسیدیم. اگر یالی با عدد 1 هنوز مونده باشه، چون هیچ عدد دیگه ای حذف نشده، پس در گراف جدید $r = n-1$ . که این تناقضه!
پس گراف ما دقیقا یک یال 1 داره، و اگه استقرا بزنیم روی تعداد راس ها، و همون روش حذف یال 1 که توضیح دادم رو پی بگیریم، اثبات میکنیم که جواب برابره با ${n \choose 2} \times \prod_{i=2}^{n-1}{i \choose 2} = \prod_{i=2}^n{i \choose 2}$
پی نوشت: در حقیقت برای انتخاب یال با عدد 1 ما ${n \choose 2}$ انتخاب داریم.
