اولین باره که به کاهو میای؟ راهنمای سایت رو حتما بخون!

ورود ثبت‌نام راهنما درباره‌ی کاهو
پرسش‌ها برچسب‌ها کاربر‌ها سوال بپرسید!

آمار پرسش:

  • پرسیده شده: 2015-08-18 10:48:40 -0500
  • مشاهده شده: 191 بار
  • بروز شده: 2015-10-04 12:17:34 -0500

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

جام حذفی(نیازمند کمک در یافتن جواب)

0

یه سوال از جام های حذفی رو گذاشتم. خودم نتونستم حلش کنم . فک کنم با استقرا بشه حلش کرد. image description

2015-08-18 10:48:40 -0500
حمیدرضا کامکاری 204 ● 6 ● 10 ● 18
پاک‌کردن   ویرایش سوال
نظرات

تمرین 14 فصل 4 الفبا

2015-09-09 21:02:20 -0500 محمدرضا

سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه

2016-10-26 09:55:56 -0500 امیر شکری

2 پاسخ

2

این غلطه جواب درستو میزارم

n+1:نفر اولو در نظر بگیرید نفر اول باید توسط نفر دوم از دور رقابت ها حذف بشه وهمینطور نفر دوم باید توسط نفر سوم و... و اگه کسی از n+1 نفر اول مثل iتوسط فردی از شماره کوچیک تر خودش حذف بشود دیگه کسی با شماره بزرگتر از i نمیتواند برنده این دور رقابت ها باشه زیرا در هر مسابقه ای ک یه شرکت کنندش کوچیکتر ازi و یه شرکت کنندش بزرگتر از i باشه واضحه کی میبره!!!پس برنده ی تنیس بازان کوچتر از i برنده ی بازی میشود

حالا ثابت میشه تو مرحله i ام تنیس بازا با شماره i تا 2 بتوان n-i+1 بعلاوه(!)i -1 باقی می مونن اگه هر مرحله نفر اول این مرحله با نفر دومشون مسابقه بده و نفر دوم ببره برا بقیه هم نصفه اول با نصفه دوم مسابقه بدن و مسلما نصفه اول ببرن افراد با شماره هایi+1 تا 2 بتوان n-i بعلاوه i باقی میمونن

پس در آخر نفر n+1 ام باقی میمونه

حالا ب احتمال زیاد درستش :2n

ابتدا ثابت میکنم حداکثر 2n+1 میشود

اگر اولین عضو بعد از مرحله j ام i باشد باشد در مرحله b حداکثر نفر ${(b-j) \times 2 + i}$ام نفر اوله مسابقه است(اثباتش با استقراست اینطوریه ک نفرiام حداکثر توسط i+2ام از بین میره پس نفر i+2 ام باید یه مرحله حداقل بیش تر از نفر iام باقی بمونه و...)

بعد از مرحله 0حداکثر نفر اول نفر اول مسابقست!پس حداکثر بعد از n مرحله2n+1 امین نفر نفر اوله

اینطوری نیست چون فرض کردیم در هر مرحله 2 نفر ابتدایی مجموعه از بین برن ولی در مرحله آخر فقط یک نفر از بین میره پس باید از 2n+1 امین نفر کمتر باشه

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

اگه ناقص بود شرمنده:)

2015-08-18 11:35:58 -0500
هادیزاده 264 ● 4
پاک‌کردن   ویرایش پاسخ
نظرات

مثال نقضش n=2 هست که نفر چهارم میتونه ببره

2015-08-18 12:40:24 -0500 حمیدرضا کامکاری

چجوری دقیقا؟!!دو بازی میکنه حداکثر تو یکیش بتونه ببره اونم وقتیه ک با سه بیافته پس نمیتونه برنده باشه

2015-08-18 12:43:22 -0500 هادیزاده

4 با 2 بازی میکنه 4 میاد بالا. 3 با 1 بازی میکنه 3 میاد بالا. 4 با 3 بازی میکنه 4 میاد بالا

2015-08-18 12:47:03 -0500 حمیدرضا کامکاری

آها درسته من با یک تفاوت حساب کردم عذر میخام

2015-08-18 12:49:29 -0500 هادیزاده

جواب 2n میشه:'(

2015-08-18 12:53:36 -0500 هادیزاده
0

$2n$

اول با استقرا ثابت میکنیم کمترین شماره ای که در مرحله $k$ ام قرار دارد حداکثر $2k-1$ است .

به ازای $ k = 1 $ که بدیهیه ! حالا فرض میکنیم کمترین شماره که در مرحله $k$ ام قرار دارد شماره $2k-1$ است . این فرد در این مرحله یا برنده می شود یا به فرد شماره $2k$ میبازد یا به فرد شماره $2k+1$ میبازد . بنابراین کمترین شماره ای که در مرحله $k+1$ حضور دارد حداکثر $2k+1 $ است .

حالا ثابت میکنیم شماره برنده مسابقه نمیتواند بیشتر از $2n$ باشد .

فرض کنید قهرمان مسابقه فرد شماره $2n+1$ است . برای این که این فرد قهرمان شود باید در مرحله $k$ ام $ ( 1<=k<=n ) $ فرد شماره $2k+1$ از فرد شماره $2k-1$ برده باشد . و همچنین فرد شماره $2k+2$ از فرد شماره $2k$ برده باشد. که حتی در اینصورت هم نفرات $2n$ و $2n-1$ به فینال میرسند و فرد $2n+1$ به فینال نمی رسد !

مثال این هم که فرد $2n$ قهرمان شه خیلی سادس .

مثلا شماره های فرد یه طرف باشن و در مرحله $k$ ام فرد $2k+1$از رقیبش ببره و شماره های زوج هم یه طرف و در مرحله $k$ ام فرد شماره $2k+2$ از رقیبش ببره و به این ترتیب $2n$ قهرمان میشه !

2015-10-04 12:17:34 -0500
محمد امین 51 ● 2 ● 3 ● 7
پاک‌کردن   ویرایش پاسخ

پاسخ شما

فقط در صورتی که پاسخی برای این پرسش دارید، آن را اینجا بنویسید و برای بحث کردن از قسمت «ثبت‌ نظر» استفاده کنید. شما می‌توانید قبل از وارد شدن به سایت پاسخ خود را بنویسید. این پاسخ ذخیره می‌شود و زمانی که شما وارد سایت شدید یا ثبت‌نام کردید منتشر می‌شود.

پیش‌نمایش:

کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر است.