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

[عمو ژپتو]

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

خوب الگوریتم من اینه
هر دفعه اون کسیو انتخاب کن که بیشترین سود رو کرده باشه بعد
بیا اونایی که ضرر کردن رو هم به ترتیب سعودیی بذار بعد از این به ترتیب از کمتری به بیشترینشو پول بده تا 0 شن با این حرکت حداکثر میشه 2n-1
حالا برای هر nهم به نظرم یه مثال نقض راحت داشته باشه مثلا اونایی که شود کردن همه به یک اندازه
بعد اونایی که ضرر کردن همشون بجز 1 ی یه اپسیلون باشن بعد برای این مثال حداقل 2n-1بار معامله لازمه

 

[rezaezio]

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

اولا سعودی غلطه ! صعودی درسته فک کنم
دوما صرفا جهت راهنمایی می گم جوابت درسته ولی بخش کمی از نمره رو می گیری
سوما یه راهنمایی دیگه هم می کنم !
سعی کنید به یه گراف دو بخشی تبدیلش کنید.

ویرایش : بچه ها می گن گراف لازم نیس ؛ منم اضافه می کنم که فقط برای فهم بهتر سوال و جواب ؛ مسئله رو تبدیل می کنیم به گراف .

 

[عمو ژپتو]

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

حالا همه به املا من گیر بدین همش
خوب آقا الان اثبات کمینه بودنش رو یکی میشه بگه ؟؟
کلا گریدی سخته اثبات کردنش (حداقل من سختمه)

 

[rezaezio]

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

سود کرده ها : x1 , x2 , x3 , x4 , ... , x n
ضرر کرده ها : y1 , y2 , y 3 , ... , y n
اثبات کمینه بودن 2n-1 :
نفرات سود کرده رو در یک بخش و نفرات ضرر کرده رو در بخش دیگه قرار می دهیم.
برای همبند بودن این گراف 2n راسی حداقل 2n-1 یال لازم است.
پس اگر جواب از 2n-1 کمتر باشد گراف همبند نیست.
اگر گراف همبند نباشد داریم : x1 + x2 + x3 + ... + x i = y1 + y2 + y3 + ... + y j
حال اعدادی را مثال میزنیم که نتوان با آن ها چنین عبارتی را ساخت :
1 , 1 , 1 , . . . , 1 , n*n)-n+1)
n , n ,n , . . . , n
اگه متوجه مثالم نشدید بگید ؛ دوباره بگم

 

[rezaezio]

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

یک سوال آسون

n*n - n عدد طبیعی داریم.ثابت کنید مجموع n تا از این اعداد بر n بخش پذیر است.

دوره 17 - دارای 15 امتیاز

 

[Milad96]

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

اگر درست حل کرده باشم، n*n -n رو بگیر n(n-1 بعدش بیا باقیمانده های n رو از 0 تا n - 1 بگیر n تا لانه.

یعدش لانه کبوتری بزن که میشه یه خانه ای هست که توش حداقل n - 1 عدد باشه.(من با دو تا حالت از اینجا به بعد حلش کردم! نمیدونم آیا با یک حالت بشه اصن) بعدش حالا دو تا حالت میشه که 1) تویه هر لانه دقیقا n - 1 عدد باشه 2) یه لانه ای وجود داشته باشه که توش حداقل n تا عدد باشه و بعدش ...

+ خبر ندارم که سیستم انجمن چه طوری یه. یعنی سوال رو باید تا ته ته گفت راهش رو یا تا یه کم از حل اش رو گفت.

 

[rezaezio]

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

درسته ! بالاخره یه نفر تو این انجمن یه سوال حل کرد #

 

[kia.celever]

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

الان چه لزومی داره که گراف همبند باشه؟

 

[عمو ژپتو]

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

ینی واثعا به چنین راه حلی نمره میدن ؟؟

 

[عمو ژپتو]

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

