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

[shoki]

سوال 19 :
اگر اینطوری هست که شما میگین اونوقت اگر حکم به ازای n=۱ برقرار باشه در اون صورت‌ به ازای همهٔ nها حله نتیجتاً کافیه حکم به ازای n=۱ اثبات بشه که واقعا راحته ...
یعنی فرض باید کرد که هر دو بازه ای اشتراکشون ناتهی هس و اگر بزرگترین بازه رو در نظر بگیریم مساله حله ... شرمنده اگر متوجه منظورتون نشدم...
سوال ۲۰ :
2n+1 تا عدد گنگ داریم . ثابت کنید حداقل n+1 تاشون هستند که جمع هر دو تای آن ها گنگ است.

 

[Goharshady]

سوال 19 :
اگر اینطوری هست که شما میگین اونوقت اگر حکم به ازای n=۱ برقرار باشه در اون صورت‌ به ازای همهٔ nها حله نتیجتاً کافیه حکم به ازای n=۱ اثبات بشه که واقعا راحته ...

واقعا به نظر شما جالب نبود؟
این همه آدم اصلا فکر نکردند. (چون من نوشته بودم سختش کنیم!)

 

[Olympiad]

سوال بعدي رو لطف كنيد!!!!!

 

[Goharshady]

مگه سوال 20 رو نمی بینی؟

 

[Goharshady]

جواب سوال 20

[center:49391bf60f]

[/center:49391bf60f]

.
سوال ۲۰ :
2n+1 تا عدد گنگ داریم . ثابت کنید حداقل n+1 تاشون هستند که جمع هر دو تای آن ها گنگ است.

می خواهم تپه نوردی کنم!
ابتدا ثابت می کنم هیچ 3 عدد گنگی وجود ندارند که جمع دو به دوی آنها گویا شود.(برهان خلف)
[center:49391bf60f]

[/center:49391bf60f]

با توجه به این تناقض حکم ثابت است.​

---------------------​

فرض کنید 2 عدد گنگ داریم که مجموع آنها گویاست. این دو عدد را a[SUB]1[/SUB] و a[SUB]2[/SUB] می نامیم.همچنین k عدد گنگ داریم که مجموع دو به دوی آنها گنگ است. این اعداد را با مجموعه ی K نشان می دهیم.​

چون جمع a[SUB]1[/SUB] و a[SUB]2[/SUB] گویاست پس برای هر

، جمع x با یکی از a[SUB]1[/SUB] و a[SUB]2[/SUB] گنگ است. حال می خواهیم ثابت کنیم یکی از a[SUB]1[/SUB] و a[SUB]2[/SUB] هست که جمعش با همه ی اعضای K گنگ می شود. فرض کنید :

. برهان خلف:​

[center:49391bf60f]

[/center:49391bf60f]

با توجه به تناقض حاصل ، حکم ثابت است.​

---------------------​

حال به استقرا فرض می کنیم حکم برای n برقرار باشد. برای برقراری حکم به ازای n+1 می دانیم که 2n+3 عدد داریم. اگر جمع دو به دوی همه ی آنها گنگ باشد که مسئله حل است. در غیر این صورت جمع دوتا از آنها گویاست. آن دوتا را کنار می گذاریم. طبق فرض استقرا از بین 2n+1 عدد دیگر n+1 عدد شرط مسئله را دارند. حال با توجه به قسمت بالا ، یک عدد دیگر هم با همه ی این n+1 عدد همین خاصیت را می سازد یعنی n+2 عدد این خاصیت را دارند و حکم ثابت است.​

دو قسمت بالا قصایایی هستند که می توان بدون اثبات هم از آنها استفاده کرد ولی جهت توضیح بیشتر اثبات آنها را هم نوشتم.​

پایه استقرا هم که بدیهی است.

 

[Olympiad]

حالا ديگه سوال بعدي !!!

 

[Goharshady]

سوال بیست و یکم

[center:f6fba1355d]

[/center:f6fba1355d]

سوال بیست و یکم:
الف )ثابت کنید تعداد رئوس با درجه فرد در هر گراف همبند زوج است.

ب) قضیه اردوش_سکرش را اثبات کنید.


علت دوقسمتی بودن سوال ؛ آسون بودنشه.

 

[shoki]

یه راه حل راحته دیگه استفاده از گراف بود و این که در مدل گرافیش هیچ دور فردی نداریم پس مساله حله ...

 

