پاک کردن اعداد یک مجموعه تا حاصل ضرب هر دوعدد باقی مانده برابر اعداد باقی مانده دیگر نشود
چرخاندن میز با n مهمان طوری که حداقل دو مهمان سرجای خود قرار بگیرند
مساله ی مسابقه ی دانشجویی 93_ ماتریس
تعداد گراف‌های دو بخشی و غیردوبخشی $n$راسی و $2n$ یالی
تورنمنت با تعداد زیادی مسیر همیلتونی
گروهی از دانش آموزان شامل حداقل نصف افراد ، هر پسر با تعداد فردی دختر دوست است
یک جدول $n \times n$ داده شده است. $k^3$ رخ در این جدول قرار داده شده است به طوری که تعداد رخ های هر سطر و تعداد رخ های هر ستون حداکثر $k$ است. ثابت کنید حداقل $k \over 2$ رخ وجود دارد که هیچ دو تایی از آنها در یک سطر یا یک ستون قرار ندارند.
نه . مطمعن نیستم که احتمالاتی هم حل بشه .اما اگه احتمالاتی حلش کنید خیلی خوبه و خوشحال کنندست. دیشب این سوال به ذهنم رسید و فکر نمی کنم در کتابی باشه .
2015-06-11 08:43:34 -0600 حمید کاملیحکم ضعیف نیست چون اگه به صورت حریصانه بر داریم هر دفعه بیشتز از k/2 میشه؟!!؟!
2015-06-11 10:05:21 -0600 حمیدرضاهسلام !
فقط باید توران بدونید چیه :) هم توی ویکی پدیا هستش ؛ هم توی کاهو
اول میایم یک گراف با $k^3$ راس در نظر می گیریم و به هر راس یک مهره در جدول متناظر می کنیم . بعدش میایم بین دو راس یال می گذاریم اگر مهره های متناظر در جدول در یک ستون یا یک سطر نباشد .
خب حالا اگه یه گراف$\frac{k}{2}$ کامل راسی توی گراف باشه مسئله حله دیگه برای اینم باید توران بزنیم .
1-حداقل تعداد یال های کل گراف : $ \alpha =\frac{(k^3-2k)*k^3}{2} $
2-حداقل تعداد یال برای نداشتن گراف کامل $\frac{k}{2}$ راسی : $\beta =\frac{(k^6).(\frac{k}{2}-2)}{2.(\frac{k}{2}-1)}$
پس چون $\beta < \alpha$ پس چنین گراف کاملی داریم و جواب می شه تمام مهره های متناظر شده به این نقاط .
موفق باشد :)
chi migi M.D! baw har dafe ye rokho vardar rokhaye hamsatro sotoonesho hazf kon mishe k^2/2 beja in maskhare bazia be ghole yeki az doostam eyne in mimoone ke partishel sum ro ba segment tree bezani ke albate man ateghad daram to ba in karet heavy light zadi... :o
2015-06-12 11:30:59 -0600 کلم برگرخ ها را در $2k^2$ دسته به این صورت قرار می دهیم. به ازای یک رخ مشخص $r$، تمام رخ هایی که هم ردیف با آن هستند را در نظر می گیریم و سپس تمام رخ های هم ستون با آن ها را نیز در نظر می گیریم. تعداد رخ های در نظر گرفته شده حداکثر برابر است با $k^2 -k$.
اگر رخ های هم ستون با رخ $r$ را نیز در نظر بگیریم و رخ های هم سطر با آن ها را نیز در نظر بگیریم باز هم حداکثر $k^2 -k$ رخ داریم. رخ $r$ و رخ های دیگری که در نظر گرفتیم حداکثر $2k^2 $ تا هستند.
اگر این رخ ها را حذف کنیم و با رخ های باقیمانده این کار را تکرار کنیم ${k \over 2 }$ دسته داریم که هر دسته شامل حداکثر $2k^2$ رخ است. اگر از هر دسته یک رخ انتخاب کنیم هیچ دو رخ انتخاب شده ای در یک سطر یا یک ستون قرار ندارند.(اثبات این موضوع هم از نحوه ی ساخت دسته ها بدیهی است . اگر نیاز به توضیح دارد، توضیح بدم ؟ )