سوال ترکیبیات برای رفع خواب آلودگی

[rezoos]

1.در هر یک از خانه های جدول n×n عددی صحیح و نا منفی نوشته شده است. در ضمن اگر عدد واقع در یک خانه از جدول برابر صفر باشد

آنگاه مجموع اعداد خانه هایی از جدول که با این خانه هم سطر یا هم ستون هستند حداقل برابر باn است.ثابت کنید مجموع اعداد جدول حداقل برابر

است (المپیاد بین المللی ریاضی،1971).


2. فرض کنید

دنباله ای از n عدد حقیقی باشد. زیر هر یک از جمله های این دنباله عددی را که معرف تعداد تکرار های این جمله در دنباله است می نویسیم. به همین ترتیب زیر دنباله ی دوم،دنباله ی سوم را می نویسیم و همین کار را تکرار می کنیم . ثابت کنید از جایی به بعد همه ی دنباله ها یکسان اند.


3.جدولی چهار سطر دارد. در سطر اول عدد های طبیعی دلخواه نوشته شده اند. سطر دوم به این صورت پر شده است : زیر عدد a ، عددی که برابر تعداد اعداد a در سطر اول است که در سمت راست این عدد قرار دارند ( خود این a را نیز حساب می کنیم). به همین روش سطر سوم زیر سطر دوم و سطر چهارم زیر سطر سوم نوشته شده است. ثابت کنید سطر دوم و چهارم این جدول با هم برابرند.

 

[Goharshady]

1.در هر یک از خانه های جدول n×n عددی صحیح و نا منفی نوشته شده است. در ضمن اگر عدد واقع در یک خانه از جدول برابر صفر باشد

آنگاه مجموع اعداد خانه هایی از جدول که با این خانه هم سطر یا هم ستون هستند حداقل برابر با

است (المپیاد بین المللی ریاضی،1971).

ببخشید ، سوال چیه؟

 

[rezoos]

ببخشید ،ویرایش کردم

 

[Goharshady]

پاسخ سوال 1:
فرض کنید هیچ صفری نداشته باشیم ، در این صورت جمع کل اعداد حداقل برابر n[SUP]2[/SUP] است و جمع هر سطر حداقل n است. در نتیجه حاصل جمع هر سطر و هر ستون دلخواه حداقل برابر 2n-x می باشد که x عدد مکان تلاقی آنهاست. حال فرض کنید در k مکان از جدول صفر گذاشته باشیم ، در این صورت حکم بالا برای سایر سطر ها و ستونها برقرار است. حالتی که مجموع کل کمترین مقدار ممکن را دارد در نظر می گیریم.( بر حسب مکان صفرها) در این حالت باید هیچ دو صفری هم سطر و هم ستون نباشند (در غیر این صورت می توانیم حالتی مثال بزنیم که مجموع کل کمتر باشد) در این صورت برای k های کمتر از n به راحتی می توان برقراری حکم را دید (زیرا مجموع هر سطر و ستون حداقل n است و n½ تا از این سطر و ستونها داریم)
برای k های بزرگتر از n نیز کافی است تعداد n-k تا از صفرها را در نظر نگیریم!
ببخشید اگر خوب توضیح ندادم.

 

[shoki]

میشه با گراف هم ثابت کرد ... البته عملا دو اثبات فرقی با هم نخواهند کرد ....

 

[seifi_seifi]

سوال یک و دو و سه همگی در صفحه ی 10 و 11 کتاب علیپور قرار دارد و میتوانید جوابهایشان را از آنجا مطالعه کنید.

 

[Goharshady]

سوال یک و دو و سه همگی در صفحه ی 10 و 11 کتاب علیپور قرار دارد و میتوانید جوابهایشان را از آنجا مطالعه کنید.

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

 

[seifi_seifi]

من هم اصلا قصد توهین نداشتم ولی اگه کسی هم ناراحت شده همین جا معذرت میخوام.

 

[Goharshady]

من صرفا به شما نگفتم ، منظورم این بود که دیگران هم رعایت کنند. (از جمله 7 نفر که خودم می شناسمشون و اونا هم می دونن که تو این لیست هستن!!)

 

[shoki]

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

...
1- اتفاقا به نظر من این طوری سوال خیلی به ارزشش اضافه می شه چون نشون دادیم که یک نویسنده ی خوبی یک چنین مسئله ای رو آورده ... و بنابراین سوال با ارزش و خوبی هست که توی کتاب خوبی اومده و اون فردی که شما میگید یک چنین چیزی رو می بینه و دیگه روی سوال فکر می کنه شاید هم بره سراغ اون کتاب و اون رو بیش تر و بهتر مطالعه کنه ...
2- بله هیچ کس چنین قصدی رو نداره و نداشته ...
پس یه سری مزیت هایی هم داره نه ؟؟

