ایده های جالب ترکیبیات ....
پاسخ : ایده های جالب ترکیبیات ....
تا حالا این سوالو با ایده فرین (اکسترمال)حل کردین؟
سوال: n تا خط تو صفحه داریم که هیچ دو تایی موازی و هیچ سه تایی همرس نیستند. صفحه به چند ناحیه افراز شده؟
پاسخ: تو هر ناحیه یه قطره آب رها کنید. می افته روی پایین ترین نقطه ی اون ناحیه. پس رو هر نقطه دقیقا یه قطره آب قرار می گیره. پس تا حالا
تا ناحیه داشتیم. یه سری ناحیه ها پایین ترین نقطه ندارن. یه سینی می ذاریم پایین قطره های اون ناحیه ها می افتن توش میشماریمشون. سینی مثل یه خط می مونه که از هر برخورد تا بعدیش یه ناحیه و بعد از اولین و آخرین برخورد یه ناحیه داریم. پس n+1 ناحیه اضافه می شود که همان
هست پس جواب میشه
به نظرم خیلی جالب بود. کلا فرین خیلی قشنگه.
تا حالا این سوالو با ایده فرین (اکسترمال)حل کردین؟
سوال: n تا خط تو صفحه داریم که هیچ دو تایی موازی و هیچ سه تایی همرس نیستند. صفحه به چند ناحیه افراز شده؟
پاسخ: تو هر ناحیه یه قطره آب رها کنید. می افته روی پایین ترین نقطه ی اون ناحیه. پس رو هر نقطه دقیقا یه قطره آب قرار می گیره. پس تا حالا
آخرین ویرایش توسط مدیر
پاسخ : ایده های جالب ترکیبیات ....
میشه لطفا نوشته هاتون رو درست کنین
تا حالا این سوالو با ایده فرین (اکسترمال)حل کردین؟
سوال: n تا خط تو صفحه داریم که هیچ دو تایی موازی و هیچ سه تایی همرس نیستند. صفحه به چند ناحیه افراز شده؟
پاسخ: تو هر ناحیه یه قطره آب رها کنید. می افته روی پایین ترین نقطه ی اون ناحیه. پس رو هر نقطه دقیقا یه قطره آب قرار می گیره. پس تا حالا
![](http://<img src="http://latex.codecogs.com/gif.latex?\binom{n}{2}" title="\binom{n}{2}" />)
تا ناحیه داشتیم. یه سری ناحیه ها پایین ترین نقطه ندارن. یه سینی می ذاریم پایین قطره های اون ناحیه ها می افتن توش میشماریمشون. سینی مثل یه خط می مونه که از هر برخورد تا بعدیش یه ناحیه و بعد از اولین و آخرین برخورد یه ناحیه داریم. پس n+1 ناحیه اضافه می شود که همان
![](http://<img src="http://latex.codecogs.com/gif.latex?\binom{n}{1}+\binom{n}{0}" title="\binom{n}{1}+\binom{n}{0}" />)
هست پس جواب میشه
![](http://<img src="http://latex.codecogs.com/gif.latex?\binom{n}{2}+\binom{n}{1}+\binom{n}{0}" title="\binom{n}{2}+\binom{n}{1}+\binom{n}{0}" />)
به نظرم خیلی جالب بود. کلا فرین خیلی قشنگه.
سوال: n تا خط تو صفحه داریم که هیچ دو تایی موازی و هیچ سه تایی همرس نیستند. صفحه به چند ناحیه افراز شده؟
پاسخ: تو هر ناحیه یه قطره آب رها کنید. می افته روی پایین ترین نقطه ی اون ناحیه. پس رو هر نقطه دقیقا یه قطره آب قرار می گیره. پس تا حالا
- ارسال ها
- 327
- لایک ها
- 378
- امتیاز
- 0
پاسخ : ایده های جالب ترکیبیات ....
ببخشید این که اکسترمال استفاده نکرده؟!!! کرده؟!
این دقیقا استدلال ریاضی برای حل سواله البته به بیان فیزیکی
تا حالا این سوالو با ایده فرین (اکسترمال)حل کردین؟
سوال: n تا خط تو صفحه داریم که هیچ دو تایی موازی و هیچ سه تایی همرس نیستند. صفحه به چند ناحیه افراز شده؟
پاسخ: تو هر ناحیه یه قطره آب رها کنید. می افته روی پایین ترین نقطه ی اون ناحیه. پس رو هر نقطه دقیقا یه قطره آب قرار می گیره. پس تا حالا
تا ناحیه داشتیم. یه سری ناحیه ها پایین ترین نقطه ندارن. یه سینی می ذاریم پایین قطره های اون ناحیه ها می افتن توش میشماریمشون. سینی مثل یه خط می مونه که از هر برخورد تا بعدیش یه ناحیه و بعد از اولین و آخرین برخورد یه ناحیه داریم. پس n+1 ناحیه اضافه می شود که همان
هست پس جواب میشه
به نظرم خیلی جالب بود. کلا فرین خیلی قشنگه.
سوال: n تا خط تو صفحه داریم که هیچ دو تایی موازی و هیچ سه تایی همرس نیستند. صفحه به چند ناحیه افراز شده؟
پاسخ: تو هر ناحیه یه قطره آب رها کنید. می افته روی پایین ترین نقطه ی اون ناحیه. پس رو هر نقطه دقیقا یه قطره آب قرار می گیره. پس تا حالا
این دقیقا استدلال ریاضی برای حل سواله البته به بیان فیزیکی
پاسخ : ایده های جالب ترکیبیات ....
گفته پایین ترین.
چند تا ایده کلی می گم که خیلی به کار میاد و بعضی هاشون خیلی معروفند. هر کدوم و خواستی بگو مثال بزنم. ( اگه تونستم البته )
اثبات وجودی: تعداد حالات خوب = تعداد حالات بد - تعداد حالات کل
ایجاد گراف حالت
در نظر گرفتن مکمل ها
خیلی از مسائل بهتره که به جای این که گراف رو در نظر بگیریم، فرض کنیم که اون گراف درخته. ( توجه هر گراف همبند یه درخت فراگیر داره )
از بالا یا از یه طرفی عکس بندازیم از سوال
سایه انداختن
پیوستگی گسسته
ریشه دار گردن درخت و آویزون کردنش . ( و bfs زدن روش )
اثبات های کمبیشینه
ببخشید این که اکسترمال استفاده نکرده؟!!! کرده؟!
این دقیقا استدلال ریاضی برای حل سواله البته به بیان فیزیکی
این دقیقا استدلال ریاضی برای حل سواله البته به بیان فیزیکی
چند تا ایده کلی می گم که خیلی به کار میاد و بعضی هاشون خیلی معروفند. هر کدوم و خواستی بگو مثال بزنم. ( اگه تونستم البته )
اثبات وجودی: تعداد حالات خوب = تعداد حالات بد - تعداد حالات کل
ایجاد گراف حالت
در نظر گرفتن مکمل ها
خیلی از مسائل بهتره که به جای این که گراف رو در نظر بگیریم، فرض کنیم که اون گراف درخته. ( توجه هر گراف همبند یه درخت فراگیر داره )
از بالا یا از یه طرفی عکس بندازیم از سوال
سایه انداختن
پیوستگی گسسته
ریشه دار گردن درخت و آویزون کردنش . ( و bfs زدن روش )
اثبات های کمبیشینه
پاسخ : ایده های جالب ترکیبیات ....
AoPS Forum - Kazakhstan NMO 2010 grade 9 P 2 • Art of Problem Solving
AoPS Forum - consecutive positive integers contains exactly 25 primes • Art of Problem Solving
AoPS Forum - 6n colored points in a line • Art of Problem Solving
البته تا جایی که من میدونم بیشتر این ایده هایی که گفتن اسم ندارن. حداقل این یکی اسمش پیوستگی گسسته نیست. یه جورایی قضیه ی مقدار میانیه.
ایده های دیگه:
استفاده از قضیه ی هال
رنگ آمیزی
Binary Search
AoPS Forum - Kazakhstan NMO 2010 grade 9 P 2 • Art of Problem Solving
AoPS Forum - consecutive positive integers contains exactly 25 primes • Art of Problem Solving
AoPS Forum - 6n colored points in a line • Art of Problem Solving
البته تا جایی که من میدونم بیشتر این ایده هایی که گفتن اسم ندارن. حداقل این یکی اسمش پیوستگی گسسته نیست. یه جورایی قضیه ی مقدار میانیه.
ایده های دیگه:
استفاده از قضیه ی هال
رنگ آمیزی
Binary Search
پاسخ : ایده های جالب ترکیبیات ....
قضیه هال - ویکی‌پدیا
اینم یه سوال مرتبط:
AoPS Forum - Akin to Erdős–Faber–Lovász, but hopefully solved • Art of Problem Solving
Binary Search یا همون جستجوی دودویی ایده ای هستش که توی بعضی از سوال ها کاربرد داره. این طوریه که شما می خواین یه متغیر خوب رو پیدا کنین... هر بار هم یه تعدادی از کل متغیر ها رو برمیدارین می بینین که این متغیر توی این دسته ای که برداشتین هست یا نه. اون وقت برای پیدا کردن اون متغیر باید حداقل سقف log n بار جستجو کنین، بعدشم این مقدار جستجو برای پیدا کردن اون متغیر کافیه.
قضیه هال - ویکی‌پدیا
اینم یه سوال مرتبط:
AoPS Forum - Akin to Erdős–Faber–Lovász, but hopefully solved • Art of Problem Solving
Binary Search یا همون جستجوی دودویی ایده ای هستش که توی بعضی از سوال ها کاربرد داره. این طوریه که شما می خواین یه متغیر خوب رو پیدا کنین... هر بار هم یه تعدادی از کل متغیر ها رو برمیدارین می بینین که این متغیر توی این دسته ای که برداشتین هست یا نه. اون وقت برای پیدا کردن اون متغیر باید حداقل سقف log n بار جستجو کنین، بعدشم این مقدار جستجو برای پیدا کردن اون متغیر کافیه.
پاسخ : ایده های جالب ترکیبیات ....
سایه انداختن: اگه n تا شکل محدب توی صفحه باشه، و هر دوتاشون قسمت مشترک داشته باشند، ثابت کنید همشون قسمت مشترک دارند ( درست یادم نیست ولی فکر کنم همین بود )
پیوستگی گسسته: یه مثال خیلی راحت، یه گردنبند داریم که n تا قرمز و n تا آبی مهره داره. ثابت کنید می شه دو نقطه اش رو برید که در هر طرف به تعداد مساوی مهره قرمز و آبی باشه . ( سوال رو شدیدا شک دارم، اصلا مطمئن نیستم )
ریشه دار کردن: یادم نیست.
اثبات های مینیماکس : فصل 3 وست رو ببینید.
سایه انداختن: اگه n تا شکل محدب توی صفحه باشه، و هر دوتاشون قسمت مشترک داشته باشند، ثابت کنید همشون قسمت مشترک دارند ( درست یادم نیست ولی فکر کنم همین بود )
پیوستگی گسسته: یه مثال خیلی راحت، یه گردنبند داریم که n تا قرمز و n تا آبی مهره داره. ثابت کنید می شه دو نقطه اش رو برید که در هر طرف به تعداد مساوی مهره قرمز و آبی باشه . ( سوال رو شدیدا شک دارم، اصلا مطمئن نیستم )
ریشه دار کردن: یادم نیست.
اثبات های مینیماکس : فصل 3 وست رو ببینید.
پاسخ : ایده های جالب ترکیبیات ....
یه ایده ی جالب: پسرو
سوال: 4 ملخ در 4 راس یک مربع بر روی صفحه قرار گرفته اند. هر بار یکی از ملخ ها با یک جهش از روی ملخ دیگری می پرد و در نقطه ی مقابل(قرینه مکان قبلی خو نسبت به مکان ملخ دیگر) فرود می آید. آیا ممکن است بعد از مدتی ملخ ها روی 4 راس یک مربع بزرگتر قرار بگیرند؟(مربع بزرگتر ممکن است دوران یافته باشد.) (مرحله ی دوم المپیاد کامپیوتر ایران، دوره ی نوزدهم)
پاسخ : نمیشود. اثبات:از آخر به اول می رویم. فرض کنیم بشود. آنگاه از یک
باید بتوان به 1*1 رسید(طبق عمل پسرو).(در ضمن a> 1) نقطه ی پایین چپ مربع را روی (0,0) قرار می دهیم. مابقی نقاط روی (0,a)و (a,a)و (a,0) مستقر اند.
حال هر عمل را که هر انجام دهیم هر مولفه ی هر راس مضرب a می ماند(چرا؟) پس a نمیتواند بیش تر از 1 باشد. تناقض!
یه ایده ی جالب: پسرو
سوال: 4 ملخ در 4 راس یک مربع بر روی صفحه قرار گرفته اند. هر بار یکی از ملخ ها با یک جهش از روی ملخ دیگری می پرد و در نقطه ی مقابل(قرینه مکان قبلی خو نسبت به مکان ملخ دیگر) فرود می آید. آیا ممکن است بعد از مدتی ملخ ها روی 4 راس یک مربع بزرگتر قرار بگیرند؟(مربع بزرگتر ممکن است دوران یافته باشد.) (مرحله ی دوم المپیاد کامپیوتر ایران، دوره ی نوزدهم)
پاسخ : نمیشود. اثبات:از آخر به اول می رویم. فرض کنیم بشود. آنگاه از یک
حال هر عمل را که هر انجام دهیم هر مولفه ی هر راس مضرب a می ماند(چرا؟) پس a نمیتواند بیش تر از 1 باشد. تناقض!