ماراتن ترکیبیات

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات

خب
منم بعد عمر ی اومدم
می خوام اثباتم رو بذارم که ببینید درسته یا نه:
خب استقرا می زنیم
حکم به ازای n=2
درسته
فرض کنیم که واسه n<=k
هم درسته می خوایم واسه n=k+1
اثبات کنیم
خب گراف رو در نظرمی کیریم
خب یه راس ور می داریم که به حداقل دو تا راس متمایز یال داشته باشه
****************************
اگه چنین راسی نباشه
یا رئوس گراف بعضیاشون تنهان
یا فقط یه یال دارن
یا جفت جفت با دویال بهم وصلن
که در این حالات مسئله حله
****************************
خب اگه گراف نا همبند باشه باز هر مولفه چون تو فرض استقرا می یوفته
مسئله حل می شه
پس فرض کنیم گراف همبنده
خب حالا از اون راسی که اول گفته شد شروع به پیمایش گراف می کنیم به صورت کاملا کیلویی و از رو ی یال ها به طوری که به راس تکراری نریم (DFS میزنیم)
خب به یه زیردرخت فراگیر از درخت می رسیم
حالا این درخت این خاصیت رو داره که هیچ دو راسی که تو دوتا شا خه از گراف هستن (هر شاخه از اولین راس نشئت می گیره .شاخه های تو خود شاخه اصلییا مهم نی)
تو گراف اصلی بهم وصل نیستن
چون از هر راس به تمام همسایه های دیده نشده اش می ریم پس غیر راس اول همسایه های هر راس تو شاخه خود اون راس است
حالا اگه یه راسی باشه که به این راسی که ماتوشیم وصل باشه ولی قبلا دیده شده باشه و ما از اون به این راس حاضر نیمده باشیم
یعنی این که این دو تا راس تویه شاخه نیستن
در حالی که می دونیم وقتی به یه راسی میرسیم تمام همسایه هاش رو میبینم
پس این حالت به وجود نمیاد
این همه حرف زدم که بگم دور ها تو گراف فقط تو هر شاخه هستن
و دوری نداریم که از دو یا بیشتر شاخه استفاده کنه
حالا یکی از شاخه هارو میگیرم چون اون شرط تعداد یال هارو داره پس اگه با یال های نداشتش در نظرش بگیریم بدون بقیه گراف تو فرض استقرا صدق می کنه
و بقیه گراف هم به همین صورت تو فرض استقرا صدق می کنه
پس حکم اثبات میشه

من نمیدونم از فرض2k-2 چه استفاده ای کردی؟

 

[goodarz]

پاسخ : ماراتن ترکیبیات

آقا یکی به من بگه شاخه چیه......اگه شاخه همونی باشه که من تو ذهنم دارم به نظرم این قسمت مشکل داره: دور ها تو گراف فقط تو هر شاخه هستن

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات

شاخه تو درخت تعریف میشه وقتی گراف رو از یه راس آویزون میکنیم به مجموعه نوادگان یه راس میگن شاخه

 

[Aref]

پاسخ : ماراتن ترکیبیات

شاخه تو درخت تعریف میشه وقتی گراف رو از یه راس آویزون میکنیم به مجموعه نوادگان یه راس میگن شاخه

میگم سوال بعدی سوال عرفان (Sir Soli) خودمون باشه استاد؟

 

[goodarz]

پاسخ : ماراتن ترکیبیات

خوب پس به نظرم همون قسمتی که گفتم مشکل داره......میشه که یه دور توی چندتا شاخه هم باشه....

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات

میگم سوال بعدی سوال عرفان (sir soli) خودمون باشه استاد؟

استاد شمایی هر چی شما بگی استاد .شما میذاری سوالش رو؟

 

[combinatorics]

پاسخ : ماراتن ترکیبیات

آره. الان فهیدم حل erfankh اشکال داره.

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات

خوب استاد با اجازه سوالشرو گذاشتم: یه درخت داریم آیا میتوان به هر راسش یه عدد از یک تا n نسبت داد به طوری که اگر تفاضل اعداد روی رئوس متناضر به یک یال رو روی هر یالی بنویسیم اعداد 1 تا n_1 رو به ما بده که n تعداد رئوسه؟

 

[combinatorics]

پاسخ : ماراتن ترکیبیات

