یه سوال کامپیوتری !!!

[Olympiad]

یه نفر یه دنباله از از اعداد 1 تا n انتخاب میکنه (که ما از اون بی خبریم !!!!!!!!) ... هدف اینه که ما یه دنباله بدیم که حداقل 1 دونه اشتراک با اون دنباله داشته باشه . در هر مرحله هم میتونیم یه جایگشت از 1 تا n بدیم و اونم بگه اشتراک داره یا نه !!!! حداقل تعداد پرسش ها چند تاست ؟؟!! (با اثبات کامل بگین !!!!!)

 

[goodarz]

پاسخ : یه سوال قشنگ کامپیوتری !!!

اگه n زوج باشه, یعنی n=2k, کافیه k+1 جایگشتی رو به طرف مقابل بدیم که درایه های 1تا k+1شون یه جایگشت دوری از 1 تا k+1 باشن. اثبات این که کمتر از این هم نمیشه با قضیه هاله.....برای n فرد هم فکر کنم استدلالی مشابه این جواب بده.

 

[emad.shahbazy]

پاسخ : یه سوال قشنگ کامپیوتری !!!

جواب این سوال برابر تعداد پریش ها ی n است به علاوه یک پریشم یعنی دنباله ای که هیچ عددیش سر جای خودش نباشه

 

[goodarz]

پاسخ : یه سوال کامپیوتری !!!

یعنی شما میگین اگه مثلا n پنجاه باشه حداقل تعداد پرسش ها برابر تعداد پریش ها+1 میشه؟؟؟؟ تو این حالت با 26 تا سوال هم میشه ها.....

 

[math]

پاسخ : یه سوال کامپیوتری !!!

به نظر من هر حالت را دوبار دارید میشمارید تعدادشان

 

[goodarz]

پاسخ : یه سوال کامپیوتری !!!

به نظر من هر پریش را دوبار دارید میشمارید تعدادشان

جواب واسه n های زوج همین چیزیه که میگین, ولی من نمی فهمم این کجاش به پریش ربط داره؟!؟! تعداد پریش های n تایی تقریبا

هست که این تعداد رشدش خیلی بزرگ تر از این حرفاست!!!!

 

[math]

پاسخ : یه سوال کامپیوتری !!!

جواب واسه n های زوج همین چیزیه که میگین, ولی من نمی فهمم این کجاش به پریش ربط داره؟!؟! تعداد پریش های n تایی تقریبا

هست که این تعداد رشدش خیلی بزرگ تر از این حرفاست!!!!

ببخشین درستش کردم. ولی برای n های فرد نمیدونم.