سوالات ترکیبیات(لانه کبوتری)2

[rezoos]

1.چند زیر مجموعه ی n عضوی از

مانند S وجود دارد که تفاضل هیچ دو عضوی از S برابر 1 نیست.
2. 55 عدد از مجموعه ی

در اختیار داریم. فرض کنید k عددی طبیعی باشد و k<9. ثابت کنید تفاضل دو تا از این اعداد برابر k است.
3.مساله ای که خیلی استفاده داره و به عبارتی مهمه! : n+1 عدد حقیقی متعلق به بازه ی (0,1] در اختیار داریم. ثابت کنید تفاضل دو تا از این اعداد از

کوچکتر است.(از کتاب ترکیبیات علیپور نوشتم!ص106 و 107)

 

[Goharshady]

1.چند زیر مجموعه ی n عضوی از

مانند S وجود دارد که تفاضل هیچ دو عضوی از S برابر 1 نیست.

چه ربطی به لانه کبوتری داره؟
مستقیما حل می کنم.
زیرمجموعه های مورد نظر را با صفر و یک متناظر می کنم. (به همان روش معروف) اینک نباید هیچ دو تا یکی مجاور باشند. چون n تا 1 و n تا 0 داریم فقط دو حالت ممکن است : با 0 شروع شود یا با 1 شروع شود.

 

[Goharshady]

1.چند زیر مجموعه ی n عضوی از

مانند S وجود دارد که تفاضل هیچ دو عضوی از S برابر 1 نیست.
2. 55 عدد از مجموعه ی

در اختیار داریم. فرض کنید k عددی طبیعی باشد و k<9. ثابت کنید تفاضل دو تا از این اعداد برابر k است.
3.مساله ای که خیلی استفاده داره و به عبارتی مهمه! : n+1 عدد حقیقی متعلق به بازه ی (0,1] در اختیار داریم. ثابت کنید تفاضل دو تا از این اعداد از

کوچکتر است.(از کتاب ترکیبیات علیپور نوشتم!ص106 و 107)

پاسخ 3:
بازه ی 0 تا 1 را به n بازه به طول

تقسیم می کنیم. به این صورت:

بدیهی است که دو عدد در یک بازه قرار می گیرند و تفاضل آنها از

کمتر می شود.

 

[rezoos]

1.چند زیر مجموعه ی n عضوی از

مانند S وجود دارد که تفاضل هیچ دو عضوی از S برابر 1 نیست.

چه ربطی به لانه کبوتری داره؟
مستقیما حل می کنم.

زیرمجموعه های مورد نظر را با صفر و یک متناظر می کنم. (به همان روش معروف) اینک نباید هیچ دو تا یکی مجاور باشند. چون n تا 1 و n تا 0 داریم فقط دو حالت ممکن است : با 0 شروع شود یا با 1 شروع شود.

1.جوابتون 2 هست؟ کتاب گفته این نیست!
2. گفتین:چون n تا 1 و n تا 0 داریم فقط دو حالت ممکن است : با 0 شروع شود یا با 1 شروع شود.
چرا فقط این دو حالته؟

 

[rezoos]

میشه سوال 3 رو این جوریم حل کنیم؟(منظور:این راه حل هم درسته؟

)
n+1 عدد را به ترتیب صعودی مرتب می کنیم:

از برهان خلف استفاده می کنیم به ازای هر i,j , j>i ,

باشد. کوچکترین تفاوت ها را در نظر می گیریم. فرض می کنیم

کوچکترین تفاضل باشد.
جملات زیر را با هم جمع می زنیم:

.
.
.

حاصل میشود:

که این با فرض اولیه تناقض دارد.بنابراین i,j ای وجود دارد که j>i ,

باشد.
از جمله راه حل های من در آوردی خودمه. نخندین، فقط بگین درسته یا نه

 

[Goharshady]

1.چند زیر مجموعه ی n عضوی از

مانند S وجود دارد که تفاضل هیچ دو عضوی از S برابر 1 نیست.

چه ربطی به لانه کبوتری داره؟
مستقیما حل می کنم.

زیرمجموعه های مورد نظر را با صفر و یک متناظر می کنم. (به همان روش معروف) اینک نباید هیچ دو تا یکی مجاور باشند. چون n تا 1 و n تا 0 داریم فقط دو حالت ممکن است : با 0 شروع شود یا با 1 شروع شود.

1.جوابتون 2 هست؟ کتاب گفته این نیست!
2. گفتین:چون n تا 1 و n تا 0 داریم فقط دو حالت ممکن است : با 0 شروع شود یا با 1 شروع شود.
چرا فقط این دو حالته؟

