سوالات ترکیبیات و مباحث ویژه !

[عمو ژپتو]

پاسخ : استقرا

خوب من تیکه ای که برای 2به توان آ ها میشه رو اثبات کنم
ینی یه مقداریش رو من میگم بعد باهم کاملش کنیم
فرض رو عوض میکنم میگم برای 2به توان آهابه جایی میرسیم که همشون روشن باشن
پایه که برای 2بدیههیه چون در ثانیه اول هر دو روشن میشن
برای آ میگیم 2 به توان آ-1 تا اول طبق فرض مسئله روشن میشن همشون و همین جوری اگه به 2 به توان آ-1 دوم هم همشون روشن میشن
فقط نکتش تو 2 تا لامپ وسطه که آیا طبق فرض انجام می شه یا نه
خوب در لحظه
نه چوب داشت شرمنده
پاکش نکردم که ببینید حد اقل

 

[عمو ژپتو]

پاسخ : استقرا

خوب راه حل قبل رو کامل میکنم
خوب طبق فرض قوی شده همه در یک لحظه روشن میشوند
خوب حالا برای 2 به توان آ طبق فرض همه لامپ ها روشن میشوند در این مرحله (اسم مرحله رو میذاریم ب) تمام 2 به توان آ-1 اول روشن و 2 به توان آ-1 دوم خاموش چون تا به حال هیچ تغیری توشون رخ نداده(چرا؟)خب در این مرحله دو لامپ وسط روشن می مانند و باقی خا موش میشوند همه (چون همشون با کناری هاشون یکیند) حالا انگار دوتا دسته داریم که هر کدوم 2 به توان آ-1 و لامپ آخرشون روشن و طبق فرض استقرا همه لامپ هاشون در نهایت روشن میشند
لم 1:خب در اواسط راه دو لامپ وسط روشن شدند و ما به فرض رفتیم حال ثابت میکنیم که مشکلی وجود ندارد ینی لامپ 2 به توان آ-1 ام دقیقا همانند لامپ 1 ام عمل میکنئ:
همانطور که دقت کرده اید در این لحظه تمامی لامپ ها به جز دولامپ وسط روشنند پس هر اتفاقی که بر روی لامپ 2 بهتوان آ ام میاتد همانند اتفاقاتی است که برای لامپ 2 به توان آ+1 ام میافتد زیرا هردو روشن و دو طرف هر دو به صورت یکسانی لامپ قرار دارد پس در نتیجه وجود این دولامپ برای یکدیگر احساس نمیشود پس همانند لامپ 1 عمل میکنند
مشکلی داشت؟

 

[مهسا.ق]

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

گراف رو هم می تونیم یه کارایی واسش بکنیم ها !!
من تاپیکش رو بزنم ؟

مهتاب
می خوای بذار یه کم انجمن نظم بگیره بعد تاپیکشو بزن آخه دیه این همه کار رو خدایی نمی شه با هم کرد
بازم من نمی دونم

روابط بازگشتی

منم به نظرم خوبه با همین بریم چون الان همین نظرسنجی بالایی رای آورد بازگشتی رو بریم یا نظرسنجی بذارم دوباره؟
چی می گید مردم؟

 

[mahtab.f]

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

منم با بازگشتی موافقم !

× باوش صبر میکنیم تا نظم بگیره !

 

[سیاوش]

پاسخ : استقرا

خوب راه حل قبل رو کامل میکنم
خوب طبق فرض قوی شده همه در یک لحظه روشن میشوند
خوب حالا برای 2 به توان آ طبق فرض همه لامپ ها روشن میشوند در این مرحله (اسم مرحله رو میذاریم ب) تمام 2 به توان آ-1 اول روشن و 2 به توان آ-1 دوم خاموش چون تا به حال هیچ تغیری توشون رخ نداده(چرا؟)خب در این مرحله دو لامپ وسط روشن می مانند و باقی خا موش میشوند همه (چون همشون با کناری هاشون یکیند) حالا انگار دوتا دسته داریم که هر کدوم 2 به توان آ-1 و لامپ آخرشون روشن و طبق فرض استقرا همه لامپ هاشون در نهایت روشن میشند
لم 1:خب در اواسط راه دو لامپ وسط روشن شدند و ما به فرض رفتیم حال ثابت میکنیم که مشکلی وجود ندارد ینی لامپ 2 به توان آ-1 ام دقیقا همانند لامپ 1 ام عمل میکنئ:
همانطور که دقت کرده اید در این لحظه تمامی لامپ ها به جز دولامپ وسط روشنند پس هر اتفاقی که بر روی لامپ 2 بهتوان آ ام میاتد همانند اتفاقاتی است که برای لامپ 2 به توان آ+1 ام میافتد زیرا هردو روشن و دو طرف هر دو به صورت یکسانی لامپ قرار دارد پس در نتیجه وجود این دولامپ برای یکدیگر احساس نمیشود پس همانند لامپ 1 عمل میکنند
مشکلی داشت؟