[rezoos]

الف)اگر تمام درجه های رئوس گراف رو با هم جمع کنیم عدد زوجی داریم (2 برابر تعداد یال ها) چون هر یال 2بار(توسط دو راسش)شمرده شده.تمام درجه های رئوس که زوج اند را با هم جمع کنیم عدد زوجی به دست می آید. مجموع رئوس با درجه ی زوج و فرد عددی زوج است.پس مجموع رئوس با درجه ی فرد نیز عددی زوج است.یعنی تعداد رئوس با درجه ی فرد زوج است.(این مساله صورت گرافی لم دست دادن بود!)

 

[rezoos]

لطفا صورت قضیه رو بیان کنین.نتونستم پیدا کنم.

 

[Goharshady]

[center:a3153f78d2]

[/center:a3153f78d2]

قضیه ی اردوش _ سکرش:​

در هر دنباله به طول mn+1 از اعداد حقیقی ، با حذف تعدادی از اعداد و حفظ ترتیب می توان به حداقل یکی از دو مورد زیر رسید:​

• دنباله ای صعودی به طول m+1
• دنباله ای نزولی به طول n+1

​

 

[Goharshady]

[center:e7009d494a]20[/center:e7009d494a]

یه راه حل راحته دیگه استفاده از گراف بود و این که در مدل گرافیش هیچ دور فردی نداریم پس مساله حله ...

تنها چیزی که به ذهنم نرسید گراف بود
البته اون 2 تا مقدمه رو قبلا می دونستم ، به همین دلیل این راه حل خیلی سریع به ذهنم اومد.

 

[Goharshady]

[center:a7a405e16a]21[/center:a7a405e16a]

(این مساله صورت گرافی لم دست دادن بود!)

خیر،
صورت گرافی تعمیم لم دست دادن بود!

بچه ها ، من همین الآن دارم این المپیاد آزمایشی رو میدم.
لطفا یک کمی طولش بدید.

 

[TG-100]

ب)آقای گوهرشادی این تو ترکیبیات علیپور هست که خیلی طولانیه,اگه راه دیگه ای می دونی لطفا خودت بگو
با تشکر

 

[Goharshady]

[center:ee10e86ad4]

[/center:ee10e86ad4]حالا که دوست ندارید سوال 21 رو حل کنید ، این یکی رو ببینید:
سوال بیست و دوم:
در هر خانه از یک جدول که 2[SUP]k[/SUP] سطر و n ستون دارد (تعداد ستونها حداقل 2 است) یکی از اعداد صفر و یک نوشته شده است.به طوری که تعداد 1 های هر سطر بزرگتر یا مساوی تعداد صفرهای آن است. ثابت کنید می توان k ستون یا کمتر از n ستون جدول انتخاب نمود و خانه های آن ستونها را رنگ کرد به گونه ای که حداقل یکی از یک های هر سطر در خانه های رنگ شده باشد.(المپیاد کامپیوتر ایران-1381)

 

[Goharshady]

[center:9a1d2e1717]22[/center:9a1d2e1717]

به نظر من این یک مثال نقض است:​

[center:9a1d2e1717]

[/center:9a1d2e1717]

 

[shoki]

@گوهر شادی: می تونم یه خواهشی کنم ...
اگه می شه سوالاتی رو که می گذارید توی کتاب های معروف نباشه ...

 

[Goharshady]

[center:a39ef5e6bf]22[/center:a39ef5e6bf]این سوال المپیاد کامپیوتره
من تو دو تا کتاب دیدمش (یکی از اونها هم ترکیبیات علی پور است)
ولی حلش رو جایی ندیدم!

مگه علی پور حل این سوال رو داره؟

لطفا اگه میتونید بگید این مثال نقضی که من نوشتم چه طوری توجیه می شه!

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

 

[shoki]

ممنونم از همکاریتون ...
اون مثال نقض هم مثال نقضه به معنای واقعی ...
در مورد حلش هم ،راه حلش در کتاب علیپور اومده...

 

[Goharshady]

[center:838121648c][HIGHLIGHT=#f2f2f2]2[/HIGHLIGHT][HIGHLIGHT=#000000]2[/HIGHLIGHT][/center:838121648c]نیومده!
فقط راهنمایی کرده
اگه اومده شماره صفحه رو بگید
شاید من کورم!!

حالا که مثال نقض داره
علی پور چه جوری اثباتش کرده؟؟؟