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

[daneshvar.amrollahi]

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

سلام. سوال سوال 144 sgu هستش. درواقع ترکیبیاتیه! (احتمالات).

فرض کنیم یه بازه به طول K داریم که روش بی نهایت عدد حقیقی وجود دارند. به چند طریق میشه 2 نقطه از این بازه انتخاب کرد به طوری که فاصله شون کوچکترمساوی Z باشه؟؟ (چون K , Z حقیقی هستند سخت شده اگر صحیح بود راحت بود!)

ایدم اینه: تو صفحه ی مختصات یه مربع به ضلع K رو در نظر بگیرید که راس پایین چپشون روی مبدا 0و0 هستش. ما میخواهیم نقاطی از صفحه را انتخاب کنیم که | x-y | کوچکتر مساوی Z باشه و تحت پوشش این مربع باشند.

این هم از شکل ایده یه ذره شهود بگیرید چی میگم!

کسی میتونه اینو تکمیل کنه؟ باید مساحت هاشور خورده رو حساب کرد.

کسی راه آسون تر داره؟

ویرایش: سوال حل شد. اگر جواب رو خواستید بگم!

 

[daneshvar.amrollahi]

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

سلام. یه سواله تئوری هستش. ممکنه تا حدی الگوریتمی هم باشه:

یه آدم به اسم A داریم که میخواد با 13 آدم دست بده. تو هر مرحله 10 نفر از اون 13 آدم انتخاب میکنه (هیچ زیرمجموعه 10 تایی رو بیش از 1 بار انتخاب نمیکنه) و با همشون 1 بار دست میده. تعداد این مراحل رو n در نظر بگیرید. سوال میگه حداقل n رو تعیین کنید به طوری که A با همه حداقل 1 بار دست داده باشه و تعداد دست دادن های هرفرد با فرد A متمایز باشه (13 تا آدم بین خودشون دست نمیدن).

a اندیس i رو برابر تعداد دست دادن های نفر i ام تعریف کنیم. میدونیم جمع a ها بزرگتر مساویه 1+2+3...+13 هستش. همچنین میدونیم جمعشون بر 10 بخشپذیره. از این 2 تا میشه نتیجه گرفت که حداقل 10 مرحله طول میده. اما آیا میشه برای 10 مثال آورد؟ ایده همینه یا کلا یه چیز دیگست؟

 

[daneshvar.amrollahi]

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

چرا همش من دارم اینجا سوال میذارم؟ یکی بیاد یه جوابی بده

سوال 5.1.33 ترکیبیات زرده. میگه که: یک سازنده ی اسباب بازی در هر روز حداقل 1 اسباب بازی درست می کنه ولی در طول سال توان ساخت بیشتر از 725 اسباب بازی را ندارد. به ازای هر عدد طبیعی مانند n ثابت کنید چند روز متوالی وجود دارد که این سازنده طی آنها دقیقا n اسباب بازی ساخته است (سال زا 365 روزه در نظر بگیرید).

خوب اومدم همون ایده ای که خودش چند بار گفته رو استفاده کردم. Si رو تعریف می کنیم تعداد اسباب بازی هایی که تا آخر روز i ام ساخته. چون هر روز حداقل 1 اسباب بازی ساخته، دنبالشون اکیدا صعودی هستش.

1 <= S[1] < S[2] < ... < S[365] <= 725

n + 1 <= S[1]+n < S[2]+n < ... < S[365]+n <= 725+n

الان 2*365 یعنی 730 تا عدد داریم که هرکدوم بین 1 تا 725+n هستند. چون هر دو دسته ای که نوشتم اکیدا صعودین، اگر لانه بزنیم: سقف ( 730 تقسیم بر (725+n) ) عدد هستند که باهم برابرند و این دو تا عدد از دو دسته ی مختلفن. ما میخوایم این مقدار تقسیمه برای هر n ای حداقل 2 بشه که بتونیم بگیم یه سری روز متوالی هستش که n تا اسباب بازی ساخته. اما معلومه که به ازای هر n ای این حاصل تقسیم بزرگتر مساوی 2 نیست!

احتمال خیلی زیاد سوتی بدی داده ام! بگید ایراد کار کجاست! ایده ی دیگه ای داره؟

*ویرایش: ببخشید حواسم نبود بیش از 1 سال هم میتونه کار کنه!

فکر کنم باید کلی ترش کنیم. مثلا بگیم k سال کار می کنه... ؟ بعدش لانه بزنیم:

ceil [ (730*K) / (725*K+n) )

میخوایم این عبارت بزگرتر مساوی 2 بشه. واسه هر عدد طبیعی که k ای میشه پیدا کرد که این عبارت درست بشه. درسته؟

 

[Anita H]

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

چرا همش من دارم اینجا سوال میذارم؟ یکی بیاد یه جوابی بده

سوال 5.1.33 ترکیبیات زرده. میگه که: یک سازنده ی اسباب بازی در هر روز حداقل 1 اسباب بازی درست می کنه ولی در طول سال توان ساخت بیشتر از 725 اسباب بازی را ندارد. به ازای هر عدد طبیعی مانند n ثابت کنید چند روز متوالی وجود دارد که این سازنده طی آنها دقیقا n اسباب بازی ساخته است (سال زا 365 روزه در نظر بگیرید).