من خوندم حل رو و درسته ولی نوشتنت عالی نبود
از همین حالا نوشتن را هم تمرین کنید ممکنه یه سوال را کامل درست حل کنید ولی به خاطر نوشتن بد نمره کم بشه ازتون ( من 0 ام دیدن بدن ) پس از همین حالا سوالایی را که حل میکنید ففرض کنید سواله مرحله 2 هستش و برای یه مصحح عصاب داغون بنویسید خیلی خیلی تاثیر داره .
راستی برای نوشتن فرمول های ریاضی از لاتکس استفاده کنیم
http://www.codecogs.com/latex/eqneditor.php

اثبات 1 سال پیش خودم :
*= اگر لامپی با یکی از لامپ های کناری خود وضعیت یکسانی داشته باشد تاثیری در روشن یا خاموش بودن یکدیگر ندارند.
با استقرا نشان میدهیم که اگر تعداد لامپ ها

بود نهایتا همه ی لامپ ها در

روشن میشوند .
حکم برای 2 و 4 واضحه . حال فرض کنیم برای

هم درست باشه اکنون

در نظر میگیریم لامپ های

.

مرحله اجرا میشود بدون تاثیر گرفتن یا گذاشتن از لامپ های R (یه نفر بگه چرا اگه نگید ازتون نمره کم میشه ) در این مرحله تمام لامپ های L روشن هستند و لامپ های R خاموش هستند بعد از 1 مرحله ی دیگر

روشن و بقیه خاموش هستند و از این مرحله به بعد R , L متقارن خواهند بود ( یعنی

وضعیت یکسانی خواهند داشت) و هر گز بر یکدیگر تاثیر نخواهند گذاشت (*)طبق فرض در تمام لامپ ها در قسمت R روشن و متناظر اون L هم روشن میشه و حکم اتباته . زیرا ما

مرحله انجام دادیم

قسمت ب را هم زود اثبات کنید دیگه

پ.ن : حسش نبود اثبات کامل با توضیحات بنویسم حالا که 2 باره خوندم دیدم اثباته افتضاحی شد همون ماله پدر بزرگ را بخونید

 

[informatic]

پاسخ : استقرا

ثابت می‌کنیم برای همــه‌ی اعداد به صورتِ

نمیشــه همــه‌ی لامپ‌ها روشن بشن !!!

خوب طبق ِ قسمتِ بالا () در مرحلــه‌ی

ــُم همــه‌ی لامپ‌های

تا

روشن هستن و لامپِ

خاموشـــه ... پس تو مرحله‌ی بعدی لامپ‌های

روشن میشن و بقیـیه‌ی لامپ‌ها هم خاموش میشن !!! که این مرحله هم‌ارز ِ همون مرحله‌ی دومــه !!!!! پس هیچ‌وقت همــه‌ی لامپا روشن نمیشن و هیچ وقت هم همشون خاموش نمیشن !!!!!

 

[سیاوش]

پاسخ : استقرا

درسته
ممنون از همه که روی این سوال فکر کردید .

اونایی که حل کردن یه آفرین بیشتر

باید بگم این سواله شورت لیست سال 2006 بود C1 البته .

یه استقرایه ساده میخواست :)

اینجا شورت لیست سال 2006
و اینم لینک خود سوال .

 

[informatic]

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

آقا لونه کبوتری به این خوبی !!! بازگشتی که بیشتر برای مرحله یکـــه ... میخواین چیکار ؟!!!؟!


اگــه فعلا مشکلتون فقط سوالـــه ، من سوال میذارم


