ماراتن ترکیبیات(پیشرفته)

[combinatorics]

پاسخ : ماراتن ترکیبیات(پیشرفته)

ای بابا! چرا المپیاد ریاضی و کامپیوتری ها انقدر بی بخارند. باز 1 روز نبودم؛ وقتی اومدم یک پست راجع به ترکیبیات در صفحه اصلی تالار گفتمان نبود. حالا برای رونق دوباره دو تا سوال می گذارم:
1) یک جدول 2000 در 2000 داریم که در هر خانه ی آن عدد 1 یا -1نوشته شده است. در این جدول جمع همه ی اعداد آن نامنفی است. ثابت کنید 1000 سطر و 1000 ستون از این جدول وجود دارد که جدول حاصل از تقاطع آن ها مجموعی ناکمتر از 1000 داشته باشد.
2) یک جدول 2001 در 2002 داریم. این جدول را با دومینو می پوشانیم. اگر هر پوشش دیگر جدول با دومینو با آرایش اولیه دست کم یک دومینو داشته باشد که بر هم منطبق باشند، ثابت کنید که ستونی از جدول در آرایش اولیه وجود دارد که همه ی دومینو ها ی آن افقی اند.

 

[fereidoon]

پاسخ : ماراتن ترکیبیات(پیشرفته)

1)قبلا مطرح شده:http://www.irysc.com/forum/t5291/#post71069

 

[goodarz]

پاسخ : ماراتن ترکیبیات(پیشرفته)

یه راهنمایی واسه دومی هم اینجاست: View topic - 1x2 tiling of a 2001x2002 table. • Art of Problem Solving راستش الان اصلا حال ندارم جوابشو بنویسم واسه همین لینک دادم. شرمنده!!!

 

[amir.ekhlasi]

پاسخ : ماراتن ترکیبیات(پیشرفته)

سؤال 3:
فرض کنید A زیرمجموعه ای n عضوی از دستگاه مانده ها به پیمانه n^2 باشد. ثابت کنید مجموعه ای n عضوی مانند B از دستگاه مانده ها به پیمانه n^2 وجود دارد به طوری که A+B شامل بیش ازn^2)/2) عضو باشد.
نکته:

 

[goodarz]

پاسخ : ماراتن ترکیبیات(پیشرفته)

راهنمایی: دوگانه شماری (همون دابل!!) کنید, یه ماتریس بکشید و یه طرفشو اعداد 1و.....وn^2 و طرف دیگه هم همه A+B های ممکن رو بذارید.....آخرش سوال به عدد e (عدد نپر) ربط پیدا می کنه.

سوال بعد: یه گراف 27 منتظم داریم و میدونیم حداقل یه دور هامیلتونی داره. ثابت کنید این گراف حداقل دوتا دور هامیلتونی داره که تو حداقل یه یال مشترکن.

 

[amir.ekhlasi]

پاسخ : ماراتن ترکیبیات(پیشرفته)

گراف منتظم چیه؟

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات(پیشرفته)

گراف منتظم چیه؟

گرافی که درجه ی تمام رئوسش برابر باشند.

 

[goodarz]

پاسخ : ماراتن ترکیبیات(پیشرفته)

کسی نمیخواد سوال منو حل کنه؟؟؟ :229:

 

[goodarz]

پاسخ : ماراتن ترکیبیات(پیشرفته)

یه راهنمایی: یه یال از دور هامیلتونی رو حذف کنید ببینید چه اتفاقی میفته.......

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات(پیشرفته)

راهنمایی: دوگانه شماری (همون دابل!!) کنید, یه ماتریس بکشید و یه طرفشو اعداد 1و.....وn^2 و طرف دیگه هم همه A+B های ممکن رو بذارید.....آخرش سوال به عدد e (عدد نپر) ربط پیدا می کنه.

سوال بعد: یه گراف 27 منتظم داریم و میدونیم حداقل یه دور هامیلتونی داره. ثابت کنید این گراف حداقل دوتا دور هامیلتونی داره که تو حداقل یه یال مشترکن.

یه کاری میکنیم این اثبات یکم بازی گونه و الگوریتمیه!!! دو راس مجاور در دور همیلتونی رو در نظر بگیرید و فرض کنید یکیشون به راسaوصل باشه چک کنید که اگه دومی به مجواری از a که aروی کمانی که راس دوم و راس اول و اون مجاوره روش هست قرار نداشته باشه وصل باشه دور پیدا میشه این الگوریتمو این جوری ارتقا بدین که دوباره از رئوس اولیه به یه سری رئوس دیگه برسید بعد هم ثابت کنید نمیشه هم از cبه d رسید هم برعکس اون وقت دور همیلتونی که می خواستید به دست میاد.
(بازگشت پشه) یه روز با ترکیبیات خوش بگذرونیم بیاید به این دوستتون کمک کنید یه روز از زندگیش لذت ببره

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات(پیشرفته)

