آرشیو سوالات از گذشته تا کنون

[rezaezio]

پاسخ : آرشیو سوالات از گذشته تا کنون

ولی بقول دوستمون ادامش رو بگو

ادامه :
با اعداد زیر نمی تونید گراف همبندی با شرایط سوال پیدا کنید .
1 , 1 ,1 , . . . , 1 , n^2-n+1
n , n ,n , n , ... , n
گروه اول رو بزار به جای سود ها و گروه دوم رو بزار به جای ضرر ها
گفتم که اگه از 2n-1 کمتر باشه گراف نا همبنده ولی شما با اعداد بالا نمی تونی گراف ناهمبندی پیدا کنی که مجموع سود ها و ضرر هاش برابر باشه !

ولی من حرفتو قبول ندارم دو تتا از استاد هایی که ما باهاشون کلاس داشتیم
وقتی اومدن گفتند باید همه چی رو بنویسی حتی همین 2n-1رو

شما می تونی پاسخنامه شاززز تو سال های گذشته رو ببینی که لازم نیست قضیه رو اثبات کنی !
اینم یه دلیل دیگه :
از ویکی‌پدیا، دانشنامهٔ آزاد
قَضیه، (به انگلیسی: Theorem) در منطق، گزاره‌ای است که از اصول موضوعه یا از گزاره‌هایی که از پیش اثبات شده‌اند

من تو مرحله 2 قضیه ها رو ثابت نمی کنم ولی شما اگه دوست داری می تونی ثابت کنی

 

[rezaezio]

پاسخ : آرشیو سوالات از گذشته تا کنون

اینم یه دلیل دیگه :

پست آخر همین تاپیک رو بخونید ، مدال دار المپیاد ریاضی گفته

http://www.sampadia.com/forum/index.php/topic,88965.140.html

حامد مهدوی :

هر قضیه ای که تو کتاب های معروف المپیاده میشه استفاده کرد مگه اینکه اثباتش پیچیده باشه و استفاده از اون سوالو بدیهی کنه !

 

[عمو ژپتو]

پاسخ : آرشیو سوالات از گذشته تا کنون

1 , 1 ,1 , . . . , 1 , n^2-n+1
n , n ,n , n , ... , n

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

 

[rezaezio]

پاسخ : آرشیو سوالات از گذشته تا کنون

کم کم دارم شباهت هایی بین جواب تو و جواب سوال می بینم
نوشتن سخته ؛ پشت PC سخت تر هم میشه ؛ فعلن چند تا سوال می زارم !

 

[rezaezio]

پاسخ : آرشیو سوالات از گذشته تا کنون

این سوال هم جالبه

:)

 

[zahra.kh]

پاسخ : آرشیو سوالات از گذشته تا کنون

الان دقيقا هم لازم بودنش اثبات شد هم كافي بودنش؟؟؟؟

 

[zahra.kh]

پاسخ : آرشیو سوالات از گذشته تا کنون

روش:
در هر مرحله دو تا از وزنه ها رو انتخاب ميكنيم.وزنه ي سنگين تر را در دسته aو وزنه هاي سبكتر رو تو b ميزاريم.(تا اينجا سقف n/2)
در مرحله بعدي از هر گروه دو تا رو انتخاب ميكنيم واسه گروه aسنگين تر رو نگه ميداريم اونيكي رو دور ميندازيم و واسه bبر عكس اين كار رو انجام ميديم(1-n/2-1+n/2)
جمع اين سه مرحله ميشه2- 3*n/2

اثبات:روي nاستقرا قوي ميزنيم
پايه ك برقراره.براي nاثبات ميكنيم
اين k+1رو به دودسته n/2تقسيم ميكنيم
دسته اول n/4 *3 -2 مرحله براي پيدا كردن مين و ماكس لازمه همين طور براي دسته دوم
2 مرحله هم دوتا مين ها و 2تا ماكس ها رو باهم مقايسه ميكنيم پس ميشه2- 3* n/2*3-4+2 == n/2 و اثبات كامل ميشه

 

[kia.celever]

پاسخ : آرشیو سوالات از گذشته تا کنون

الان یه مثال برا 2n-1 زدیم. ولی اینو باید بگیم که حالتی وجود نداره که حداقلش از 2n-1 بیشتر بشه!

 

[zahra.kh]

پاسخ : آرشیو سوالات از گذشته تا کنون

بنظر من اين اثبات كامل نيست
الان گفتيد با 2-2nبار جابجايي نميشه(پس لازم بودنش اثبات شد)
حالا بايد اينم اپبات شه كه با اين تعداد حتما ميشه(كافي بودنش هنوز اثبات نشده)

 

[rezaezio]

پاسخ : آرشیو سوالات از گذشته تا کنون

الان یه مثال برا 2n-1 زدیم. ولی اینو باید بگیم که حالتی وجود نداره که حداقلش از 2n-1 بیشتر بشه!

وقتی 2n-1 رو تو حالت کلی اثبات کنی دیگه اینی که شما گفتی لازم نیس !
چرا می خواید الکی گیر بدید ؟

 

[rezaezio]

پاسخ : آرشیو سوالات از گذشته تا کنون

غلطه !
اولا که الگوریتمی که گفتی غلطه (اگه فهمیده باشم که منظورت چیه )
کی گفته که با سه مرحله ای که تو گفتی بزرگترین و کوچکترین میشن ؟ X-(
با این سه مرحله که تو گفتی مثلا اگه اولش 1000 تا وزنه باشن می رسیم به دو تا دسته 250 تایی
دوما !
مرتبه الگوریتمت میشه log n) * n)
ولی مرتبه پاسخ سوال n هست
واضحِ که الگوریتمت درست نیس

 

