ریاضی-علوم کامپیوتر- المپیاد

ریاضیات _ علوم کامپیوتر _ المپیاد ریاضی و کامپیوتر

ریاضی-علوم کامپیوتر- المپیاد

ریاضیات _ علوم کامپیوتر _ المپیاد ریاضی و کامپیوتر

درباره ی من
دکتری ریاضی (ترکیبیات)
ارشد علوم کامپیوتر _ صنعتی شریف
hamid.kamely@yahoo.com
instagram: hamidkameli1366
61 10 739 0912
سوابق کاری من

در این صفحه هر روز سوالی برای المپیاد ریاضی و کامپیوتر گذاشته می شود.
سوالها در سه سطح آسان ، متوسط و سخت هستند
اگر برای سوالی راهنمایی نیاز بود در نظرات همین صفحه اعلام کنید
اگر روی هر موضوع کلیک کنید لیست سوالهای آن موضوع نمایش داده می شود
موضوعات و تعداد سوالها در روزهای آینده بیشتر می شود(بنا به درخواست شما)


الگوریتم های ترکیبیاتی

نظریه گراف

استقرا

لانه کبوتری

هندسه ترکیبیاتی

شمارش

روشهای احتمالاتی

نظرات  (۲۱)

3 شمارش:
چون رقم شماره 10 در معکوس روی 1 می افتد و 9 بر روی 2 و تا اخر 5 زوج میشود که برای هرکدام 3 حالت وجود دارد 01 10 00  پس میشود 3**5
 
الگوریتم الف:
میشه m-1 
از زوجیت میشه رفت
مثلا بگیم نفر آخر کلاهی که رنگش زوجه رو بگه(اگر زوجیت یکسان بود سیاه رو بگه) و نفر بعد ببینه اگر زوجیت رنگ کلاهی که گفته تغییر کرده میفهمه خودش به همون رنگه در غیر اینصورت به رنگ دیگس پس همه به جز نفر اخر(بدترین حالت) زنده میتونن بمونن

7 شمارش
اول مهره ها رو جوری میچنیم که هیچ 2 سبزی مجاور نشن بعد میخوایم از یه جایی این رشته رو ببریم که قطعا 2 ردیف ایجاد میشه که هیچ 2 سبزی مجاور نشن که میشه (9و11)*18
اما یه سری حالت هست که در رشته اولیه فقط و فقط 2 سبز کنار هم بیفتن و ما دقیقا از همونجا ببریم یعنی ردیف اول با سبز تموم شه و ردیف 2 با سبز شروع بشه
که برای حساب این حالات اول 8 تا سبزو بین 10 تا آبی میچینیم میشه (8و11) که میخوایم مهره سبز 9 امی رو کنار یکی از اون 8 مهره بذاریم که براش 16 تا جا داریم(8*2) پس در کل میشه (9و11)*18+(8و11)*16
3 لانه:
اول میگیم 21 خانه داریم و 2 رنگ پس یه رنگ هست که در  [21/2]=11 خونه اومده باشه 
بعد تو جدول در نظر میگیریم و میگیم(سطر ها 3 تا و ستونها 7 تا) در هر سطر 11/3 حداقل 3 تا از زنگ مثلا سفید اومده و در یکی از سظر ها از سفید 4 تا داریم
پس خوب اعداد 1 تا 7 رو برای سطر ها شماره گذاری میکنیم بعد میگیم در هر سطر شماره خانه های رنگ های سفید را مشخص میکنیم
شماره خانه های رنگهای سفید هر سطر با سطر دیگر حداکثر 1 اشتراک میتواند داشته باشد در غیر اینصورت مستطیل تشکیل میشود
حالا میبینیم که اگر برای سفید ها در هر سطر حداکثر 1 اشتارک بگیریم در سطر 3(میدانیم سطری با 4 رنگ سفید هست ما فرض میکنیم سطر 3) رنگ سفید 4 امی قطعا بایکی از سطرهای دیگر اشتراک دارد پس مستطیل یافت میشود