فرض کنید یه جدولِ n*n از اعداد صحیح داریم و اختلافِ هر دو خونه‌ی مجاور(مجاور ِ ضلعی) حداکثر 1 ـــه .... ثابت کنید عددی وجود دارد کــه حداقل

بار تکرار شده است ... (اگــه اینُ حل کردید ، میتونید برای n ــِش هم ثابت کنید ، یعنی ثابت کنید عددی وجود داره کــه حداق n بار تکرار شده است ! ... تا اونجایی کــه یادمــه این قسمتش لونه‌کبوتر نبود ولی ایدش قشنگ بود !!!)


پ.ن : قسمتِ اولش تقریبا آسونــه ولی قسمتِ دوم (برای n !!!) میشه گفت ایده باید بزنید !!!!!!!!!!

 

[ROZHIN kocholoo]

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

هر کاری کردم بخش دومش به حالت خاص حل شد
برا اولی یه جورایی رو تعداد اعداد ل.ک رفتم بعد ثابتش کردم.
برا دومی رو چینش اعداد کار کردم که یه جورایی دراومد که تو قطرها عدد یکسان قرار می گیره که بعد دراومد که رو قطر اصلی هم یک عدد دیده می شه (همیشه)که همون n می شه
اصلا یه جوری شد که خودم خوشم نیومد ولی بازم یه راه بود درست غلطش دیگه

 

[عمو ژپتو]

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

یه چیزی به نظرتون برای قسمت 1 ش اینکه بیایم اعداد رو تو هر سطر سورت کنیم به درد نمیحوره
به نظرم اگه اینکارو کنیم برای قسمت دومشم به درد میخوره ها
یه نکته
به نظرم باید فضای انجمن عوض شه قرار نیست سوال بذاریم خودمون حل کنیم باید بیاید باهم حل کنیم آروم آروم موافقید

 

[ROZHIN kocholoo]

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

اونجوری هم امتحان کردم ولی مستقیم به جواب 2 رسیدم بدون اینکه به جواب یک برسم.
اگر سورتشون هم کنیم همون حالتی که توضیح دادم درمیاد.(همون حالت قطریه)

 

[عمو ژپتو]

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

اونجوری هم امتحان کردم ولی مستقیم به جواب 2 رسیدم بدون اینکه به جواب یک برسم.
اگر سورتشون هم کنیم همون حالتی که توضیح دادم درمیاد.(همون حالت قطریه)

خوب یک در مورد راه حل تون توضیح بدید که ما هم بفهمیم و کامل کنیم باهم

 

[parand]

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