[zahra.kh]

پاسخ : آرشیو سوالات از گذشته تا کنون

خوب جواب من رو هم بديد ايها الناس

 

[rezaezio]

پاسخ : آرشیو سوالات از گذشته تا کنون

خوب جواب من رو هم بديد ايها الناس

حالت 2n-1 اش که بدیهیه ! 10 ثانیه فکر کن بعد پست بده

 

[zahra.kh]

پاسخ : آرشیو سوالات از گذشته تا کنون

وقتي نفهميديد منظورمو نگيد غلطه.
اگه 1000تا داشته باشيم اولش دوتا دسته 500تايي درس ميشه يكي مينيموم هان يكي هم ماكسيموم ها
حالا مثلا تو دسته ماكسيموم ها ميايم اول دوتا انتخاب ميكنيم اوني ك بزرگتررو نگه ميداريم كمتر رو ميندازيم بره بعد يكي ديگه از دسته ماكسيموم ها برميداريم و بين اونا ماكس رو انتخاب ميكني اونيكي رو ميندازه بره و همينطور تا اخر
دو تا دسته 250 تايي رو از كجا اورديد؟؟؟؟

 

[kia.celever]

پاسخ : آرشیو سوالات از گذشته تا کنون

وقتی 2n-1 رو تو حالت کلی اثبات کنی دیگه اینی که شما گفتی لازم نیس !
چرا می خواید الکی گیر بدید ؟

گیر الکی؟ ^-^
الان مگه شما نمیگی تو هر حالتی حداکثر با 2n-1 تا حرکت می شه حل کرد قضیه رو؟
خوب الان هر حالتی رو اثبات نکردی که!! یه حالت مثال زدی!
الان یکی می تونه ادعا کنه یه حالتی هست که حداقل با مثلاً 3n تا حل بشه! شما باید اثبات کنی که چنین حالتی وجود نداره!
به عبارت دیگه هر حالتی که باشه حداکثر با 2n-1 تا حرکت حل می شه! (اینو می خوایم اثبات کنیم!)

 

[zahra.kh]

پاسخ : آرشیو سوالات از گذشته تا کنون

دقيقا چطور ميگي بديهيه
شما حدس زدي با 2n-1مرحله هيچكس نه سود كنه نه ضرر.
اين كوجاش بديهيه؟؟؟

 

[rezaezio]

پاسخ : آرشیو سوالات از گذشته تا کنون

در جواب هر دو شما :
همه کسایی که سود کردن ؛ میان با n تبادل پول ؛ به اندازه مقدار سودشون پول میدن به یه نفر از ضرر کرده ها مثلا همه پول میدن به جواد !
حالا این آقا جواد قصه ما میاد با n-1 نفر ضرر کرده دیگه تصفیه می کنه ( با n-1 تبادل )
n + n - 1 = 2n-1
این الگوریتم برای 2n-1

 

[کاربر حذف شده 8031]

پاسخ : آرشیو سوالات از گذشته تا کنون

استقرا رو n میزنیم.ابتدا میبینیم که پایه استقرا به ازا 1 و 2 درسته!
بعد میگیم: به ازایn=k هم درسته. یعنی فرض میکنیم!
حالا حکم یعنی k+2 را باید اثبات کنیم!
میگیم k تا از این را k+2 انتخاب کرده طبق فرض استقرا میدونیم که این k تا به 3k/2-2 وزن کردن بزرگترین و کوچیکترین وزنه در میاد!حالا اون بزرگترین و کوچکترین رو b و a مینامیم. , و اون دوتایی رو هم که وزن نکردیم c و d می نامیم.
حال یکبار c و d وزن کرده و میفهمیم که کدوم کوچیکتر و کدوم بزرگتره!حال فرض میکنیم c از d بزرگتره.
ویکبار دیگه a و c و بار دیگر b و d وزن کرده و به ترتیب کوچیکترین و بزرگترین وزنه بدست میاد!
پس:3k/2-2 +3 = 3(k+2)/2-2 است!
حکم اثبات شد!
در اصل ما یکبار برای زوج ها و یکبار برای فرد ها گفتیم!
کثیف گفتم میدونم!

 

[rezaezio]

پاسخ : آرشیو سوالات از گذشته تا کنون

منظورتو نفهمیده بودم
خوب الان می دونی چند تا مرحله لازم داری ؟
فرض کن اولش 1001 باشن
با 501 مرحله میشن دو تا دسته
یکی 500 تایی و دیگری 501 ای !
499 تا دسته اولیه لازم داره
500 تا دسته دومیه
501 + 500 + 499 = 1500
توی عبارت سوال n رو بزار 1000 ؛ میشه 1498
رد شد

* رد نشد

 

[zahra.kh]

پاسخ : آرشیو سوالات از گذشته تا کنون

منظورتو نفهمیده بودم
خوب الان می دونی چند تا مرحله لازم داری ؟
فرض کن اولش 1001 باشن
با 501 مرحله میشن دو تا دسته
یکی 500 تایی و دیگری 501 ای !
499 تا دسته اولیه لازم داره
500 تا دسته دومیه
501 + 500 + 499 = 1500
توی عبارت سوال n رو بزار 1000 ؛ میشه 1498
رد شد

* رد نشد

اصلا دقت نميكنيد.اولش با 1001 حساب ميكني اخرش 1000 رو جاگذاري ميكني؟؟؟ X-( X-(
1001 رو جاگذاري كن ميشه 1500.
و جواب قطعا درسته