سلام 
سوال دو نظریه گراف
اگر تعداد راس های گراف را n در نظر بگیریم درجه هر راس عددی بین 0 تا n-1 است به طوری که هیچ وقت درجه دو راس همزمان 0 و n-1 نمی شود در نتیجه حداقل درجه دو راس برابر است
سلام 
پاسخ سوال یک نظریه گراف
بلند ترین مسیر را در نظر می گیریم راس اول و اخر را A و B  در نظر می گیریم حال اگر راس های A و B به راسی خارج از مسیر وصل باشند تناقض است زیرا مسیری بلند تر ساخته ایم پس در نتیجه این دو راس به راسی در مسیر وصل می شوند که در این صورت دور خواهیم داشت
سلام
جواب سوال الگوریتم های ترکیبیاتی :
قسمت اول)
کلاه ها را سیاه و سفید در نظر بگیرید
جواب برابر با m-1 است زیرا اگر به نفر اخر بگوییم که اگر زوجیت کلاه های سیاه دیگر افراد صف زوج بود رنگ کلاه خود را سیاه و در غیر این صورت سفید بگوید حال اگر تمام افراد را از اخر صف به ترتیب پیش قاضی ببریم m-1  نفر زنده می مانند
قسمت دوم)
کلاه ها را سیاه و سفید و قرمز در نظر بگیرید
جواب برابر با m-1 است زیرا اگر به نفر اخر بگوییم که اگر زوجیت کلاه های سیاه و سفید دیگر افراد صف برابر بود(یعنی یا هر دو زوج بودن یا هر دو فرد)رنگ کلاه خود را سیاه و در غیر این صورت سفید بگوید حال اگر تمام افراد را از اخر صف به ترتیب پیش قاضی ببریم m-1  نفر زنده می مانند
۲۵ خرداد ۹۷ ، ۱۵:۳۳ محمدرضا قلیچ خانی
سلام استاد کاملی عزیز. 
جواب سوال الگوریتم های ترکیبیاتی : 
جواب هر دو قسمت جزء صحیح m/2 میشه 
نفر اول رنگ کلاغ آخری را میگوید نفر دوم رنگ کلاغ دومی از آخر را میگوید و... پس این افراد رنگ کلاهشان را می فهمند
پاسخ:
سلام. 
غلطه. هم راه حل هم جواب
سلام.
مباحث فوق فقط مربوط به مبحث ترکیبیات المپیاد ریاضی هستند لطفا سوال از مباحث دیگر هم قرار دهید.
با تشکر از شما استاد بزرگوار.
پاسخ:
سلام. درست می فرمایید. خیلی سرم شلوغه . اما در اولین فرصت سعی می کنم فعالیت این صفحه رو خیلی گسترش بدم. 
پاسخ سوال 5 هندسه ترکیبیاتی
استقرا میزنیم
به ازای n=2که حکم برقرار است 
به ازای n=3 هم حکم برقرار است 
اکنون فرض میکنیم حکم به ازای t بزرگتر مساوی 2 تاk برقرار است
 اکنون به ازای k +1 