ميشه اينطوري بگيم؟
قسمت يكش:
كوكترين و بزرگترين اعداد اين جدول رو در نظر ميگيريم، اين دو تا حداكثر 2n-2 تا ميتونن با هم اختلاف داشته باشن(يعني تو دورترين حد از هم باشند يعني روي دو تا راس غير مجاور باشند)
كه يعني حداكثر1-2n عدد هست تو جدول
و چون n*n=n^2 عدد هست تو جدول طبق لانه كبوتري(تعميمش البته!)حداقل يك عدد هست كه حداقل (n^2/(2n-1 بار تكرار شده تو جدول كه اين عدد از

يه ذره بيشتره حتي!

 

[ROZHIN kocholoo]

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

من اینجوری گفتم که اول اون 2nعدد (n-....n)رو بدون در نظر گرفتن قوانین تو جدول می ذاریم که دو سطر رو می گیرند .اگر همین روند رو ادامه بدیم هر عددn/2بار دیده می شه.حالا اعداد رو بر اساس اون قانونا می ذاریم که علاوه بر این که نوع چینش اعدادمون تغییر می کنه بعضی از اعداد تعداد تکرارشون کم می شه بنابراین طبق اصل ل.ک گروهی تعدادشون کمتر از n/2و گروهی بیش تر از n/2می شه بنابراین عدد یا اعدادی وجود دارند که تعدادشون از n/2یش تره.
برای بخش 2از همون اول اعداد رو با رعایت قوانین می چینیم یک عدد (ترجیحا بزرگترین)رو یه گوشه ی جدول می ذاریم و بقیه اعداد بدون تکرار عمدی به صورت یکتا قرار می گیرن
1- 2- 3- 4- 5-
0 1- 2- 3- 4-
1 0 1- 2- 3-
2 1 0 1- 2-
3 2 1 0 1-
خب تو اون مثال می بینید که تکرار ها به صورت اریبه و رو قطر اصلی هم فقط یک عدد تکرار شده که تعدادش همون nمی شه
اگر هم سعی کنیم مثلا به جای 3- 4- بذاریم(تکرار عمدی)تو خونه سمت راست و ژایینش 3- قرار می گیره پس با هر تکرار عمدی عددی که حذف شد تعدادش یکی بیشتر می شه
که باز هم تعدادn پایداره.

 

[عمو ژپتو]

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

راستی یه سوال
نمیتونیم بگیم که مثلا اگه کوچیکترین عدد جدول 5 باشه بزرگترینش حداکثر 10
ببخشید راه حل دوتا بالایی رو ندیدم
خوب من میگم نمیشه قوی ترش کرد؟

 

[ROZHIN kocholoo]

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

در حالت عادی تو اون مثاله اگه کوچکترین عدد 5 باشه بزرگترین 13 می شه ولی اگه تکرار عمدی داشته باشه چرا که نشه.

 

[عمو ژپتو]

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

من این دوتا راه حلتون رو که خوندم به نظرم هیچکدوم درست نمیاد
کسی حل نکرده اینو
من دوسه تا ایده به زهنم رسید اما خوب هیچکدوم جواب ندادن
مثلا ببینید میایم میگیم تمام اعداد رو ازشون کم میکنیم جوری که کوچیکترن عدد 0 باشه
خوب این مشکلی نیست به طبع
حالا اگه بزرگترین عدد n باشه که مسئله حله
حالا اگه بزرگترین عدد kباشه که k>n اونوقت اگه یکم روش کار شه به نظرم به نتیجه میرسه
مثلا اگه یدونه k باشه پس حتما 2 تا k-1حداقل هست و چون گفتیم 1 دونه باشه پس حداقل 3 تاk-2 هست....
و خوبیش اینه که چون k>n و این روند یکی یکی میره پس به عددی میرسیم که تعدادش بیشتر از n ولی خوب یکم مشکل داره
یه نکته دیگه هم که هست چون تو جدول 0 داریم پس k فاصلش تا 0 هم یه چیزیه که میشه روش کار کرد و k نمیتونه همه جا باشه....
خوب همه بیاید یکم باهم روش فکر کنیم حل شه دیگه

 

[ROZHIN kocholoo]

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

1- دقت داشتید که تو سئوال گفته اعداد صحیح هستند ؟
منم تقریا همون کار شما رو کردم ولی اعدادم محدوده از n-تا n بنابراین kمن هیچ وقت از n بیش تر نمی شد .

برای بخش 2از همون اول اعداد رو با رعایت قوانین می چینیم یک عدد (ترجیحا بزرگترین)رو یه گوشه ی جدول می ذاریم و بقیه اعداد بدون تکرار عمدی به صورت یکتا قرار می گیرن
1- 2- 3- 4- 5-
0 1- 2- 3- 4-
1 0 1- 2- 3-
2 1 0 1- 2-
3 2 1 0 1-

منظور از تکرار قطری اینه که به قول شما kیکی باشه.

حالا اگه بزرگترین عدد kباشه که k>n اونوقت اگه یکم روش کار شه به نظرم به نتیجه میرسه
مثلا اگه یدونه k باشه پس حتما 2 تا k-1حداقل هست و چون گفتیم 1 دونه باشه پس حداقل 3 تاk-2 هست....
و خوبیش اینه که چون k>n و این روند یکی یکی میره پس به عددی میرسیم که تعدادش بیشتر از n ولی خوب یکم مشکل داره

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

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

از این تیکه هیچی نفهمیدم واضح تر توضیح بدین

 

[ROZHIN kocholoo]

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

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

 

[sayna]

پاسخ : استقرا

چرا سوال نمیذارید ؟ قرار نیست حتما ِ حتما هم حل بشه ، خوبیه این جور تاپیکا اینه که راجع به یه سوال می‌شه کلی بحث کرد ، ایده جدید برای حلش داد و اینا ! در کل خواستم بگم تاپیک نخوابه :د