خوب اومدم همون ایده ای که خودش چند بار گفته رو استفاده کردم. Si رو تعریف می کنیم تعداد اسباب بازی هایی که تا آخر روز i ام ساخته. چون هر روز حداقل 1 اسباب بازی ساخته، دنبالشون اکیدا صعودی هستش.

1 <= S[1] < S[2] < ... < S[365] <= 725

n + 1 <= S[1]+n < S[2]+n < ... < S[365]+n <= 725+n

الان 2*365 یعنی 730 تا عدد داریم که هرکدوم بین 1 تا 725+n هستند. چون هر دو دسته ای که نوشتم اکیدا صعودین، اگر لانه بزنیم: سقف ( 730 تقسیم بر (725+n) ) عدد هستند که باهم برابرند و این دو تا عدد از دو دسته ی مختلفن. ما میخوایم این مقدار تقسیمه برای هر n ای حداقل 2 بشه که بتونیم بگیم یه سری روز متوالی هستش که n تا اسباب بازی ساخته. اما معلومه که به ازای هر n ای این حاصل تقسیم بزرگتر مساوی 2 نیست!

احتمال خیلی زیاد سوتی بدی داده ام! بگید ایراد کار کجاست! ایده ی دیگه ای داره؟

*ویرایش: ببخشید حواسم نبود بیش از 1 سال هم میتونه کار کنه!

فکر کنم باید کلی ترش کنیم. مثلا بگیم k سال کار می کنه... ؟ بعدش لانه بزنیم:

ceil [ (730*K) / (725*K+n) )

میخوایم این عبارت بزگرتر مساوی 2 بشه. واسه هر عدد طبیعی که k ای میشه پیدا کرد که این عبارت درست بشه. درسته؟

عه جدن بیشتر از یه سال هم میتونه کار کنه؟ :‌))
خب کا رو مساوی ان بذار درست میشه :-‌""

 

[daneshvar.amrollahi]

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

یه دنباله ی نا متناهی از اعداد طبیعی بزرگتر از ۱ داریم که اعدادش دو به دو متمایزند. ثابت کنید برای ۱۰۰ تاشون این ویژگی برقراره:

a [ i ] > i

فکر کنم به جای ۱۰۰ بشه هر عددی گذاشت. اومدم خلف زدم گفتم فرض حداکثر واسه ۹۹ تاش برقرار باشه. یعنی واسه متناهی تاش برقرار باشه. یعنی واسه نا متناهی تاش داریم : a [ j ] <= j . حالا نمیدونم از این میشه به تناقض رسید یا نه؟!

کسی میتونه حلش کنه؟

 

[Fliqpy]

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

فرض کنید از N به بعد، a[j]<=j
فرض کنید برای نامتناهی تاشون داشته باشیم a[j]<j پس a[j]<=j-1 حالا جمع N عضو اول دنباله رو بگیر M. پس چون نامتناهی تا عدد داشتیم که a[j]<j یه K هست که تا اونجا M+N تا از این عددا اومده. پس جمع K عضو اول دنباله رو بگیرید. از یه طرف چون اعضا متمایزن پس از جمع K عدد طبیعی اول یعنی K(K+1)/2 بیشتره، از طرفی هستش جمع N عضو اول دنباله(M) و جمع باقی اعضا، اما باقی اعضا در این خاصیت صدق میکنند که حداقل M تاشون از اندیسشون کمترن و باقی از اندیسشون کمتر مساوی، پس جمعشون از K(K+1)/2-N(N+1)/2-M نابیشتره، پس جمع کل از K(K+1)/2-N(N+1)/2 ناکمتره، در حالی که حداقل K(K+1)/2 هست که تناقضه.
پس از T به بعد a[j]=j پس قبل از T همه اعداد کمتر از T هستن و از طرفی بیشتر از 1 پس حداکثر T-2 حالت دارن در حالی که T-1 عدد داریم که تناقضه.

 

[daneshvar.amrollahi]

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

یه جور دیگه هم فکر کنم بشه گفت:

خلف میزنیم. فرض می کنیم فقط n تا عدد باشن که از اندیسشان بزرگتر باشند

میایم مینویسمشان:

a[x1] = y1 , y1 > x1
a[x2] = y2 , y2 > x2
...
a[xn] = yn , yn > xn
​

فرض می کنیم y1 < y2 < y3 < ... <yn . یه جدول میکشیم ۲ تا ستون داره. توی ستون چپش اندیس ها رو مینویسیم زیر هم. یعنی x1 , x2 , ... .
توی ستون سمت راستش مقدار هارو مینویسیم یعنی y1 , y2 , ... yn. میدونیم مقادیر ستون راست از ۱ میتونند باشند تا n. اما مقادیر سمت راست نمیتونند ۱ باشند. پس مقدار هایی که سمت چپ داره از راست بیشتره. از اونجا که به هر عدد توی ستون راست فقط یک عدد از سمت چپ map میشه (یک به یکه) ، یعنی یکی از عدد های سمت چپ به یه عدد بزرگتری map شده که اصلا تو ستون راست نبوده! چون تعداد راستیا از چپیا کمتره! تناقض. چونکه فرض کرده بودیم yn بزگرترینه.

فکر کنم خیلی بد گفتم