بکی از نقطه ها را در نظر نمیگیریم مثلا C حکمی که گفتیم برقرار است به ازای k تا اون خط شکسته رو میکشیم اکنون فاصله ی C را با همه ی پاره خط های خط شکسته مان در نظر بگیرید پاره خطی که با نقطه C کمترین فاصله رو داشت را AB میگیریم از Aبه C وصل کرده و از C به B اکنون تا قبل که طبق فرض استقرا مان خط شکسته خودشو قطع نمیکرد الان هم AC و CB خط شکسته رو قطع نمیکنند زیرا اگر قطع کنند آنگاه AB کوتاه ترین فاصله تا C رو نداشته .
پاسخ سوال 4 هندسه ترکیبیاتی
هر 3 نقطه ای از بین نقاط تشکیل 1 مثلث میدهند ما مثلثی را انتخاب میکنیم که بیشترین مساحت ممکن را داشته باشد مانند ABC 
از Aخطی موازی BC میکشیم از Cخطی موازی AB میکشیم و از Bخطی موازی AC خطوط کشیده شده یک دیگر را قطع میکنند فرضا در D و Eو F هیچ نقطه ی دیگری خارج از DEF نیست زیرا مثلا فرض کنید نقطه ای بالای خط موازی BC که از A رسم شده باشد (بالای ضلع ED ) آنگاه این نقطه با B و C مثلثی میدهد که مساحتش از ABC بیشتر است که این تناقض است برای اضلاع DF و FE نیز به همین صورت اثبات میکنیم پس نتیجه شد که همه ی نقاط داخل مثلث DEF هستتد  ما طبق صورت مسیله داریم که ABC در مثلثی به مساحت 1 جا میشود DEF مثلثی متشابه با ABC است با نسبت تشابه 2 پس اکنون کافی است ما آن مثلث به مساحت 1 را با نسبت تشابه 2 بزرگش کنیم که مثلثی به مساحت 4 حاصل میشود و DEF داخل آن قرار میگیرد
پاسخ سوال 1 لانه کبوتری
به مربع هایی به ضلع رادیکال 2 هفتم تقسیم میکنینم که 1 تقسیم بر رادیکال 2 هفتم میشه3.5رادیکال2 که عددی کمتر از 5 عه که حتی اگر 5 هم باشد آنگاه 25 مربع داریم و 51 نقطه که طبق لانه کبتری در مربعی 3 نقطه وجود خواهد داشت
پاسخ سوال 7 شمارش
ابتدا 19 مهره را در یک ردیف میچینیم طوری که هیچ دو سبزی کنار هم نیافتند (که باید اول آبی ها رو بچینییم ک میشه 1 طریق بعد 11تا جای خالی ایجاد میشه که 9 تا سبز رو توشون میزاریم که ینی میشه ترکیب 9 از 11 حالا این رشته 19 مهره ای رو از 18 جا میتونیم قطع کنیم و سمت راستیه رو در ردیف بالا و سمت چپیه رو در ردیف پایین قرار بدیم  اما  این همه حالات نیست
برخی از حالات هستن که ردیف اول با سبز تموم و ردیف دوم با سبز شروع شه که مسلما مهره یکی مونده به آخر در ردیف بالا آبی و مهره دوم در ردیف پایین آبی خواهد بود
اکنون 10 مهره آبی و 7 مهره سبز را در نظر بگیرید 2 تا از مهره های آبی رو توی ی باکس میگیریم اکنون به 9 حالت اون باکسه و 8 مهره ی آبی دیگه رو میشه توی ی ردیف قرار داد که 10تا جای خالی بینشون ایجاد میشه و به ترکیب 7 از 10 مهره های سبزو بینشون میزاریم و از هر جا که باکس آبی باشه جداش میکنیم و میشه همون حالتایی که بالا گفتم 
حالا فقط مونده حالتی که ی سبز توی ردیف 1 باشه و ردیف 2 هم با سبز شروع شه پس مهره ردیف دوم آبی خواهد بود  حالا دوباره تعداد رشته های متشکل از 7 تا سبز و 9 تا آبی رو در میاریم ک میشه ترکیب 7 از 10
و حالتی که ی سبز توی ردیف 2 باشه و ردیف 1 هم با سبز تموم شه ک اینم بازم میشه 7 از 10
ینی در کل 2310

پاسخ سوال1 گراف
یک راس از اون گراف رو انتخاب میکنیم مثلا B از بین مسیر هایی که از این راس شروع میشود بلندترینشان را انتخاب میکنیم آخرین راس در این مسیر را A بنامیم اکنون A درجه اش یک است مگر اینکه به راسی دیگر هم وصل شود که واسه اون راسه 2 حالت پیش میاد 
1 اینکه یا اون راسه ک قراره بهش وصل شه توی مسیر Aتا B عه ک میشه دور و حکم ثابته
2یا توی اون مسیر نیست و همچنان دور نمیدهد که در آن صورت B تا Aبلند ترین مسیر نیست
پاسخ سوال 3 لانه کبوتری
جدول ما 21 خونه داره که ممکنه 1 تا سیاه 20 تا سفید یا 2 تا سیاه 19 تاسفید یا ... یا 10 تا سیاه 11 تا سفید داشته باشه 
در کل رنگی که حداکثر جدول رو اشغال کرده حداقل 11 خونه رو گرفته (از حالا به بعد روی رنگی که حداکثر جدول رو پر کرده بحث میکنم و اصطلاحا  به خوته هایی ک توسط اون پر شدن میگم علامت خوردن )
در جدول ما ک 7 تا سطر داره یا سطری نیست که علامت نداشته باشه و یا فقط 1 سطر بی علامت وجود دارد زیرا که اگر 2 سطر بی علامت وجود داشته باشن مستطیل توی اون رنگ پدید اومده
حالتی ک ی سطر بی علامت داشته باشیم رو بررسی میکنیم از بین 6 سطر دیگه فرض میکنیم x سطر 3 علامت yسطر 2 علامت و z سطر یک علامت داشته باشن اگه x برابر با 1 باشه اون وقت y برابره با 0 از طرفی x بیشتر 1هم نمیتونه باشه چون اونطوری بدیهتا مستطیل میده پش zمیشه 8 در حالی که ما فقط توی 6 سطر علامت گذاشتبم ن 9 تا و تناقضه
و اگه که x برابر با 0 باشه y بیشتر از 3 نمیتونه باشه چون اون طوری طبق لانه کبوتری مستطیل خواهد داد پس y حداکثر 3 عه پس z میشه 5  که باز هم میشه 8 سطر و ما فقط 6 سطر داریم  و تناقضه
حالا فرض میکنیم همه سطر ها علامت دارن باز هم همون قضیه بالا پیش میاد و خب 9 از 7 هم بیشتره و 8 هم از 7 بیشتره و تناقضه
پس همواره ی مستطیل وجود داره با 11 خونه علامت خورده ک مسلما با بیش از 11 هم وجود خواهد داشت همچنان
پاسخ سوال 9 شمارش
حاصل جمع 4 تا عدد که یا یک باشن یا 4 درمیاد 4 یا 7 یا 10 یا 13 یا 16 که 7 و 13 تنها اعداد اول و تنها اعداد فرد هستن پس حکم سوال رو تغییر میدیم ب این ک مجموعشون فرد شه 
الان اون مربع سمت راست بالایی عه به ضلع 3 را در نظر بگیرین هر کدوم از خونه هاش میتونه 4 باشه یا 1 ینی 2 ب توان 9
حالا مجموع عددای توی این مربع 3 در 3 رو mدر نظر بگیرین m 
الان هر کدوم از خونه های (سطر اول ستون چهارم ) ، (سطردوم ستون چهارم )،(سطر سوم ستون چهارم ) یکتا تایین میشن چون ک مجموع هم سطری هاشون یا زوجه یا فرد ک اگ زوج باشه اون باید فرد و اگ فرد باشه اون باید زوج شه
و خونه های (ستون اول سطر چهارم) ، (ستون دوم ، سطر چهارم )،(ستون سوم سطر چهارم ) هم ب همون دلیل ک بالا گفتم یکتا تایین میشن خونه ی سطر چهارم ستون چهارم هم یکتا تایین میشه چون ک زوجیت حاصل جمع هم ستونی هاش با زوجیت حاصل جمع هم سطری هاش یکیه چون که در هر حال زوجیت حاصل جمع هم سطری هاش  و یا هم ستوتی هاش مخالف زوجیت m عه چون ک در جمع با m برابر میشه با حاصل جمع 3 عدد فرد که فرد عه پس خونه سطر چهارم ستون چهارم هم یکتا تایین شد یعنی در کل شد به 512 حالت



پاسخ سوال 6 شمارش
یک جدول 5 در 5 در نظر میگیریم 
حالتی ک سطر اول علامت خورده باشه رو  a1 
حالتی ک سطر دوم علامت خورده باشه رو a2  و ......
و حالتی ک سطر پنجم علامت خورده باشه رو a5 مینامیم
حالتی که ستون اول علامت خورده باشه رو b1 
حالتی که ستون دوم علامت خورده باشه رو b2 و ...
و حالتی که ستون ششم علامت خورده باشه رو b5 مینامیم
اکنون مجموعه A مساوی a1 و a2 و .... تا b5 رو در نظر بگیرید 
هر آرایش در جدول 5 در 5 ما دارای شرایط مسیله ب طور یکتایی یکی از زیر مجموعه های مجموعه Aاست جز علامت خوردن کل جدول که هم از a1 تا a5 به وجود میاد و هم از b1 تا b5 و هم از کل A
اکنون حرفی ک زدم رو اثبات میکنم 
فرض کنین جدول ما ی خونه خالی داشته باشه اون خونه ی خالی توی ی سطره و این یعنی ما از هیچ a ای واسه اون سطر استفاده نمیکنیم پس بقیه خونه های توی اون سطر ک علامت خوردن از b ب وجود اومدن و اون خونه های بالا یا پایین خونه ی خالی ما از a استفاده شده واسشون که خب الان دیدیم یکتا تایین شد ک جدول ما از چه زیر مجموعه ای ب وجود اومده  از طرفی هر زیر مجموعه ای هم (جز تهی) آرایشی از جدول میده که مورد قبول شرایط مسیله است و اون حالته ک میده بدیهتا یکتاست
و اگر جدول ما هم 2 خانه خالی یا بیشتر داشته باشد بازم یکتاست زیر مجموعه به وجود آورنده اش با همان استدلالی که واسه 1 خانه خالی کردم میشه ب این نتیجه رسید پس در کل 2 ب توان 10 منهای 3(یکی ب خاطر اون تهی عه دو تا هم ب خاطر اون 3 تا ک یک نتیجه یکسان میدادن )
پاسخ سوال 3 شمارش
رقم اول از سمت چپ هنگام جمع با معکوس با رقم دهم جمع میشود ک این  کلا دو تایی باهم میتوننن 3 حالت (0 و 0)،(0و 1 )، (1و0 )داشته باشن واسه جفت رقمای دوم و نهم_سوم و هشتم_چهارم و هفتم_پنجم و ششم هم قضیه همینه ک در کل در میاد 3 ب توان 5
پاسخ سوال 4 شمارش
یع جدول 2 در 10 ، 10 تا ستون داره از اون جا که هیچ دو خانه دارای ضلع مشترک هر دو تایی نباید علامت داشته باشن پس از هر ستون یا ی خونه علامت میخوره یا 0 خونه 
0 ستون بی علامت نی چون ک اونطوری 10 تا علامت گذاشتیم ن یکی
بیش از یک ستون بی علامت نیس چون ک اونطوری کمتر از 9 علامت گذاشتیم 
پس1 ستون بی علامت داریم
در حالتی ک اون ستون بی علامت ستون اول باشه جدول ب 2 حالت پر میشه چرا ک ستون دوم رو میگیریم اگ بالایی عه دارای علامت باشه باقی جدول ب طور یکتا در میاد و اگ پایینی عه دارای علامت باشه هم همین طور 
در حالتی هم ک ستون بی علامت ستون دهم باشه هم قضیه همینه
و در حالات دیگه به 2 ×2 حالت(2 حالت سر اون مستطیل سمت راست ک ایجاد میشه و 2 حالت سر اون مستطیل سمت چپ )
در کل در میاد 
36 حالت
پاسخ سوال 5 شمارش
بدیهی است ک زیر مجموعه مورد نظر تک عضوی نیست
ابتدا زیر مجموعه های دو عضوی را میابیم
X+Y=13
X و Y باید بزرگ تر از1 باشند زیرا که مجموعه ی ما اعداد طبیعی کوچک تر از 13 است
فرض کنیم 13 دایره در یک ردیف داریم در 12 جا میتوانیم از هم جدایش کنیم و سمت راستی را برابر Y و سمت چپی را برابر X در نظر میگیریم پس میشه 12 حالت از طرفی x=y هم نداریم زیرا که 13 عددی فرد است اما 12 تقسیم بر 2 میشه 6 زیرا که ترتیب عناصر توی زیر مجموعه ها اهمیتی نداره
حالا میریم سراغ زیر مجموعه های 3 عضوی 
x+y+z= 13 با شرط x و y  و zبزرگ تر از 1 که دوباره با همون تصور توپ ها میرسیم به ترکیب 2 از 12 که میشه 66 اما این حالت تکراری هم داره توی عنصر های زیر مجموعه ک غیر قابل قبوله حالتی ک 2 عدد تکراری و سومی متفاوت باشه به 6 حالتی که توی زیر مجموعه های دو عضوی رسیدیم دقت کنین از اونجایی که 13 عددی فرد است پس از x  و y  یکی زوج و یکی فرده ک اگه اون زوجه رو تقسیم بر دو کنیم میشه همین حالت هایی که الان دنبالشونیم پس هر 6 تا حالت 18 تا از 66 حالت بالا رو میدن پس میشه 48 که چون دوباره ترتیب مهم نی ی تقسیم بر 3 فاکتویل میخوره و میشه 8 هر 3 تا تکراری هم نداریم چون 13 بر 3 بخشپذیر نی
حالا میریم سراغ 4 تایی ها
اول ثابت میکنم 5 تایی یا بیشتر وجود نداره چون که در مینیمم مجموع توی ی زیر مجموعه 5 عنصری در میاد 15 ک از 13 بیشتره
حالا همون 4 تایی ها کوچک ترین عنصر زیر مجموعه 4 عضوی نمیتونه 2 باشه ک چرا ک در مینیموم مجموع 14 در میاد پس یکه که حالا روی یکی مونده ب کوچک ترین عنصر حالت بندی میکنیم ک یا دو عه یا 3 (4 نمیتونه باشه زیرا ک دوباره تو همون مینیمم میرسیم ب مجموع 16
حالا اگه2 باشه ب (1 و 2 و 3 و7 ) و (1 و 2 و 4 و 6 ) میرسیم و اگه 3 باشه ب (1 و 3 و 4 و 5 ) میرسیم 
ک در کل میشه 6+8+3
سطح سوالات خیلی پایینه لطفا کمی بالا ببرید 





پاسخ:
ابتدا این سوالها رو حل کنید. 
راه حل اینها رو بنویسید . 
حتما سوالات سخت تر هم قرار می دم. 
۲۹ دی ۹۶ ، ۰۰:۵۶ روژینا شهبازی
2 لانه کبوتری
فرض خلف میکنیم که اشتراک کمتر 1/9 است پس فرض کنیم قالیچه اول به اندازه 1 جا میگیرد اما قالی دوم از 8/9 کمتر جای میگیرد(چون از 1/9 کمتر اشتراک دارد) و به همین ترتیب قالی سوم کمتر از 7/9 جا میگیرد و ...
که جمع 1/9+...+1=5 ولی ما فرض کرده بودیم کمتر از اینها جا میگیرد در نتیجه کمتر از 5 جا میگیرد که خلاف فرض مسئله است
2 گراف
درجه رئوس باید از :
0 1 .....  n-1 باشد اما اینکه راس دارای n-1 درجه به همه وصل است پس راسی نمیتواند 0 درجه داشته باشد پس اثبات شد بنابر لانه کبوتری
البته این سوال خیلی اسون بود

پاسخ:
درسته . اگر بتونی جواب ها رو مجزا بنویسی خیلی بهتره. بله بعد از مرحله اول سوال های سخت تر می زارم.

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">