مجتبی توی سوال اعدادی که روی رئوس میگذاریم، دلخواهند یا شرط دارند. اگر شرطی نداشته باشند، سوال با یک استقرای ساده حل میشه. اگر منظورت اینه که همه ی اعداد 1 تا n باید روی رأس ها ظاهر بشوند، این مسأله هنوز در حد یک حدس مانده است.(حدس درخت جذاب توسط رینگل-1964)
ضمنا قرار شد هر سوال را در ماراتن مربوط به آن بنویسیم. ماراتن ترکیبیات فقط مخصوص مبحث ترکیبیات مقدماتی است. ماراتن ترکیبیات پیشرفته مخصوص سوالات پیشرفته ی ترکیبیات است. ماراتن گراف هم برای گراف.

 

[mahanmath]

پاسخ : ماراتن ترکیبیات

تعدادی نقطه تو صفحه هستن که فاصله ۲ به ۲ اون ها از یک کمتر نیست . فرض کنید

نشان دهنده حداقل تعداد نقاط باشد که بتوان از بین هر

نقطه با خاصیت گفت شده یه مجموعه

عضوی از نقاط پیدا کرد که فاصله ۲ به ۲ اون ها حداقل

باشه .

حالا هر کسی کرانی برای

بدست بیاره که از واسه بقیه رشدش کند تر باشه برنده است .

(مدل سوالای خلاقیت !)

کران خودم رو بد از اولین کرانی که بگید میزارم .(کران های مزخرف مثل صفر :67:! یک ، یکیو نصفی..... از این حرفا نگید خواهشا )

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات

یه دایره رو یه بار بادایره های به شعاع d/2 پر کنیم یه بار با شعاع 1/2 به طوری که وقتی با d/2 پر میکنیم n تا دایره ساخته بشه کران من تعداد دایرهی به شعاع 1/2 که اونو پر کنند هست.فک کنم یه ضریبی از d رو هم بشه از این کران کم کرد.

 

[goodarz]

پاسخ : ماراتن ترکیبیات

منم تقریبا همون کاری که مجتبی گفته بودو کرده بودم و آخرش به این رسیدم که تعداد نقاط حتما باید بیشتر از این باشه: (ببخشید اگه دیر پست می کنم چون اینا رو صبح نوشته بودم ولی تا الان بیرون بودم!!)

که

خیلی خوشگله نه؟؟؟!!!؟!

 

[Kavoshgar]

سوالی از ترکیبیات

کلیه اعداد چهار رقمی با ارقام 1و2و3و...و6 را روی کاغذ نوشتیم . مجموع این اعدا چقدر است ؟

 

[alimohammadi]

پاسخ : سوالی از ترکیبیات

اگر شرطي براي تكرار ارقام نداريم هر عدد در جايگاه يكان،دهگان ،... 3^6 بار مي آيد اين حالات رو جمع ميكنيم
(1+2+...+6)3^6+(10+20+30...+60)3^6+....+(1000+2000+...+6000)3^6=3^6*6*7/2*(1+10+100...+1000)

 

[mahanmath]

پاسخ : ماراتن ترکیبیات

یه دایره رو یه بار بادایره های به شعاع d/2 پر کنیم یه بار با شعاع 1/2 به طوری که وقتی با d/2 پر میکنیم n تا دایره ساخته بشه کران من تعداد دایرهی به شعاع 1/2 که اونو پر کنند هست.فک کنم یه ضریبی از d رو هم بشه از این کران کم کرد.

مجتبی می شه این کران رو دقیق بنویسی، که یه مقایسه ای بتونیم داشته باشیم .

منم تقریبا همون کاری که مجتبی گفته بودو کرده بودم و آخرش به این رسیدم که تعداد نقاط حتما باید بیشتر از این باشه: (ببخشید اگه دیر پست می کنم چون اینا رو صبح نوشته بودم ولی تا الان بیرون بودم!!)

که

خیلی خوشگله نه؟؟؟!!!؟!

گودرز تو هم یه خورده به سر رو این کرانت برس ، چیه این آخه ؟!!!


کران من این بود :

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات

order کران گودرز =d^2.n

 

[goodarz]

پاسخ : ماراتن ترکیبیات

order کران گودرز =d^2

این الان خوبه یا بد؟؟ من گفتم f(n,d) از اون همیشه بیشتره...

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات

ببخشید باید مینوشتم d^2.n. الان این خیلی خوبه چون رشدش خیلی کمه.

 

[mahanmath]

پاسخ : ماراتن ترکیبیات

نه دیگه مجتبی ! اونی که باید رشدش کند باشه کران بالا منه ولی گودرز کران پائین داده که باید رشدش زیاد باشه تا ارزشمند بشه تقریبش .

سعی کنید یه کران بالا (مس واسه من نه البته :3 پیدا کنید ، که دیگه بریم سوال بعد .

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات

مشکل ایکه تو. تایین نکردی کران بالا میخوای یا کران پایین.