اگر درست حل کرده باشم، n*n -n رو بگیر n(n-1 بعدش بیا باقیمانده های n رو از 0 تا n - 1 بگیر n تا لانه.

یعدش لانه کبوتری بزن که میشه یه خانه ای هست که توش حداقل n - 1 عدد باشه.(من با دو تا حالت از اینجا به بعد حلش کردم! نمیدونم آیا با یک حالت بشه اصن) بعدش حالا دو تا حالت میشه که 1) تویه هر لانه دقیقا n - 1 عدد باشه 2) یه لانه ای وجود داشته باشه که توش حداقل n تا عدد باشه و بعدش ...

+ خبر ندارم که سیستم انجمن چه طوری یه. یعنی سوال رو باید تا ته ته گفت راهش رو یا تا یه کم از حل اش رو گفت.

گاش تا تهش رو میگفتید حالا

 

[rezaezio]

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

2 حالت داره :
1- از همه باقی مانده ها n-1 تا داریم که می تونیم یه مثال پیشنهادی بدیم مثلا : n-2 تا 0 و یدونه 1 و یدونه n-1
2-از یه باقی مانده n تا داریم : n تا رو از اون باقی مونده می دیم

 

[rezaezio]

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

الان چه لزومی داره که گراف همبند باشه؟

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

ینی واثعا به چنین راه حلی نمره میدن ؟؟

آره ؛
راه حل کامله و جوب نداره ؛ حالا شاید من بد نوشتم

 

[عمو ژپتو]

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

آره ؛
راه حل کامله و جوب نداره ؛ حالا شاید من بد نوشتم

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

 

[rezaezio]

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

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

 

[عمو ژپتو]

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

خوب اینو آره قبول دارم ولی فکر کنم سره مرحله 2 همینم باید ثابت کنی
خوب من ادامش رو نفهمیدم

 

[rezaezio]

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

خوب اینو آره قبول دارم ولی فکر کنم سره مرحله 2 همینم باید ثابت کنی
خوب من ادامش رو نفهمیدم

عزیز دلم ؛ قضیه توی هیچ امتحانی اثبات لازم نداره (صرفا جهت اطلاع)
ادامش هم میگه پس اگه از 2n-1 کمتر باشه پس گراف ناهمبنده
ولی با اون اعداد که مثال زدم گراف نا همبند رو نمی تونی به دست بیاری

 

[kia.celever]

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

عزیز دلم ؛ قضیه توی هیچ امتحانی اثبات لازم نداره (صرفا جهت اطلاع)

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

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

 

[rezaezio]

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

قضیه : گراف n راسی برای همبند بودن n-1 یال لازم داره .

در مورد اثبات قضیه در مرحله 2 هم یه نکته بگم
اگه لازم باشه قضیه ها رو تو المپیاد ثابت کنیم یعنی المپیاد ریاضی ها باید تو هندسه فقط اثبات قضیه حفظ کنن (از فیثاغورس گرفته تا منلاووس)
+
لانه کبوتری هم قضیه می باشد , ولی لازم نیست توی المپیاد اثباتش کنید .

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

به دلایل بسیار حرفتون بسیار غیرمنطقی می باشد .

 

[kia.celever]

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

به دلایل بسیار حرفتون بسیار غیرمنطقی می باشد .

این حرف رو از خودم در نیاوردم!
درسته. لازم نیست لانه کبوتریو اثبات کنید تو مرحله 2! ولی لانه کبوتری اونقدر بدیهی هست که بهش می گن "اصل" لانه کبوتری!
اما در مورد بقیه قضیه ها خود آدم باید تشخیص بده که نوشتن اثباتشون لازمه یا نه ...
حالا شما ول کن این حرفارو! ادامه اثباتو بگو!

 

[عمو ژپتو]

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

این حرف رو از خودم در نیاوردم!
درسته. لازم نیست لانه کبوتریو اثبات کنید تو مرحله 2! ولی لانه کبوتری اونقدر بدیهی هست که بهش می گن "اصل" لانه کبوتری!
اما در مورد بقیه قضیه ها خود آدم باید تشخیص بده که نوشتن اثباتشون لازمه یا نه ...
حالا شما ول کن این حرفارو! ادامه اثباتو بگو!

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