حق با شماست
ببخشید ، اشتباه شد!
n تا یک داریم. ابتدا آنها را به یک طریق در یک سطر می چینیم. سپس باید بین هر دو تا یک ، صفر قرار دهیم. (پس n-1 صفر مصرف شد) حالا صفر n ام را می توانیم آخر دنباله بگذاریم یا اول آن بگذاریم یا هر جایی بین 1 ها یعنی n+1 حالت داریم.
واقعا برای این اشتباه معذرت می خواهم.

 

[Goharshady]

میشه سوال 3 رو این جوریم حل کنیم؟(منظور:این راه حل هم درسته؟

)
n+1 عدد را به ترتیب صعودی مرتب می کنیم:

از برهان خلف استفاده می کنیم به ازای هر i,j , j>i ,

باشد. کوچکترین تفاوت ها را در نظر می گیریم. فرض می کنیم

کوچکترین تفاضل باشد.
جملات زیر را با هم جمع می زنیم:

.
.
.

حاصل میشود:

که این با فرض اولیه تناقض دارد.بنابراین i,j ای وجود دارد که j>i ,

باشد.
از جمله راه حل های من در آوردی خودمه. نخندین، فقط بگین درسته یا نه

حاصل

نمی شود ، از آن نامساوی ها نتیجه می شود که

و این تناقض است.
ضمنا از کوچکترین تفاضل چه استفاده ای کردید؟ یعنی اصلا لازم بود؟

 

[Goharshady]

اشتباه من از آن جا ناشی شد که سوال را درست نخواندم و فکر کردم باید به پیمانه ی 2n حساب کنم.

 

[rezoos]

1.چند زیر مجموعه ی n عضوی از

مانند S وجود دارد که تفاضل هیچ دو عضوی از S برابر 1 نیست.

چه ربطی به لانه کبوتری داره؟
مستقیما حل می کنم.

زیرمجموعه های مورد نظر را با صفر و یک متناظر می کنم. (به همان روش معروف) اینک نباید هیچ دو تا یکی مجاور باشند. چون n تا 1 و n تا 0 داریم فقط دو حالت ممکن است : با 0 شروع شود یا با 1 شروع شود.

1.جوابتون 2 هست؟ کتاب گفته این نیست!
2. گفتین:چون n تا 1 و n تا 0 داریم فقط دو حالت ممکن است : با 0 شروع شود یا با 1 شروع شود.
چرا فقط این دو حالته؟

حق با شماست
ببخشید ، اشتباه شد!
n تا یک داریم. ابتدا آنها را به یک طریق در یک سطر می چینیم. سپس باید بین هر دو تا یک ، صفر قرار دهیم. (پس n-1 صفر مصرف شد) حالا صفر n ام را می توانیم آخر دنباله بگذاریم یا اول آن بگذاریم یا هر جایی بین 1 ها یعنی n+1 حالت داریم.

واقعا برای این اشتباه معذرت می خواهم.

خواهش میکنم.ممنون که توضیح دادین.

 

[rezoos]

میشه سوال 3 رو این جوریم حل کنیم؟(منظور:این راه حل هم درسته؟

)
n+1 عدد را به ترتیب صعودی مرتب می کنیم:

از برهان خلف استفاده می کنیم به ازای هر i,j , j>i ,

باشد. کوچکترین تفاوت ها را در نظر می گیریم. فرض می کنیم

کوچکترین تفاضل باشد.
جملات زیر را با هم جمع می زنیم:

.
.
.

حاصل میشود:

که این با فرض اولیه تناقض دارد.بنابراین i,j ای وجود دارد که j>i ,

باشد.
از جمله راه حل های من در آوردی خودمه. نخندین، فقط بگین درسته یا نه

حاصل

نمی شود ، از آن نامساوی ها نتیجه می شود که

و این تناقض است.

ضمنا از کوچکترین تفاضل چه استفاده ای کردید؟ یعنی اصلا لازم بود؟

بله،ببخشید.باز طبق معمول اشتباه کردم.
ویرایش کردم.

کوچکترین تفاضل منظورم این بود که چون به ترتیب صعودی مرتب کردیم عددی که با a[SUB]i [/SUB]کوچکترین تفاضل را دارد یا a[SUB]1+i [/SUB]هست یا a[SUB]i-1[/SUB][SUB]
[/SUB]
فرض کردم a[SUB]i+1 [/SUB]هست اگه هم a[SUB]i+1 [/SUB]باشه بازم همون جور میشه![SUB]
[/SUB]

 

[Goharshady]

حالا درست شد
راه زيبايي است ، آفرين بر شما
راستي شما مدرسه نمي رويد؟ آخه بعضي وقتها ساعت 10 يا 11 صبح آنلاين هستيد!