حالا یه سوال قشنگ یه گراف داریم میانگین درجاتش 3.2 هست مینیمم درجش هم3 هست مسطح و مثلث آزاد هم هست ثابت کنید دوری به طول 4 یا8 دارد.

این هم سوال بعد یه نکته راجع به این سوال :سوال پایان دوره گراف بچس کامپیوتر امسال

 

[goodarz]

پاسخ : ماراتن ترکیبیات(پیشرفته)

مجتبی شرمنده ولی من این راهتو 5بار خوندم هیچی نفهمیدم!!! میشه یکم بیشتر توضیح بدی؟؟

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات(پیشرفته)

راستشو بخوای یکم سخته نوشتنش خوب از اولش شروع میکنیم تا تموم شه
دو راس مجاور aوb رو در نظر میگیریم به یه راس می گیم خوب اگه b بهش وصل باشه حالا اونایی که a بهشون وصل هست رو در نظر میگیریم برای این مجموعه از رئوس راس مجاوری رو که در جهت خلاف کمان دایره ای که شامل راس a هست رو در نظر میگیریم اگه اینا خوب بودن که میشه دور رو با یکم بازی کردن در اورد اگه نه دو باره این رئوس رو در نظر میگیریم و این کار رو تکرار میکنیم هر با یه سری راس جدید به مجموعه ای که اگه خوب باشن مسئله حله اضافه میشه از طرفی اگه اول راس c بتونه پس از مراحلی این رو ثابت کنه که اگه راس d خوبه دور وجود داره اونوقت c نمیتونه این کار رو ا d انجام بده این هم به همون صورت ثابت میشه با یکم بازی در میاد.

 

[goodarz]

پاسخ : ماراتن ترکیبیات(پیشرفته)

فقط یه سوال, از فرد-منتظم بودنش چه استفاده ای شده؟؟؟؟

سوال بعدی: مربع واحد abcd به 12^10 تا مربع کوچکتر (نه لزوما مساوی) تقسیم شده. ثابت کنید جمع محیط تمام مربع هایی که با قطر ac نقطه مشترک دارن از 1500 بیشتر نیست.

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات(پیشرفته)

حالا یه سوال قشنگ یه گراف داریم میانگین درجاتش 3.2 هست مینیمم درجش هم3 هست مسطح و مثلث آزاد هم هست ثابت کنید دوری به طول 4 یا8 دارد.

از قضیه اویلر استفاده کنید

 

[zz_torna2]

پاسخ : ماراتن ترکیبیات(پیشرفته)

خوب دیگه وقتشه....:3:

سوال بعدی توسط MBGO عزیز:


2m نفر دور یک دایره اند، به چند حالت میتوان m نقر از بین آنها انتخاب کرد که هسچ سه نفری متوالیا دور دایره نباشند.

 

[zz_torna2]

پاسخ : ماراتن ترکیبیات(پیشرفته)

راهنمایی 1:اصل شمول و عدم شمول.

2
فرض کنید A مجموعه شامل n عدد صحیح باشد به طوری که مجموع اعضا هر زیرمجموعه ناتهی از A بر n+1 بخشپذیر نباشد.ثابت کنید باقی مانده های اعضا A در تقسییم بر n+1 برابرند.

 

[victor]

پاسخ : ماراتن ترکیبیات(پیشرفته)

راهنمایی:
در مرحله اول اعداد
a_1
a_2
a_1+a_2
.
.
.
.

a_1+...a_n
در نظر بگیرید

 

[MBGO]

پاسخ : ماراتن ترکیبیات(پیشرفته)

راهنمایی:
در مرحله اول اعداد
a_1
a_2
a_1+a_2
.
.
.
.

a_1+...a_n
در نظر بگیرید

یعنی جواب 100 ه؟
یکم بیشتر توضیح میدی؟

 

[victor]

پاسخ : ماراتن ترکیبیات(پیشرفته)

یعنی جواب 100 ه؟
یکم بیشتر توضیح میدی؟

ینی چی جواب 100ه؟
این اعدادو که در نظر بگیرید میدونیم که هیچ کدوم از این اعداد بر n+1بخشپذیر نیستن تعدادشونم که n+1است پس حتما به پیمانهn+1 دو عدد از این عددها با هم برارند میدونیم که از اون اعدادی که با هم جمع کردیم(همونایی که نوشتم)هیچ کدوم با هم برار نیست
(به پیمانهn+1)(چرا؟)پس حتما a_1,a_2به پیمانهn+1باهم برارن حالا باز از اینجا به بعد اعداد زیر را در نظر بگیرید
a_1
a_2
a_3
a_1+a_2
.
.
.
a_1+...+a_n