در عین حال با این موضوع موافقم که نباید بگیم توی فلان کتابه بلکه اگر توی همین سایت یا جایی دیگر ارسال شده اون جا رو نام ببریم ...

من هم شرمنده ام ...

...از جمله 7 نفر که خودم می شناسمشون و اونا هم می دونن که تو این لیست هستن!!

شرمنده که ارسالم به تاپیک ربطی نداره ولی خوب ،مجبور شدم جواب بدم ...

 

[Goharshady]

بله!
یک مزیت داشت ، اون هم این بود که من بالاخره کتاب ترکیبیات علیپور رو خریدم تا بخونم! (هرچند همه ی تمریناتش تکراری به نظر می رسه!

)

 

[Goharshady]

2. فرض کنید

دنباله ای از n عدد حقیقی باشد. زیر هر یک از جمله های این دنباله عددی را که معرف تعداد تکرار های این جمله در دنباله است می نویسیم. به همین ترتیب زیر دنباله ی دوم،دنباله ی سوم را می نویسیم و همین کار را تکرار می کنیم . ثابت کنید از جایی به بعد همه ی دنباله ها یکسان اند.


3.جدولی چهار سطر دارد. در سطر اول عدد های طبیعی دلخواه نوشته شده اند. سطر دوم به این صورت پر شده است : زیر عدد a ، عددی که برابر تعداد اعداد a در سطر اول است که در سمت راست این عدد قرار دارند ( خود این a را نیز حساب می کنیم). به همین روش سطر سوم زیر سطر دوم و سطر چهارم زیر سطر سوم نوشته شده است. ثابت کنید سطر دوم و چهارم این جدول با هم برابرند.

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

 

[rezoos]

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

 

[Goharshady]

پاسخ سوال 3: (من جوابی غیر از اونی که تو علیپور نوشته یاد ندارم ولی همونو بیشتر توضیح میدم.)
این چهار سطر را در نظر بگیرید. فرض کنید به این صورت باشند:
[center:9b46d9e632]

[/center:9b46d9e632]

برای اثبات حکم کافی است ثابت کنیم برای هر i دلخواه داریم :

فرض کنید β[SUB]i[/SUB] = k در این صورت k تا از اعداد دنباله ی

برابر

هستند. زیر این اعداد به ترتیب از k تا 1 نوشته شده است. حال فرض کنید

در این صورت m تا از اعداد دنباله ی

برابر با β[SUB]i[/SUB] = k هستند. پس هر یک از اعداد از k تا 1 حداقل با m تا از

برابرند و هریک از آنها حداکثر m-1 بار در بقیه جاها ظاهر شده اند. پس در دنباله ی

دقیقا k جمله با

برابر هستند. پس

ببخشید اگه خوب ننوشتم.

 

[rezoos]

پاسخ سوال 1:
1. در این صورت حکم بالا برای سایر سطر ها و ستونها برقرار است.
2.(در غیر این صورت می توانیم حالتی مثال بزنیم که مجموع کل کمتر باشد)
3. n½ تا از این سطر و ستونها داریم)

4.برای k های بزرگتر از n نیز کافی است تعداد n-k تا از صفرها را در نظر نگیریم
ببخشید اگر خوب توضیح ندادم.

1.منظورتون از سایر سطر ها و ستون ها تمام سطر ها و ستون هاییه که صفر نداشته باشن؟
2.منظورتون از مجموع کل مجموع کل اعداد در اون سطره؟
3.چرا؟(از کجا فهمیدین؟)
4.خب اگه اونارو صفر در نظر نگیریم حتما به جاش عدد بزرگتری رو در نظر گرفتیم،اون وقت حداقل نمیشه.


بهتون بر نخوره ها! راه حل شما غلط نیس! من خنگم!

 

[rezoos]

راجع به سوال 3:
وقتی میگه تعداد تکرار های این جمله در دنباله منظورش اینه که تعدادش در کل دنباله یا در زیر دنباله ی

?

 

[Goharshady]

ببخشید
ولی این زیردنباله ای که شما نوشته اید همان دنباله ی کامل است ، من منظورتون رو نمی فهمم!

 

[Goharshady]

پاسخ سوال 1:
1. در این صورت حکم بالا برای سایر سطر ها و ستونها برقرار است.
2.(در غیر این صورت می توانیم حالتی مثال بزنیم که مجموع کل کمتر باشد)
3. n½ تا از این سطر و ستونها داریم)

4.برای k های بزرگتر از n نیز کافی است تعداد n-k تا از صفرها را در نظر نگیریم
ببخشید اگر خوب توضیح ندادم.

1.منظورتون از سایر سطر ها و ستون ها تمام سطر ها و ستون هاییه که صفر نداشته باشن؟
2.منظورتون از مجموع کل مجموع کل اعداد در اون سطره؟
3.چرا؟(از کجا فهمیدین؟)
4.خب اگه اونارو صفر در نظر نگیریم حتما به جاش عدد بزرگتری رو در نظر گرفتیم،اون وقت حداقل نمیشه.


بهتون بر نخوره ها! راه حل شما غلط نیس! من خنگم!

1-منظورم از سایر سطرها و ستونها دقیقا همانی است که شما برداشت کرده اید
2-منظور از مجموع کل ، مجموع همه ی اعداد جدوله
3-فکر می کنم خوب ننوشتم و برداشت دیگه ای شده ، منظورم این بود که حداقل این مقدار از سطر و ستونها داریم که بدیهی هم هست
4-فرض کنید به جای صفرهایی که در نظر نگرفته ایم ، جای خالی گذاشته باشیم و جای خالی ها را در جمع به حساب نیاوریم. در این صورت هم حکم برقرار است ، در نتیجه با در نظر نگرفتن این صفرها هیچ مشکلی پیش نمی آید!

 

[rezoos]

پاسخ سوال 1:
1. در این صورت حکم بالا برای سایر سطر ها و ستونها برقرار است.
2.(در غیر این صورت می توانیم حالتی مثال بزنیم که مجموع کل کمتر باشد)
3. n½ تا از این سطر و ستونها داریم)

4.برای k های بزرگتر از n نیز کافی است تعداد n-k تا از صفرها را در نظر نگیریم
ببخشید اگر خوب توضیح ندادم.

1.منظورتون از سایر سطر ها و ستون ها تمام سطر ها و ستون هاییه که صفر نداشته باشن؟
2.منظورتون از مجموع کل مجموع کل اعداد در اون سطره؟
3.چرا؟(از کجا فهمیدین؟)
4.خب اگه اونارو صفر در نظر نگیریم حتما به جاش عدد بزرگتری رو در نظر گرفتیم،اون وقت حداقل نمیشه.


بهتون بر نخوره ها! راه حل شما غلط نیس! من خنگم!

1-منظورم از سایر سطرها و ستونها دقیقا همانی است که شما برداشت کرده اید
2-منظور از مجموع کل ، مجموع همه ی اعداد جدوله
3-فکر می کنم خوب ننوشتم و برداشت دیگه ای شده ، منظورم این بود که حداقل این مقدار از سطر و ستونها داریم که بدیهی هم هست

4-فرض کنید به جای صفرهایی که در نظر نگرفته ایم ، جای خالی گذاشته باشیم و جای خالی ها را در جمع به حساب نیاوریم. در این صورت هم حکم برقرار است ، در نتیجه با در نظر نگرفتن این صفرها هیچ مشکلی پیش نمی آید!

1.ممنون،فهمیدم
2.ممنون،فهمیدم
3.مقدار سطر و ستون ها یک مقدار ثابت است، چطور میتونین واسه ش حداکثر یا حداقل قائل بشین؟
4.نمیتونیم که جای خالی بذاریم!حتما باید با اعداد پر کنیم!وکوچکتر از صفر هم نمیتونیم بذاریم(طبق روی سوال!)مجبوریم اعداد بزرگتر از صفر بذاریم که در اون صورت حداقل مقدار بزرگتری در میاد!

 

[Goharshady]

ببین ، اون اثبات رو کلا فراموش کن!
این اثبات ساده تر رو ببین:
اگر در جدول صفر نداشته باشیم ، جمع اعداد جدول n[SUP]2[/SUP] است. حالا اگر در محل تقاطع یک سطر و ستون خاص 0 قرار گرفته باشد ، مجموع آن سطر و ستون (وقتی حداکثر کاهش را داشته باشد) نصف می شود. پس در حالتی کمترین مجموع را داریم که مجموع همه ی سطر و ستونها نصف شده باشد. در این حالت مجموع کل اعداد حداقل n[SUP]2[/SUP]½ است.